Теорема о разложении функции по переменным

Всякая логическая функция может быть разложена по переменным , где , то есть представлена в виде:

Дизъюнкция в правой части равенства берется по всем наборам параметров . Конъюнкций, соединенных знаком дизъюнкции будет штук.

Разложение функции по всем переменным носит название совершенной дизъюнктивной нормальной формы.

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

Конъюнктивная нормальной формой (КНФ) называется конъюнкция элементарных дизъюнкций.

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