Алгебра Жегалкина

Алгебра Жегалкина — множество булевых функций, на котором определены нульарная операция взятия единицы ${\displaystyle 1}$, бинарная операция конъюнкции ${\displaystyle \land }$ и бинарная операция суммы по модулю два ${\displaystyle \oplus }$. Константа ноль вводится как ${\displaystyle 1\oplus 1=0}$. Операция отрицания вводится соотношением ${\displaystyle \neg x=x\oplus 1}$. Операция дизъюнкции следует из тождества ${\displaystyle x\lor y=x\land y\oplus x\oplus y}$[1].

При помощи алгебры Жегалкина всякую совершенную дизъюнктивную нормальную форму можно единственным образом преобразовать в полином Жегалкина (теорема Жегалкина).

Основные тождества

• ${\displaystyle x\land (y\land z)=(x\land y)\land z}$, ${\displaystyle x\land y=y\land x}$
• ${\displaystyle x\oplus (y\oplus z)=(x\oplus y)\oplus z}$, ${\displaystyle x\oplus y=y\oplus x}$
• ${\displaystyle x\oplus x=0}$
• ${\displaystyle x\oplus 0=x}$
• ${\displaystyle x\land (y\oplus z)=x\land y\oplus x\land z}$

Таким образом, базис булевых функций ${\displaystyle {\bigl \langle }\wedge ,\oplus ,1{\bigr \rangle }}$ является функционально-полным логическим базисом.

Также функционально полным является и его инверсный логический базис ${\displaystyle {\bigl \langle }\lor ,\odot ,0{\bigr \rangle }}$, где ${\displaystyle \odot }$- инверсия операции XOR (эквиваленция). Для этого базиса тождества также инверсные: ${\displaystyle 0\odot 0=1}$ — вывод константной единицы, ${\displaystyle \neg x=x\odot 0}$ — вывод операции отрицания, ${\displaystyle x\land y=x\lor y\odot x\odot y}$- операция конъюнкции.

Функциональная полнота этих двух базисов следует из полноты базиса ${\displaystyle \{\neg ,\land ,\lor \}}$.

См. также

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

Примечания

1. Капитонова Ю. В., Кривой С. Л., Летичевский А. А. Лекции по дискретной математике. — СПб., БХВ-Петербург, 2004. — isbn 5-94157-546-7, с 110-111