Antoshka

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

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

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

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

Слайд 1

Лекция №4 Вывод в логике предикатов. Обратный вывод в логическом программировании.

Слайд 2

План лекции • Унификация • Обобщенное правило Modus Ponens • Прямой логический вывод • Обратный логический вывод • Обратный вывод в логическом программировании.

Слайд 3

Унификация Унификация позволяет отождествлять формулы логики предикатов путем замены свободных переменных на термы. Подстановкой (унификатором) называется множество пар вида ={x1 /t1 , x2 /t2 ,…, xn /tn }, где ti - терм, xi - переменная, не входящая в терм ti . Подстановка может применяться к терму,предикату,предложению. Результат применения подстановки к выражению обозначается Subst( , ) (или ). Пример: Для унификации выражений Knows(John,x) и Knows (y,z) можно использовать подстановки θ1 = {y/John, x/z } или θ2 = {y/John, x/John, z/John} В результате применения подстановки θ1 получаем Knows(John,z)= Knows(John,z) В результате применения подстановки θ2 получаем Knows(John, John)= Knows(John, John)

Слайд 4

Наибольший общий унификатор • Унификатор θ1 = {y/John, x/z } является более общим , чем унификатор θ2 = {y/John, x/John, z/John}, так как θ2 = Subst ( { z/John }, θ1 ) = θ1 { z/John } Утверждение: Для любой унифицируемой пары выражений существует единственный наибольший общий унификатор (НОУ), уникальный с точностью до переименования переменных НОУ= { y/John, x/z }

Слайд 5

Унификация Еще один пример: унификатором для двух выражений King(x) and Greedy(x) и King(John) and Greedy(y) является θ = {x/John,y/John} Унификатор выражений: Unify( , ) = if = 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)

Слайд 6

Унификация Например, подстановкой для двух выражений King(x) and Greedy(x) и King(John) and Greedy(y) является θ = {x/John,y/John} Унификатор выражений: Unify( , ) = if = 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)

Слайд 7

Унификация Например, подстановкой для двух выражений King(x) and Greedy(x) и King(John) and Greedy(y) является θ = {x/John,y/John} Унификатор выражений: Unify( , ) = if = 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)

Слайд 8

Унификация Например, подстановкой для двух выражений King(x) and Greedy(x) и King(John) and Greedy(y) является θ = {x/John,y/John} Унификатор выражений: Unify( , ) = if = 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)

Слайд 9

Унификация Например, подстановкой для двух выражений King(x) and Greedy(x) и King(John) and Greedy(y) является θ = {x/John,y/John} Унификатор выражений: Unify( , ) = if = 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}

Слайд 10

Обобщенное правило Modus Ponens p1 ', p2 ', … , pn ', ( p1 p2 … pn q) , Subst(θ,q) где Subst(θ, pi ') = Subst(θ, pi) для всех i Пример, Дано: p1 ' = King(John) p2 ' = Greedy(y) King(x) Greedy(x) Evil(x) p1 = King(x), p2 = Greedy(x), q = Evil(x) θ = {x/John,y/John} Subst(θ,q) = Evil(John)

Слайд 11

Пример построения базы знаний Постановка задачи: • Закон гласит, что продажа оружия недружелюбным странам, осуществляемая любым американским гражданином, является преступлением. Ракета является оружием. Если какая-либо страна является врагом Америки, то эта страна является недружелюбной. Полковник West является американским гражданином. Полковник West продал государству Nono, являющемуся врагом Америки, все ракеты. • Является ли полковник West преступником?

Слайд 12

Представление задачи с помощью хорновских дизъюнктов (БЗ) ... Для американца преступлением является продажа оружия недружелюбным странам: American(x) Weapon(y) Sells(x,y,z) Hostile(z) Criminal(x) Страна Nono …имеет ракеты, т.e., x Owns(Nono,x) Missile(x): Owns(Nono,M1 ) and Missile(M1 ) …все ракеты проданы стране Nono полковником по имени West Missile(x) Owns(Nono,x) Sells(West,x,Nono) Ракеты являются оружием: Missile(x) Weapon(x) Враг Америки считается «недружелюбным»: Enemy(x,America) Hostile(x) Полковник West является американцем … American(West) Страна Nono, враг Америки… Enemy(Nono,America)

Слайд 13

Алгоритм прямого вывода 1) Прямой вывод начинается с известных фактов, содержащихся в базе знаний БЗ. 2) Активизируются правила, антецеденты которых могут быть унифицированы (с подстановкой ) с имеющимися фактами, 3)В соответствии с обобщенным правилом Modus Ponens к известным фактам добавляются заключения этих правил после применения к ним подстановки . Процесс продолжается до тех пор, пока не будет получен ответ на запрос, или пока алгоритм не достигнет фиксированной точки.

Слайд 14

Алгоритм прямого вывода

Слайд 15

Алгоритм прямого вывода

Слайд 16

Алгоритм прямого вывода

Слайд 17

Алгоритм обратного вывода 1) Действует в обратном направлении, от цели q к известным фактам. 2) Цель q‘ унифицируется с заголовками правил, имеющихся в БЗ: p1 p2 … pn q где Unify(q, q‘ )= . 3) Subst( , p1 p2 … pn ) Subst( ,q). 4) В случае успешной унификации генерируется конъюнкция подцелей Subst( , p1) Subst( ,p2) … Subst( ,pn), каждая из которых доказывается самостоятельно. 5) Процесс продолжается до полного подтверждения всех сгенерированных в процессе доказательства подцелей фактами, имеющимися в БЗ. В процессе доказательства производится композиция всех получаемых подстановок, что приводит к получению итоговой подстановки, являющейся решением задачи.

Слайд 18

Алгоритм обратного вывода

Слайд 19

Алгоритм обратного вывода

Слайд 20

Алгоритм обратного вывода

Слайд 21

Алгоритм обратного вывода

Слайд 22

Алгоритм обратного вывода

Слайд 23

Алгоритм обратного вывода

Слайд 24

Алгоритм обратного вывода

Слайд 25

Алгоритм обратного вывода

Слайд 26

Логическое программирование. Декларативная и процедурная семантика Логическая программа обладает как декларативной, так и процедурной семантикой. Правило в программе на языке Prolog вида A :- B1 , B2 , … , Bn . можно трактовать двояко: 1) как логическое высказывание B1 B2 … Bn A (декларация) 2) как определение процедуры A, утверждающее, что для выполнения A надо последовательно выполнить подпрограммы B1 , B2 , … , Bn .

Слайд 27

Обратный вывод в логическом программировании Цель : g Правило: a:- b1,…, bm. ___________________________________ Применение обобщенного правила Modus Ponens состоит из следующих шагов: 1) Унификация цели g и заголовка правила a = Unify(g, a) 2) Формируем новую цель - b1’ ,…, bm’ где b1’ = Subst( , b1), …, bm’ = Subst( , bm) К полученным целям вновь применяется Modus Ponens, и т. д., пока все цели не подтвердятся фактами.

Слайд 28

Логическая программа. Пример использования составных термов parent(person("Bill", male), person("John", male)). parent(person("Pam", female),person("Bill", male)). parent(person("Pam", female),person("Jane", female)). parent(person("Jane", female), person(("Sue", female)). father(P,person(Name, male)) :- parent(P,person(Name, male)). mother(P,person(Name,female)) :-parent(P,person(Name,female)). grandFather(Person,TheGrandFather):- parent(Person, ParentOfPerson), father(ParentOfPerson,TheGrandFather). grandMother(Person,TheGrandMother):- parent(Person, ParentOfPerson), mother(ParentOfPerson,TheGrandMother).

Слайд 29

Дерево вывода (алгоритм обратного вывода) parent(person("Bill", male),person(Name, female)) parent(person("Jane", female),person(Name, female)) grandMother(person("Pam", female), GMother) parent(person("Pam", female), Parent), mother(Parent,GMother) mother(person("Bill", male),GMother) mother(person("Jane", female),GMother) {Person / person("Pam", female)} {Parent / person("Bill", male)} {GMother / person(Name, female)} {GMother / person(Name, female)} {Parent / person("Jane", female)} {Name / "Sue"} Yes GMother = person("Sue", female) No

Слайд 30

Возможные темы РГР 1) планирование финансовых ресурсов предприятия, 2) выбор коммерческого банка, 3) выбор стратегии производства, 4) оценка конкурентоспособности продукции, 5) выбор поставщика продукции, 6) подбор кадров, 7) подбор оптимального тарифного плана сотовой связи, 8) определение качества продукции, 9) определение соответствия сотрудника занимаемой должности.


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

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

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

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

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



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

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

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