Метод трикутника для побудови полінома Жегалкіна: зв’язок з трикутником Паскаля
Introduced by Soviet scientist I. Zhegalkin in 1927, Zhegalkin polynomial is a way to represent a Boolean function as an exclusive or of conjunctions of variables. One of the known algorithms for constructing Zhegalkin polynomial is so called ‘triangle method’ proposed in 1985–1987 by Soviet mathema...
Saved in:
| Date: | 2020 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2020
|
| Subjects: | |
| Online Access: | https://journal.iasa.kpi.ua/article/view/189119 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | System research and information technologies |
| Download file: |  |
Institution
System research and information technologies| _version_ | 1867334403211919361 |
|---|---|
| author | Spectorsky, I. Ya. Galganov, O. A. |
| author_facet | Spectorsky, I. Ya. Galganov, O. A. |
| author_institution_txt_mv | [
{
"author": "I. Ya. Spectorsky",
"institution": "Навчально-науковий комплекс \"Інститут прикладного системного аналізу\" Національного технічного університету України \"Київський політехнічний інститут імені Ігоря Сікорського\", Київ"
},
{
"author": "O. A. Galganov",
"institution": "Навчально-науковий комплекс \"Інститут прикладного системного аналізу\" Національного технічного університету України \"Київський політехнічний інститут імені Ігоря Сікорського\", Київ"
}
] |
| author_sort | Spectorsky, I. Ya. |
| baseUrl_str | http://journal.iasa.kpi.ua/oai |
| collection | OJS |
| datestamp_date | 2020-08-11T08:50:57Z |
| description | Introduced by Soviet scientist I. Zhegalkin in 1927, Zhegalkin polynomial is a way to represent a Boolean function as an exclusive or of conjunctions of variables. One of the known algorithms for constructing Zhegalkin polynomial is so called ‘triangle method’ proposed in 1985–1987 by Soviet mathematician V.P. Suprun. Applying of the triangle method mainly coincides with step-by-step constructing Pascal triangle rows using the equality Cn+1k+1 = Cnk + Cnk+1. Therefore, it would be natural to expect for the relation between the calculation of Zhegalkin polynomial by the triangle method and an arrangement of binomial coefficients in Pascal triangle. In this paper, the connection between the triangle method and constructing of Pascal triangle is studied. Besides that, a rather simple proof of the triangle method correctness is proposed. This proof is based on juxtaposition of the triangle method steps and a step-by-step construction of Pascal triangle. |
| doi_str_mv | 10.20535/SRIT.2308-8893.2020.1.12 |
| first_indexed | 2025-07-17T10:26:38Z |
| format | Article |
| fulltext |
І.Я. Спекторський, О.А. Галганов, 2020
129 Системні дослідження та інформаційні технології, 2020, № 1
УДК 512.563 : 517.987.3
DOI: 10.20535/SRIT.2308-8893.2020.1.12
МЕТОД ТРИКУТНИКА ДЛЯ ПОБУДОВИ ПОЛІНОМА
ЖЕГАЛКІНА: ЗВ’ЯЗОК З ТРИКУТНИКОМ ПАСКАЛЯ
І.Я. СПЕКТОРСЬКИЙ, О.А. ГАЛГАНОВ
Анотація. Поліном Жегалкіна — зручний спосіб зображення булевої функції
у вигляді суми за операцією (xor, або сума за модулем 2) скінченної кілько-
сті кон’юнкцій змінних — запропонований у 1927 р. радянським ученим
І.І. Жегалкіним. Одним з алгоритмів побудови полінома Жегалкіна для заданої
булевої функції є метод трикутника, запропонований у 1985–1987 рр. радянсь-
ким математиком В.П. Супруном. Застосування методу трикутника збігається
з почерговою побудовою рядків трикутника Паскаля з використанням відомо-
го співвідношення 11
1
k
n
k
n
k
n CCC . Природно очікувати на зв’язок обчис-
лення полінома Жегалкіна методом трикутника з розташуванням біноміальних
коефіцієнтів у трикутнику Паскаля. Проаналізовано зв’язок методу трикутника
з побудовою рядків трикутника Паскаля; запропоновано відносно просте дове-
дення коректності методу трикутника шляхом зіставлення кожного кроку ал-
горитма з покроковою побудовою рядків біноміальних коефіцієнтів у трикут-
нику Паскаля.
Ключові слова: булева функція, поліном Жегалкіна, метод трикутника, три-
кутник Паскаля.
ВСТУП
Поліном Жегалкіна — зручний спосіб зображення булевої функції у вигляді
суми за операцією (xor, або сума за модулем 2) скінченної кількості
кон’юнкцій (логічного добутку) змінних — запропонований у 1927 р. радян-
ським ученим І.І. Жегалкіним ([1]). Відомо (див., напр., [2, 3]), що кожну
булеву функцію можна зобразити у вигляді полінома Жегалкіна єдиним
способом (з точністю до переставлення доданків та множників у межах до-
данка).
Відомі різні алгоритми побудови полінома Жегалкіна для заданої буле-
вої функції — метод еквівалентних перетворень (з побудованої
диз’юнктивної або кон’юнктивної нормальної форми), метод невизначених
коефіцієнтів, метод Паскаля (половинне ділення) тощо. Менш відомий
зручний (хоча не найефективніший) метод трикутника, запропонований
у 1985 р. радянським математиком В.П. Супруном для симетричних булевих
функцій [4], а в 1987 р. — поширений на довільні булеві функції [5].
Застосування методу трикутника по суті збігається з побудовою кожно-
го наступного рядка трикутника Паскаля почерговим додаванням двох сусід-
ніх значень у попередньому рядку, тобто з використанням співвідношення
11
1
k
n
k
n
k
n CCC . Природно очікувати на зв’язок обчислення полінома Же-
галкіна методом трикутника (і зрештою будь-яким іншим методом) з розта-
шуванням біноміальних коефіцієнтів у трикутнику Паскаля. Проте ані опис
І.Я. Спекторський, О.А. Галганов
ISSN 1681–6048 System Research & Information Technologies, 2020, № 1 130
методу трикутника у працях [5, 6], ані доведення у [5] (як узагальнення ана-
логічного результату, доведеному для симетричних булевих функцій [4]) не
розкривають зв’язок цього методу з біноміальними коефіцієнтами.
Мета роботи: надати відносно просте доведення методу трикутника з
розкриттям тісного зв’язку між матрицею перетворення вектора значень бу-
левої функції у вектор коефіцієнтів полінома Жегалкіна з розташуванням
біноміальних коефіцієнтів у трикутнику Паскаля.
ОПЕРАТОР ПЕРЕТВОРЕННЯ ВЕКТОРА ЗНАЧЕНЬ БУЛЕВОЇ ФУНКЦІЇ
У ВЕКТОР КОЕФІЦІЄНТІВ ПОЛІНОМА ЖЕГАЛКІНА
Нехай f — n-арна булева функція, тобто BBf n : , де }1,0{B ; за потре-
би арність 0n вказують у позначенні функції f , використовуючи позна-
чення )(nf . У випадку 0n функцію )0(f вважають константою 0 або 1.
Булеву функцію ),,,( 21 nxxxf зазвичай задають її вектором значень
),,,(
1210
nfffw f , де kf ( 120 nk ) — значення f на двійковому
наборі n
n Bxxx ),,,( 21 , що відповідає двійковому запису числа k, тобто
),,,( 21 nk xxxff , якщо
n
i
in
ixk
1
2 .
Поліномом Жегалкіна називають суму за операцією (суму за моду-
лем 2) скінченної кількості кон’юнктів (добутку змінних); кожна змінна
входить у кожен кон’юнкт не більше одного разу; порожній кон’юнкт (що
не містить жодної змінної) є константою 1; кон’юнкти, що містять ті самі
змінні і відрізняються лише порядком їх запису, вважають однаковими; ко-
жен кон’юнкт входить у поліном не більше одного разу. Очевидно, що полі-
ном Жегалкіна є «традиційним» поліномом над полем ,},1,0{ , яке ізо-
морфне полю Галуа )2(GF (також використовують позначення 2 ) та
кільцю класів лишків 2/2 , і яке у цьому контексті називають алгеб-
рою Жегалкіна.
Поліном Жегалкіна можна подати у вигляді
k
k
jjjm
nk
njjj
n xxxaxxxf
21
21
0
1
21 ),,,(
, (1)
де }1,0{ma ( nknkjjj 1 ,211 ), індекси kjjj ,,, 21 відпо-
відають розрядам у двійковому записі номера m, тобто
n
jjj
k
i
jn
k
im 001001001002
211
.
Приклад 1. Зведемо у таблицю номери коефіцієнтів ma у десятковій
системі та двійковому коді для 3 ,2 ,1 ,0 n і запишемо відповідні кон’юнкти
(див. таблицю).
Метод трикутника для побудови полінома Жегалкіна: зв'язок з трикутником Паскаля
Системні дослідження та інформаційні технології, 2020, № 1 131
Кодування кон’юнктів у поліномі Жегалкіна для 3n
m m
десяткова
система
двійковий код
Кон’юнкт десяткова
система
двійковий
код
Кон’юнкт
0n : номер відсутній 1 3n
1n 000 0 1
0 0 1 001 1 3x
1 1 1x 010 2 2x
2n 011 3 21xx
0 00 1 100 4 1x
1 01 1x 101 5 31xx
2 10 2x 110 6 21xx
3 11 21xx
111 7 321 xxx
Для 3 ,2 ,1 n співвідношення (1) набуває вигляду
1101)( xaaxf , 2131221021 ),( xxaxaxaaxxf ;
32173263151432322310321 ),,( xxxaxxaxxaxaxxaxaxaaxxxf ;
у випадку 0 n булева функція f та відповідний поліном Жегалкіна a є
константою 0 або 1.
Очевидно, що поліном Жегалкіна над змінними nxxx ,,, 21 однознач-
но (з точністю до порядку доданків та множників у межах кожного доданка)
визначено коефіцієнтами ma ( 120 nm ), які формують вектор fp кое-
фіцієнтів полінома Жегалкіна.
Відомо [2, 3], що для кожної булевої функції існує єдиний (з точністю
до порядку доданків та множників у межах кожного доданка) поліном Же-
галкіна. Ураховуючи очевидну лінійну залежність між вектором значень fw
та вектором коефіцієнтів полінома Жегалкіна fp булевої функції )(nf , мо-
жемо розглядати співвідношення (тут i далі, якщо не вказано інше, операції
додавання та множення, визначені за арифметикою поля 2 )
ffn wpA , (2)
де nA — матриця розмірності nn 22 над полем 2 (двійкова матриця).
Матриця nA у співвідношенні (2) визначає систему 2n лінійних рівнянь, які
(а отже і nA ) можна отримати підставленням у формулу (1) усіх можливих
наборів значень змінних nxxx ,,, 21 у порядку зростання за номером
n
i
in
ixk
1
2 .
І.Я. Спекторський, О.А. Галганов
ISSN 1681–6048 System Research & Information Technologies, 2020, № 1 132
Приклад 2. Для 3 ,2 ,1 ,0n співвідношення (2) набуває вигляду
fa )1( ;
)1(
)0(
11
01
1
0
f
f
a
a
;
)1,1(
)0,1(
)1,0(
)0,0(
1111
0101
0011
0001
3
2
1
0
f
f
f
f
a
a
a
a
;
)1,1,1(
)0,1,1(
)1,0,1(
)0,0,1(
)1,1,0(
)0,1,0(
)1,0,0(
)0,0,0(
11111111
01010101
00110011
00010001
00001111
00000101
00000011
00000001
7
6
5
4
3
2
1
0
f
f
f
f
f
f
f
f
a
a
a
a
a
a
a
a
.
Зазначимо, що за обраної нумерації елементів у векторах fw та fp
матриця nA для будь-якого 0n є нижньотрикутною. З огляду на існування
та єдиність полінома Жегалкіна для кожної булевої функції рівняння (2) ві-
дносно fp за будь-якого фіксованого fw має єдиний розв’язок.
Множину kB для 1k розглядатимемо як лінійний простір над полем
2 з покоординатним застосуванням як суми векторів; nA — матриця
лінійного перетворення у
n
B2 , визначеного за співвідношенням (2).
Матрицю nA можна побудувати рекурсивно за 0n (див., напр., [6]);
для зручності наведемо відповідне твердження та його просте доведення.
Лема 1. Для послідовності матриць nA ( 0n ) справджується рекурент-
не співвідношення:
база рекурсії
)1(0 A ; (3)
крок рекурсії
nn
n
n
AA
A
A
nn
n
n 0
22
2
2
1 . (4)
Доведення. Застосуємо принцип математичної індукції, якщо 0n .
База. Для 0n отримуємо: 0
)0( )( axf , )( 0awp ff , звідки )1(0 A
як матриця тотожного перетворення у BB 1 . Отже, співвідношення (3)
справджується.
Припущення. Нехай 0m , і для mn твердження леми справджується.
Метод трикутника для побудови полінома Жегалкіна: зв'язок з трикутником Паскаля
Системні дослідження та інформаційні технології, 2020, № 1 133
Крок. Доведемо твердження леми для 1 mn . Увівши m -арні функ-
ції ),,,,1(),,,( 12121 mmmmx xxxfxxxf та ),,,( 121 mmx xxxf
),,,,0( 12 mm xxxf , отримаємо:
),,,(),,,(),,,,( 121121121 11 mmxmmxmm xxxfxxxxfxxxxxf
),,,(),,,()1( 121121 11 mmxmmx xxxfxxxxfx
)).,,,(),,,((),,,( 1212112 111 mmxmmxmmx xxxfxxxfxxxxf (5)
Визначення функцій
1xf і
1x
f та розклад (5) дозволяють записати
вектор коефіцієнтів fp та вектор значень fw і через
1xfp і
1xfp та через
1xfw і
1xfw відповідно (тут і далі операція на векторах застосовується по-
координатно):
1
1
2
2
x
x
m
m
f
f
f w
w
w ;
11
1
2
2
xx
x
m
m
ff
f
f pp
p
p ,
звідки
)(
00
111
1
11
1
xxx
x
xx
x
ffmfm
fm
ff
f
mm
m
f
mm
m
ppApA
pA
pp
p
AA
A
p
AA
A
f
f
f
fm
fm
w
w
w
pA
pA
x
x
x
x
1
1
1
1
.
Отже, ff
mm
m
wp
AA
A
0
для довільної булевої функції )(mf . Оскільки
матрицю лінійного у nB перетворенні ff wp у співвідношенні (2) ви-
значено однозначно, отримуємо твердження кроку рекурсії (4):
mm
m
m
AA
A
A
0
1 .
Наслідок. Перетворення ff wp інволютивне, тобто nIAn 2
2 (або
1 nn AA ) для кожного 0n .
Доведення. Достатньо довести рівність nIAn 2
2 для довільного 0n ,
застосовуючи принцип математичної індукції.
База. Для 0n з урахуванням співвідношення (3) отримуємо:
1
22
0 )1()1( IA .
Припущення. Нехай 0m , і для mn твердження nIAn 2
2 справджу-
ється.
І.Я. Спекторський, О.А. Галганов
ISSN 1681–6048 System Research & Information Technologies, 2020, № 1 134
Крок. Доведемо твердження nIAn 2
2 для 1 mn . З урахуванням
співвідношення (4) маємо:
nm
m
m
II
I
I
AAA
A
AA
A
AA
mmm
m
mm
m
mn 22
2
2
2
22
2
1
2
1
0
000
.
Приклад 3. Обчислимо nA для 30 n за рекурентними співвідно-
шеннями (3) і (4):
)1(0 A ;
11
010
00
0
1
AA
A
A ;
1111
0101
0011
0001
11
1
2
0
AA
A
A ;
11111111
01010101
00110011
00010001
00001111
00000101
00000011
00000001
22
2
3
0
AA
A
A .
Зауваження 1. Існування та єдиність розв’язку рівняння (2) і трикут-
ність матриці nA для довільного 0n дозволяє знаходити коефіцієнти по-
лінома Жегалкіна добре відомим методом невизначених коефіцієнтів,
розв’язуючи рівняння (2) послідовним обчисленням координат вектора fp
без безпосереднього обчислення nA (детальніше див., напр., [6]).
Зауваження 2. Твердження леми 1 фактично обґрунтовує коректність
відомого методу Паскаля — рекурсивне обчислення вектора коефіцієнтів
полінома Жегалкіна за вектором значень булевої функції послідовним ді-
ленням вектора значень навпіл (детальніше див., напр., [6]).
Зауваження 3. Завдяки співвідношенню 1 nn AA , яке забезпечує на-
слідок з леми 1, рівняння (2) допускає обертання: ffn pwA , що дозволяє
(за наявності матриці nA ) безпосередньо обчислювати вектор коефіцієнтів
полінома Жегалкіна fp за заданим вектором значень fw .
МЕТОД ТРИКУТНИКА: МАТРИЦЯ ОПЕРАТОРА ПЕРЕТВОРЕННЯ
Метод трикутника побудови полінома Жегалкіна для булевої функції
BBf n : , який запропонував радянський вчений В.П. Супрун [4–6], полягає
у побудові векторів
nn
Bvvv 21210 ,,, за рекурентними співвідношеннями
Метод трикутника для побудови полінома Жегалкіна: зв'язок з трикутником Паскаля
Системні дослідження та інформаційні технології, 2020, № 1 135
fwv 0 ,
nk
i
k
i
k
ik
i
ikvv
kiv
v
21 якщо ,
;0 якщо ,
1
1 (6)
для 220 nk . Доведено [5] і для випадку симетричних булевих функцій
[4], що координати kv0 ( 120 nk ) утворюють вектор коефіцієнтів полі-
нома Жегалкіна, тобто
12
12
1
1
0
0 ,,,
n
nvvvp f .
Зі співвідношення (6) очевидно, що 121
n
k
k
k
k
k vvv
( 120 nk ), а отже,
1212
12
12
1
12
0
12
12
1
1
0
0 ,,,,,,
nn
n
nnn
n vvvvvvvp f ,
тобто застосуванням рекурентного співвідношення (6) дістаємо 12
n
vp f за
22 n кроків.
Приклад 4. Для булевої функції )2(f з вектором значень )1101(fw
маємо:
).1011()01 ,1 0, ,1(
);1010()11 ,10 0, ,1(
);1011()10 ,01 ,11 ,1(
);1101(
3
2
1
0
v
v
v
wv f
Таким чином, )1011(3 vp f , тобто поліном Жегалкіна функції f
містить кон’юнкти з номерами 0, 2 і 3, що відповідає двійковим кодам 00
10 та 11. Отже, отримуємо такий поліном Жегалкіна:
21121 1),( xxxxxf .
Приклад 5. Для булевої функції )3(f з вектором значень
)11111101(fw отримуємо:
).10000011()01 ,1 ,0 ,0 ,0,0 ,0 ,1(
);10000010()11 ,10 ,0 ,0 ,0,0 ,0 ,1(
);10000011()01 ,10 ,00 ,0 ,0,0 ,0 ,1(
);10000010()11 ,10 ,00 ,00 ,0 ,0 ,0 ,1(
);10000011()01 ,10 ,00 ,00 ,00 0, 0, ,1(
);10000010()11 ,10 ,00 ,00 ,00 ,00 0, ,1(
);10000011()10 ,01 ,11 ,11 ,11 ,11 ,11 ,1(
);11111101(
7
6
5
4
3
2
1
0
v
v
v
v
v
v
v
wv f
І.Я. Спекторський, О.А. Галганов
ISSN 1681–6048 System Research & Information Technologies, 2020, № 1 136
Таким чином, )10000011(7 vp f , тобто поліном Жегалкіна функції
f містить кон’юнкти з номерами 0, 6 та 7, що відповідає двійковим кодам
000, 110 та 111. Отже, маємо такий поліном Жегалкіна:
32121321 1),,( xxxxxxxxf .
Зазначимо, що за побудовою (співвідношення (6)) у кожному з векторів
n
Bvk 2 ( 121 nk ) перші k координат збігаються з відповідними ко-
ординатами вектора 1kv , що дозволяє визначати вектори kv ( 120 nk )
як вектори меншої розмірності ( 120 ,2 nkk kBv
n
), і саме так зазви-
чай діють під час опису методу [4–6]. Однак у цій роботі для подальшого
розгляду доцільно не зменшувати розмірність векторів kv ( 120 nk ) на
кожному кроці рекурсії, доповнюючи перші k координат відповідними ко-
ординатами вектора 1kv , отриманого на попередньому кроці.
Запишемо рекурентне співвідношення (6) у векторно-матричному ви-
гляді над полем 2 :
fwv 0 , k
kn
k vTv 1,
1
,
де
110000000
011000000
001100000
000110000
000011000
00000
00000
00000
00000
,
kI
knT , 121 nk ,
звідки для перетворення ff pw дістаємо fnnnf wTTTp nn 1,22,12,
за
арифметикою 2 .
Уведемо до розгляду матриці
1,22,12, nnnn TTTT nn
за арифметикою поля 2 ;
1,22,12, nnnn TTTT nn
за арифметикою кільця .
Очевидно, що 2 mod nn TT , де 2 mod застосовується до кожного
елемента матриці
nT .
Приклад 6. Для 2n отримуємо:
1111
0101
0011
0001
1100
0110
0011
0001
1100
0110
0010
0001
1100
0100
0010
0001
2T
Метод трикутника для побудови полінома Жегалкіна: зв'язок з трикутником Паскаля
Системні дослідження та інформаційні технології, 2020, № 1 137
за арифметикою 2 ;
1331
0121
0011
0001
1100
0110
0011
0001
1100
0110
0010
0001
1100
0100
0010
0001
2
T
за арифметикою .
Легко пересвідчитися, що 2 mod 22
TT . Наведемо проміжний етап
обчислення для
2T :
1210
0121
0011
0001
1100
0110
0011
0001
1100
0110
0010
0001
1,22,2
TT .
Приклад 7. Для 3n отримуємо:
11000000
01100000
00110000
00010000
00001000
00000100
00000010
00000001
11000000
01100000
00100000
00010000
00001000
00000100
00000010
00000001
11000000
01000000
00100000
00010000
00001000
00000100
00000010
00000001
3
T
11000000
01100000
00110000
00011000
00001100
00000110
00000010
00000001
11000000
01100000
00110000
00011000
00001100
00000100
00000010
00000001
11000000
01100000
00110000
00011000
00001000
00000100
00000010
00000001
172135352171
01615201561
0015101051
00014641
00001331
00000121
00000011
00000001
11000000
01100000
00110000
00011000
00001100
00000110
00000011
00000001
І.Я. Спекторський, О.А. Галганов
ISSN 1681–6048 System Research & Information Technologies, 2020, № 1 138
за арифметикою ;
11000000
01100000
00110000
00010000
00001000
00000100
00000010
00000001
11000000
01100000
00100000
00010000
00001000
00000100
00000010
00000001
11000000
01000000
00100000
00010000
00001000
00000100
00000010
00000001
3T
11000000
01100000
00110000
00011000
00001100
00000110
00000010
00000001
11000000
01100000
00110000
00011000
00001100
00000100
00000010
00000001
11000000
01100000
00110000
00011000
00001000
00000100
00000010
00000001
11111111
01010101
00110011
00010001
00001111
00000101
00000011
00000001
11000000
01100000
00110000
00011000
00001100
00000110
00000011
00000001
за арифметикою ;
Легко пересвідчитися, що 2 mod 33
TT . Наведемо проміжні етапи об-
числення для
3T :
12100000
01210000
00121000
00012100
00001210
00000121
00000011
00000001
1,22,2
TT ;
13310000
01331000
00133100
00013310
00001331
00000121
00000011
00000001
1,32,33,3
TTT ;
14641000
01464100
00146410
00014641
00001331
00000121
00000011
00000001
1,32,33,34,3
TTTT ;
Метод трикутника для побудови полінома Жегалкіна: зв'язок з трикутником Паскаля
Системні дослідження та інформаційні технології, 2020, № 1 139
1510105100
0151010510
0015101051
00014641
00001331
00000121
00000011
00000001
1,32,33,34,35,3
TTTTT ;
16152015610
01615201561
0015101051
00014641
00001331
00000121
00000011
00000001
1,32,33,34,35,36,3
TTTTTT .
Теорема 1. Матриця
nT ( 0n ) містить трикутник Паскаля під голо-
вною діагоналлю:
12
12
2
12
1
12
0
12
1
1
0
1
0
0
00
000
n
nnnn CCCC
CC
C
Tn
. (7)
Доведення. Математичною індукцією за 1k ( 12 nk ) доведемо
рівність
k
kkk
k
kkk
k
kkk
k
kkk
k
kkk
k
kkk
CCC
CCC
CCC
CCC
CCC
CCC
CC
C
nTknTknT
10
10
10
10
10
10
1
1
0
1
00000
00000
00000
000
000000
00000
00000
000000
00000000
0
1,1,,
. (8)
База. У випадку 1k співвідношення (8) є тривіальним:
І.Я. Спекторський, О.А. Галганов
ISSN 1681–6048 System Research & Information Technologies, 2020, № 1 140
11000
01100
00110
00011
00001
110000000
011000000
001100000
000110000
000011000
00000
00000
00000
00000
1
1,
I
nT .
Припущення. Нехай 221 nm , і для mk співвідношення (8)
справджується.
Крок. Доведемо рівність (8) для 1 mk . Використовуючи відому то-
тожність 1
1
1
i
m
i
m
i
m CCC , а також очевидні рівності 0
1
0 0 mm CC та
1
10
m
m
m
m CC , отримуємо:
110000000
011000000
001100000
000110000
000011000
00000
00000
00000
00000
1
1,,1,
mI
nmnmn TTT
m
mmm
m
mmm
m
mmm
m
m
m
m
m
m
m
mm
m
mm
m
m
m
mmm
m
mmm
CCC
CCC
CCC
CC
C
CC
CmCC
CCCC
CCC
CC
C
v
10
10
10
120
10
110
1
1
1
1
0
1
1
1
0
1
0
0
0
00
00
000
0000
00000
00000
00000
00
10
00000
00000
00000
00000
0
00
000
Метод трикутника для побудови полінома Жегалкіна: зв'язок з трикутником Паскаля
Системні дослідження та інформаційні технології, 2020, № 1 141
.
1
1
1
1
0
1
1
1
1
1
0
1
1
1
1
1
0
1
1
11
1
1
1
1
0
1
1
1
1
1
1
0
1
11
1
1
1
1
0
1
110
1
1
1
1
0
1
1
1
0
1
0
0
0
00
00
000
0000
000000
00000
00000
2
100
0
00000
00000
00000
00000
00000
0
0
0
0
0
00
000
m
mmm
m
mmm
m
mmm
m
m
m
m
m
m
m
mm
m
m
m
mmm
m
m
m
m
m
mmm
m
m
m
mmm
m
mmm
CCC
CCC
CCC
CC
C
Cm
mCC
CCCC
CCCCC
CCCC
CCC
CC
C
Отже, співвідношення (8) справджується для 1 mk . Таким чином,
згідно з принципом математичної індукції, рівність (8) справджується для
кожного 121 nk . Шукану рівність (7) тепер дістаємо зі співвідношення
(8), якщо 12 nk . □
Твердження теореми 1, а також «проміжну» рівність (8), продемонст-
ровано у прикладах 6 та 7.
КОРЕКТНІСТЬ МЕТОДУ ТРИКУТНИКА
Деякі властивості парності біноміальних коефіцієнтів
Парність біноміальних коефіцієнтів зручно досліджувати, використовуючи
техніку кільця поліномів ][2 x над полем 2 . Нагадаємо (див. [7]), що кі-
льце поліномів K[x] над комутативним кільцем K з одиницею визначають як
сукупність нескінченних послідовностей елементів із K, у кожній з яких усі
члени, починаючи з деякого, дорівнюють 0 (нулю кільця K). Операції дода-
вання та множення кільця K природним чином поширюють на K[x], тракту-
ючи елементи послідовностей як коефіцієнти полінома. Елементи кільця
K[x] для зручності зображують поліномами зі змінною x (змінну x уведено
винятково для зручності позначень).
У кільці поліномів K[x] справджується низка алгебричних властивос-
тей, відомих для класичних поліномів кільця ][x ; зокрема, у кільці K[x]
справджується біноміальна формула. Детальніше про кільце поліномів див.,
напр. [7].
Лема 2. Число k
nC
2
є парним для всіх 0n , 121 nk .
Доведення. Твердження леми доводитимемо математичною індукцією
за 0n .
База. Для 0n твердження леми тривіальне завдяки відсутності цілих
121 0 k .
І.Я. Спекторський, О.А. Галганов
ISSN 1681–6048 System Research & Information Technologies, 2020, № 1 142
Припущення. Нехай твердження леми справджується для 0nn , тобто
k
nC 02
є парним для всіх 121 0 nk .
Крок. Нехай 0nn +1. Для полінома
102)1(
n
x за біноміальною фор-
мулою отримуємо розклад
102)1(
n
x
1010
10
1010
10101010
22
2
1212
2
22
2
1
2
0
2
nn
n
nn
nnnn xСxСxСxСС , (9)
а з урахуванням припущення індукції за арифметикою 2 :
101000010 222
2
2
2
22 1211)1()1(
nnnnnn
xxxxxx . (10)
Порівнюючи коефіцієнти поліномів у розкладах (9) та (10) за арифме-
тикою 2 (зокрема, ототожнюючи цілі числа за еквівалентністю 2 mod ),
отримуємо твердження кроку індукції:
.21 якщо 0,
;2 або 0 якщо ,1
1
1
2 0
0
10 n
n
k
k
kk
C n )2 mod( .
Таким чином, згідно з принципом математичної індукції, твердження
леми справджується для кожного 0n , тобто число k
nC
2
є парним для всіх
0n , 121 nk .
Надалі для зручності позначень покладемо
0j
iC для ij , (11)
вважаючи біноміальні коефіцієнти j
iC визначеними для всіх невід’ємних
ji, . Легко пересвідчитись, що тотожність 1
1
1
j
i
j
i
j
i CCC для ij
також справджується:
.1 :
;0 :
1
1
1
1
1
1
i
i
i
i
i
i
j
i
j
i
j
i
CCCij
CCCij
Лема 3. Числа k
mC , k
m nC
2
,
n
n
k
m
C 2
2
мають однакову парність для всіх
120 nm , 120 nk , 0n .
Доведення. Для полінома mn
x 2)1( ( 120 nm ) за арифметикою
2 з урахуванням леми 2 отримуємо:
))(1()1()1()1( 10222 mm
mmm
mm xCxCCxxxx
nnn
.21212010 mm
mmm
mm
mmm
nnn
xCxCxCxCxCC (12)
Метод трикутника для побудови полінома Жегалкіна: зв'язок з трикутником Паскаля
Системні дослідження та інформаційні технології, 2020, № 1 143
Порівнюючи коефіцієнти у розкладі (12) з відповідними коефіцієнтами
у розкладі за біноміальною формулою, дістаємо шукане твердження леми:
n
nn
k
m
k
m
k
m CCC 2
22
)2 mod(
для 120 nm , 120 nk , 0n .
Приклад 8. Продемонструємо результат леми 3 для 2n , 30 m ,
30 k :
172135352171
01615201561
0015101051
00014641
1331
0121
0011
0001
1,357,2121,735,1
0,201,156,615,1
0,100,101,55,1
0,40,60,41,1
.
У наведеному фрагменті трикутника Паскаля з урахуванням рівності
(11) біля кожного елемента k
mC для 30 m , 30 k (лівий верхній кут)
наведено елементи k
mC 4 , 4
4
k
mC . Легко пересвідчитися, що для кожних
30 m , 30 k елементи k
mC , k
mC 4 , 4
4
k
mC дійсно мають однакову пар-
ність.
Зауваження 4. Розглядаючи розклад поліномів над полем p , можна
досліджувати подільність біноміальних коефіцієнтів на довільне просте p;
наприклад, нескладно довести:
0k
pnC ) mod( p для 11 npk , 0n ;
0
1
k
pnC ) mod( p для npk 0 , 0n .
Детальніше про властивості біноміальних коефіцієнтів за pmod для
простого p див., напр., [8].
Доведення коректності методу трикутника
Теорема 2. Матриця nT , що визначає метод трикутника для булевої функції
)(nf , визначає перетворення ff pw , тобто ffn pwT за арифметикою
поля 2 .
Доведення. З урахуванням леми 1 для доведення рівності nn AT до-
статньо довести математичною індукцією рекурентні співвідношення (3) і
(4) для nT ( 0n ).
І.Я. Спекторський, О.А. Галганов
ISSN 1681–6048 System Research & Information Technologies, 2020, № 1 144
База. Для 0n отримуємо: )1(00 AT , тобто співвідношення (3) для
00 AT справджується.
Припущення. Нехай твердження теореми справджується для 0nn ,
тобто
00 nn AT .
Крок. Нехай 0nn +1. За теоремою 1 для 12,0 10 nji та з ураху-
ванням рівності (11) маємо:
2mod
, якщо ,0
; якщо ,2mod
)( ,10
j
i
j
i
jin C
ij
ijC
T
;
де mod — бінарна операція взяття остачі від ділення; зокрема, для a
непарне. якщо,1
парне; якщо,0
2mod
a
a
a
Далі з теореми 1 негайно випливає рівність jinjin TT ,,1 )()(
00
2modj
iC для 12,0 0 nji . Звідси за лемою 3 отримуємо:
2mod)()()()( 0000000 2,21,21,1,
j
ijinjinjinjin CTTTT nnn
для 12,0 0 nji . Таким чином, три блоки
120
1201
0
00
)(
n
n
j
inT ,
122
1201
100
00
)(
nn
n
j
inT ,
122
1221
100
1000
)(
nn
nn
j
inT збігаються між собою та з матри-
цею
0nT . Отже, з урахуванням кроку індукції та леми 1
11 0
00
0
00
0
0
00
n
nn
n
nn
n
n A
AA
A
TT
T
T ,
що доводить твердження кроку індукції. Згідно з принципом математичної
індукції співвідношення рекурсії (4) для nT справджується для всіх 0n ,
що завершує доведення теореми. □
ВИСНОВКИ
1. Метод трикутника побудови полінома Жегалкіна, запропонований
у працях [4, 5], тісно пов’язаний з трикутником Паскаля: рядки трикутника
Паскаля з точністю до еквівалентності за 2mod формують не тільки матри-
цю методу nT , а і проміжні матриці knT , ( 121 nk ), які відповідають
окремим крокам алгоритма.
2. Зв’язок з трикутником Паскаля дозволяє обґрунтувати коректність
методу трикутника, зіставляючи рекурентну побудову матриць nT ( 0n ) та
покрокову побудову рядків трикутника Паскаля (див. доведення теореми 1).
Метод трикутника для побудови полінома Жегалкіна: зв'язок з трикутником Паскаля
Системні дослідження та інформаційні технології, 2020, № 1 145
ЛІТЕРАТУРА
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 Con-
ference Proceedings. — 1997. — N 20. — P. 253–275.
Надійшла 10.01.2020
|
| id | journaliasakpiua-article-189119 |
| institution | System research and information technologies |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2025-07-17T10:26:38Z |
| publishDate | 2020 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| resource_txt_mv | journaliasakpiua/ed/f6911e3fca3f245b174d3e3041fd9aed.pdf |
| spelling | journaliasakpiua-article-1891192020-08-11T08:50:57Z Triangle method for constructing Zhegalkin polynomial: connection with Pascal's triangle Метод треугольника для построения полинома Жегалкина: связь с треугольником Паскаля Метод трикутника для побудови полінома Жегалкіна: зв’язок з трикутником Паскаля Spectorsky, I. Ya. Galganov, O. A. поліном Жегалкіна метод трикутника трикутник Паскаля полином Жегалкина метод треугольника треугольник Паскаля boolean function Zhegalkin polynomial triangle method Pascal’s triangle Introduced by Soviet scientist I. Zhegalkin in 1927, Zhegalkin polynomial is a way to represent a Boolean function as an exclusive or of conjunctions of variables. One of the known algorithms for constructing Zhegalkin polynomial is so called ‘triangle method’ proposed in 1985–1987 by Soviet mathematician V.P. Suprun. Applying of the triangle method mainly coincides with step-by-step constructing Pascal triangle rows using the equality Cn+1k+1 = Cnk + Cnk+1. Therefore, it would be natural to expect for the relation between the calculation of Zhegalkin polynomial by the triangle method and an arrangement of binomial coefficients in Pascal triangle. In this paper, the connection between the triangle method and constructing of Pascal triangle is studied. Besides that, a rather simple proof of the triangle method correctness is proposed. This proof is based on juxtaposition of the triangle method steps and a step-by-step construction of Pascal triangle. Полином Жегалкина — удобный способ представления булевой функции в виде суммы по операции ⨁ (xor, или сумма по модулю 2) конечного числа конъюнкций переменных — предложен в 1927 г. советским ученым И.И. Жегалкиным. Одним з алгоритмов построения полинома Жегалкина для заданной булевой функции есть метод треугольника, предложенный в 1985–1987 гг. советским математиком В.П. Супруном. Применение метода треугольника совпадает с пошаговым построением треугольника Паскаля "строка за строкой" по известному соотношению Cn+1k+1 = Cnk + Cnk+1. Естественно ожидать связь между вычислением полинома Жегалкина методом треугольника с расположением биномиальных коэффициентов в треугольнике Паскаля. Проанализирована связь метода треугольника с построением строк треугольника Паскаля; предложено относительно простое доказательство корректности метода треугольника путем сопоставления шагов алгоритма с пошаговым построением строк биномиальных коэффициентов в треугольнике Паскаля. Поліном Жегалкіна — зручний спосіб зображення булевої функції у вигляді суми за операцією ⨁ (xor, або сума за модулем 2) скінченної кількості кон’юнкцій змінних — запропонований у 1927 р. радянським ученим І.І. Жегалкіним. Одним з алгоритмів побудови полінома Жегалкіна для заданої булевої функції є метод трикутника, запропонований у 1985–1987 рр. радянським математиком В.П. Супруном. Застосування методу трикутника збігається з почерговою побудовою рядків трикутника Паскаля з використанням відомого співвідношення Cn+1k+1 = Cnk + Cnk+1. Природно очікувати на зв’язок обчислення полінома Жегалкіна методом трикутника з розташуванням біноміальних коефіцієнтів у трикутнику Паскаля. Проаналізовано зв’язок методу трикутника з побудовою рядків трикутника Паскаля; запропоновано відносно просте доведення коректності методу трикутника шляхом зіставлення кожного кроку алгоритма з покроковою побудовою рядків біноміальних коефіцієнтів у трикутнику Паскаля. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2020-06-23 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/189119 10.20535/SRIT.2308-8893.2020.1.12 System research and information technologies; No. 1 (2020); 129-145 Системные исследования и информационные технологии; № 1 (2020); 129-145 Системні дослідження та інформаційні технології; № 1 (2020); 129-145 2308-8893 1681-6048 uk https://journal.iasa.kpi.ua/article/view/189119/209253 Copyright (c) 2021 System research and information technologies |
| spellingShingle | поліном Жегалкіна метод трикутника трикутник Паскаля Spectorsky, I. Ya. Galganov, O. A. Метод трикутника для побудови полінома Жегалкіна: зв’язок з трикутником Паскаля |
| title | Метод трикутника для побудови полінома Жегалкіна: зв’язок з трикутником Паскаля |
| title_alt | Triangle method for constructing Zhegalkin polynomial: connection with Pascal's triangle Метод треугольника для построения полинома Жегалкина: связь с треугольником Паскаля |
| title_full | Метод трикутника для побудови полінома Жегалкіна: зв’язок з трикутником Паскаля |
| title_fullStr | Метод трикутника для побудови полінома Жегалкіна: зв’язок з трикутником Паскаля |
| title_full_unstemmed | Метод трикутника для побудови полінома Жегалкіна: зв’язок з трикутником Паскаля |
| title_short | Метод трикутника для побудови полінома Жегалкіна: зв’язок з трикутником Паскаля |
| title_sort | метод трикутника для побудови полінома жегалкіна: зв’язок з трикутником паскаля |
| topic | поліном Жегалкіна метод трикутника трикутник Паскаля |
| topic_facet | поліном Жегалкіна метод трикутника трикутник Паскаля полином Жегалкина метод треугольника треугольник Паскаля boolean function Zhegalkin polynomial triangle method Pascal’s triangle |
| url | https://journal.iasa.kpi.ua/article/view/189119 |
| work_keys_str_mv | AT spectorskyiya trianglemethodforconstructingzhegalkinpolynomialconnectionwithpascalstriangle AT galganovoa trianglemethodforconstructingzhegalkinpolynomialconnectionwithpascalstriangle AT spectorskyiya metodtreugolʹnikadlâpostroeniâpolinomažegalkinasvâzʹstreugolʹnikompaskalâ AT galganovoa metodtreugolʹnikadlâpostroeniâpolinomažegalkinasvâzʹstreugolʹnikompaskalâ AT spectorskyiya metodtrikutnikadlâpobudovipolínomažegalkínazvâzokztrikutnikompaskalâ AT galganovoa metodtrikutnikadlâpobudovipolínomažegalkínazvâzokztrikutnikompaskalâ |