Слайд 2Равносильные преобразования в логике высказываний
Логическая равносильность, законы логики.
Равносильные преобразования в логике
![Равносильные преобразования в логике высказываний Логическая равносильность, законы логики. Равносильные преобразования в](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1139056/slide-1.jpg)
высказываний.
Преобразование форм представления формул логики высказываний.
Проблема дедукции в логике высказываний.
Слайд 3Логическая равносильность, законы логики.
Два высказывания равносильны, если они одновременно истинны или
![Логическая равносильность, законы логики. Два высказывания равносильны, если они одновременно истинны или](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1139056/slide-2.jpg)
одновременно ложны.
Две формулы равносильны если их эквиваленция является тавтологией (общезначима).
F1 ↔ F2 ≡ 1
Слайд 4Логическая равносильность, законы логики.
Равносильность – это отношение между формулами и как отношение
![Логическая равносильность, законы логики. Равносильность – это отношение между формулами и как](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1139056/slide-3.jpg)
обладает свойствами рефлексивности, симметричности, транзинтивности.
Равносильности логики высказываний называют законами логики.
Основные законы логики и основные тавтологии: законы Аристотеля, де Моргана, идемпотентности.
Слайд 6Логическая равносильность, законы логики.
Алгебра формул логики высказываний подобна алгебре множеств (законы коммутативности,
![Логическая равносильность, законы логики. Алгебра формул логики высказываний подобна алгебре множеств (законы](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1139056/slide-5.jpg)
ассоциативности, дистрибутивности выполняются для алгебры высказываний).
Слайд 7Законы
Х ∨ УZ = (X ∨ У)(Х ∨ Z) – закон
![Законы Х ∨ УZ = (X ∨ У)(Х ∨ Z) – закон](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1139056/slide-6.jpg)
дистрибутивности дизъюнкции относительно конъюнкции.
X ∨ УХ = Х; Х(Х ∨ У) = Х – закон поглощения
ХУ ∨ ХУ = У; (Х ∨ У)(Х ∨ У) = Х – закон склеивания
Слайд 8Если в равносильные формулы вместо какой-то переменной или подформулы подставить одну и
![Если в равносильные формулы вместо какой-то переменной или подформулы подставить одну и](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1139056/slide-7.jpg)
ту же формулу, то полученные формулы останутся равносильными. Это обозначается так:
(Х || У) или (Х,У) – «вместо Х подставить У».
Слайд 9Принцип двойственности
Две формулы, не содержащие знаков импликации и эквиваленции называют двойственными,
![Принцип двойственности Две формулы, не содержащие знаков импликации и эквиваленции называют двойственными,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1139056/slide-8.jpg)
если каждую из них можно получить из другой заменой символов конъюнкции, дизъюнкции, “0”, “1” на символы дизъюнкции, конъюнкции, “1”, “0”.
Принцип двойственности утверждает, что если две формулы равносильны, то и двойственные им формулы тоже равносильны.
Слайд 10Дополнительные законы логики
PQ → P – “конъюнкция сильнее каждого из его
![Дополнительные законы логики PQ → P – “конъюнкция сильнее каждого из его](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1139056/slide-9.jpg)
членов.”
P → (P ∨ Q) – “дизъюнкция слабее каждого из её членов.”
P → (Q → P) – “истина из чего угодно.”
P → (P → Q) – “из ложного всё что угодно.”
“Перестановка посылок.” [P→ (Q → R)] ↔ [Q → (P → R)] – тавтология.
“Объединение и разъединение посылок.” [P → (Q → R)]↔[(PQ) → R]
Слайд 11Равносильные преобразования в логике высказываний
Замену одной формулы другой ей равносильной будем
![Равносильные преобразования в логике высказываний Замену одной формулы другой ей равносильной будем](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1139056/slide-10.jpg)
называть равносильным преобразованием данной формулы.
Упрощение формулы уменьшает число высказывательных переменных или знаков операций (минимизация).
Слайд 12Формулы равносильных преобразований
![Формулы равносильных преобразований](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1139056/slide-11.jpg)
Слайд 13Формулы равносильных преобразований
![Формулы равносильных преобразований](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1139056/slide-12.jpg)
Слайд 15Преобразование форм представления формул логики высказываний
Скобочная форма, образуется непосредственно после формализации
![Преобразование форм представления формул логики высказываний Скобочная форма, образуется непосредственно после формализации](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1139056/slide-14.jpg)
высказывания
Дизъюнктивная нормальная форма (ДНФ) – дизъюнкция элементарных конъюнкций.
Конъюнктивная нормальная форма (КНФ) – конъюнкция элементарных дизъюнкций.
КНФ также называют клаузальная форма.
Слайд 16Преобразование форм представления формул логики высказываний
Клауза – элементарная дизъюнкция.
Литера, литерал – элементарное
![Преобразование форм представления формул логики высказываний Клауза – элементарная дизъюнкция. Литера, литерал](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1139056/slide-15.jpg)
высказывание или его отрицание.
Дизъюнкт – дизъюнкция конечного числа литералов.
Хорновский дизъюнкт имеет не более одной не инверсной литеры.
Слайд 17Пример:
Преобразование в КНФ обычно производится при помощи распределительного закона.
СКНФ получают из КНФ
![Пример: Преобразование в КНФ обычно производится при помощи распределительного закона. СКНФ получают](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1139056/slide-16.jpg)
путём добавления к каждому дизъюнту заведомо отрицательной литеры.
Слайд 18Совершенная дизъюнктивная нормальная форма (СДНФ) – в каждой элементарной конъюнкции имеются все
![Совершенная дизъюнктивная нормальная форма (СДНФ) – в каждой элементарной конъюнкции имеются все](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1139056/slide-17.jpg)
n пропозициональных переменных.
Совершенная конъюнктивная нормальная форма (СКНФ) – в каждой элементарной дизъюнкции имеются все n пропозициональных переменных.
Слайд 19Проблема дедукции в логике высказываний
В логике помимо равносильности широко используется относительные
![Проблема дедукции в логике высказываний В логике помимо равносильности широко используется относительные](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1139056/slide-18.jpg)
следования.
Формула S является следствием множества формул H (H├ S) если при всех интерпретациях, при которых истинны все формулы из H, истинна также и формула S.
Тавтология – следствие из пустого множества формул.
Слайд 20S является следствием из H тогда и только тогда, когда H →
![S является следствием из H тогда и только тогда, когда H →](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1139056/slide-19.jpg)
S ≡ 1
(H├ S) ↔ (H → S) ≡ 1
├ (H → S) ≡ 1
(H1, H2, … , Hn) ├ S ↔ ├ (H1⋅ H2⋅ … ⋅ Hn) → S – импликация из конъюнкций этих формул тоже общезначима.
Слайд 21Фундаментальная проблема логики: определить является ли S следствием из множества формул H
![Фундаментальная проблема логики: определить является ли S следствием из множества формул H](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1139056/slide-20.jpg)
(проблема дедукции).
Проблема описывается следующим выражением:
H∨S ≡ 0 (невыполнимо)