Теорема доказана.
Таблица 1.3
Таблица 1.2
Статья
http://mathhelpplanet.com/static.php?p=ravnosilnyye-preobrazovaniya-formul
http://pgap.chat.ru/zap/zap134.htm#0
Нетрудно привести примеры формул, которые «выражают одно и то же». Таковы, например, формулы XÚY и YÚX. Подобные формулы мы будем называть равносильными. Прежде, чем дать соответствующее определение, условимся о следующем обозначении.
Определение. Формулы F и G называются равносильными, если для любой интерпретации j выполняется равенство j(F)=j(G).
Убедимся в том, что формулы F=X®Y и G=ØXÚY равносильны. Ясно, что если интерпретации j и y совпадают на X и Y, то j(F)=y(F) и j(G)=y(G). Следовательно, для проверки равенства j(F)=j(G) из определения равносильности надо рассмотреть лишь интерпретации, которые различаются на X и Y (а таких интерпретаций четыре) и вычислить соответствующие значения j(F) и j(G). Другими словами, надо составить совместную таблицу истинности формул F и G (см. таблицу 1.2).
| X | Y | F = X®Y | ØX | G = ØXÚY |
В таблице 1.2 для удобства вычисления значения интерпретаций на G введен промежуточный столбец ØX. Мы видим, что столбцы формул F и G совпадают. Это означает, что формулы F и G равносильны.
Близким к понятию равносильности является понятие тождественной истинности.
Определение. Формула F называется тождественно истинной если для любой интерпретации j выполняется равенство j(F)=1.
Например, формула F=X&Y®X является тождественно истинной. Для проверки равенства j(F)=1 не надо рассматривать все интерпретации, а лишь четыре, которые различаются на атомарных формулах X и Y. Для таких интерпретаций надо вычислить значение формулы F, т.е. составить таблицу истинности формулы F (см. таблицу 1.3). Таблица 1.3 для удобства вычисления значения j(F) содержит промежуточный столбец X&Y.
| X | Y | X&Y | F=X&Y®X |
Мы видим, что столбец формулы F состоит из одних единиц. Это означает, что формула F тождественно истинна.
Теорема 1.1. Формулы F и G равносильны тогда и только тогда, когда формула F«G является тождественно истинной.
Доказательство. Предположим, что формулы F и G равносильны и рассмотрим интерпретацию j. Ясно, что j(F«G)=j(F)«j(G). Поскольку значения истинности j(F) и j(G) совпадают, то по таблице истинности эквиваленции имеем равенства j(F)«j(G)=1. Это означает, что формула F«G тождественно истинна.
Предположим теперь, что формула F«G тождественно истинна и рассмотрим интерпретацию j. Имеем, что 1=j(F«G)=j(F)«j(G). Но из таблицы истинности эквиваленции следует, что если j(F)«j(G)=1, то j(F)=j(G).
В логике высказываний довольно часто приходится проводить преобразования формул, сохраняющие равносильность. Для таких преобразований используются так называемые законы логики высказываний. Приведем список этих законов.
Пусть F,G и Н – некоторые формулы логики высказываний. Тогда следующие формулы равносильны:
| 1) F&1 и F; | 2) FÚ1 и F; |
| 3) F&0 и 0; | 4) FÚ0 и F; |
| 5) F&F и F; | 6) FÚF и F; |
| 7) F&G и G&F; | 8) FÚG и GÚF; |
| 9) F&(G&H) и (F&G)&H; | 10) FÚ(GÚH) и (FÚG)ÚH; |
| 11) F&(GÚH) и (F&G)Ú(F&H); | 12) FÚ(G&H) и (FÚG)&(FÚH); |
| 13) F&(FÚG) и F; | 14) FÚ(F&G) и F; |
| 15) F&ØF и 0; | 16) FÚØF и 1; |
| 17) Ø(F&G) и ØFÚØG; | 18) Ø(FÚG) и ØF&ØG; |
| 19) ØØF и F; | 20) F®G и ØFÚG; |
| 21) F«G и (F®G)&(G®F). |
Доказательство этих равносильностей (законов логики высказываний) легко получается с помощью таблиц истинности. Отметим, что в примере на определение равносильности мы фактически доказали закон 20.
Прокомментируем список законов. Законы 5 и 6 называются идемпотентностью, 7 и 8 – коммутативностью, 9 и 10 – ассоциативностью соответственно конъюнкции и дизъюнкции. Ассоциативность конъюнкции означает, что в конъюнкции трех формул скобки можно ставить как угодно, а, следовательно, вообще не ставить. Из этого утверждения следует, что в конъюнкции четырех, пяти и т.д. любого конечного числа формул скобки можно ставить как угодно и поэтому вообще не ставить. Аналогичное замечание можно сделать и для дизъюнкции.
Законы 11 и 12 называются дистрибутивностями. Более точно, закон 11 – дистрибутивность конъюнкции относительно дизъюнкции, а закон 12 – дистрибутивность дизъюнкции относительно конъюнкции. Для применения этих законов в преобразованиях формул удобно иметь в виду следующий аналог. Заменим в законе 11 формулы F,G и Н соответственно буквами a,b и с, знак & заменим умножением *, а знак Ú – сложением+. Мы получим известное числовое тождество
a*(b+c) = a*b+a*c (*)
Это тождество есть дистрибутивность умножения чисел относительно сложения. В школе применение этого равенства слева направо называется раскрытием скобок, а справа налево вынесением общего множителя. Отличие операций над высказываниями & и Ú от числовых операций * и + состоит в том, что для высказываний выполняются обе дистрибутивности, а для чисел только одна. Сложение не дистрибутивно относительно умножения.
Закон 15 называется законом противоречия, закон 16 – законом исключенного третьего, закон 19 – снятием двойного отрицания. Законы 13 и 14 называются законами поглощения, а законы 17 и 18 – законами де Моргана в честь известного французского математика и логика 19 века.
Имея законы логики высказываний, мы получаем еще один способ доказательства равносильности двух формул, наряду с построением совместной таблицы истинности. Этот способ состоит в переходе от одной формулы к другой с помощью законов. В его основе лежит следующее легко доказываемое утверждение: если в некоторой формуле F заменить подформулу G равносильной ей формулой G′, то получим формулу F′, равносильную исходной формуле F. Проиллюстрируем второй способ на следующем примере: доказать равносильность формул
F=[X&(Z®Y)]Ú[(X®Z)&Y] и
G=(XÚY)&(YÚØZ).
В силу закона 20, формулы Z®Y и X®Z равносильны соответственно формулам ØZÚY и ØXÚZ, поэтому формула F равносильна формуле
F1=[X&(ØZÚY)]Ú[(ØXÚZ)&Y].
Дважды применив дистрибутивность (закон 11) и пользуясь ассоциативностью связок & и Ú, получим, что формула F1 равносильна формуле
F2=(XÚØXÚZ)&(ØZÚYÚØXÚZ)&(XÚY)&(ØZÚYÚY).
В силу коммутативности дизъюнкции, законов 16 и 2, формулы XØXÚZ и ØZÚYÚØXÚZ равносильны 1. Применив теперь законы 1 и 6 и коммутативность дизъюнкции, получим, что формула F2 равносильна G.
Логика высказываний обладает довольно слабыми выразительными возможностями. В ней нельзя выразить даже очень простые с математической точки зрения рассуждения. Рассмотрим, например, следующее умозаключение. «Всякое целое число является рациональным. Число 2 – целое. Следовательно, 2 – рациональное число». Все эти утверждения с точки зрения логики высказываний являются атомарными. Средствами логики высказываний нельзя вскрыть внутреннюю структуру и поэтому нельзя доказать логичность этого рассуждения в рамках логики высказываний. Мы рассмотрим расширение логики высказываний, которое называется логика предикатов первого порядка или короче: логика первого порядка.