Синтез в базисе Жегалкина.

Полиномом Жегалкина называется представление логической функции в базисе {Å, И, НЕ} (имеется соответствующая алгебра Жегалкина). В данном представлении инверсия реализуется как сумма по модулю 2 с константой 1.

Для представления ДНФ в виде полинома Жегалкина необходимо выразить дизъюнкцию через конъюнкцию и инверсию.

Например:

хÚ y= =(хÅ 1)(yÅ 1)Å 1=

=xyÅ xÅ yÅ 1Å 1=xyÅ xÅ y.

(1Å 1=0).

Пример. Представить в виде полинома Жегалкина логическую функцию xÚ yÚ z.

xÚ yÚ z= =(хÅ 1)(yÅ 1)(zÅ 1)Å 1=(xyÅ xÅ yÅ 1)(zÅ 1)Å 1=

=xyzÅ xzÅ yzÅ xyÅ xÅ yÅ 1Å 1=xyzÅ xzÅ yzÅ xyÅ xÅ y.

Для преобразования полинома Жегалкина используются обычные приемы элементарной алгебры (исключение составляет равносильность аÅ а=0).

Полином Жегалкина может быть получен по таблице истинности путем суммирования по модулю 2 конъюнкций переменных без инверсии x_i или инверсных переменных (x_jÅ 1) соответствующих рабочих наборов.

Например, получим полином Жегалкина для функции f, таблица истинности которой имеет вид табл. 54.

Таблица 54

Таблица истинности

Тогда получим:

f=(xÅ 1)(yÅ 1)zÅ (xÅ 1)y(zÅ 1)Å x(yÅ 1)(zÅ 1)Å xyz=

=(xyÅ xÅ yÅ 1)zÅ (xzÅ xÅ zÅ 1)yÅ x(yzÅ yÅ zÅ 1)Å xyz=

=xÅ yÅ z,

что и требовалось доказать, ибо и рассматривалась функция сложения по модулю 2 трех аргументов.