2015-03-08
655
А называется элементарной дизъюнкцией, если она состоит из переменных и их отрицаний, связанных операцией дизъюнкции. Говорят, что А находится в КНФ, если она представляет собой конъюнкцию, возможно одночленную, элементарных дизъюнкций. КНФ: A = x 1 & (
Ú x 2) & (x 1 Ú).
Теорема о приведении к КНФ. " A $ B º A, находящаяся в КНФ. B называется КНФ А.
Доказательство: Аналогично теореме 1. Применяют обобщенные законы Де Моргана, чтобы привести операции отрицания к переменным. Применяют формулы дистрибутивности дизъюнкции относительно конъюнкции. A 3 º A и находится в КНФ.
Найдем КНФ для функций:
| х1 | х2 | х3 | f1(х1, х2, х3) | f2(х1, х2, х3) |
f1(х1, х2, х3)= (х1 Ú х2 Ú 
3 ) 
(х1 ÚÚ x 3 ) ( 1Ú х2 Ú x 3 ) ( 1ÚÚ 3 )
f2(х1, х2, х3)= (х1 Ú х2 Ú x 3) (х1 ÚÚ x 3 ) ( 1Ú х2 Ú x 3 ) ( 1ÚÚ x 3)
