Элементы математической логики. Исчисление высказываний
3. РАВНОСИЛЬНОСТЬ ФОРМУЛ ИСЧИСЛЕНИЯ ВЫСКАЗЫВАНИЙ. КОНЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА
Формулы ц и ш называются равносильными, если формула ц ? ш тождественно истина. Например, формула (p p) q равносильна q, потому что формула (p p) q ? q тождественно истина (проверку с помощью таблиц истинности предоставляем читателю). Формулы p p и qq также равносильны, потому что тождественно истинна формулы p p ? qq.
Равносильность формул может быть использована для упрощения формул, т.е. для замены какой-то формулы другой формулой, ей равносильной, (эквивалентной), но содержащей либо меньшее число связок, либо меньшее число переменных, либо другие переменные, либо и то, и другое, и третье вместе взятой.
Из определения равносильности формул следует, что тождества (3) - (9) дают нам правила преобразования исходной формулы в новую, ей равносильную к этим правилам добавим и другие правила. Так, любую формулу можно заменить эквивалентной (равносильной) формулой, в которой не содержится знаки «>», «?» и в которой отрицание опущено лишь на элементарные высказывания. С помощью таблиц истинности можно убедиться в эквивалентности следующих формул:
(р ? q) ? (р > q) (q>р) (10)
р > q ?p q (11)
(р ? q) ? (p q) (qр) (12)
(р ? q) ? (p q) (рq) (13)
_____
(р > q) ? р q (14)
р 1 ? р (15)
р 0 ? 0 (16)
р 0 ? р (17)
р 1 ? 1 (18)
р q ?р q (19)
р q ?рq (20)
Итак, подобно тому, как в алгебре мы имеем возможность преобразовывать, одно выражение в другое, с какой-то точки зрения более простое (скажем, приводить алгебраическое выражение к удобному для логарифмирования виду, заменять таблицу, задающую определитель, числом и т.д.), мы можем преобразовать составные высказывания. Важное значение в алгебре высказываний имеет преобразование любого составного высказывания к конъюнктивной нормальной форме. Эта нормальная форма состоит из конъюнкции дизъюнкций, где каждый дизъюнктивный член является либо элементарным высказыванием, либо его отрицанием.
На основании установленных эквивалентностей вводим следующие правила:
а1) Со знаками и можно оперировать как в алгебре, пользуясь ассоциативным, коммутативным и дистрибутивным законами;
а2) р можно заменить р;
а3) р q можно заменить выражениемр q, а р q - выражениемрq ;
а4) р > q можно заменить выражением p q, а р ? q - выражением (p q) (qр).
Например, привести к конъюнктивной нормальной форме формулу:
((р q) q ) (rq).
Последовательным применением правила а3) получаем :
((р q) q ) (rq) ?((р q) q ) (rq) ?((р q) q ) (rq) ?
? ((рq) q ) (rq).
Применяя к последней формуле закон дистрибутивности, получаем формулу:
(р q )( qq) (rq).
Наконец, применяя правило а2) получаем конъюнктивную нормальную форму:
(р q )( qq) (rq).
Очевидно, что эта форма определяется не однозначно. Так, используя то, что qq ? 1 и (15), получаем другую конъюнктивную нормальную форму первоначальной формулы: (pq) rq)
Запишем обобщения законов поглощения (7):
р( р q1 q2 … qп ) ? р (21)
р ( р q1 q2 … qп ) ? р (211)
р( р q1 ) ( р q2 ) … (р qп ) ? р (22)
р ( р q1 ) (р q2 ) … (р qп ) ? р (221)
Из них, а также (9), (3), (15)-(18) получаем новые эквивалентности, а значит, правила преобразования, которые позволяют сокращать число переменных, входящих в формулу:
р ( qq) ? р (23)
р ( qq) ? р (24)
р ( qq) ? 1 (25)
р ( qq) ? 0 (26)
Используя, справа налево дистрибутивный закон (6), получаем два новых соотношения:
(р q ) (р r) ? р (q r) (27)
(р q ) (р r) ? р (q r) (28)
Например, упростить выражение:
(р q r) (р qr ).
Применяя (28), учитывая, что rr ? 0 и (17) получаем:
(р q r) (р qr ) ? (р q) (rr ) ? р q.
Иногда оказывается полезным для упрощения формулы повторить в ней какие-то выражения, используя, справа налево законы поглощения (21)-(22).
Например, упростить выражение
(р q ) (р q) (рq).
Повторим р q и, используя (6), (2), (17), (4) получаем:
(р q ) (р q) (р q) (рq) ? (q(рр)) (р (q q)) ? (q0) (р 0) ? qр ? р q.
Иногда для каких-то целей необходимо вводить в формулу новые переменные (буквы). Это делается с учетом тождеств (24) и (25) и законов дистрибутивности (6). Так, в выражение р q можно ввести букву r. В самом деле, используя (3), а также (6), получаем:
р q?(р q) (r r ) ? (р q r) (р qr )