Докажем, что если формулы j1 и j2 равносильны, то формула j1«j2 тождественно истинна, то есть если j1ºj2, то |‑j1«j2 и если |‑j1«j2, то j1ºj2.
Доказательство. Действительно, если j1ºj2, то формулы j1 и j2 принимают обе значение И или обе значение Л при любом наборе значений входящих в них переменных, а в этом случае формула j1«j2, согласно определению эквивалентности, принимает только значение И, то есть |‑j1«j2. Обратно, если ‑j1«j2, то j1 и j2 принимают при любом наборе значений входящих в них переменных обе значение И или обе значение Л, то есть j1ºj2.
Таким образом, исходя из доказанного предложения, каждая из перечисленных в таблице равносильностей порождает тождественно истинную формулу (достаточно заменить знак равносильности = или º знаком эквивалентности «).
Наоборот, если j1¹j2, то для некоторого набора x 1,…, x n значений переменных одно высказывание будет иметь значение И, другое – Л. Тогда j1(x 1,…, x n) «j2(x 1,…, x n) будет ложным высказыванием, а следовательно, формула j1(x 1,…, x n) «j2(x 1,…, x n) не будет тождественно истинной.
Тем самым задача об установлении равносильности двух формул сводится к установлению тождественной истинности формул частного вида.
Наряду с отношением равносильности между формулами логики высказываний рассматриваются некоторые другие отношения, представляющие большой интерес для логики и ее приложений. Среди них наиважнейшим является отношение логического следования.
Пусть j1(x 1,…, x n)ºj1 и j2(x 1,…, x n)ºj2 – две формулы логики высказываний от переменных x 1,…, x n. Будем говорить, что формула j2(x 1,…, x n) является логическим следствием формулы j1(x 1,…, x n), если j2 принимает значение И для всех наборов значений переменных, для которых j1 истинна. Это означает также, что если представить обе формулы их таблицами истинности, то множество наборов, для которых j1 истинна содержится в множестве наборов, для которых истинна формула j2.
Например, согласно этому определению j2=(x Ú z) является логическим следствием j1=((x Ú y)& z). Это видно их соответствующих таблиц истинности.
| x | y | z | j1=((x Ú y)& z) | j2=(x Ú z) |
Определение. Формула j2(x 1,…, x n) является логическим следствием формулы j1(x 1,…, x n) тогда и только тогда, когда тождественно истинна формула
j1(x 1,…, x n)®j2(x 1,…, x n).
Из сказанного видно, что формулы j1 и j2 равносильны тогда и только тогда, когда каждая из них является логическим следствием другой. Из определения также следует, что всякая формула является логическим следствием тождественно ложной формулы. Действительно, так как в этом случае формула j1 никогда не принимает значение И, то множество наборов, для которых j1 истинно, пусто и содержится, следовательно, в множестве наборов истинности для любой формулы j2.
Отметим, что введенные отношения (тождества и следования) относятся не к единичным высказываниям, как это имело место для понятия импликации, а к целым множествам высказываний, описываемых формулами j1(x 1,…, x n) и j2(x 1,…, x n).
Формулу j1(x 1,…, x n) можно рассматривать как условие, которое может быть выполнимо или нет в зависимости от истинности j1.
Перечень тождественно истинных формул
1. (p Þ q)(r Þ q)Û(p Ú r Þ q);
2. pq Þ p;
3. (p Þ q)(p Þ r)Û(p Þ qr);
4. (p Þ q) p Þ q;
5. 
;
6. 
‑ закон контрапозиции;
7. 
? ‑ закон расширенной контрапозиции;
8. p Þ(q Þ r)Û pq Þ r;
9. 
;
10. 
;
11. (p Þ q)(q Þ r)Û(p Þ r) –.закон силлогизма.
Подстановка
Разумеется, этот перечень не исчерпывает тождественно истинные формулы, находящие применение в исчислении высказываний. Вместе с тем каждая из перечисленных тождественно истинных формул порождает новые ТИФ в результате подстановки вместо какой-нибудь входящей в нее переменной произвольной формулы.
Действительно, если |‑j(…, р,…) содержит переменную р, то, подставив вместо переменной р всюду, где она входит в j, произвольную формулу y, в результате получим формулу j(…, y,…), которая принимает те же значения, что и исходная формула j(…, р,…), так как y принимает те же значения (И, Л), что и р.
Конечно, можно применять подстановку к нескольким или даже ко всем переменным, входящим в ТИФ.
Например, тождественно истинной формулой является
|‑(j1Þj2)(j2Þj3)Û(j1Þj3), так как эта формула получается из (11) подстановкой вместо p формулы j1, вместо q формулы j2 и вместо r формулы j3.
