Общий обзор языка Пролог

Лекция 1 Общий обзор языка Пролог Содержание 1.1 Пример программы: родственные отношения. 1.2 Утверждения. 1.3 Факты. 1.4 Вопросы. 1.4.1 Переменные. 1.4.2 Конъюнкция целей. 1.5 Правила. 1.5.1 Конъюнкция в правилах. 1.5.2 Переменные в теле правила. 1.6 Структура Пролог-программы. Пролог - это язык программирования, используемый для решения задач, в которых присутствуют объекты и существуют отношения между этими объектами. Программа на Прологе находит решение путем логического вывода чего-то на основе некоторых уже известных фактов. Обычно Пролог-программа – это совокупность фактов и правил, позволяющих делать какие-либо заключения. Основными конструкциями языка Пролог являются факты, правила, вопросы. 1.1 Пример программы: родственные отношения Рассмотрим дерево родственных отношений: 1.2 Утверждения Программа на Прологе есть совокупность утверждений. Утверждения состоят из целей и хранятся в базе данных Пролога. Таким образом, база данных Пролога может рассматриваться как программа на Прологе. В конце каждого утверждения ставится точка. Утверждение также иногда называется предложением. Основная операция Пролога - доказательство целей, входящих в утверждение. Существуют два типа утверждений: • факт: это одиночная цель, которая, безусловно, истинна; • правило: состоит из одной головной цели и одной или более хвостовых целей, которые истинны при некоторых условиях. Разница между правилами и фактами чисто семантическая. Хотя для правил, мы используем синтаксис операторов, нет никакого синтаксического различия между правилом и фактом. 1.3 Факты Факты содержат отношения (или утверждения), которые всегда являются истинными (для данной программы). При записи фактов следует придерживаться следующих правил: • имена отношений и объектов должны начинаться со строчной буквы; • сначала записывается имя отношения, затем в круглых скобках через запятую – имена аргументов; • каждый факт заканчивается точкой. Введем отношение - родитель-(parent) между объектами. parent(tom, bob). Это факт, определяющий, что Tom является родителем Bob. parent - имя отношения, tom, bob - его аргументы. Теперь можно записать программу, описывающую все дерево родственных отношений. parent(pam, bob). parent(tom, bob). parent(tom, liz). parent(bob, ann). parent(bob, pat). parent(marry, ann). parent(pat, julie). Эта программа состоит из семи предложений. Каждый факт записан в виде отношения parent. Еще пример факта: like(bob, pam). Совокупность фактов в Прологе называется базой данных. 1.4 Вопросы После того как мы сообщили программе факты (создали базу данных) и правила, можно задавать Пролог-программе вопросы, касающиеся этих предложений. Эти вопросы должны быть того же типа, что и описанные в программе отношения. Вопрос – это предложение, состоящее из одного тела. Вопрос обычно в Прологе начинается с ?- Например: ?-parent(bob, pat). Yes Когда Пролог получает вопрос, он пытается сопоставить его с фактами или с правилами, у которых имя отношения совпадает с именем запроса. Если такое совпадение находится, то проверяются имена аргументов. После чего выдается ответ: да (yes). На вопрос ?-parent(bob, marry). No Ответ будет нет (no), так как такого факта в базе данных или правила нет. 1.4.1 Переменные Можно задать вопрос и узнать кто родитель liz: ?-parent(X, liz). X=tom Здесь X - переменная. Ее величина неизвестна и она может принимать значения. В данном случае ее значением будет объект, для которого это утверждение истинно. Вопрос: ?-parent(X, bob). X=tom X=pam Можно задать вопрос, кто является чьим родителем. Или найти такие X и Y, что X является родителем Y. ?-parent(X, Y). X=pam Y=bob Y=tom X=bob и т.д. 1.4.2 Конъюнкция целей Можно задать более общий вопрос: Кто является родителем родителя Julie? Так как нет отношения grandparent, то можно вопрос разбить на две части: 1. Кто родитель julie. Предположим- Y. 2. Кто родитель Y. Предположим- X. Тогда составной вопрос: ?-parent(Y, julie), parent(X, Y). X=bob Y=pat При поиске решения сначала находится Y, а затем по второму условию Х. Вопрос: Кто внуки Tom?: ?-parent(tom, Y), parent(Y, X). Y=bob X=ann Y=bob X=pat И наконец, есть ли у ann и pat общий родитель? ?-parent(Y, ann), parent(Y, pat). Y=bob 1.5 Правила Введем отношение ребенок child, обратное к parent (родитель). Можно было бы определить аналогично: child(liz, tom). Но можно использовать, что отношение child обратно к parent и записать данное утверждения в виде правила: child(Y, X):-parent(X, Y). Правило читается так: Для всех X и Y. Y-child X, если X-parent Y. Правило отличается от факта тем, что факт всегда истина, а правило описывает утверждение, которое будет истинной, если выполнено некоторое условие. Поэтому в правиле выделяют: заключение и условие child(Y, X):-parent(X, Y). голова тело Если условие parent(X, Y) выполняется, то логическим следствием из него будет утверждение child(Y, X). Как правило используется Прологом? Зададим вопрос ?-child(liz, tom). В программе нет данных о child. Но есть правило, которое верно для всех X и Y, в том числе для liz и tom. Мы должны применить правило для этих значений. Для этого надо подставить в правило вместо X-tom, а вместо Y-liz. В этом случае говорят, что переменные будут связаны, а операция будет называться подстановкой. Получаем конкретный случай для правила child(liz, tom):-parent(tom, liz). Условная часть приняла вид parent(tom, liz). Теперь надо выяснить выполняется ли это условие. Исходная цель child(liz, tom) заменяется подцелью parent(tom, liz), которая выполняется, поэтому Пролог ответит "yes". 1.5.1 Конъюнкция в правилах Добавим еще отношения в базу данных, унарное, определяющее пол. male(tom). male(bob). female(pam). female(marry). female(liz). female(ann). female(pat). female(jolie). Теперь определим отношение mother. Оно описывается следующим образом: Для всех X и Y. X-mother Y, если X- parent Y и X -female. Таким образом правило будет mother(X, Y):-parent(X, Y), female(X). Запятая между двумя условиями означает конъюнкцию целей. Это означает, что два условия должны быть выполнены одновременно. Как система ответит на вопрос? ?-mother(pam, bob). Yes Находится правило mother, производится подстановка X=pam, Y=bob и получается правило mother(pam, bob):-parent(pam, bob), female(pam). Сначала удовлетворяются parent, а затем female. Пролог отвечает: yes Вопрос: ?-mother(X, bob). X=pam 1.5.2 Переменные в теле правила Определим отношение sister. Для любых X и Y. X sister Y, если у X и Y есть общий родитель, и X female. Запишем правило на Прологе sister(X, Y):-parent(Z, X), parent(Z, Y), female(X). Здесь Z-общий родитель. Можно спросить ?-sister(ann, pat). Yes ?-sister(pat, pat). Yes Ответ будет "yes". Так как мы не потребовали, чтобы X и Y были разные. Добавим в исходное отношение условие, которое будет указывать на то, что X и Y разные. sister(X, Y):-parent(Z, X), parent(Z, Y), female(X), X<>Y. 1.6 Структура Пролог-программы Предложение факт правило вопрос состав голова. голова:- тело. ?-тело.