Алгебра Жегалкина

Это алгебра, в которой определены две логические операции: сложение по модулю «два» и конъюнкция.

Справедливы следующие соотношения:

Чтобы записать полином Жегалкина для произвольной формулы алгебры логики нужно все входящие в нее операции заменить на сложение по модулю «два» и конъюнкцию, используя при этом равносильности:

Совершенная дизъюнктивная нормальная форма (СДНФ)

Элементарной конъюнкцией n-переменных называется конъюнкция этих переменных или их отрицаний.

Дизъюнктивной нормальной формой (ДНФ) для формулы А называется равносильная ей формула, представляющая собой дизъюнкцию элементарных конъюнкций.

Для любой формулы алгебры логики можно получить ДНФ, при чем не единственную.