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

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

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

Основные тождестваПравить

$\text{[math]}$ $\text{[math]}$ $x\land (y\land z)=(x\land y)\land z$ , $\text{[math]}$ $\text{[math]}$ $x\land y=y\land x$
$\text{[math]}$ $\text{[math]}$ $x\oplus (y\oplus z)=(x\oplus y)\oplus z$ , $\text{[math]}$ $\text{[math]}$ $x\oplus y=y\oplus x$
$\text{[math]}$ $\text{[math]}$ $x\oplus x=0$
$\text{[math]}$ $\text{[math]}$ $x\oplus 0=x$
$\text{[math]}$ $\text{[math]}$ $x\land (y\oplus z)=x\land y\oplus x\land z$

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

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

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

См. такжеПравить

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

ПримечанияПравить

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

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

[1]