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

Совершенная конъюнктивная нормальная форма (СКНФ) некоторой формулы представляет собой еще одну стандартную форму записи произвольных выражений алгебры логики.

Будем называть элементарной дизъюнкцией дизъюнкцию отдельных переменных, некоторые из которых могут иметь знаки отрицания. Например, формулы X₁X₂X₃ или - элементарные дизъюнкции. ФормулыилиX₁(X₂&X₃) не являются элементарными дизъюнкциями.

Конъюнктивная нормальная форма (КНФ) некоторой формулы – это эквивалентная данной формуле дизъюнкция элементарных конъюнкций.

Совершенная конъюнктивная нормальная форма (СКНФ) некоторой формулы – это ее КНФ, где в каждой элементарной дизъюнкции содержатся все переменные данной формулы.

Процесс построения СКНФ во многом аналогичен построению СДНФ. Основные этапы построения СКНФ следующие:

1) выразить заданную формулу, используя только операции дизъюнкции, конъюнкции и отрицания (как показано в подразделе 5.4);

2) используя законы де Моргана, свести все операции отрицания к отдельным переменным;

3) используя основные равносильности алгебры логики (в основном - закон дистрибутивности), получить КНФ;

4) используя операцию развертывания (будет рассмотрена ниже), получить СКНФ.

Пример 5.5 – Построить СКНФ для следующей формулы:

(X1  X3) → ((X1 & X2) ↓ (X1 & ))

Решим задачу в порядке, указанном выше.

Первые два этапа решения задачи уже выполнены в примере 5.4. Напомним, что формула, выраженная только через операции дизъюнкции, конъюнкции и отрицания, со знаками отрицания, сведенными к отдельным переменным, имеет следующий вид:

Получим для нее КНФ, а затем – СКНФ.

Получение КНФ. Воспользуемся несколько раз законом дистрибутивности или, проще говоря, раскроем скобки в формуле таким образом, чтобы получить конъюнкцию элементарных дизъюнкций:

Учитывая, что AA = A, перепишем полученную формулу:

.

Эта формула представляет собой КНФ, т.е. конъюнкцию элементарных дизъюнкций. В данном случае имеются четыре элементарные дизъюнкции: ,,,. Полученная формула – КНФ, но не СКНФ, так как не во всех элементарных дизъюнкциях содержатся все три переменные. В данном случае в первой и третьей элементарных конъюнкциях не хватает переменнойX_5.

Получение СКНФ. Для этого применяется операция развертывания. Она также во многом аналогична операции развертывания, рассмотренной при построении СДНФ. Пусть в некоторой элементарной дизъюнкции (обозначим ее как A) не хватает некоторой переменной B. Элементарная дизъюнкция A заменяется на A  0 (так как A  0 = A). Затем, так как , записываем формулуA  0 как . Далее применяем свойство дистрибутивности:. Таким образом, исходная элементарная дизъюнкцияA заменяется на две элементарные дизъюнкции, в одной из которых содержится недостающая переменная B, а в другой – ее отрицание. Эта операция выполняется со всеми элементарными дизъюнкциями, пока все они не будут содержать все переменные, имеющиеся в формуле, т.е. пока не будет получена СКНФ.

Применим операцию развертывания к рассматриваемому примеру. Выполним развертывание первой элементарной дизъюнкции, где не хватает переменной X₃:

Аналогично выполним развертывание третьей элементарной конъюнкции:

Таким образом, все операции развертывания выполнены. Вместо КНФ можно записать следующую формулу:

Учитывая, что A & A = A, можно переписать эту формулу без повторяющихся элементарных дизъюнкций:

Эта формула – СКНФ для выражения (X₁X₃) → ((X₁ & X₂)↓(X₁ & )).

Примечание – Как и при построении СДНФ, чтобы убедиться, что СКНФ построена правильно, следует составить и сравнить таблицы истинности для исходной формулы и для СДКФ.

Элементарные дизъюнкции, составляющие СКНФ, называются конституентами нуля. Каждая из них принимает значение 0 (ложь) только при одном наборе переменных. Например, =0 только приX₁=1, X₂=1, X₃=0 (так как только при этих значениях переменных = = 000=0). Таким образом, рассматриваемая в данном примере формула принимает значение, равное 0, при четырех наборах значений переменных. Эти наборы следующие: X₁=1, X₂=1, X₃=0; X₁=1, X₂=1, X₃=1; X₁=1, X₂=0, X₃=0; X₁=1, X₂=0, X₃=1. При остальных наборах значений переменных формула принимает значение 1.

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