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

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

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

Основные идентичности

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

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

См. также

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

Ссылки

• Жегалкин, Иван Иванович (1927). «О технике вычисления высказываний в символической логике» (PDF) . Математический сборник . 34 (1): 9–28 . Проверено 12 января 2024 г.

Дальнейшее чтение

• https://encyclopediaofmath.org/wiki/Zhegalkin_algebra