Многочлены Жегалкина

Мы уже заметили, что конъюнкция совпадает с обычным арифметическим умножением, попробуем ввести сложение: 0+0=0; 0+1-1; 1+0=1; 1+1=? Если принять 1+1=1, то получим дизъюнкцию. Если принять 1+1=0, то получим исключающее или. Принимаем второе соотношение: х+у=хÅу. Такое сложение совпадает с известным в теории чисел сложением по модулю 2. Заметим, что всегда хÅх=0.

Всякая композиция сложений, умножений и констант называется арифметическим многочленом.

Многочленом Жегалкина называют многочлен вида , где суммирование ведется по некоторому множеству различных наборов (i₁, i₂,…,i_k), в котором ни один индекс не повторяется.

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

Выразим три основные логические операции через сложение и умножение, превратив их в многочлены Жегалкина.

Конъюнкция хÙу=ху уже готовый многочлен Жегалкина. Отрицание =хÅ1. Дизъюнкция

=(xÅ1)(yÅ1)+1= xy Å x Å y Å1Å1= xy Å x Å y.