Светлана Ахматова TVTB17. Содержание Введение Что такое логическое программирование? Planner Backtracking Стек Prolog 1.1 Пример программы: родственные. - презентация

1 Светлана Ахматова TVTB17

2 Содержание Введение Что такое логическое программирование? Planner Backtracking Стек Prolog 1.1 Пример программы: родственные отношения 1.2 Факты 1.3 Вопросы 1.4 Переменные

3 1.5 Конъюнкция целей 1.6 Правила 1.7 Конъюнкция в правилах 1.8 Переменные в теле правила 1.9 Cтруктура пролог-программы

4 Введение Искусственный интеллект это наука и технология создания интеллектуальных машин, особенно интеллектуальных компьютерных программ. ИИ связан со сходной задачей использования компьютеров для понимания человеческого интеллекта, но не обязательно ограничивается биологически правдоподобными методами. Логический подход к созданию систем искусственного интеллекта направлен на создание экспертных систем с логическими моделями баз знаний с использованием языка предикатов.

5 Что такое логическое программирование? Логическое программирование парадигма программирования, основанная на автоматическом доказательстве теорем, а также раздел дискретной математике, изучающий принципы логического вывода информации на основе заданных фактов и правил вывода.

6 Логическое программирование основано на теории и аппарате математической логики с использованием математических принципов резолюций. Логическое программирование относится к декларативному программированию, поскольку программа на нём скорее описывает свойство задачи, нежели алгоритм её решения. Такой идеал выражен в следующем уравнении Роберта Ковальского: Алгоритм = Логика + Управление

7 Planner Первым языком логического программирования был язык Planner, в котором была заложена возможность автоматического вывода результата из данных и заданных правил перебора вариантов (совокупность которых называлась планом). Planner использовался для того, чтобы понизить требования к вычислительным ресурсам (с помощью метода backtracking) и обеспечить возможность вывода фактов, без активного использования стека.

8 Backtracking Термин backtrack был введен в 1950 году американским математиком Дерриком Генри Лемером. Поиск с возвратом ( Backtracking) общий метод нахождения решений задачи, в которой требуется полный перебор всех возможных вариантов в некотором множестве М. Как правило позволяет решать задачи, в которых ставятся вопросы типа: «Перечислите все возможные варианты …», «Сколько существует способов …», «Есть ли способ …», «Существует ли объект…» и т. п.

9 Стек Стек ( англ. стопка) структура данных, в которой доступ к элементам организован по принципу LIFO(англ. last in first out, «последним пришёл первым вышел»).

10 Prolog Prolog - это язык программирования, используемый для решения задач, в которых действуют объекты и отношения между этими объектами. Программа на прологе состоит из предложений, которые могут быть фактами, правилами или вопросами. На языке Prolog было написано много экспертных систем для юридических, медицинских, финансовых и других проблемных областей.

11 1.1 Пример программы: родственные отношения

12 1.2 Факты Введем отношение -родитель- (parent) между объектами, parent (tom, bob). Это факт, определяющий, что Том является родителем Боба. parent - имя отношения, tom, bob - его аргументы. parent (pam, bob). parent (tom, bob). parent (tom, liz). parent (bob, ann). parent (bob, pat). parent (mary, ann). parent (pat, juli).

13 Эта программа состоит из семи предложений (утверждений), clause(клоз). Каждый клоз записан фактом в виде отношения parent. При записи фактов надо соблюдать следующие правила: 1) Имена всех отношений и объектов с маленькой буквы. 2) Сначала записывается имя отношения, затем в круглых скобках через запятую объекты. 3) В конце ставится точка.

14 1.3 Вопросы Вопрос в обычном прологе начинается с ?- Вопрос записывается также, как и факт. Например: 1) ? - parent (bob, pat) yes 2) ?-parent (bob,mary) no

15 1.4 Переменные Можно задать вопрос и узнать кто родитель liz: 1) ?-parent (X, liz) X= tom Вопрос : ?-parent (X, bob) X=tom X=pam

16 1.5 Конъюнкция целей Можно задать более общий вопрос: Кто является родителем родителя juli. Так как нет отношения grandparent, то можно разбить на два вопроса: 1) кто родитель juli. Предположим- Y. 2) кто родитель Y. Предположим- X. Вопрос: ?-parent (Y, juli), parent (X, Y). X=bob Y=pat

17 1.6 Правила Введем отношение peбенок child, обратное к parent "родитель". Можно было бы определить аналогично: child (liz, tom). Но можно использовать, что отношение child обратно к parent и записать в виде утверждения- правила : child(Y, X):-parent (X, Y). Правило читается так: Для всех X и Y Y -child X, если X -parent Y.

18 Правило отличается от факта тем, что факт всегда истина, а правило описывает утверждение, которое будет истинной, если выполнено некоторое условие. Поэтому в правиле выделяют: заключение условие child(Y, X) :- parent (X, Y). голова тело head body Если условие parent (X, Y). выполняется, то логическим следствием из него будет утверждение child(Y, X).

19 1.7 Конъюнкция в правилах Добавим еще одно отношение в базу данных, унарное, определяющее пол. male(tom). male(bob). male(jim). female(liz). female(pam). female(pat). female(ann). Теперь определим отношение mother. Оно описывается следующим образом: Для всех X Y X -mother Y, if X- parent Y и X -female

20 Таким образом правило будет mother(X, Y):-parent(X, Y), female(X). Можно записать mother(X, Y):-parent(X, Y), female(X). или mother(X, Y):- parent(X, Y), female(X). Запятая между двумя условиями означает конъюнкцию целей. Это означает, что два условия должны быть выполнены одновременно.

21 Как система ответит на вопрос? ?-mother (pam, bob). yes Находится правило mother, производится подстановка X=pam Y=bob Получаем правило mother(pam, bob):- parent(pam, bob), female(pam). Сначала удовлетворяются parent, а затем female Пролог отвечает: yes

22 1.8 Переменные в теле правила Определим отношение sister Для любых X и Y X sister Y, if у X и Y есть общий родитель, и X female Запишем правило на прологе sister (X, Y):- parent(Z,X), parent(Z,Y), female(X). Здесь Z-общий родитель. Z-некоторый, любой. Можно спросить: ?-sister(ann, pat).yes ?-sister(pat, pat). yes

23 1.9 Cтруктура пролог-программы предложение - факт, правило, вопрос clause fact, rule, goal cостав head head... ? | | body body..

24 Спасибо за внимание!