14. 5. Логическая равносильность. Законы логики

Два высказывания равносильны, если они одновременно истинны или одновременно ложны.

Две формулы равносильны если их эквиваленция является тавтологией (общезначима).

F₁↔F₂≡1.

Равносильность – это отношение между формулами и как отношение обладает свойствами рефлексивности, симметричности, транзитивности.

Равносильности логики высказываний называют законами логики.

Основные законы логики и основные тавтологии: законы Аристотеля, де Моргана, идемпотентности, а также остальные равносильности, рассмотренные нами в дискретной математике.

Иногда доказывают равносильность формул А и В, если они являются следствием друг друга.

А→В, В→А. Тогда А≡В.

В логике часто используется прием подстановки.

Если в равносильные формулы вместо какой-то переменной или подформулы подставить одну и ту же формулу, то полученные формулы останутся равносильными. Это обозначается так:

(Х||У) или (Х,У) – «вместо Х подставить У».

Принцип двойственности.

Две формулы, не содержащие знаков импликации и эквиваленции называют двойственными, если каждую из них можно получить из другой заменой символов конъюнкции, дизъюнкции, «0», «1» на символы дизъюнкции, конъюнкции, «1», «0», соответственно.

Принцип двойственности утверждает, что если две формулы равносильны, то и двойственные им формулы тоже равносильны.

Иногда законами логики называют только тавтологии, т.е. тождественно истинные формулы. Рассмотрим такие законы [1]:

1. PQ→P – «конъюнкция сильнее каждого из его членов»;

2. P→(PÚQ) – «дизъюнкция слабее каждого из её членов»;

3. P→(Q→P) – «истина из чего угодно»;

4. P→(P→Q) – «из ложного всё что угодно»;

5. [P→(Q→R)]↔[Q→(P→R)] «перестановка посылок»;

6. [P→(Q→R)]↔[(PQ)→R] «объединение и разъединение посылок»;

7. [(P→R)(Q→R)]↔[(PÚQ)→R] «правило разбора случаев»;

8. [(P→Q)→[(P→Q)→P] «правило приведения к противоречию»;

9. [(P→Q)(Q→R)]→(P→R) «цепное заключение».

Эти законы можно, например, доказать путем использования формул равносильных преобразований или путем построения дерева редукции формулы.

Например: PQ→P= .

14.6. Формы представления формул логики высказываний

Скобочная форма, образуется непосредственно после формализации высказывания.

Дизъюнктивная нормальная форма – дизъюнкция элементарных конъюнкций.

Конъюнктивная нормальная форма – конъюнкция элементарных дизъюнкций.

КНФ также называют клаузальной формой.

Клауза – элементарная дизъюнкция.

Литера, литерал – элементарное высказывание или его отрицание.

Дизъюнкт – дизъюнкция конечного числа литералов.

Хорновский дизъюнкт имеет не более одной не инверсной литеры.

Пример.

.

Хорновские дизъюнкты используются в языке ПРОЛОГ (PROLOG, от PROgramming in LOGic – программирование в логике; разработан в 1972 г. Аланом Колмари) для описания правил типа «Если, то». Кстати, в ПРОЛОГЕ с помощью импликации записываются и так называемые факты: .

.

Т.е. факт – это утверждение истинности некой формулы.

Преобразование в КНФ обычно производится при помощи распределительного закона.

СКНФ получают из КНФ путём добавления к каждому дизъюнкту тождественно ложной литеры.