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

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

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

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

• $x\wedge (y\wedge z)=(x\wedge y)\wedge z$, $x\wedge y=y\wedge 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\wedge (y\oplus z)=x\wedge y\oplus x\wedge z$

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

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

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

См. также

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