DOI: https://doi.org/10.20535/SRIT.2308-8893.2020.1.12

Метод трикутника для побудови полінома Жегалкіна: зв’язок з трикутником Паскаля

I. Ya. Spectorsky, O. A. Galganov

Анотація


Поліном Жегалкіна — зручний спосіб зображення булевої функції у вигляді суми за операцією ⨁ (xor, або сума за модулем 2) скінченної кількості кон’юнкцій змінних — запропонований у 1927 р. радянським ученим І.І. Жегалкіним. Одним з алгоритмів побудови полінома Жегалкіна для заданої булевої функції є метод трикутника, запропонований у 1985–1987 рр. радянським математиком В.П. Супруном. Застосування методу трикутника збігається з почерговою побудовою рядків трикутника Паскаля з використанням відомого співвідношення Cn+1k+1 = Cnk + Cnk+1. Природно очікувати на зв’язок обчислення полінома Жегалкіна методом трикутника з розташуванням біноміальних коефіцієнтів у трикутнику Паскаля. Проаналізовано зв’язок методу трикутника з побудовою рядків трикутника Паскаля; запропоновано відносно просте доведення коректності методу трикутника шляхом зіставлення кожного кроку алгоритма з покроковою побудовою рядків біноміальних коефіцієнтів у трикутнику Паскаля.

Ключові слова


поліном Жегалкіна; метод трикутника; трикутник Паскаля

Повний текст:

PDF

Посилання


Zhegalkin I.I. O tehnike vychislenij predlozhenij v simvolicheskoj logike / I.I. Zhegalkin // Matematicheskij sbornik. — 1927. — S. 9–28.

Marchenkov S.S. Zamknutye klassy bulevyh funktsij / S.S. Marchenkov. — M.: Fizmatlit, 2000. — 128 s.

Jablonskij S.V. Vvedenie v diskretnuju matematiku / S.V. Jablonskij. — M.: Nauka. — 1986. — 272 s.

Suprun V.P. Polinomial'noe razlozhenie simmetricheskih bulevyh funktsij / V.P. Suprun // Izv. AN SSSR. Tehnicheskaja kibernetika. — 1985. — № 4. — S. 123–127.

Suprun V.P. Tablichnyj metod polinomial'nogo razlozhenija bulevyh funktsij / V.P. Suprun // Kibernetika. — 1987. — № 1. — S. 116–117.

Suprun V.P. Osnovy teorii bulevyh funktsij / V.P. Suprun. — M.: Lenand, 2017. — 208 s.

Zavalo S.T. Kurs alhebry / S.T. Zavalo. — K.: Vyshcha shk., 1985. — 503 s.

Granville A. Arithmetic Properties of Binomial Coefficients I: Binomial coefficients modulo prime powers / A. Granville // Canadian Mathematical Society Conference Proceedings. — 1997. — N 20. — P. 253–275.


Пристатейна бібліографія ГОСТ


1. Жегалкин И.И. О технике вычислений предложений в символической логике / И.И. Жегалкин // Математический сборник. — 1927. — С. 9–28.

2. Марченков С.С. Замкнутые классы булевых функций / С.С. Марченков. — М.: Физматлит, 2000. — 128 с.

3. Яблонский С.В. Введение в дискретную математику / С.В. Яблонский. — М.: Наука. — 1986. — 272 с.

4. Супрун В.П. Полиномиальное разложение симметрических булевых функций / В.П. Супрун // Изв. АН СССР. Техническая кибернетика. — 1985. — № 4. — С. 123–127.

5. Супрун В.П. Табличный метод полиномиального разложения булевых функций / В.П. Супрун // Кибернетика. — 1987. — № 1. — С. 116–117.

6. Супрун В.П. Основы теории булевых функций / В.П. Супрун. — М.: Ленанд, 2017. — 208 с.

7. Завало С.Т. Курс алгебри / С.Т. Завало. — К.: Вища шк., 1985. — 503 с.

8. Granville A. Arithmetic Properties of Binomial Coefficients I: Binomial coefficients modulo prime powers / A. Granville // Canadian Mathematical Society Conference Proceedings. — 1997. — N 20. — P. 253–275.