Лекция №3
•Синтаксис и семантика логики высказываний
•Хорновские БЗ.
•Алгоритм прямого и обратного вывода.
•Синтаксис и семантика логической программы.
•Понятие унификации
Синтаксис логики высказываний
•Выделяют атомарные и сложные высказывания.
•Атомарные высказывания (неделимые синтаксические элементы) состоят из одного пропозиционального символа, для обозначения которых используются прописные символы P, Q, S, Каждый пропозициональный символ может быть либо истинным, либо ложным.
•Два пропозициональных символа имеют постоянный смысл: True – тождественно истинное высказывание, False – тождественно ложное высказывание.
•Сложные высказывания формируются из более простых высказываний с помощью логических связок: отрицание (не), конъюнкция (и), дизъюнкция (или), импликация (влечет за собой), двухсторонняя импликация (если и только если). Правила формирования сложных высказываний: если S, S1 и S2 – высказывания пропозициональной логики, то высказываниями пропозициональной логики являются также S, S1 S2 ,
S1 S2 , S1 S2 , S1 S2 .
Семантика логики высказываний
•Логические исчисления обладают так называемой встроенной семантикой: т.е. задав значения всем атомарным высказываниям, значения сложных высказываний вычисляются автоматически в соответствии с таблицей истинности. Это свойство называется композициональностью логики
•В логике семантика языка определяет истинность каждого высказывания применительно к каждому из возможных наборов значений атомарных высказываний, называемых возможными моделями.
Например в модели m = { S1= true , S2= false, S3= true } сложное высказывание
S1 S2 S3 является истинным
Семантика логики высказываний
(таблица истинности)
Логический вывод и логическое следствие
Логический вывод – это процесс получения новых высказываний из базы знаний: БЗ -i
Два желательных свойства алгоритма логического вывода: непротиворечивость и полнота.
Непротиворечивым (сохраняющим истинность)
называется алгоритм логического вывода, позволяющий получать только такие высказывания, которые действительно являются логическими следствиями из базы знаний. Противоречивый алгоритм создает такие высказывания, которые не имеют места на самом деле.
Алгоритм называется полным, если он позволяет вывести все высказывания, которые являются логическими следствиями базы знаний.
Проверка по моделям
•Простейший алгоритм логического вывода – проверка по моделям, в котором осуществляется перебор всех возможных моделей для проверки истинности высказывания во всех моделях, в которых истинна база знаний БЗ.
•Является непротиворечивым и полным.
•Может применяться лишь к конечной БЗ.
•Всего надо перебрать 2k возможных моделей (k – количество пропозициональных символов)
Хорновские базы знаний
Хорновские дизъюнкты являются дизъюнкциями литералов, среди которых положительным является один и только один литерал.
Хорновский дизъюнкт A B C, эквивалентен импликации
( A B ) C ,
Т.е. может интерпретироваться в виде правила «Если А и В, то С»
Базы знаний, состоящие из хорновских дизъюнктов, называются базами знаний в хорновской форме.
Почему хорновские базы знаний получили широкое распространение?
1) Дизъюнкт с одним положительным литералом эквивалентен импликации,
антецедент консеквент
где антецедент – коньюнкция положительных литералов, консеквент – единственный положительный литерал.
A B C … F G
Выражения такого вида очень хорошо подходят для описания ситуации во многих предметных областях.
Почему хорновские базы знаний получили широкое распространение?
2)Логический вывод с использованием хорновских дизъюнктов может осуществляться с помощью алгоритма прямого логического вывода и обратного логического вывода. Оба эти алгоритма являются очень естественными для человеческого восприятия.
Почему хорновские базы знаний получили широкое распространение?
3)Получение логических следствий помощью хорновских дизъюнктов может осуществляться за время, линейно зависящее от размера базы знаний. Это означает, что процедура логического вывода оказывается весьма недорогостоящей применительно ко многим базам знаний, встречающимся на практике.