Метод редукций проверки тождественной истинности формул логики высказываний.

Минимум

Законы логики высказываний.

1.А& A A; A A И(закон сохранения); AVA A; A~A

2.Закон комутативности

A& B A~B B~A; AVB BVA; A B B A

3.Закон «лжи-истина»

А& И А; AVИ И

4.Закон противоречия

А& Л

5.Закон исключения третьего: АV И

6.Закон двойного отрицания:

7.Закон дистрибутивности:

A& (BVC) (A& B)V(A& C)

AV(B& C) (AVB)& (AVC)

A~(B~C) (A~B)~C

A (B C) (A B) C

8.Закон де Моргана: V ; &

9.Закон поглощения: A& (AVB) A; AV(A& B) A

10. Формулы расщепления: A (A& B)V(A& ); A (AVB)& (AV )

11. A B VB ; AVB B ; A& B V ;

A~B (A B)& (B A) (A& B)V( & ) (BV )& (AV )

Метод редукций проверки тождественной истинности формул логики высказываний.

Правильные рассуждения

При доказательстве утверждений математических рассуждений используют рассуждения, которые на языке логики можно выразить формулами. Рассуждение называется правильным, если из коньюнкции посылок следует заключение. Таким образом правильность рассуждений можно установить, составив соответствующую ему формулу логики высказываний и доказать, что она является тавтологией.

Утверждение о правильности рассуждения по схеме …

Пусть … посылки, Q- заключение.

Утверждение.

Рассуждение по схеме … правильны тогда и только тогда, когда тавтология.

Доказательство

1.

Пусть рассуждение по этой схеме является правильным, допустим по определению импликаций. Если же , то при любых Q. Следовательно формула тавтология.

2.

Пусть - тавтология. Допустим , тогда , иначе - не тавтология. Таким образом формула Q есть логическое следствие формулы , т.е рассуждение по этой схеме -правильное.