Равносильность формул логики. Законы логики

Лекция №3
План
1. Понятие равносильности формул логики высказываний.
2. Основные равносильности формул логики высказываний.

Понятие равносильности формул
Рассмотрим две формулы логики высказываний: , .
Составим для них таблицы истинности.
Что вы можете сказать о значениях этих формул?

Понятие равносильности формул
Определение. Формулы F1 и F2 называются равносильными, если они принимают одинаковые истинностные значения при любом наборе значений переменных, входящих в эти формулы. Обозначают: F1 ≡ F2.
Теорема. Формулы F1 и F2 являются равносильными, если формула F1 ↔ F2 является тождественно истинной (тавтологией).
Справедливость утверждения непосредственно следует из определения эквиваленции.

Основные равносильности формул (законы логики)
Одной из задач логики является установление равносильности логических формул или их упрощение. Построение таблиц истинности в этом случае может оказаться очень громоздким или вообще не давать нужный результат. В таких случаях целесообразно осуществить равносильные преобразования формул.
Рассмотрим основные равносильности формул логики (законы логики) и правила преобразований формул логики.

Основные равносильности формул (законы логики)

Основные равносильности формул (законы логики)

Основные равносильности формул (законы логики)

Основные равносильности формул (законы логики)
При упрощении логических формул, как правило, исключают операции импликации, эквиваленции, штрих Шеффера, стрелку Пирса и сложение по модулю 2, и осуществляют переход к стандартному базису логических функций, содержащему операции конъюнкции, дизъюнкции и отрицания. При этом добиваются, чтобы отрицания стояли только над отдельными переменными, а сами переменные или их отрицания связывались операциями дизъюнкции и конъюнкции.

Основные равносильности формул (законы логики)

Основные равносильности формул (законы логики)
При выполнении равносильных преобразований логических формул наряду с перечисленными выше законами логики используют следующие правила преобразований:
Правило подстановки. Пусть F1 и F2 - равносильные формулы, содержащие некоторую формулу F. Если формулу F заменить в формулах F1 и F2 на формулу G, то формулы G1 и G2 также будут равносильными: G1≡G2.
.

Основные равносильности формул (законы логики)
Так, согласно правилу подстановки,
например, из равносильности формул
вытекает равносильность формул
В данном случае в исходные формулы вместо формулы А мы подставили формулу А→С, при этом новые формулы также равносильны.

Основные равносильности формул (законы логики)
При выполнении равносильных преобразований логических формул наряду с перечисленными выше законами логики используют следующие правила преобразований:
Правило замены. Пусть в формуле F1 выделена формула F и G - равносильная ей формула: F≡G. Если формулу F в формуле F1 заменить на формулу G, то полученная формула G1 будет равносильна формуле F1 : F1 ≡ G1.
.