Нетрудно привести примеры формул, которые «выражают одно и то же». Таковы, например, формулы 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).

Таблица 1.2

В таблице 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.

Таблица 1.3

Мы видим, что столбец формулы 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 и Н – некоторые формулы логики высказываний. Тогда следующие формулы равносильны:

Доказательство этих равносильностей (законов логики высказываний) легко получается с помощью таблиц истинности. Отметим, что в примере на определение равносильности мы фактически доказали закон 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 равносильна формуле

F₁=[X&(ØZÚY)]Ú[(ØXÚZ)&Y].

Дважды применив дистрибутивность (закон 11) и пользуясь ассоциативностью связок & и Ú, получим, что формула F₁ равносильна формуле

F₂=(XÚØXÚZ)&(ØZÚYÚØXÚZ)&(XÚY)&(ØZÚYÚY).

В силу коммутативности дизъюнкции, законов 16 и 2, формулы XØXÚZ и ØZÚYÚØXÚZ равносильны 1. Применив теперь законы 1 и 6 и коммутативность дизъюнкции, получим, что формула F₂ равносильна G.