Конъюнктивная нормальная форма

А называется элементарной дизъюнкцией, если она состоит из переменных и их отрицаний, связанных операцией дизъюнкции. Говорят, что А находится в КНФ, если она представляет собой конъюнкцию, возможно одночленную, элементарных дизъюнкций. КНФ: A = x ₁ & ( Ú x ₂) & (x ₁ Ú).

Теорема о приведении к КНФ. " A $ B º A, находящаяся в КНФ. B называется КНФ А.

Доказательство: Аналогично теореме 1. Применяют обобщенные законы Де Моргана, чтобы привести операции отрицания к переменным. Применяют формулы дистрибутивности дизъюнкции относительно конъюнкции. A ₃ º A и находится в КНФ.

Найдем КНФ для функций:

f₁(х₁, х₂, х₃)= (х₁ Ú х₂ Ú ₃ ) (х₁ ÚÚ x ₃ ) ( ₁Ú х₂ Ú x ₃ ) ( ₁ÚÚ ₃ )

f₂(х₁, х₂, х₃)= (х₁ Ú х₂ Ú x ₃) (х₁ ÚÚ x ₃ ) ( ₁Ú х₂ Ú x ₃ ) ( ₁ÚÚ x ₃)