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

Определение.

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

Алгебра Жегалкина, названная по имени предложившего её советского ученого, строится на основе операций сложения по модулю 2 и конъюнкции.

Алгебра , образованная множеством вместе с операциями конъюнкции (), суммы по модулю 2 () и константами 0 и 1, называется алгеброй Жегалкина.

Пусть - булевы переменные, тогда формула , содержащая только операции конъюнкции и суммы по модулю 2, является формулой алгебры Жегалкина.

Непосредственной проверкой по таблицам истинности можно установить следующие основные тождества (свойства этой алгебры):

1) , - коммутативность;

2) , - ассоциативность;

3) - дистрибутивность относительно ;

4) - свойства констант.

Все эти свойства подобны обычной алгебре, но в отличие от булевой алгебры закон дистрибутивности суммы по модулю 2 относительно конъюнкции не имеет силы .

Справедливы также следующие тождества:

5) - закон идемпотентности для ;

6) - закон приведения подобных при выполнении операции суммы по модулю 2.

Таким образом, в алгебре Жегалкина, как и в булевой алгебре, не могут появляться коэффициенты при переменных и показатели степени.

В алгебре Жегалкина используются следующие соотношения, позволяющие перейти от любой формулы булевой алгебры к соответствующей ей формуле алгебры Жегалкина , и наоборот .

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

Пример. Докажем тождество , используя таблицы истинности функции (таблица 3.26).

Таблица 3.26 - Таблица истинности функций и

Дата добавления: 2014-10-22