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

Система булевых функций {+, &, 1} – полна, более того, она является базисом, называемым базисом Жегалкина (при удалении функции, из которой она становится неполной).

Многочленом Жегалкина называется многочлен, являющийся сум­мой константы и различных одночленов, в которые каждая из переменных входит не выше, чем в первой степени.

- Многочлен Жегалкина константы равен самой же константе;

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

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

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

и т.д.

Коэффициенты a_{1 ,... i ,} и свободный член а_о принимают значения 0 или 1, а число слагаемых в формуле равно 2ⁿ, где n — число переменных. Знак — сумма по модулю два.

Теорема Жегалкина. Каждая булева функция f(x₁,…, х_n) может быть представлена в виде многочлена Жегалкина и притом единственным образом, с точностью до порядка слагаемых.