Полином Жегалкина

Множество булевых функций, заданный в базисе Жегалкина S4={⊕,&,1} называется алгеброй Жегалкина.

Основные свойства.

1. коммутативность

H1⊕H2=H2⊕H1

H1&H2=H2&H1

2. ассоциативность

H1⊕(H2⊕H3)=(H1⊕H2)⊕H3

H1&(H2&H3)=(H1&H2)&H3

3. дистрибутивность

H1&(H2⊕H3)=(H1&H2)⊕(H1&H3)

4. свойства констант

H&1=H

H&0=0

H⊕0=H

5. H⊕H=0

H&H=H

Утверждение. Через операции алгебры Жегалкина можно выразить все другие булевы функции:

¬X=1⊕X

XvY=X⊕Y⊕XY

X∼Y=1⊕X⊕Y

X→Y=1⊕X⊕XY

X↓Y=1⊕X⊕Y⊕XY

X|Y=1⊕XY

Определение. Полиномом Жегалкина (полиномом по модулю 2) от n переменных X1,X2 ... Xn называется выражение вида:

C0⊕C1X1⊕C2X2⊕  ...  ⊕CnXn⊕C12X1X2⊕  ...  ⊕C12  ...  nX1X2  ...  Xn,

где постоянные Ck могут принимать значения 0 ли 1.

Если полином Жегалкина не содержит произведений отдельных переменных, то он называется линейным (линейная функция).

Например, f=X⊕YZ⊕XYZ и f1=1⊕X⊕Y⊕Z - полиномы, причем вторая является линейной функцией.

Теорема. Каждая булева функция представляется в виде полинома Жегалкина единственным образом.

Приведем основные методы построения полиномов Жегалкина от заданной функции.

1. Метод неопределенных коэффициентов. Пусть P(X1,X2  ...  Xn) - искомый полином Жегалкина, реализующий заданную функцию f(X1,X2  ...  Xn). Запишем его в виде

P=C0⊕C1X1⊕C2X2⊕  ...  ⊕CnXn⊕C12X1X2⊕  ...  ⊕C12  ...  nX1X2  ...  Xn

Найдем коэффициенты Ck. Для этого последовательно придадим переменным X1,X2  ...  Xn значения из каждой строки таблицы истинности. В итоге получим систему из 2n уравнений с 2n неизвестными, имеющую единственное решение. Решив ее, находим коэффициенты полинома P(X1,X2 ... Xn).

2. Метод, основанный на преобразовании формул над множеством связок {¬,&}. Строят некоторую формулу Ф над множеством связок {¬,&}, реализующую данную функцию f(X1,X2 ... Xn). Затем заменяют всюду подформулы вида ¬A на A⊕1, раскрывают скобки, пользуясь дистрибутивным законом (см. свойство 3), а затем применяют свойства 4 и 5.

Пример. Построить полином Жегалкина функции f(X,Y)=X→Y

Решение.

1. (метод неопределенных коэффициентов). Запишем искомый полином в виде:

P=C0⊕C1X⊕C2Y⊕C12XY

Пользуясь таблицей истинности

X0011
Y0101
X→Y1101

получаем, что

f(0,0)=P(0,0)=C0=1

f(0,1)=P(0,1)=C0⊕C2=1

f(1,0)=P(1,0)=C0⊕C1=0

f(1,1)=P(1,1)=C0⊕C1⊕C2⊕C12=1

Откуда последовательно находим, C0=1, C1=1, C2=0, C12=1

Следовательно: x→y=1⊕X⊕XY.

2. (Метод преобразования формул.). Имеем:

X→Y=¬XvY=¬(X¬Y)=(X(Y⊕1))⊕1=1⊕X⊕XY

Заметим, что преимущество алгебры Жегалкина (по сравнению с другими алгебрами) состоит в арифметизации логики, что позволяет выполнять преобразования булевых функций довольно просто. Ее недостатком по сравнению с булевой алгеброй является громоздкость формул.