Операция двоичного сложения. Многочлен Жегалкина

х1	х2

Суммой по модулю два М2 или строгой дизъюнкцией двух переменных х₁ и х₂ называется булева функция , которая равна 1 тогда и только тогда, когда равна 1 только одна переменная.

Полиномом (многочленом) Жегалкина от п переменных называется функция

P = a₀ + a₁x₁ +a₂x₂ + ...a_nx_n +a_{n +1}x₁x₂ +...+a_{n +C}²_nx_n-1x_n + ...+a_2n-1x₁x₂..xn

Всего здесь 2^п слагаемых. Напомним, что + сейчас означает сложение по модулю 2, коэффициенты a₀, a₁,..., a₂ⁿ_-1 являются константами (равными нулю или единице).

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

Теорема. Любая функция п переменных может быть представлена полиномом Жегалкина и это представление единственно.

Многочлен Жегалкина булевой функции двух переменных:

Многочлен Жегалкина булевой функции трех переменных:

Коэффициенты а_1,…..,i и свободный член а₀ принимают значения 0 или 1, а число слагаемых в формуле равно 2ⁿ, где n – число переменных.

Пример №1.

Дана ДНФ . Требуется найти для этой функции полином Жегалкина.

Решение: Ставим двойное отрицание и по закону де Моргана получаем:

Учитывая свойство суммы по модулю два: «уберём» отрицания. Учтем, что четное число слагаемых по модулю два равно 0, а нечетное - одному такому слагаемому, получим:

Последнее выражение и является полиномом Жегалкина.

Пример 2.

( xy + 1)((x + 1)(y + 1) + 1)((y + 1)z + 1) + 1 = (xy + 1)(xy + x + y)(yz + z + 1) + 1 = (x + y)(yz + z + 1) + 1= xyz + yz + xz +yz + x + y + 1 = xyz + xz + x +y + 1.

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