Antoshka

Путь к Файлу: /нгту / Введение в спец / AVDEENKO / ЛЕКЦИИ ИИС / Лекция 3_ИИС.ppt

Ознакомиться или скачать весь учебный материал данного пользователя
Скачиваний:   121
Пользователь:   Antoshka
Добавлен:   29.10.2014
Размер:   301.5 КБ
СКАЧАТЬ

Наверх страницы

Содержимое презентации:

Слайд 1

Лекция №3 • Синтаксис и семантика логики высказываний • Хорновские БЗ. • Алгоритм прямого и обратного вывода. • Синтаксис и семантика логической программы. • Понятие унификации

Слайд 2

Синтаксис логики высказываний • Выделяют атомарные и сложные высказывания. • Атомарные высказывания (неделимые синтаксические элементы) состоят из одного пропозиционального символа, для обозначения которых используются прописные символы P, Q, S, Каждый пропозициональный символ может быть либо истинным, либо ложным. • Два пропозициональных символа имеют постоянный смысл: True – тождественно истинное высказывание, False – тождественно ложное высказывание. • Сложные высказывания формируются из более простых высказываний с помощью логических связок: отрицание  (не), конъюнкция  (и), дизъюнкция  (или), импликация  (влечет за собой), двухсторонняя импликация  (если и только если). Правила формирования сложных высказываний: если S, S1 и S2 – высказывания пропозициональной логики, то высказываниями пропозициональной логики являются также  S, S1  S2 , S1  S2 , S1  S2 , S1  S2 .

Слайд 3

Семантика логики высказываний • Логические исчисления обладают так называемой встроенной семантикой: т.е. задав значения всем атомарным высказываниям, значения сложных высказываний вычисляются автоматически в соответствии с таблицей истинности. Это свойство называется композициональностью логики • В логике семантика языка определяет истинность каждого высказывания применительно к каждому из возможных наборов значений атомарных высказываний, называемых возможными моделями. Например в модели m = { S1= true , S2= false, S3= true } сложное высказывание S1  S2  S3 является истинным

Слайд 4

Семантика логики высказываний (таблица истинности) P Q  P PQ PQ PQ P  Q false false true false false true true false true true false true true false true false false false true false false true true false true true true true

Слайд 5

Логический вывод и логическое следствие Логический вывод – это процесс получения новых высказываний из базы знаний: БЗ- i  Два желательных свойства алгоритма логического вывода: непротиворечивость и полнота. Непротиворечивым (сохраняющим истинность) называется алгоритм логического вывода, позволяющий получать только такие высказывания, которые действительно являются логическими следствиями из базы знаний. Противоречивый алгоритм создает такие высказывания, которые не имеют места на самом деле. Алгоритм называется полным, если он позволяет вывести все высказывания, которые являются логическими следствиями базы знаний.

Слайд 6

Проверка по моделям • Простейший алгоритм логического вывода – проверка по моделям, в котором осуществляется перебор всех возможных моделей для проверки истинности высказывания  во всех моделях, в которых истинна база знаний БЗ. • Является непротиворечивым и полным. • Может применяться лишь к конечной БЗ. • Всего надо перебрать 2k возможных моделей (k – количество пропозициональных символов)

Слайд 7

Хорновские базы знаний Хорновские дизъюнкты являются дизъюнкциями литералов, среди которых положительным является один и только один литерал. Хорновский дизъюнкт  A   B  C, эквивалентен импликации ( A  B )  C , Т.е. может интерпретироваться в виде правила «Если А и В, то С» Базы знаний, состоящие из хорновских дизъюнктов, называются базами знаний в хорновской форме.

Слайд 8

Почему хорновские базы знаний получили широкое распространение? 1) Дизъюнкт с одним положительным литералом эквивалентен импликации, антецедент  консеквент где антецедент – коньюнкция положительных литералов, консеквент – единственный положительный литерал. A  B  C  …  F  G Выражения такого вида очень хорошо подходят для описания ситуации во многих предметных областях.

Слайд 9

Почему хорновские базы знаний получили широкое распространение? 2) Логический вывод с использованием хорновских дизъюнктов может осуществляться с помощью алгоритма прямого логического вывода и обратного логического вывода. Оба эти алгоритма являются очень естественными для человеческого восприятия.

Слайд 10

Почему хорновские базы знаний получили широкое распространение? 3) Получение логических следствий помощью хорновских дизъюнктов может осуществляться за время, линейно зависящее от размера базы знаний. Это означает, что процедура логического вывода оказывается весьма недорогостоящей применительно ко многим базам знаний, встречающимся на практике.

Слайд 11

Алгоритмы прямого и обратного логического вывода Основываются на применении правила Modus Ponens :   ,   α1 , … ,αn , α1  …  αn  β ————————————————— β

Слайд 12

Алгоритм прямого логического вывода • Начинает свою работу с известных фактов, содержащихся в БЗ. • Если для некоторой импликации становятся истинными все предпосылки, то ее заключение добавляется к базе знаний в соответствии с правилом Modus Ponens. • Процесс продолжается до тех пор, пока: - к базе знаний добавляется изначально заданный запрос q (алгоритм достигает успеха в доказательстве q), - новые факты не добавляются в базу знаний (алгоритм достиг фиксированной точки). Если при достижении фиксированной точки исходный запрос q не достигнут, то последний не может быть выведен из базы знаний.

Слайд 13

Алгоритм прямого логического вывода: пример

Слайд 14

Алгоритм прямого логического вывода: пример

Слайд 15

Алгоритм прямого логического вывода: пример

Слайд 16

Алгоритм прямого логического вывода: пример

Слайд 17

Алгоритм прямого логического вывода: пример

Слайд 18

Алгоритм прямого логического вывода: пример

Слайд 19

Алгоритм прямого логического вывода: пример

Слайд 20

Алгоритм прямого логического вывода: пример

Слайд 21

Алгоритм прямого логического вывода: пример

Слайд 22

Алгоритм обратного логического вывода • Действует в обратном направлении от запроса к данным. • Если запрос q содержится среди фактов, то на этом алгоритм завершает работу. • В противном случае алгоритм использует те импликации в базе знаний, для которых q является заключением: - Если все посылки найденной импликации являются фактами, то выводим q и заканчиваем доказательство. - Иначе ищем импликации для доказательства посылок.

Слайд 23

Алгоритм обратного логического вывода: пример

Слайд 24

Алгоритм обратного логического вывода: пример

Слайд 25

Алгоритм обратного логического вывода: пример

Слайд 26

Алгоритм обратного логического вывода: пример

Слайд 27

Алгоритм обратного логического вывода: пример

Слайд 28

Алгоритм обратного логического вывода: пример

Слайд 29

Алгоритм обратного логического вывода: пример

Слайд 30

Алгоритм обратного логического вывода: пример

Слайд 31

Алгоритм обратного логического вывода: пример

Слайд 32

Алгоритм обратного логического вывода: пример

Слайд 33

Алгоритм обратного логического вывода: пример

Слайд 34

Логика предикатов против логики высказываний • Логика высказываний предполагает, что мир состоит из фактов; • Логика предикатов (как и естественный язык) предполагает, что мир содержит: – Объекты: люди, дома, числа, цвета, мячи, … – Отношения: являться красным, круглым, быть братом, больше чем, лежит между, является частью, принадлежит, … – Функции: отец, лучший друг, плюс, …

Слайд 35

Логическое программирование базируется на логике предикатов

Слайд 36

Синтаксис и семантика логической программы Логическая программа представляет собой базу знаний, состоящую из предложений. Каждое предложение имеет синтаксис A :- B1, B2, … , Bn. где A, B1, B2, … , Bn – предикаты. Декларативный (логический) смысл предложения: B1, B2, … , Bn  A

Слайд 37

Синтаксис и семантика логической программы Предикат – это выражение вида pred (term1 ,...,termm) где pred – имя предиката (предикатный символ), term1 ,...,termm - термы. Декларативный смысл предиката и термов: предикат задает отношение между объектами, задаваемыми термами term1 ,...,termm .

Слайд 38

Синтаксис и семантика логической программы Терм – это константа, переменная или составной терм. Константа – число или атом. Атом – цепочка символов, начинается с маленькой буквы. Указывает на конкретный объект. Переменная – цепочка символов, начинается с большой буквы. Указывает на неопределенный объект. Составной терм – выражение вида: func (term1 ,...,termm) где func – имя функции (функциональный символ), term1 ,...,termm - термы. Позволяет реализовать понятие функции.

Слайд 39

Примеры предложений логической программы отец(олег,семен). мать(мария, семен). родитель (X,Y):- отец(X,Y); мать(X,Y). родитель (мария,семен). родители(X,Y,Z):- отец(X, Z), мать(Y,Z). прародитель(X,Y):- родитель(X,Z), родитель(Z,Y). предок(X,Y):- родитель(X,Y). предок(X,Y):- родитель(X,Z),предок(Z,Y). любит(X,поклонник(X)):- звезда(X).

Слайд 40

Унификация Унификация позволяет отождествлять формулы логики предикатов путем замены свободных переменных на термы. Подстановкой называется множество пар вида ={x1/t1, x2/t 2 ,…, xn/t n}, где i t i - терм, xi - переменная, не входящая в терм t i , причем xi  xj для любых ij. Подстановка может применяться к терму, атомарной формуле, высказыванию или к их множеству. Результат применения подстановки  к выражению  обозначается Subst(, ) (или ) и называется примером выражения. Пример  получается путем одновременной замены каждой переменной xi из  на терм ti .

Слайд 41

Унификация Например, подстановкой для двух выражений King(x)  Greedy(x) и King(John)  Greedy(y) является θ = {x/John,y/John} Унификатор выражений: Unify( ,) =  if  =  p q  Knows(John,x) Knows(John,Jane) Knows(John,x) Knows(y,OJ) Knows(John,x) Knows(y,Mother(y)) Knows(John,x) Knows(x,OJ)

Слайд 42

Унификация Например, подстановкой для двух выражений King(x)  Greedy(x) и King(John)  Greedy(y) является θ = {x/John,y/John} Унификатор выражений: Unify( ,) =  if  =  p q  Knows(John,x) Knows(John,Jane) {x/Jane} Knows(John,x) Knows(y,OJ) Knows(John,x) Knows(y,Mother(y)) Knows(John,x) Knows(x,OJ)

Слайд 43

Унификация Например, подстановкой для двух выражений King(x)  Greedy(x) и King(John)  Greedy(y) является θ = {x/John,y/John} Унификатор выражений: Unify( ,) =  if  =  p q  Knows(John,x) Knows(John,Jane) {x/Jane} Knows(John,x) Knows(y,OJ) {x/OJ,y/John} Knows(John,x) Knows(y,Mother(y)) Knows(John,x) Knows(x,OJ)

Слайд 44

Унификация Например, подстановкой для двух выражений King(x)  Greedy(x) и King(John)  Greedy(y) является θ = {x/John,y/John} Унификатор выражений: Unify( ,) =  if  =  p q  Knows(John,x) Knows(John,Jane) {x/Jane} Knows(John,x) Knows(y,OJ) {x/OJ,y/John} Knows(John,x) Knows(y,Mother(y)) {y/John,x/Mother(John)} Knows(John,x) Knows(x,OJ)

Слайд 45

Унификация Например, подстановкой для двух выражений King(x)  Greedy(x) и King(John)  Greedy(y) является θ = {x/John,y/John} Унификатор выражений: Unify( ,) =  if  =  p q  Knows(John,x) Knows(John,Jane) {x/Jane} Knows(John,x) Knows(y,OJ) {x/OJ,y/John} Knows(John,x) Knows(y,Mother(y)) {y/John,x/Mother(John)} Knows(John,x) Knows(x,OJ) {fail}


Внимание! Не забудьте ознакомиться с остальными документами данного пользователя!

Соседние файлы в текущем каталоге:

На сайте уже 21970 файлов общим размером 9.9 ГБ.

Наш сайт представляет собой Сервис, где студенты самых различных специальностей могут делиться своей учебой. Для удобства организован онлайн просмотр содержимого самых разных форматов файлов с возможностью их скачивания. У нас можно найти курсовые и лабораторные работы, дипломные работы и диссертации, лекции и шпаргалки, учебники, чертежи, инструкции, пособия и методички - можно найти любые учебные материалы. Наш полезный сервис предназначен прежде всего для помощи студентам в учёбе, ведь разобраться с любым предметом всегда быстрее когда можно посмотреть примеры, ознакомится более углубленно по той или иной теме. Все материалы на сайте представлены для ознакомления и загружены самими пользователями. Учитесь с нами, учитесь на пятерки и становитесь самыми грамотными специалистами своей профессии.

Не нашли нужный документ? Воспользуйтесь поиском по содержимому всех файлов сайта:



Каждый день, проснувшись по утру, заходи на obmendoc.ru

Товарищ, не ленись - делись файлами и новому учись!

Яндекс.Метрика