Русская Википедия:Алгебра Жегалкина

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

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

• <math>x \land ( y \land z) = (x \land y) \land z</math>, <math>x \land y = y \land x</math>
• <math>x \oplus ( y \oplus z) = (x \oplus y) \oplus z</math>, <math>x \oplus y = y \oplus x</math>
• <math>x \oplus x = 0</math>
• <math>x \oplus 0 = x</math>
• <math>x \land ( y \oplus z) = x \land y \oplus x \land z</math>

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

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

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

См. также

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