Следствие. Полином Жегалкина

Пусть f (x ₁,..., x_n) Î P ₂, представим ее в виде формулы через конъюнкцию и сумму по модулю два, используя числа 0 и 1. Это можно сделать, так как { x ₁& x ₂, x ₁Å x ₂, 0, 1} полна в Р ₂. В силу свойства x & (y Å z)= xy Å xz можно раскрыть все скобки, привести подобные члены, и получится полином от n переменных, состоящий из членов вида х х ... х , соединенных знаком Å. Такой полином называется полиномом Жегалкина.

Общий вид полинома Жегалкина

где , s = 0, 1,..., n, причем при s = 0 получаем свободный член а ₀.