yandex rtb 1
ГоловнаЗворотній зв'язок
yande share

Математическая логика

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

Определение 1.16. Система элементов {0,1}, на которой определены операции & и Ø (конъюнкции и сложения по mod 2), для которых выполняются соотношения:

ху = ух                                           (1.14)

x(yz)=xy                                           (1.15)

хх =0                                               (1.16)

х0 = х                                              (1.17)

а также соотношения булевой алгебры (1.3, 1.4, 1.6, 1.7, 1.10, 1.11), относящиеся к конъюнкции и константам, называется алгеброй Жегалкина.

Из таблицы истинности операции сложения по mod 2 следует, что

¬х=х1                                                                                                                     (1.18)

Операцию дизъюнкции через  и & можно выразить так:

xvy=¬(¬x¬y) = (x1)(y1)1=xyxy                        (1.19)

Определение 1.16. Всякая формула алгебры Жегалкина, имеющая вид суммы (по mod 2) произведений булевых переменных, называется полиномом Жегалкина.

Если в каждый член полинома Жегалкина каждая переменная входит один раз и в первой степени, n полином не содержит одинаковых членов, то такой полином Жегалкина называется каноническим.

Теорема 1.6. Всякая булева функция единственным образом представима в виде канонического полинома Жегалкина.

Всякую булеву формулу можно представить в виде полинома Жегалкина, используя соотношения (1.18), (1.19). Из (1.19) следует, что если f1&f2=0, то f1vf2=f1f2. Отсюда можно сформулировать правило для представления булевой функции в виде полинома Жегалкина: для булевой формулы, заданной в виде СДНФ, достаточно заменить знак v на знак , представить отрицания переменных как ¬х = х1, раскрыть скобки по правилу умножения полиномов (1.15) и привести подобные члены.

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

Все функции одной переменной линейны. Линейными функциями двух переменных являются сложение mod 2 (ху) и эквивалентность:

x¬x¬yvxy=(x1)(y1) xy=xyxy1xy=xy1

 

10