Алгебра Жегалкина (GliyQjg "yigltnug)

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

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

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

$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$ - операция конъюнкции.