Слайд 2
Основные элементы языка Пролог
Алфавит языка Пролог включает следующие
символы:
A, B, C, …, Z, a, b, c,…,z —
прописные и строчные буквы латинского алфавита.
0,1,2,3,4,5,6,7,8,9 — цифры.
+ - = * / < > [ ] : ; , | . —специальные знаки.
Основные конструкции логического программирования - термы и утверждения.
Слайд 3
Определение и классификация термов
Логические термы
Простые
термы
Составные термы
Константы
Переменные
Числа
Атомы
Строки
Слайд 4
Числовые константы
Числа в языке Пролог используются целые и
вещественные.
Целые числа записываются так же, как в любом
другом языке программирования; целые отрицательные числа записываются со знаком, в записи положительных чисел знак можно опустить, например, 135, 0, -89.
Вещественные константы могут быть представлены в форме с фиксированной точкой и с плавающей точкой, например, 135.712 и 0.135712E+3,соответственно.
Символьные атомы не должны содержать пробелы.
Например,
may, all, factorial — символьные атомы.
Например, :- >= *.
Например, ‘Mary’, ‘Маша’,’1_мая’, ‘Arity_Prolog’.
Последовательность латинских букв, цифр и знака подчеркивания, начинающая со строчной буквы.
Последовательность специальных знаков есть атом
Любое слово из букв латинского и русского алфавита и цифр, заключенное в апострофы
Атомы
Слайд 6
Переменные
Имя переменной в Прологе —
это последовательность латинских букв, цифр и знака подчеркивания, начинающаяся
с прописной буквы или знака подчеркивания.
Например, X, All, S1 — переменные.
Переменные используются для представления объектов, значения которых определяются в ходе решения задачи. Переменные записываются в качестве аргументов предикатов в Пролог-программе и в запросах.
Слайд 7
Анонимные переменные
Если значение аргумента предиката не принимается
во внимание, то этот аргумент обозначается анонимной переменной, то
есть вместо имени переменной указывается знак подчеркивания «_».
Слайд 8
Строки
Строки — это последовательности символов, заключенная в апострофы.
Строки используются в задачах обработки текстов на естественных языках.
'' — пустая строка. Строки могут включать пробелы, например, '1 января 2003 года ' есть строка, и 'Turbo-Prolog' тоже строка.
Слайд 9
Составные термы
Составной терм — это конструкция вида f(t1,t2,…,tk),
где f — символьный атом, определяющий функциональную константу или
главный функтор, а t1,t2,…,tk — термы, каждый из которых может быть составным термом. Составной терм по-другому называется структурой.
Слайд 10
Примеры составных термов
book(Author,Title,Year) — пример составного терма.
.(H,T) –
список, пример составного терма.
Слайд 11
Представление фактов
Самая простая программа на Прологе является множеством
фактов.
Факт — это предикатная структура, заканчивающаяся точкой, которая
записывается следующим образом:
<имя предиката>(<терм1>,<терм2>,…,<термn>).
Слайд 12
Представление фактов (продолжение)
Факт представляет собой утверждение о том,
что соблюдается некоторое отношение. С их помощью можно выражать
произвольные отношения между объектами.
Например, student(‘Иванов’,’МГГУ’).
Этот факт определяет отношение между термами, первым из которых является фамилия студента, а вторым ⎯место его учебы.
Слайд 13
Синтаксические правила записи фактов:
Имя предиката в утверждении-факте есть
символьный атом.
После имени предиката записывается список аргументов в круглых
скобках. Между именем предиката и открывающей скобкой ‘(‘ не должно быть пробела.
Слайд 14
Синтаксические правила записи фактов:
3. Возможны нуль—местные предикаты в фактах,
т.е. предикаты, не имеющие аргументов.
4. В качестве аргументов в списке
могут быть как переменные, так и константы.
5. В конце факта обязательна точка.
Слайд 15
Переменные в фактах
Переменные в фактах неявно связываются квантором
всеобщности. Это означает, что факт
p(T1,T2,…Tn).
где Ti –переменные
следует понимать так
∀(T1) ∀(T2)… ∀(Tn) p(T1,T2,…Tn) —истина.
Факты, содержащие переменные, называются универсальными.
Слайд 16
Примеры универсальных фактах
Примерами универсальных фактов являются следующие утверждения:
plus(X,0,X).
что означает, сумма любого числа Х с нулем равна
X.
proiz(X,0,0).
что означает, произведение любого числа Х с нулем равна 0.
Слайд 17
Представление правил
Правила ⎯ это средство определения новых утверждений
с помощью уже существующих в Пролог-программе утверждений (фактов и
правил).
С точки зрения синтаксиса языка Пролог правило ⎯это утверждение вида
A:⎯ B1,B2,…Bn. (n≥0)
где A ⎯ заголовок правила, а конъюнкция предикатов B1,B2,…Bn
называется телом правила.
Слайд 18
Переменные в правилах
В правилах, так же как и
в фактах, переменные неявно связаны квантором всеобщности.
Например, утверждение
«Точка с координатами (X,Y) принадлежит окружности с радиусом, равным 2, и с центром в точке начала координат, если X2+Y2=4.»
На Прологе будет записано следующим образом:
circle(X,Y):⎯ X*X+Y*Y=4.
что означает для любых X и Y, таких что X*X+Y*Y*=4, точка (X,Y) принадлежит окружности с радиусом, равным 2, и с центром в точке начала координат.
Слайд 19
Процедуры
Набор правил, заголовки которых имеют одно и то
же имя и арность (число аргументов), описывает одно и
то же отношение и называется процедурой.
Правила, составляющие одну и ту же процедуру, должны следовать в тексте программы подряд. В процедуру нельзя включать правила с другим заголовком.
Слайд 20
Область действия переменных
Логические переменные служат для
обозначения неопределенных объектов.
Областью действия переменной является
одно утверждение (факт или правило).
Слайд 21
Подстановки
Подстановкой называется конечное
(возможно, пустое) множество пар вида
Xi
= ti, где Xi⎯переменная, а ti⎯терм, не
содержащий переменную Xi.
Слайд 22
Подстановки и конкретизация переменных
Результат применения подстановки θ к
утверждению A обозначается Aθ и получается путем замены каждого
вхождения в A каждой переменной Xi на соответствующий терм ti.
С помощью подстановок производится конкретизация переменных (аналог присвоения значений) .
Слайд 23
Примеры утверждений
Утверждение B является примером утверждения A, если
найдется такая подстановка θ, что B=Aθ. Например, факт summa(1,2,3),
которое означает, что 1+2=3, является примером утверждения summa(X,Y,3) при применении подстановки θ={X=1,Y=2}.
Утверждение С называется общим примером утверждений A B, если найдутся такие подстановки θ1 и θ2, что C=Aθ1 и C=Bθ2, т.е. C является примером A и B одновременно. Например, факт summa(1,2,3) является общим примером утверждений summa(X,2,Z) и summa(1,Y,Z) при применении подстановок θ1={X=1,Z=3} и θ2={Y=2,Z=3}.
Слайд 24
Примеры утверждений
Утверждение B является примером утверждения A, если
найдется такая подстановка θ, что B=Aθ.
Например, факт summa(1,2,3),
которое означает, что 1+2=3, является примером утверждения summa(X,Y,3) при применении подстановки θ={X=1,Y=2}.
Слайд 25
Вопросы (запросы).
Вопрос (целевое утверждение) ⎯ это средство извлечения
информации из логической программы.
С помощью вопроса выясняется, истинно
ли некоторое утверждение или нет. С точки зрения логики поиск ответа на вопрос состоит в определении того, является ли утверждение (вопрос) логическим следствием программы или нет.
Слайд 26
Простые вопросы
Вопросы, состоящие из одной цели, называются
простыми вопросами.
Слайд 27
Конъюнктивные вопросы
Вопрос, включающий в себя конъюнкцию предикатов p1,p2,…,pn
, называется конъюнктивным вопросом.
Каждый предикат pi называется целью.
Конъюнктивный вопрос ⎯ это конъюнкция целей.
Слайд 28
Переменные в вопросах
Вопрос, не содержащий переменных, называется основным
вопросом, а вопрос, включающий переменные, называется неосновным.
Переменные в
вопросах неявно связаны квантором существования.
Слайд 29
Переменные в вопросах
Вопрос
Goal: p(X1,X2,…Xn).
где X1,X2,…Xn⎯переменные, предполагает
утвердительный ответ, если существует такой набор термов t1,t2,…tn, что
подстановка {X1=t1,X2=t2,…Xn=tn} в предикат p дает результат “истина”.
Если существует, хотя бы одна такая подстановка, то вопрос
Goal: p(X1,X2,…Xn).
выводим из логической программы, т.е. является логическим следствием программы.
Слайд 30
Общие переменные в конъюнктивных вопросах
Конъюнктивные вопросы обычно содержат
общие переменные. Переменные называются общими, если они входят в
две или более цели конъюнктивного запроса.
Слайд 31
Пример простой Пролог⎯программы
Программа «Родственники» является примером простой Пролог⎯программы.
Пусть имеется генеалогическое дерево, определяющее степень родства между людьми.
Рис.3
Слайд 32
Отношение parent
Родственные отношения можно записать с помощью
фактов, соответствующие
отношению
parent(,)
parent(‘Памелла’,’Джон’).
parent(‘Памелла’,’Элизабет’).
parent(‘Том’,’Джон’).
parent(‘Том’,’Элизабет’).
parent(‘Джон’,’Анна’).
parent(‘Джон’,’Пат’).
parent(‘Элизабет’,’Эд’).
parent(‘Пат’,’Джим’).
Слайд 33
Отношение person
Расширим эту программу фактами, определяемыми
схемой отношения person(,,):
person(‘Памелла’,’ж’,72).
person(‘Том’,’м’,78).
person(‘Джон’,’м’,42).
person(‘Элизабет’,’ж’,35).
person(‘Эд’,’м’,14).
person(‘Анна’,’ж’,20).
person(‘Пат’,’ж’,25).
person(‘Джим’,’м’,3).
Отношение
person определяет характеристики
человека
Слайд 34
Текст программы
parent(‘Памелла’,’Джон’).
parent(‘Памелла’,’Элизабет’).
parent(‘Том’,’Джон’).
parent(‘Том’,’Элизабет’).
parent(‘Джон’,’Анна’).
parent(‘Джон’,’Пат’).
parent(‘Элизабет’,’Эд’).
parent(‘Пат’,’Джим’).
person(‘Памелла’,’ж’,72).
person(‘Том’,’м’,78).
Слайд 35
Текст программы
person(‘Джон’,’м’,42).
person(‘Элизабет’,’ж’,35).
person(‘Эд’,’м’,14).
person(‘Анна’,’ж’,20).
person(‘Пат’,’ж’,25).
person(‘Джим’,’м’,3).
Слайд 36
Примеры вопросов к программе «Родственники»
Вопрос 1.
Вопрос ”Является ли
Пат родителем Джима? ” на Прологе можно задать следующим
образом:
? - parent(‘Пат’,’Джим’).
Пролог-система будет искать в программе факт, совпадающий с вопросом, и, обнаружив такой факт, система выдаст ответ ‘YES’.
В случае, когда соответствующий факт не обнаружен, система выдаст ответ ‘NO’.
Слайд 37
Примеры вопросов к программе «Родственники»
Вопрос 2.
Вопрос ”Кто отец
Элизабет и сколько ему лет? ” на Прологе можно
задать следующим образом:
? - parent(Х,’Элизабет’),person(X,'м', Y).
Пролог-система выдаст ответ:
X=Том
Y=78
YES
Если возраст не интересует пользователя, то в вопросе используется анонимные переменные, обозначаемые знаками подчеркивания ‘_’.
Слайд 38
Примеры вопросов к программе «Родственники»
Вопрос 3.
Вопрос ”Кто отец
Элизабет? ” на Прологе можно задать следующим образом:
? -
parent(Х,’Элизабет’),person(X,'м', _).
Пролог-система выдаст ответ:
X=Том
YES
Слайд 39
Примеры вопросов к программе «Родственники»
Вопрос 3.
Приведенные примеры вопросов
относятся к
программе, состоящей из одних фактов. Для того
чтобы сократить
и упростить вопросы в Пролог
программах задаются правила.
Вопрос 3 можно упростить, если задать следующее
правило:
“X является отцом Y, если X является родителем Y,
и X – мужчина.”
На языке Пролог это правило записывается так:
father(X,Y):-parent(X,Y),person(X,’м’,_).
Слайд 40
Примеры вопросов к программе «Родственники»
Вопрос 3.
А вопрос 3
записывается следующим образом:
? - father(X,’Jim’).
Пролог-система выдаст тот же ответ:
X=Том
YES
Слайд 41
Лабораторная работа № 1. Простейшая программа на языке
Пролог.
Необходимо выполнить следующие действия:
1. Описать с помощью фактов 4-уровневовое
генеалогическое дерево
в Пролог⎯программе
“Родственники”, включающей предикаты parent и
person.
2. Написать правила, определяющие следующие
отношения:
“X является отцом Y” .
“X является бабушкой Y” .
“X является сестрой Y” .
“X является племянником Y” .
“X является племянницей Y” .
