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

(КНФ и СКНФ)

Определение 1. Элементарной дизъюнкцией п пере­менных называется дизъюнкция переменных или их от­рицаний.

Элементарная дизъюнкция п переменных может быть записана в виде:

,

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

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

Например, для формулы имеем:

,то есть КНФ А .

Но так как x , , , , то KHФ

А так как , то КНФ .

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

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

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

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

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

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

Один из способов получения СКНФ состоит в исполь­зовании таблицы истинности для формулы А.

Действительно, получив с помощью таблицы истин­ности СДНФ А, мы получим СКНФ А, взяв отрицание , то есть СКНФ .

Другой способ получения СКНФ, использующий рав­носильные преобразования, состоит в следующем:

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

2. Если в полученной КНФ А входящая в нее эле­ментарная дизъюнкция В не содержит переменную x_i, то, используя равносильность , элементар­ную дизъюнкцию В заменяют на две элементарные дизъ­юнкции и каждая из которых содержит переменную x_i.

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

4. Если некоторая элементарная дизъюнкция, вхо­дящая в КНФ А, содержит переменную х_i дважды, то лишнюю можно отбросить, пользуясь равносильностью .

5. Если некоторая элементарная дизъюнкция, вхо­дящая в КНФ А, содержит переменную х_i и ее отрица­ние, то и, следовательно, вся элементарная дизъюнкция имеет значение 1, а поэтому ее можно от­бросить, как единичный член конъюнкции.

Ясно, что после описанной процедуры будет получе­на СКНФ А.

Например, для формулы КНФ .

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

Элементарная дизъюнкция содержит пере­менную х дважды, но , и поэтому КНФ ; причем ни одна из элементарных дизъ­юнкций не содержит переменную и ее отрицание. Зна­чит, теперь выполнены все условия СКНФ А, и, следо­вательно, СКНФ .

§ 12. Проблема разрешимости

Все формулы алгебры логики делятся на три класса:

1) тождественно истинные,

2) тождественно ложные и

3) выполнимые.

Определения тождественно истинной и тождествен­но ложной формул даны выше.

Формулу А называют выполнимой, если она прини­мает значение «истина» хотя бы на одном наборе значе­ний входящих в нее переменных и не является тожде­ственно истинной.

В связи с этим возникает задача: к какому классу относится данная формула?

Эта задача носит название проблемы разрешимости.

Очевидно, проблема разрешимости алгебры логики разрешима.

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

Однако практическое использование таблицы истин­ности для формулы А(х₁,х₂,...,х_п) при больших п зат­руднительно.

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

Предположим, что мы имеем критерий тождествен­ной истинности для формул алгебры логики. Рассмот­рим механизм его применения.

Применим критерий тождественной истинности к формуле А. Если окажется, что формула А - тождественно истинная, то задача решена. Если же окажется, что фор­мула А не тождественно истинная, то применим крите­рий тождественной истинности к формуле . Если ока­жется, что формула А - тождественно истинная, то ясно, что формула - тождественно ложная, и задача решена.

Если же формула не тождественно истинная, то оста­ется единственно возможный результат: формула А вы­полнима.

Установим теперь критерий тождественной истин­ности произвольной формулы алгебры логики. С этой целью предварительно сформулируем и докажем кри­терий тождественной истинности элементарной дизъ­юнкции.

Теорема 1. Для того, чтобы элементарная дизъюнк­ция была тождественно истинной, необходимо и доста­точно, чтобы в ней содержалась переменная и ее отри­цание.

Доказательство. Необходимость. Пусть элементарная дизъюнкция тождественно истинна, но в нее одновремен­но не входит некоторая переменная и ее отрицание. При­дадим каждой переменной, входящей в элементарную дизъюнкцию без знака отрицания, значение ложь, а каж­дой переменной, входящей в элементарную дизъюнкцию под знаком отрицания - значение «истина». Тогда, оче­видно, вся элементарная дизъюнкция примет значение ложь, что противоречит условию.

Достаточность. Пусть теперь элементарная дизъюн­кция содержит переменную и ее отрицание. Так как , то и вся элементарная дизъюнкция будет тож­дественно истинной.

Критерий тождественной истинности элементарной дизъюнкции позволяет сформулировать и доказать критерии тождественной истинности произвольной фор­мулы алгебры логики.

Теорема 2. Для того, чтобы формула алгебры логи­ки А была тождественно истинна, необходимо и дос­таточно, чтобы любая элементарная дизъюнкция, вхо­дящая в КНФ А, содержала переменную и ее отрица­ние.

Доказательство. Необходимость. Пусть А - тожде­ственно истинна. Тогда и КНФ А - тождественно истин­на. Но КНФ А А₁&А₂&...&А_п, где А, - элементарные дизъюнкции (i = 1,2,..., n). Так как КНФ А 1, то А_i 1 (i = 1,2,..., n). Но тогда по теореме 1 каждая элементар­ная дизъюнкция A_i содержит переменную и ее отрица­ние.

Достаточность. Пусть любая элементарная дизъ­юнкция A_i, входящая в КНФ А, содержит переменную и ее отрицание. Тогда по теореме 1 (i = 1,2..... n). При этом и КНФ .

Например, выясним, является ли формула тождественно истинной.

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

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

Теорема 3. Для того, чтобы элементарная конъюн­кция была тождественно ложной, необходимо и доста­точно, чтобы в ней содержалась переменная и ее отри­цание.

Теорема 4. Для того, чтобы формула алгебры логики А была тождественно ложной, необходимо и достаточ­но, чтобы любая конъюнкция, входящая в ДНФ А, содер­жала переменную и ее отрицание.