Отношение равносильности и эквивалентность
Докажем, что если формулы 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, то для некоторого набора x1,…,xn значений переменных одно высказывание будет иметь значение И, другое – Л. Тогда j1(x1,…,xn) «j2(x1,…,xn) будет ложным высказыванием, а следовательно, формула j1(x1,…,xn) «j2(x1,…,xn) не будет тождественно истинной.
Тем самым задача об установлении равносильности двух формул сводится к установлению тождественной истинности формул частного вида.
Наряду с отношением равносильности между формулами логики высказываний рассматриваются некоторые другие отношения, представляющие большой интерес для логики и ее приложений. Среди них наиважнейшим является отношение логического следования.
Пусть j1(x1,…,xn)ºj1 и j2(x1,…,xn)ºj2 – две формулы логики высказываний от переменных x1,…,xn. Будем говорить, что формула j2(x1,…,xn) является логическим следствием формулы j1(x1,…,xn), если j2 принимает значение И для всех наборов значений переменных, для которых j1 истинна. Это означает также, что если представить обе формулы их таблицами истинности, то множество наборов, для которых j1 истинна содержится в множестве наборов, для которых истинна формула j2.
Например, согласно этому определению j2=(xÚz) является логическим следствием j1=((xÚy)&z). Это видно их соответствующих таблиц истинности.
| x | y | z | j1=((xÚy)&z) | j2=(xÚz) |
Определение.Формула j2(x1,…,xn) является логическим следствием формулы j1(x1,…,xn) тогда и только тогда, когда тождественно истинна формула
j1(x1,…,xn)®j2(x1,…,xn).
Из сказанного видно, что формулы j1 и j2 равносильны тогда и только тогда, когда каждая из них является логическим следствием другой. Из определения также следует, что всякая формула является логическим следствием тождественно ложной формулы. Действительно, так как в этом случае формула j1 никогда не принимает значение И, то множество наборов, для которых j1 истинно, пусто и содержится, следовательно, в множестве наборов истинности для любой формулы j2.
Отметим, что введенные отношения (тождества и следования) относятся не к единичным высказываниям, как это имело место для понятия импликации, а к целым множествам высказываний, описываемых формулами j1(x1,…,xn) и j2(x1,…,xn).
Формулу j1(x1,…,xn) можно рассматривать как условие, которое может быть выполнимо или нет в зависимости от истинности 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.
Дата добавления: 2017-11-04; просмотров: 470;