Теорема Жегалкина. Способы построения полиномов Жегалкина. Линейные функции

Теорема Жегалкина: Всякая булева функция f(x₁,…,x_n) представима полиномом Жегалкина, т.е в виде , где в каждом наборе вида (i₁,…,i_k) все i_j различны, а суммирование ведется по некоторому множеству таких несовпадающих наборов. Представление функции в виде полинома Жегалкина единственно с точностью до порядка слагаемых.

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

Аксиомы булева кольца и равенства, выражающие операции дизъюнкции, конъюнкции и отрицания через операции этого кольца:

. Если в эквивалентности формулы φ и ψ являются различными конституентами 1, то их произведение равно 0.