Множество булевых функций, заданный в базисе Жегалкина 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

H⊕H=0

H&H=H

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

¬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 переменных X₁,X₂ … X_n называется выражение вида:

C₀⊕C₁X₁⊕C₂X₂⊕  …  ⊕C_nX_n⊕C₁₂X₁X₂⊕  …  ⊕C_{12  …  n}X₁X₂  …  X_n,

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

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

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

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

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

1. Метод неопределенных коэффициентов. Пусть P(X₁,X₂  …  X_n) — искомый полином Жегалкина, реализующий заданную функцию f(X₁,X₂  …  X_n). Запишем его в виде

P=C₀⊕C₁X₁⊕C₂X₂⊕  …  ⊕C_nX_n⊕C₁₂X₁X₂⊕  …  ⊕C_{12  …  n}X₁X₂  …  X_n

Найдем коэффициенты C_k. Для этого последовательно придадим переменным X₁,X₂  …  X_n значения из каждой строки таблицы истинности. В итоге получим систему из 2ⁿ уравнений с 2ⁿ неизвестными, имеющую единственное решение. Решив ее, находим коэффициенты полинома P(X₁,X₂ … X_n).

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

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

Решение.

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

P=C₀⊕C₁X⊕C₂Y⊕C₁₂XY

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

X	0	0	1	1
Y	0	1	0	1
X→Y	1	1	0	1

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

f(0,0)=P(0,0)=C₀=1

f(0,1)=P(0,1)=C₀⊕C₂=1

f(1,0)=P(1,0)=C₀⊕C₁=0

f(1,1)=P(1,1)=C₀⊕C₁⊕C₂⊕C₁₂=1

Откуда последовательно находим, C₀=1, C₁=1, C₂=0, C₁₂=1

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

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

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

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