WikiSort.ru - Не сортированное

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

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

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

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

См. также

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

Примечания