Многочлены

В заключение рассмотрим ещё один полный (т.е. такой, при помощи которого можно выразить любую зависимость) набор операций: единица, XOR, конъюнкция (далее: \(1,+,\cdot\)).

С этим набором операций ситуация не сильно сложнее: интерполяционная формула Лагранжа для вершин \(n\)-мерного куба даёт выражение

\[ f(x) = \sum_a f(a) (x_1+\overline{a_1}) (x_2+\overline{a_2})\ldots (x_n+\overline{a_n}) \]

Верность равенства тривиально проверяется подстановкой \(a\) или же замечанием о том, что эта формула получена путём формальной замены в СДНФ дизъюнкции на XOR. Поскольку для любого значения \(x\) не более чем один из дизъюнктов равен 1, XOR дизъюнктов СДНФ равен их дизъюнкции.

После раскрытия скобок и приведения подобных получается сумма одночленов, каждый из которых любую из переменных содержит в не более чем первой степени. Такая сумма называется многочленом Жегалкина функции \(f\).

Различных одночленов \(2^n\), поэтому различных многочленов Жегалкина \(2^{2^n}\) — ровно столько же, сколько и \(n\)-арных операций. Поскольку любая операция имеет хотя бы один многочлен Жегалкина, то, согласно принципу Дирихле, любая операция имеет ровно один многочлен Жегалкина.

Например, импликация имеет многочлен Жегалкина

\[ x\Rightarrow y = (x+1)y+(x+1)(y+1)+xy = xy + x + 1 \]