Слайд 2Лекция №3
План
1. Понятие равносильности формул логики высказываний.
2. Основные равносильности формул логики высказываний.
![Лекция №3 План 1. Понятие равносильности формул логики высказываний. 2. Основные равносильности формул логики высказываний.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1103986/slide-1.jpg)
Слайд 3Понятие равносильности формул
Рассмотрим две формулы логики высказываний: , .
Составим для них таблицы
![Понятие равносильности формул Рассмотрим две формулы логики высказываний: , . Составим для](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1103986/slide-2.jpg)
истинности.
Что вы можете сказать о значениях этих формул?
Слайд 4Понятие равносильности формул
Определение. Формулы F1 и F2 называются равносильными, если они принимают
![Понятие равносильности формул Определение. Формулы F1 и F2 называются равносильными, если они](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1103986/slide-3.jpg)
одинаковые истинностные значения при любом наборе значений переменных, входящих в эти формулы. Обозначают: F1 ≡ F2.
Теорема. Формулы F1 и F2 являются равносильными, если формула F1 ↔ F2 является тождественно истинной (тавтологией).
Справедливость утверждения непосредственно следует из определения эквиваленции.
Слайд 5Основные равносильности формул (законы логики)
Одной из задач логики является установление равносильности логических
![Основные равносильности формул (законы логики) Одной из задач логики является установление равносильности](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1103986/slide-4.jpg)
формул или их упрощение. Построение таблиц истинности в этом случае может оказаться очень громоздким или вообще не давать нужный результат. В таких случаях целесообразно осуществить равносильные преобразования формул.
Рассмотрим основные равносильности формул логики (законы логики) и правила преобразований формул логики.
Слайд 6Основные равносильности формул (законы логики)
![Основные равносильности формул (законы логики)](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1103986/slide-5.jpg)
Слайд 7Основные равносильности формул (законы логики)
![Основные равносильности формул (законы логики)](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1103986/slide-6.jpg)
Слайд 8Основные равносильности формул (законы логики)
![Основные равносильности формул (законы логики)](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1103986/slide-7.jpg)
Слайд 9Основные равносильности формул (законы логики)
При упрощении логических формул, как правило, исключают операции
![Основные равносильности формул (законы логики) При упрощении логических формул, как правило, исключают](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1103986/slide-8.jpg)
импликации, эквиваленции, штрих Шеффера, стрелку Пирса и сложение по модулю 2, и осуществляют переход к стандартному базису логических функций, содержащему операции конъюнкции, дизъюнкции и отрицания. При этом добиваются, чтобы отрицания стояли только над отдельными переменными, а сами переменные или их отрицания связывались операциями дизъюнкции и конъюнкции.
Слайд 10Основные равносильности формул (законы логики)
![Основные равносильности формул (законы логики)](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1103986/slide-9.jpg)
Слайд 11Основные равносильности формул (законы логики)
При выполнении равносильных преобразований логических формул наряду с
![Основные равносильности формул (законы логики) При выполнении равносильных преобразований логических формул наряду](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1103986/slide-10.jpg)
перечисленными выше законами логики используют следующие правила преобразований:
Правило подстановки. Пусть F1 и F2 - равносильные формулы, содержащие некоторую формулу F. Если формулу F заменить в формулах F1 и F2 на формулу G, то формулы G1 и G2 также будут равносильными: G1≡G2.
.
Слайд 12Основные равносильности формул (законы логики)
Так, согласно правилу подстановки,
например, из равносильности формул
вытекает
![Основные равносильности формул (законы логики) Так, согласно правилу подстановки, например, из равносильности](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1103986/slide-11.jpg)
равносильность формул
В данном случае в исходные формулы вместо формулы А мы подставили формулу А→С, при этом новые формулы также равносильны.
Слайд 13Основные равносильности формул (законы логики)
При выполнении равносильных преобразований логических формул наряду с
![Основные равносильности формул (законы логики) При выполнении равносильных преобразований логических формул наряду](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1103986/slide-12.jpg)
перечисленными выше законами логики используют следующие правила преобразований:
Правило замены. Пусть в формуле F1 выделена формула F и G - равносильная ей формула: F≡G. Если формулу F в формуле F1 заменить на формулу G, то полученная формула G1 будет равносильна формуле F1 : F1 ≡ G1.
.