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

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

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

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

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

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

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

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

См. также

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