Задача определения истинности формул решается в соответствии с принятыми правилами интерпретации высказываний в логике. Стандартная (главная) интерпретация операций в исчислении высказываний представляется следующей таблицей:
Таблица 4. Таблица истинности логических операций
| x | y | Ø x | xÙy | x Ú y | x ® y |
Здесь цифрой 0 обозначено значение «ложь», цифрой 1 – значение «истина».
Эквивалентность формул означает совпадение их значений истинности для всех возможных наборов входящих в них переменных. Операцию эквивалентности обозначают, обычно, знаком тождества º.
Существуют формулы, имеющие одно и то же значение, при различных значениях входящих в них переменных. К ним относятся тавтология и противоречие.
Тавтология – это формула, истинная при любой интерпретации входящих в нее переменных. Так, формула x Ú Øx всегда истинна. Действительно, значение дизъюнкции есть истина, если хотя бы один ее операнд истинен, а в этой формуле, если x - ложь, то Øx - истина.
Противоречие – это формула, ложная при любой интерпретации входящих в нее переменных. Так, формула xÙØx всегда ложна. Действительно, значение конъюнкции есть ложь, если хотя бы один ее операнд ложен, а в этой формуле, если x - истина, то Øx – ложь.
Если заданы значения переменных, то, используя стандартную интерпретацию, можно определить, истинна или нет данная формула.
Определение истинности формул с помощью таблиц истинности
Пример Л4. Определить, истинна или нет формула Ø(x Ú Ø y) ® xÙy, если а) x=1, y=0; б) x=0, y=1.
Решение. Для решения задачи нужно подставить данные значения x и y в формулу и использовать интерпретацию операций, учитывая их приоритет. Так, для а): Ø(1 Ú Ø0) ® 1Ù0 º Ø 1 ® 0 º 0 ® 0 º 1. Ответ: при x=1, y=0 данная формула истинна. Для б): Ø(0 Ú Ø1) ® 0Ù1 º Ø(0 Ú 0) ®0 º Ø0 ® 0 º 1 ® 0 º 0. Ответ: при x=0, y=1 данная формула ложна. Этот процесс можно представить таблицей:
| x | y | Ø y | x Ú Ø y | Ø(x Ú Ø y) | xÙy | Ø(x Ú Ø y) ® xÙy |
Такими таблицами удобно пользоваться, если формула сложная и требуется определить ее истинность для всех возможных значений переменных.<
Пример Л5. Определить истинность формулы j º Ø(xÙy) ® ØxÚØyÚØz ® xÚyÚz для всех значений переменных x, y, z.
Решение. Решаем задачу с помощью таблицы, разбивая исходную формулу на подформулы:
| x | y | z | xÙy | Ø(xÙy) º j1 | Øx | Øy | Øz | ØxÚØyÚØz º j2 | xÚyÚz º j3 | j1®j2 º j4 | j4 ® j3 º j |
Создав такую таблицу, можно ответить на вопрос: является ли данная формула тавтологией? Ответ – нет, т.к. при x=0, y=0, z=0 ее значение есть 0, а тавтология истинна при любых x, y, z. Является ли эта формула противоречием? Нет, т.к. есть наборы переменных, при которых она истинна. Из таблицы видно, что, например, «усеченная» формула Ø(xÙy) ® ØxÚØyÚØz является тавтологией (все ее значения истинны), а, соответственно, ее отрицание Ø(Ø(xÙy) ® ØxÚØyÚØz) будет противоречием (все значения ложны). <
Упрощение формул
Следующая важная задача в приложениях логики высказываний – упрощение формул. Под упрощением понимается получение более простой (например, более короткой, не содержащей знаков ®, скобок, отрицаний над составными формулами) формулы, эквивалентной данной. Для этого используются эквивалентные преобразования формул, основанные на следующих известных тождествах (правилах):
1) Ø (А Ú В) º ØА Ù ØВ
2) Ø (АÙВ) º ØА Ú ØВ
3) АÙ(В Ú С) º АÙВ Ú АÙС
4) А Ú (ВÙС) º (А Ú В) Ù (А Ú С)
5) А Ú (АÙВ) º А
6) АÙ(А Ú В) º А
7) (АÙВ) Ú ØВ º А Ú ØВ
8) Ø Ø А º А
9) А ® В º Ø А Ú В
10) А ® В º Ø В ® ØА
11) АÙВ º ВÙА
12) А Ú В º В Ú А
13) (АÙВ)ÙС º АÙ(ВÙС)
14) (А Ú В) Ú С º А Ú (В Ú С)
15) (А º В) º (В º А)
16) А® (В ® С) º АÙВ ® С
17) А Ú А º А
18) АÙА º А
19) А Ú В Ú Ø В º В Ú Ø В
20) А Ú В ÙØ В º А
21) АÙ(ВÚØ В) º А
Здесь А, В, С – (под)формулы, в частности, логические переменные. Обычно, при преобразованиях вначале избавляются от импликаций с помощью правила 9, затем от отрицаний над составными формулами (правила 1, 2, 8) и скобок. Если в конечном результате преобразований получена тавтология, например, хÚØх, то исходная формула также является тавтологией, т.к. она эквивалентна полученной. Аналогично, результат xÙØx говорит о противоречивости исходной формулы. Правило 19 говорит о том, что в дизъюнкции подформула-тавтология и будет результатом, т.к. она всегда истинна, а для истинности дизъюнкции достаточно истинности хотя бы одного операнда. Правило 20 говорит о том, что противоречие не влияет на результат дизъюнкции, т.к. оно всегда ложно и результат определяется истинностью или ложностью оставшейся формулы. Соответственно тавтология не влияет на результат конъюнкции (правило 21), т.к. она всегда истинна и окончательный результат зависит только от значения оставшейся формулы.
Пример Л6. Упростить формулу: Ø(ØxÙØy)Ú(x ® y)Ùx.
Решение. Проводим цепочку преобразований (в скобках указывается номер применяемого правила):
Ø(ØxÙØy)Ú(x ® y)Ùx º (9) º Ø(ØxÙØy)Ú(Ø x Ú y)Ùx º (2) º Ø Øx Ú Ø Øy Ú (Ø x Ú y)Ùx º (8, 11, 3) º x Ú y Ú Ø xÙx Ú yÙx º (20) º x Ú y Ú yÙx º (5) º x Ú y. <
Пример Л7. Определить, является ли формула Ø(ØxÙØy)Ú(x ® y)Ùx противоречием?
Решение. Проделав упрощения, приведенные в примере 1, получим, что исходная формула эквивалентна формуле x Ú y, которая противоречием не является. Ответ – нет.
Пример Л8. Определить, является формула xÚ Ø((y Ú z) Ùx) тавтологией?
Решение. Упростим формулу: x Ú Ø((y Ú z) Ùx) º (2) º x Ú Ø(y Ú z) Ú Ø x º (12) º x Ú Øx Ú Ø(y Ú z) º (19) º x Ú Ø x. Ответ – да. <