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