Глава II нормальные формы формул логики высказываний

§ 1. Нормальная форма

Определение: формула логики высказываний имеет нормальную форму, если она: а) не содержит знаков ,  и  и б) знаки отрицания стоят в ней только при переменных.

Например, формула

((p  q)  r)  (((r  s)  (p  s  r))  (s  q))

имеет нормальную форму, а формула

((p  q)  r)  (q  s)

не имеет.

Любую формулу А, не имеющую нормальной формы, можно конечным числом применений правила замены преобразовать в формулу А`, которая будет иметь нормальную форму. Процесс такого преобразования будем называть процессом приведения формулы к нормальной форме.

Для того чтобы данную формулу привести к нормальной форме, необходимо произвести в ней следующие равносильные замены:

1. каждую подформулу вида (А  В) заменить согласно равносильности (17)¹ формулой ((А  В)  (А  В));

2. каждую подформулу вида (А  В) заменить согласно равносильности (16) формулой ((А  В)  (В  А));

3. каждую подформулу вида (А  В) заменить согласно равносильности (13) формулой (А  В);

4. каждую подформулу вида (А  В) заменить согласно равносильности (10) формулой (А  В);

5. каждую подформулу вида (А  В) заменить согласно равносильности (11) формулой (А  В);

6. каждую подформулу вида  А заменить согласно равносильности (1) формулой А.

Формула имеет нормальную форму, если ни один из перечисленных пп. 1 — 6 настоящего предписания к ней не применим.

Пусть, например, дана формула

(p  q)  ((q  r)  s).

Согласно равносильности (17) получаем формулу

((p  q)  (p  q))  ((q  r)  s).

Из нее согласно равносильности (16) получаем формулу

((p  q)  (p  q))(((q  r)  (r  q))  s),

затем согласно равносильности (13) — формулу

((p  q)  (p  q))  (((q  r)  (r  q))  s)

и далее согласно равносильности (10) — формулу

((p  q)  (p  q))  (((q  r)  (r  q))  s),

после чего, дважды применяя правило замены, согласно равносильности (11) — формулу

((p  q)  (p  q))  (((q  r)  (r  q))  s).

Наконец, трижды применяя правило замены, согласно равносильности (1) получаем следующую формулу в нормальной форме:

((p  q)  (p  q))  (((q  r)  (r  q))  s),

которую, пользуясь соглашением о бесскобочной записи кратной дизъюнкции, можно записать

(p  q)  (p  q))  ((q  r)  (r  q))  s.

Упражнения

Привести к нормальной форме формулы:

1) (p  q);

2) (p  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)).

§ 2. Проблема разрешения

Итак, каждая формула логики высказываний принадлежит одному из следующих трех классов: 1) истинных при любых логических значениях своих переменных (тождественно-истинные формулы); 2) ложных при любых логических значениях своих переменных (тождественно-ложные формулы); 3) истинных при одних логических значениях своих переменных и ложных при других значениях (нейтральные формулы).

Формула логики высказываний называется выполнимой, если хотя бы для одного набора логических значений своих переменных она получает значение «истина». Таким образом, тождественно-истинные и нейтральные формулы выполнимые, а тождественно-ложные невыполнимые.

Задача, состоящая в отыскании процедуры, позволяющей для любой формулы выяснить, какому из трех перечисленных выше классов она принадлежит, называется семантической проблемой разрешения для формул логики высказываний. В соответствии с этим процедура, позволяющая конечным числом простых действий решить проблему разрешения, называется разрешающей процедурой. Ясно, что процесс построения по данной формуле отвечающей ей таблицы есть разрешающая процедура семантической проблемы разрешения для формул логики высказываний.

Однако использовать процесс построения таблицы в качестве разрешающей процедуры семантической проблемы разрешения практически удобно лишь в тех случаях, когда в формулу входит небольшое число переменных и она не очень длинная. Следует учитывать, что число строк в таблице быстро растет с увеличением числа входящих в формулу переменных. Например, число строк при трех переменных равно 8, при шести переменных — 64, а при десяти переменных — уже 1024. Стремясь избежать построения громоздких таблиц, ищут другие, более удобные, разрешающие процедуры.

Заметим, что для того чтобы получить разрешающую процедуру, достаточно найти способ, позволяющий отличить тождественно-истинные формулы от всех остальных. В самом деле, если в результате применения такой процедуры к формуле А выясняется, что она тождественно-истинна, то проблема разрешения решена. Если же выясняется, что она не тождественно-истинна, то данную процедуру нужно применить к формуле А. Если в результате ее применения к ~А выяснится, что А тождественно-истинная формула, то значит, формула А тождественно-ложна. Если же ~А так же, как А, не тождественно-истинна, — значит, формула А нейтральная, т. е. при одних значениях переменных она истинна, а при других ложна.

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

Будем говорить, что некоторая пропозициональная переменная входит в формулу, приведенную к нормальной форме, регулярно, если она входит в нее одновременно с отрицанием и без отрицания. Если переменная входит в формулу, приведенную к нормальной форме, только с отрицанием или только без отрицания, то будем говорить, что она входит в формулу нерегулярно.

Разрешающая процедура заключается в следующем:

1) приводим формулу к нормальной форме;

2) в формуле, приведенной к нормальной форме, выделяем переменные, которые входят в нее нерегулярно;

3) вместо всех нерегулярно входящих переменных и отрицаний нерегулярно входящих переменных подставляем на всех местах, где они встречаются в нормальной форме, букву «Л», т. е. подставляем «Л» вместо переменной или вместо отрицания переменной;

4) применяем правило замены по равносильностям (48), (48'), (50) и (50') ко всем подформулам получившейся формулы до тех пор, пока остаются поводы для его применения; в результате длина формулы будет сокращаться и могут появиться новые нерегулярно входящие переменные; с ними поступаем таким же образом, т. е. согласно пп. 3 и 4. Предусмотренные в пп. 2 — 4 преобразования повторяем до тех пор, пока не получим формулу, не содержащую нерегулярно входящих переменных;

5) рассматриваем следующие две формулы, которые получаются из формулы, не содержащей нерегулярно входящих переменных, если:

а) вместо одной из регулярно входящих переменных на всех местах подставить букву «И» и применить правило равносильной замены согласно равносильностям (43), (47)—(50);

б) вместо той же самой переменной на всех местах подставить букву «Л» и применить правило равносильной замены согласно равносильностям (44), (47)—(50).

К формулам а) и б), если это возможно, снова применяем пп. 2 —4 , а затем согласно п. 5 из формул а) и б) получаем соответственно формулы аа), аб) и ба), бб) и т. д. до тех пор, пока не исчерпаем возможности применения пп. 2 —5.

Если в результате применения данной процедуры к произвольной формуле А все заключительные формулы будут «И», то формула А тождественно-истинная, если же хотя бы одна заключительная формула есть «Л», то формула А не тождественно-истинная.

Проиллюстрируем изложенное на следующих двух примерах.

1. Пусть дана формула, уже имеющая нормальную форму,

(p₁  (p₂  p₃  (p₄  (p₅ (p₆  p₁  p₇)))))  (((p₆ ((p₈  p₉  p₅)  (p₇  p₈  p₉)))  p₁) p₂  p₃).

Тождественно-истинная она или нет?

Нерегулярно входящей в этой формуле является только переменная р₄. Подставляем вместо р₄ букву Л и, применив правило замены сначала по равносильности (48'), а затем по равносильности (50), получаем формулу

(p₁  (p₂  p₃))  (((p₆  (( p₈  p₉  p₅)  (p₇  p₈  p₉)))  p₁)  p₂  p₃).

Теперь появилась новая нерегулярно входящая переменная p₆. Подставляем вместо р₄ букву Л и применив правило замены по равносильности (48'), а затем по равносильности (50'), получаем формулу

(p₁  (p₂  p₃))  (p₁  p₂  p₃),

в которой уже нет нерегулярно входящих переменных.

В соответствии с п. 5 подставляем вместо р₁ буквы И и Л и рассматриваем получившиеся формулы:

а) (И  (p₂  p₃))  (~И  p₂  p₃),

из которой согласно равносильностям (47'), (43), (48') и (50) получаем формулу

p₂  p₃

б) (Л  (p₂  p₃))  (~Л  p₂  p₃),

из которой согласно равносильностям (48'), (44), (47') и (50') получаем формулу

p₂  p₃;

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

2. Пусть дана формула

(p (q  r))  ((p  q)  (p  r)).

Является ли она тождественно-истинной? Приведем ее к нормальной форме:

(p  (q  r))  ((p  q)  (p  r));

(p  (q  r))  ((p  q)  p  r);

(p  q  r))  ((p  q)  p  r);

(p  q  r))  ((p  q)  p  r).

Здесь нет нерегулярно входящих переменных, поэтому вместо регулярно входящей переменной р согласно п. 5 подставляем буквы «И» и «Л» и получаем формулы:

а) (И  q  r)  ((И  q)  (И  r);

(q  r)  (q r);

б) (Л  q  r)  ((Л  q)  (Л  r).

Сразу находим, что формула б) равносильна И. Формула же а) порождает согласно п. 5, формулы аа) и аб):

аа) (И  r)  (И  r);

~r  r,

которая при любых подстановках дает И, и

аб) (Л  r)  (Л  r),

которая равносильна И.

Так как все заключительные формулы — И, то исходная формула тождественно-истинная.

Упражнения

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

1. p  (q  (p  q));

2. p (p  q);

3. (p  q)  (р  q);

4. (р  (р  q));

5. (р  q)  ((q  r)  (p  r));

6. ((р (q  q))  (p  r));

7. (p  q)  ((p  r)  (q  r)).

8. (p  q) r)  (p  r);

9. (p  r)  ((q  r)  p));

10. (p  q)  (q  (p  r));

11. (p  r)  (q  (q  r)).