Дизъюнктивные и конъюнктивные нормальные формы связок

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

Для любой формулы алгебры логики путем равно­сильных преобразований можно получить ее ДНФ, при­чем не единственную. Например, для формулы А = х Ù (х ® y) имеем:

А = х Ù (Ø х Ú y) = (х Ù Ø х) Ú (х Ù y) = х Ù y, то есть

ДНФ А = (х Ù Ø х) Ú (х Ù y) и

ДНФ А = х Ù y.

Среди многочисленных ДНФ А существует единствен­ная ДНФ А, для которой выполняются перечисленные выше четыре свойства совершенства. Такая ДНФ А называется совершенной дизъюнктив­ной нормальной формой формулы А (СДНФ А).

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

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

Например, для формулы А = Ø (х Ú у) º х Ù у имеем:

А = (Ø (х Ú у) ® х Ù у) Ù (х Ù у ® Ø (х Ú у)) =

= (х Ú у Ú х Ù у) Ù (Ø (х Ù у) Ú Ø (х Ú у)) =

= (х Ú х Ú у) Ù (х Ú у Ú у) Ù (Ø х Ú Ø у Ú Ø х) Ù (Ø х Ú Ø у Ú Ø у), то есть

КНФ А = (х Ú х Ú у) Ù (х Ú у Ú у) Ù (Ø х Ú Ø у Ú Ø х) Ù (Ø х Ú Ø у Ú Ø у).

Но так как х Ú х = х, у Ú у = у, Ø х Ú Ø х = Ø х, Ø у Ú Ø у = Ø у, то

КНФ A = (х Ú у) Ù (х Ú у) Ù (Ø х Ú Ø у) Ù (Ø х Ú Ø у).

А так как (х Ú у) Ù (х Ú у) = х Ú у, (Ø х Ú Ø у) Ù (Ø х Ú Ø у) = (Ø х Ú Ø у), то

КНФ A = (х Ú у) Ù (Ø х Ú Ø у).

КНФ А называется совершенной конъюнктивной нормальной формой формулы А (СКНФ А), если для нее выполнены условия:

- Все элементарные дизъюнкции, входящие в КНФ А, различны.

- Все элементарные дизъюнкции, входящие в КНФ А, содержат все переменные.

- Каждая элементарная дизъюнкция, входящая в КНФ А, не содержит двух одинаковых переменных.

- Каждая элементарная дизъюнкция, входящая в КНФ А, не содержит переменную и ее отрицание.

- Можно доказать, что каждая не тождественно истин­ная формула имеет единственную СКНФ.