Полином Жегалкина

---

Полином Жегалкина — многочлен над полем ${\displaystyle \mathbb {Z} _{2}}$, то есть полином с коэффициентами вида 0 и 1, где в качестве произведения берётся конъюнкция, а в качестве сложения — исключающее или. Полином был предложен в 1927 году Иваном Жегалкиным в качестве удобного средства для представления функций булевой логики. В зарубежной литературе представление в виде полинома Жегалкина обычно называется алгебраической нормальной формой (АНФ).

Теорема Жегалкина — утверждение о существовании и единственности представления всякой булевой функции в виде полинома Жегалкина^[1].

Полином Жегалкина представляет собой сумму по модулю два попарно различных произведений неинвертированных переменных, где ни в одном произведении ни одна переменная не встречается больше одного раза, а также (если необходимо) константы 1^[1]. Формально полином Жегалкина можно представить в виде

Этому требованию отвечает, в частности, система функций ${\displaystyle {\bigl \langle }\wedge ,\oplus ,1{\bigr \rangle }}$ (конъюнкция, сложение по модулю два, константа 1). На её основе и строятся полиномы Жегалкина.

---