4.4.2. Конъюнктивные нормальные формы

Элементарной дизъюнкцией D_i является многоместная конъюнкция попарно различных литералов, т. е. D_i = . К элементарным дизъюнкциям относятся также одиночные литералы и константа 0 – дизъюнкция, состоящая из пустого множества литералов. Число литераловr элементарной дизъюнкции называется ее рангом. Элементарная дизъюнкция называется полной относительно переменных x₁, x₂, …, x_n, если она содержит символы всех переменных (со знаком отрицания или без него). Ранг таких дизъюнкций равен n.

Конъюнктивная нормальная форма (КНФ) – это выражение вида D_i, т. е. конъюнкция элементарных дизъюнкций. Примером конъюнктивной нормальной формы является выражение (х₂ х₃  х₄)(х₁ х₂). Одна элементарная дизъюнкция также может считаться КНФ.

Согласно принципу двойственности выражение (4.1) можно преобразовать в следующее выражение, которое также справедливо:

f(x₁, x₂, …, x_n) =f(₁, ₂, … , _m, x_m+1, … , x_n)).

Эта формула называется конъюнктивным разложением функции f (x₁, x₂, … , x_n) по переменным x₁, x₂, … , x_m. Справедливость ее может быть доказана так же, как справедливость формулы (4.1). Так же крайними случаями конъюнктивного разложения являются разложение по одной переменной и по всем переменным. Последнее называется совершенной конъюнктивной нормальной формой (СКНФ) и имеет вид

f(x₁, x₂, …, x_n) =f(₁, ₂, … , _n)). (4.2)

СКНФ, представляющую произвольную булеву функцию, так же, как ее СДНФ, легко построить по табличному заданию этой функции. Согласно формуле достаточно выделить наборы (₁, ₂, … , _n), на которых функция принимает значение 0 (если f(₁, ₂, … , _n) = 1, то весь сомножитель (1) обращается в 1), и для каждого из них ввести в СДНФ полную элементарную дизъюнкцию, где любая переменнаяx_i присутствует с отрицанием, если _i = 1, и без отрицания, если _i = 0.

Очевидно, для любой булевой функции f(x₁, x₂, …, x_n), кроме константы 1, существует единственная СКНФ (с точностью до порядка литералов и дизъюнкций). Так же, как СДНФ, эта форма представления булевой функции является канонической. СКНФ для функции, которую задает табл. 4.5, имеет следующий вид:

(х₁  х₂  х₃)(х₁  х₂ х₃)(х₁ х₂ х₃)(х₁ х₂  х₃)(х₁ х₂ х₃).

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