Слайд 1Лекция 8 Формулы в логике высказываний. Принцип резолюций
Атомарными формулами логики
высказываний называются буквы U, V, W, X, Y, Z с
индексами и без них, а также символы истины 1 и лжи 0.
Формулами логики высказываний называются:
атомарные формулы;
выражения вида (F)&(G), (F)(G), (F), (F) (G), (F) (G), где F и G – формулы логики высказываний.
Слайд 2Формула представляет собой форму для получения высказываний. Пусть, например, дана
формула F=X&YZ. Если вместо X, Y и Z подставить соответственно
высказывания А1= «четырехугольник ABCD является параллелограммом», А2= «в четырехугольнике ABCD смежные стороны равны», А3= «в четырехугольнике ABCD диагонали перпендикулярны», то получается высказывание А4= «если четырехугольник ABCD является параллелограммом и его смежные стороны равны, то диагонали перпендикулярны».
Слайд 3Интерпретация
Если вместо X, Y и Z подставить другие высказывания, то
можно получить новое высказывание, имеющее ту же «форму». Данный процесс
называется интерпретацией.
Интерпретацией в широком смысле будет называться функция:
φ: AP
такая, что φ (1) – истинное высказывание, а φ (0) – ложное.
Слайд 4Равносильность и законы логики высказываний
Формула F называется тождественно истинной (тавтологией),
если для любой интерпретации φ выполняется равенство φ(F)=1.
Тавтологии:
x (x
y)
((x y) & (y z)) (x z)
(x y) (x) y
принимают значения И при всех значениях входящих в них переменных
Слайд 5Равносильность и законы логики высказываний
Формулы F1 и F2 называются равносильными,
если их эквиваленция F1 F2 – тавтология.
Формулы F и G
называются равносильными, если для любой интерпретации φ выполняется равенство φ(F)= φ(G).
Слайд 6Равносильность и законы логики высказываний
Формулы F=XY и G=XY являются равносильными.
Для проверки равенства φ(F)= φ(G) надо составить совместную таблицу истинности
формул F и G.
Формула F=X&YX является тождественно истинной.
Слайд 7Логическая равносильность
Равносильность – это отношение между формулами. Равносильные формулы ЛВ
называют законами логики.
Слайд 8Законы логики высказываний
Равносильные формулы ЛВ называют законами логики
закон тождества
закон противоречия
закон исключенного третьего
закон двойного отрицания
закон идемпотентности
законы коммутативности
законы ассоциативности
законы дистрибутивности
законы де Моргана
Законы логики высказываний
Слайд 10Задание
Доказать равносильность формул
F=[X&(ZY)] [(XZ)&Y] и G=(XY)&(YZ).
Слайд 11Задание
Доказать, что формула G=YX не является логическим следствием формул F1=XY,
F2=XY, F3=Y.
Слайд 12Аксиомы логики высказываний
Формулы, связанные отношением выводимости (следования), называются аксиомами логики
высказываний
Аксиомы логики высказываний
F1 ├(F2 F1)
F1&F2├ F1
F1&F2├ F2
F1├(F1 F2)
F2├(F1
F2)
Формула в левой части этих отношений называется условием. Формула в правой части – это следствие или заключение.
Слайд 13Аксиомы ЛВ в натуральном исчислении высказываний рассматриваются как правила. Так
аксиомы (2, 3), получили название правил исключения (выделения) конъюнкта.
Правило
исключения в общем виде записывается так
F1 F2… Fm… Fn├ Fm
На естественном языке это правило определяется следующим образом: из истинности конъюнкции следует истинность любого из ее конъюнктов.
Слайд 14Аксиомы (4, 5) получили название правил введения дизъюнкта:
Fl├ F1 F2…
Fm… Fn.
Это правило означает, что из истинности формулы Fm
следует истинность ее дизъюнкции с любыми другими формулами.
И еще одно правило из натурального исчисления высказываний – правило введения конъюнкции: если F1, F2, …Fk – список истинных формул, то
F1, F2, …Fk├ F1 F2… Fm… Fk.
Слайд 15ПРИОРИТЕТЫ ЛОГИЧЕСКИХ ОПЕРАЦИЙ
Вычисление значений логических выражений выполняется в определенном
порядке, согласно их приоритету:
- инверсия
- конъюнкция
- дизъюнкция
- импликация и эквивалентность
Операции одного приоритета выполняются слева направо. Для изменения порядка действий используются скобки.
Слайд 16Логическое следствие
Определение. Формула G называется логическим следствием формул F1, F2,…,
Fk, если для любой интерпретации φ из того, что φ(F1)=φ(F2)=…=φ(Fk)=1
следует, что φ(G)=1.
Слайд 17Логическое следствие
Если импликация F1 F2 тавтология, то говорят, что формула
F2 следует из формулы F1, или выводима из F1. Для
обозначения выводимости (следования) используется обозначение
F1├F2.
Знак ├ выводимости иногда называют турникетом.
Слайд 18 Справедливость следования формулы F2 из F1: нет такого набора логических
переменных, когда F1=И, а F2=Л, иначе импликация (F1 F2)=Л, что
противоречит определению тавтологии.
Пример
Отношение x├xy.
Составить таблицу истинности импликации x├xy и убедиться в том, что она тавтология.
Очевидно, что если x=И, то в любом случае
(x y)=И.
В силу равноправности переменных можно также задать отношение y├ x y.
Слайд 19Приведение формул ЛВ к конъюнктивной нормальной форме
Простые формулы ЛВ (логические
переменные и константы) рассматривают как атомарные формулы, или как простые
атомы. По определению отрицание атомной формулы – это тоже формула ЛВ.
Атом и его отрицание называются дополняющими друг друга литералами.
Литерал в ЛВ – это атом или его отрицание.
Пользуясь известными законами логики, всякую формулу ЛВ можно преобразовать в равносильную формулу вида:
где – так называемые фразы – это формулы ЛВ, представляющие собой дизъюнкцию конечного числа литералов.
Слайд 20Конъюнктивная нормальная форма
Конъюнктивной нормальной формой (КНФ) называется конъюнкция конечного числа
дизъюнктов (фраз).
Теорема. Любая формула ЛВ имеет логически эквивалентную (равносильную) ей
КНФ.
Слайд 21 Для приведения формул ЛВ к КНФ нужно выполнить следующее:
Логические операции
импликации и эквиваленции заменить равносильными им формулами по схеме
x ↔ y ≡ (x y) (x y)
Знак отрицания перед сложным выражением внести к его составляющим элементам, воспользовавшись законами де Моргана
Операции дизъюнкции внести внутрь скобок
Слайд 22Фраза
записывается в виде
где – литералы.
При
этом КНФ приобретает вид
Литералы во внутренних фигурных скобках неявно
объединяются дизъюнкциями, а фразы неявно объединяются связками-конъюнкциями.
Слайд 23Пример
Пусть нужно привести к КНФ формулу
Действуя согласно приведенному
алгоритму, последовательно находим
Отбрасывая знаки и , получаем
Слайд 24Исчисление высказываний
Исчисление логики высказываний (ЛВ) помимо всех элементов формального языка
ЛВ включает
законы ЛВ ( );
аксиомы ЛВ
правила вывода
Слайд 25С помощью правил вывода из некоторого множества истинных формул (тавтологий)
F1,F2,…,Fn получают (выводят) формулу F. Для этого используют запись:
или
├
Слайд 26Модус поненс (modus ponens)
В классическом исчислении высказываний (ИВ) используется два
правила вывода
Модус поненс (modus ponens)
A, AB├ B
или
А, AB
B
Из истинности условия импликации и истинности самой импликации следует истинность следствия (заключения) импликации.
Слайд 27Правило подстановки
Пусть А(х) – формула ЛВ, зависящая от логической переменной
х. Тогда из А(х) выводима формула А(F), то есть
А(х)
├ А(F),
если в формулу А(х) вместо каждого вхождения переменной х подставить формулу F.
Слайд 28Принцип резолюции
В исчислении высказываний используют правило или принцип резолюции,
предложенный в 1965 г. Дж. Робинсоном как достаточно эффективный способ
машинных выводов.
Принцип резолюции используется в форме двух правил:
правило простой резолюции
правило резолюции
Слайд 29Простая резолюция
AB, B ├ A
Из истинности дизъюнкции и отрицания одного
из ее дизъюнктов следует истинность формулы, полученной удалением этого дизъюнкта.
Слайд 30Резолюция
AB, (B)C ├ AC
Из истинности двух дизъюнкций, одна из которых
содержит дизъюнкт, а другая его отрицание следует (выводима) формула дизъюнкции
исходных формул без дизъюнкта и его отрицания.
Слайд 31Из дизъюнктов XYZ и XY выводим дизъюнкты YZ Y.
Правило
резолюций можно применять не обязательно к самым левым литералам. Тогда
правило резолюций, примененное к Y и Y, даст XZX или Z.
□– пустой дизъюнкт, т.е. дизъюнкт, не содержащий литералов.
В дизъюнктах не писать повторяющиеся литералы и не писать □, если есть другие литералы.
Слайд 32Логическое следствие
Определение. Формула G называется логическим следствием формул F1, F2,…,
Fk, если для любой интерпретации φ из того, что φ(F1)=φ(F2)=…=φ(Fk)=1
следует, что φ(G)=1.
Слайд 33Пусть S – множество дизъюнктов. Выводом из S называется последовательность
дизъюнктов
D, D2, ..., Dn
такая, что каждый дизъюнкт этой последовательности принадлежит
S или следует из предыдущих по правилу резолюций.
Дизъюнкт D выводим из S, если существует вывод из S, последним дизъюнктом которого является D.
Например, если S={XYZ, YU, X}, то последовательность D1= XYZ, D2= YU, D3=XZU, D4=X, D5=ZU – вывод из S. Дизъюнкт ZU выводим из S.
Слайд 34 Определение. Множество формул {F1, F2,…, Fm} называется выполнимым, если существует
интерпретация φ такая, что
φ(F1)=φ(F2)=…=φ(Fm)=1.
Проверку выполнимости множества формул {F1,
F2,…, Fm} можно провести построением совместной таблицы истинности этих формул. Если найдется хотя одна строка, в которой в столбцах формул F1, F2, …, Fm стоят единицы, то это множество формул выполнимо. Если такой строки нет, то множество формул невыполнимо.
Слайд 35 Теорема. Формула G является логическим следствием формул F1,F2,…,Fk тогда и
только тогда, когда множество формул L={F1,F2,…,Fk,G} невыполнимо.
Слайд 36Теорема. Множество дизъюнктов логики высказываний S невыполнимо тогда и только
тогда, когда из S выводим пустой дизъюнкт.
Для доказательства того, что
формула G является логическим следствием множества формул F1,…,Fk применяется метод резолюций. Сначала составляется множество формул T={F1,…,Fk, G}. Затем каждая из этих формул приводится к конъюнктивной нормальной форме и в полученных формулах зачеркиваются знаки конъюнкции.
Слайд 37 Получается множество дизъюнктов S. И, наконец, ищется вывод пустого дизъюнкта
из S. Если пустой дизъюнкт выводим из S, то формула
G является логическим следствием формул F1,…,Fk. Если из S нельзя вывести □, то G не является логическим следствием формул F1,…,Fk.
Слайд 38Покажем, что формула G=Z является логическим следствием формул F1=X
Y, F2=X Z, G=(Y Z) Z. Сформируем
множество формул T={F1,F2, G}. Приведем формулы F1 и F2 к КНФ (формула G сама имеет эту форму). Мы получим, что YZ,
F1 равносильна (XY),
F2 равносильна ( XZ),
G равносильна Y Z.
Слайд 39Тогда множество дизъюнктов S равно
{XY, XZ, (Y Z
)}.
Из множества S легко выводится пустой дизъюнкт:
XY, XZ ,Y
Z, Y, Z, Z, □.
Следовательно, формула G является логическим следствием формул F1, и F2.
![ЗаданиеДоказать равносильность формулF=[X&(ZY)] [(XZ)&Y] и G=(XY)&(YZ).](/img/thumbs/30812bdc260dc0880b5d5d36733e356b-800x.jpg "Лекция 8 Формулы в логике высказываний. Принцип резолюций ЗаданиеДоказать равносильность формулF=[X&(ZY)] [(XZ)&Y] и G=(XY)&(YZ).")
