§12. Полином Жегалкина

Теорема 3.16 (Жегалкина) Любую булеву функцию f(х1, х2,...,хn) можно единственным образом представить в виде:

где ai (0 ≤ i≤ k) являются постоянными, равными нулю или единице. Правая часть записанного равенства называется полиномом Жегалкина.

Доказательство. Если функция тождественно равна нулю, то, очевидно, f(x1, x2,..., xn)=а0, а0 = 0. Пусть f(x1,x2,..., xn) не тождественно равна нулю. Рассмотрим сумму всех собственных конституент единицы функции:

$К_1 + К_2 +... +К_s$

Покажем, что сумма (3.21) представляет нашу функцию. Пусть f(b1, b2,... bn)= 1, тогда на наборе (b1, b2,..., bn) одна из собственных конституент единицы принимает значение 1, положим, Кj. Остальные собственные конституенты единицы на этом наборе равны нулю. Тогда сумма (3.21) обращается в единицу. Если f(b1, b2,..., bn)=0, то на наборе (b1, b2,..., bn) все собственные конституенты Кi (1≤ i≤ s) обращаются в нуль, следовательно, и сумма (3.21) тоже равна нулю. Итак, доказано, что

$f(x_1, x_2,..., x_n) ~ К_1 + К_2 +... +К_s.$

В конституентах единицы исключим отрицание, используя соотношение:

$¬x ~1+ x$

Появившиеся при этом скобки раскроем, используя дистрибутивность конъюнкции относительно сложения по модулю два. Далее приведем подобные члены, используя соотношения: x + x +...+ x ~ 0, когда имеем четное число слагаемых, и x + x +...+ x ~ x, когда имеем нечетное число слагаемых.

В результате получим требуемый полином Жегалкина.

Теперь докажем единственность. Максимальное возможное число слагаемых в полиноме Жегалкина равно числу подмножеств множества (x1, x2,..., xn) следовательно, равно $2^n$. Различные полиномы Жегалкина получаются, если некоторые аi = 0, другие аj = 1. Таким образом, число полиномов Жегалкина равно $2^{2^n}$. Число различных булевых функций от n переменных, как известно, тоже равно $2^{2^n}$ , причем каждая функция (по доказанному) имеет свой полином. Отсюда и следует единственность полинома Жегалкина для данной функции.