Совершенная конъюнктивная нормальная форма

Для одной и той же формулы можно составить множество равносильных ей КНФ. Но среди них существует единственная КНФ со свойствами совершенства.

Перечислим свойства совершенства для КНФ:

1. Каждый логический множитель формулы содержит все переменные, входящие в функцию.

2. Все логические множители различны.

3. Ни один множитель не содержит одновременно переменную и ее отрицание.

4. Ни один множитель не содержит одну и ту же переменную дважды.

КНФ, для которой выполняются свойства совершенства называется совершенной КНФ (СКНФ).

Любая не тождественно истинная формула имеет единственную СКНФ.

Один из способов получения СКНФ состоит в использовании таблицы истинности для :

1. Составляют СДНФ.

2. Для получения СКНФА строят отрицание СДНФ, т.е.

Или из наборов переменных, при которых А ложна, составляют элементарные дизъюнкции, в которых переменная, вошедшая со значением истина вводится с отрицанием, а со значением ложь – без отрицания. Из полученных элементарных дизъюнкций составляют конъюнкцию.

Другой способ основан на равносильных преобразованиях

Приведем соответствующий алгоритм:

1. Путем равносильных преобразований получить какую – либо КНФ.

2. Если какая-либо элементарная дизъюнкция В не содержит переменную х_i, то вводят ее, используя равносильность . И используют свойство дистрибутивности.

3. Если в КНФ входят две одинаковые дизъюнкции В, то лишнюю отбрасывают, используя свойство идемпотентности В B º B.

4. Если какая-либо дизъюнкция содержит x_i вместе с отрицанием, то В º 1. И В исключают из КНФ.

5. Если какая-либо дизъюнкция содержит переменную x_i дважды, то одну из них отбрасывают, используя свойство x_iv x_i º x_i.

Примеры.

1. Составить СКНФ для формулы по таблице истинности и путем равносильных преобразований.

Составим таблицу истинности, которая содержит 4 строки, для

Тогда

Такую же формулу мы получили бы, строя СКНФА на наборах, при которых А ложна.

Преобразуем формулу:

2.Аналогичное задание для формулы

Таблица истинности имеет вид:

Составим СКНФА на наборах, при которых А=0:

Преобразуем формулу:

3. Путем равносильных преобразований получить СКНФА.

Задачи для самостоятельного решения.

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

2. Найдите СДНФ для всякой тождественно ис­тинной формулы, содержащей: 1) одно переменное, 2) два переменных, 3) три переменных.

3.Найдите СКНФ для всякой тождественно лож­ной формулы, содержащей: 1) одно переменное, 2) два переменных, 3) три переменных.

4. Докажите равносильность формул и сравнением их совершенных нормальных форм (конъюнктивных или дизъюнктивных).

5. Найдите более простой вид формул, имеющих следующие совершенные нормальные формы:

Контрольные вопросы

1. Перечислить свойства совершенства для ДНФ.

2. Перечислить свойства совершенства для КНФ.

3. Сколько для одной формулы можно составить СДНФ и СКНФ?

4. Как по таблице истинности составить СДНФ?

5. Связь между СДНФА и СКНФА.

6. Как путем равносильных преобразований составить СДНФ и СКНФ формулы?