Конспект лекций Дискретная математика

Алгебра Жегалкина и линейные функции.

Определение. Алгебра над множеством логических функций с двумя бинарными операциями называется алгеброй Жегалкина.

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

В алгебре Жегалкина выполняются следующие соотношения (знак умножения опущен):

2.1. ,

2.2. ,

2.3 ,

2.4 .

Кроме того, выполняются соотношения, ранее сформулированные булевой алгебры, относящиеся к конъюнкции и константам. Отрицание и дизъюнкция выражаются так:

2.5 ,

2.6 .

Если в произвольной формуле алгебры Жегалкина раскрыть скобки и произвести все упрощения по вышеуказанным соотношениям, то получится формула, имеющая вид Суммы произведений, то есть полином (многочлен) по модулю 2. Такая формула называется полиномом Жегалкина для данной функции.

От булевой формулы всегда можно перейти к формуле алгебры Жегалкина, используя равенства 2.5 и 2.6, а также прямое следствие из равенства 2.6: если , то . Оно, в частности, позволяет заменять знак дизъюнкции знаком в случаях, когда исходная формула представляет собой СДНФ.

Пример 2. Составить полиномы Жегалкина для данных функций:

а) ,

б) .

Заметим, что если в полученных полиномах Жегалкина произвести обратную замену функций, то получим упрощённые формулы булевой алгебры.

Теорема 11.2. Для всякой логической функции существует полином Жегалкина и притом единственный.

Существование такого полинома, по сути, уже доказано, а для доказательства его единственности достаточно показать существование взаимно однозначного соответствия между множеством всех функций переменных и множеством всех полиномов Жегалкина.

Определение. Функция, у которой полином Жегалкина имеет вид , где параметры равны нулю или единице, называется линейной.

Все функции от одной переменной линейны. Также линейными являются функции эквивалентность и сумма по модулю 2.

Содержание