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

Возникает вопрос, можно ли установить какую-нибудь закономерную связь между структурой формулы и ее семантикой, между ее логической формой и логическим содержанием? Оказывается, что такая связь существует и можно указать простой метод, позволяющий по виду формулы, приведенной к некоторой стандартной форме, судить о том, тождественно-истинная она или нет.

Условимся называть элементарной дизъюнкцией формулу, которая имеет вид

A ₁ Ú A ₂ Ú...Ú A_n,

где n ³ 1, a A_i, (i £ n) есть либо переменная, либо отрицание переменной. Например, формула

р Ú q Ú ~ r Ú p Ú ~ q Ú r —

элементарная дизъюнкция, формула же

(p Ù q) Ú r Ú р

элементарной дизъюнкцией не является, так как ее первый дизъюнктивный член не есть ни переменная, ни отрицание переменной.

Теорема. Элементарная дизъюнкция тождественно-истинна, тогда и только тогда, когда в ней содержится хотя бы одна пара дизъюнктивных членов, из которых один есть некоторая переменная, а другой — ее отрицание.

Доказательство. В самом деле, элементарная дизъюнкция, содержащая такую пару, либо уже имеет вид

Е Ú ~ E Ú D,

где Е — переменная, а D — элементарная дизъюнкция (которой может и не быть), либо ей можно придать этот вид в результате применения правила замены по равносильности (4). Так как подформула Е Ú ~ E тождественно-истинная, то согласно (49') вся элементарная дизъюнкция

Е Ú ~ E Ú D

тождественно-истинная формула, независимо от того, истинна или ложна подформула D.

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

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

В ₁ Ù В ₂Ù...Ù В_m,

где В ₁, В _2,..., В_m — элементарные дизъюнкции и m ³ 1. Например, формула

p Ù (~ q Ú r) Ù ~ s Ù (~ p Ú q)

имеет конъюнктивную нормальную форму.

Любая формула логики высказываний в результате ряда равносильных замен может быть приведена к конъюнктивной нормальной форме. Формулу, равносильную данной и имещую конъюнктивную нормальную форму, будем называть конъюнктивной нормальной формой данной формулы.

Для того чтобы формулу привести к КНФ, необходимо вначале с помощью известной процедуры привести ее к нормальной форме. Затем каждую подформулу вида (A Ú(B Ù C)) согласно равносильности (6) и каждую подформулу вида ((B Ú C) Ú A) согласно равносильности (6') заменить фоpмyлoй ((A Ú B) Ù (A Ú C)).

Формула имеет КНФ, если она имеет нормальную форму и в ней нет подформул вида

(A Ú(B Ù C)) и ((B Ú C) Ú A).

Рассмотрим процесс приведения формулы к КНФ на следующем примере. Пусть дана формула

(~ p Ù q) ® (p «~ r).

Приведем ее вначале к нормальной форме:

~(~ p Ù q) Ú (p «~ r);

~(~ p Ù q) Ú ((~ p Ú ~ r) Ù (~~ r Ú p));

(~~ p Ú ~ q) Ú ((~ p Ú ~ r) Ù (~~ r Ú p)).

(p Ú ~ q) Ú ((~ p Ú ~ r) Ù (r Ú p)).

Затем с помощью равносильности (6) получаем формулу

(p Ú ~ q Ú ~ p Ú ~ r) Ù (p Ú ~ q Ú r Ú p),

которая имеет КНФ.

Формула не единственным образом представима в КНФ. Например, формула

p «q

имеет следующие представления в КНФ:

(~ р Ú q) Ù (~ q Ú р);

(~ р Ú q) Ù (~ q Ú р Ú r) Ù (~ q Ú р Ú ~ r);

(p Ú ~ q) Ù (q Ú ~ q) Ù (q Ú ~ p).

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

Так, если знак отрицания стоит перед конъюнкцией [дизъюнкцией], содержащей более двух конъюнктов [дизъюнктов], как, например, в формулах ~(А Ù В Ù С) [~(А Ú В Ú С)], ~(А Ù В Ù С Ù D) [~(А Ú В Ú С Ú D)] и т.д., то мы не будем восстанавливать скобки и дважды, трижды и т. д. применять правило замены по равносильностям (10) [(11)], а сразу будем писать формулы (~ А Ú ~ В Ú ~ С) [(~ А Ù ~ В Ù ~ С)], (~ А Ú ~ В Ú ~ С Ú ~ D) [(~ А Ù ~ В Ù ~ С Ù ~ D)] и т. д., т. е. пользоваться обобщенными законами де Моргана:

~(A ₁ Ù A ₂ Ù... Ù А_n) равносильно ~ A ₁ Ú ~ A ₂ Ú...Ú ~ А_n;

~(A ₁ Ú A ₂ Ú...Ú А_n) равносильно ~ A ₁ Ù ~ A ₂ Ù...Ù ~ А_n.

Далее, если в формуле встречаются подформулы вида (А Ù В) Ú (C Ù D), (А Ù В) Ú (С Ù D Ù Е) и т. п., то вместо того, чтобы дважды, трижды и т. д. применять правило замены по равносильности (6) и (6') и писать, например, в первом случае сначала формулу

((А Ù В) Ú С) Ù ((А Ù В) Ú D),

а затем

(С Ú А) Ù (С Ú В) Ù (D Ú А) Ù (D Ú В),

будем сразу писать последнюю формулу, т. е. пользоваться обобщенным законом дистрибутивности дизъюнкции относительно конъюнкции:

(A ₁ Ù... Ù А_m) Ú (В ₁Ù...Ù В_n) равносильно

(В ₁Ú A ₁) Ù...Ù (В ₁Ú А_m)Ù...Ù (В_n Ú A ₁) Ù...Ù (В_n Ú А_m).

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

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

Таким образом, по виду некоторой формулы в КНФ можно судить о том, тождественно-истинна она или нет. Например, пусть дана формула

(р ® ~ q) «(q ® ~ р).

Приводим ее к КНФ:

(~(р ® ~ q) Ú (q ® ~ р)) Ù (~(q ® ~ р) Ú (р ® ~ q));

(~(~ р Ú ~ q) Ú (~ q Ú ~ р)) Ù (~(~ q Ú ~р) Ú(~ p Ú ~ q));

((р Ù q) Ú (~ q Ú ~ р)) Ù ((q Ù р) Ú(~ p Ú ~ q));

(~ q Ú ~ p Ú p) Ù (~ q Ú ~ p Ú q) Ù (~ p Ú ~ q Ú q) Ù (~ p Ú ~ q Ú p).

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

Каждая не тождественно-истинная формула имеет КНФ, которая называется совершенной.

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

а) в ней нет двух одинаковых конъюнктивных членов (одинаковыми считаются такие конъюнктивные члены, которые получаются один из другого в результате замены по равносильности (4));

б) ни в одном конъюнктивном члене нет двух одинаковых дизъюнктов;

в) ни в одном конъюнктивном члене нет таких двух дизъюнктов, из которых один есть переменная, а другой — отрицание этой переменной;

г) в каждом конъюнктивном члене содержатся все переменные данной формулы.

Для того чтобы привести формулу к СКНФ, необходимо:

1) известным уже способом привести ее к КНФ;

2) на основании равносильностей (2), (4) и (8) устранить из КНФ повторяющиеся конъюнкты, т. е. из всех имеющихся одинаковых конъюнктивных членов оставить один и вычеркнуть остальные;

3) на основании равносильностей (4) и (9) устранить все повторения в конъюнктивных членах КНФ, т. е. из всех имеющихся одинаковых дизъюнктов оставить один и вычеркнуть остальные;

4) на основании равносильностей (2), (4) и (47) устранить из КНФ те конъюнктивные члены, которые являются тождественно-истинными элементарными дизъюнкциями;

5) ко всем тем конъюнктивным членам, в которых отсутствует какая-нибудь из содержащихся в данной формуле переменных Е, на основании равносильности (50) приписать знак дизъюнкции и вслед за ним тождественно-ложную конъюнкцию (Е Ù ~ Е), а затем применить правило замены по равносильности (6). Эту процедуру повторять до тех пор, пока не окажется, что в каждый конъюнктивный член входят все переменные, содержащиеся в данной формуле;

6) если в получившейся КНФ снова появились одинаковые конъюнктивные члены, то надо устранить повторения.

Пусть, например, к СКНФ нужно привести формулу

((p ® q) Ù ~(~ r Ù ~ p) Ù (~ q ® r))Ú р.

Вначале приведем ее к КНФ:

((~ p Ú q) Ù (r Ú p) Ù (q Ú r)) Ú p;

((p Ú ~ p Ú q) Ù (p Ú r Ú p) Ù (p Ú q Ú r)).

Затем вычеркиваем первый конъюнктивный член и устраняем повторения во втором. Получаем формулу

(p Ú r) Ù (p Ú q Ú r).

Так как в первом конъюнктивном члене отсутствует переменная q, то присоединяем к нему знаком дизъюнкции формулу (q Ù ~ q):

(р Ú r Ú (q Ù ~ q)) Ù (р Ú q Ú r).

Воспользовавшись законом дистрибутивности дизъюнкции относительно конъюнкции, получаем формулу

(р Ú r Ú q) Ù (р Ú r Ú ~ q) Ù (р Ú q Ú r).

Устраняем один из одинаковых конъюнктивных членов и получаем формулу в СКНФ:

(р Ú r Ú q) Ù (р Ú r Ú ~ q).

Упражнения

I. Привести к КНФ следующие формулы и проверить, являются они тождественно-истинными или нет:

1) р ® ((р ® q) ® q);

2) ((р ® q) Ù (r ® s)) ® ((р Ù r) ® (q Ù s));

3) (р ® q) ® ((р Ù r) ® (q Ù r));

4) (р ® (q Ù r)) «((р ® q) Ù (р ® r));

5) ((р ® q) Ú (р ® r)) ® (р ® (q Ú r));

6) (p «q) ® ((p «r) ® (q «r)).

7) ((p Ú ~ q) ® r) ® (p Ù r);

8) (p Ú r) ® ((q Ù ~ r) ® p);

9) (p ® q) ® (~ q ® (p Ú r));

10) (p ® r) ® ~(q ® (q ® r)).

II. Привести к СКНФ следующие формулы:

1) (р ® q) Ú ~(~ q Ú r);

2) ((~(р ® q) ® q) Ú ~ q) Ú (р Ù r);

3) (p «q) ® ((p «r) ® (q «r)).

4) ((p Ú ~ q) ® r) ® (p Ù r);

5) ~ (p Ú r) ® ~ ((q Ù ~ r) ® ~ p);

6) (p ® q) ®~ ((q ® p) Ú r);

7) ~ (p ® r) ® ~(q Ú (q ® r)).

Не нашли, что искали? Воспользуйтесь поиском: