Многочлены Жегалкина являются еще одним интересным подклассом формул, позволяющим однозначно представлять булевы функции.
Многочленами Жегалкина назваются формулы над множеством функций FJ={ 0, 1, *, +}
Таким образом, каждый многочлен Жегалкина (возможно, после раскрытия скобок и "приведения" подобных членов) представляет сумму (по модулю 2) положительных (монотонных) элементарных конъюнкций (т.е. элементарных конъюнкций без отрицаний)
Для любой булевой функции существует задающий ее многочлен Жегалкина. Он единственен с точностью до перестановок слагаемых и порядка переменных в конъюнкциях.