Аннотация: Общая характеристика языка Пролог: базы знаний и экспертные системы. Объекты и термы Пролога: объекты Пролога — имена, переменные и списки; основные и неосновные термы; атомы. Факты Пролога: синтаксис фактов; универсальные факты. Правила Пролога: проблема недостаточности фактов для описания базы знаний; синтаксис правила — заголовок и тело правила; процедура как объединение правил с одним заголовком; программа Пролога как совокупность фактов и правил. Запросы Пролога: синтаксис запроса; ответ на запрос без переменных; запрос с переменными и интерпретация переменных при выполнении программы; примеры программ с запросами для них.
Общая характеристика языка Пролог
Математическая логика дает нам ясный и точный язык для явного выражения знаний, гипотез и целей. Возможность машинного доказательства теорем , основанного на специальном выводе, названном принципом резолюций , впервые была получена Дж. Робинсон в 1965 году. Это привело к желанию построить язык программирования , который позволил бы реализовать одну из интеллектуальных сторон деятельности человека — проведение рассуждений в виде программ.
Вводная лекция по логическому программированию. Язык программирования Пролог на примерах
В начале 70-х годов прошлого века группой под руководством А. Колмероэ в Марселе на Фортране была написана программа для доказательства теорем , названная Прологом (от Programmation en Logique). Это привело в конце десятилетия к разработке языка Пролог и в дальнейшем развитию этого языка и в целом направления, которое получило название логического программирования.
Язык Пролог близок к модели Маркова: также основой является поиск подходящей подстановки — интерпретация переменных . Но подстановки ищутся в правилах языка (аналог рефал-предложений ), и целью является именно поиск подстановки .
Программа на Прологе состоит из правил , которые представляют собой продукции с предикатами (относительно объектов) в левой и правой части. Тем самым программа Пролога выражает некоторые знания о внешнем мире (задаче или группе задач), необходимые для решения задач. Правила, не содержащие посылки в продукции, называются фактами , а вся система правил программы образует базу знаний .
Вопрос задачи, называемый запросом , — это также некоторый предикат , истинностью которого мы интересуемся. Если запрос не содержит переменных , то вычисление его значения дает ответ «Да» при его истинности либо ответ «Нет» при его ложности. Если же в предикате запроса есть переменные , то ищутся их значения ( интерпретация ), при которых этот предикат и все предикаты программы становятся истинными. В этом и состоят вычисления программы на Прологе.
Так как каждый предикат — это функция , то Пролог является языком функционального программирования.
Итак, в языке Пролог рассматриваются объекты и 3 вида утверждений относительно объектов: факты, правила и запросы. Единственной структурой данных является терм .
Объекты и термы Пролога
Объектами Пролога являются
- имена (начинаются со строчной буквы), строки символов (заключаются в апострофы ) и числа — константные объекты или константы; например, автомобиль, дом, иван, ‘a+b’ , ‘X’ , 123;
- переменные — могут принимать значения других объектов, и мы их будем писать прописными латинскими буквами: например, X, A, W ;
- списки — их элементами являются любые объекты; списки мы заключаем в квадратные скобки, разделяя элементы запятыми; например, [] — пустой список (он является константой, мы его будем обозначать также nil и любой список завершать этим элементом, чтобы показать конец списка), [a, b, c, nil ] — список, состоящий из трех констант a , b и c ; [X, [b, Y, ‘X’, nil ], nil ] — список, состоящий из двух элементов, первый из которых — переменная X , а второй — список из трех элементов: имени b , переменной Y и строки ‘X’ .
Завершающий список элемент nil можно при записи опускать, подразумевая его в необходимых случаях. Для конкатенации (соединения) списков и элементов в один список используется точка как бинарная операция соединения левой части ( головы списка ) и правой части ( хвоста списка ). В случае операции конкатенации квадратные скобки на нулевом уровне можно опускать. Например, a.X.Y.a при X=b , Y=c есть список [a, b, c, a] , также при X=[b] , Y=[c] есть тот же список , а при X=[b, [d, e]] и Y=[[c]] есть список [a, b, [d, e], [c], a] .
Что за язык программирования Пролог такой? Душкин объяснит
Теперь индуктивно введем понятие терма . Термами являются объекты Пролога. Кроме того, термами являются составные термы . Составной терм образуется из имени функции и списка аргументов (термов Пролога) в круглых скобках. Синтаксически составной терм имеет вид
f(t1. tn),
— аргументы.
Примерами составных термов являются: холодный (вода), отец (иван, петр), list(d, list(b, nil )) и bintree(bintree( nil , 7, nil ), L, 12) .
В первом примере составным термом является высказывание с именем булевой функции 1 аргумента-константы, которое имеет логическое значение истина или ложь .
Во втором примере отношение «иван является отцом петра» задается как булева функция с 2 аргументами-константами.
В третьем примере бинарная функция с именем list и двумя аргументами имеет в качестве первого аргумента константный объект d , а в качестве второго аргумента — составной терм с именем той же функции и возвращает, по-видимому, список .
В четвертом примере функция с именем bintree и тремя аргументами возвращает в виде списков бинарное дерево с корнем 7, правым сыном 12 и левым сыном, который определяется переменной L.
Термы , в которые не входят переменные, назовем основными , а термы , содержащие переменные, — неосновными . Так, три первых примера выше являются основными термами , а четвертый пример — неосновным термом .
В логическом программировании основной структурой является предикатная функция, описываемая составным термом, которая имеет истинностное значение (истина или ложь ), возможно зависящее от значений аргументов. Такой предикат называется атомарным, или атомом .
Факты
Факты — это простейшие утверждения относительно объектов программы, которые считаются истинными, т. е. имеют смысл аксиом программы. Каждый факт оформляется в виде атомарного предиката и стрелки влево, которая находится справа от него. Так, в следующем примере
мужчина (иван)
задается, что объекты иван и петр являются мужчинами , что иван является отцом петра и что дважды два — четыре.
Почему ставится стрелка? Общий вид записи продукции «если A , то B «, где A и B — предикаты, выражается на Прологе следующим образом:
Факт не имеет посылки и читается «то B «, т. е. утверждение B рассматривается как истинный факт.
Множество фактов образуют простейшую программу Пролога. Но атомарный предикат факта может содержать переменные в качестве аргументов или неосновные термы . В этом случае по умолчанию считается, что добавлен квантор всеобщности с переменными предиката. Такие факты называются универсальными : они истинны для любых значений переменных. Например,
любит (X, яблоко)
означает, что любой объект программы «любит яблоко». Универсальные факты сокращают запись программы.
Источник: intuit.ru
Пример программы на языке Пролог
Предположим, надо определить, кто является сестрой Ann?
Тот факт, что Tom является родителем Bob (стрелки на рисунке) можно записать следующим образом:
parent- имя отношения –предикат
tom,bob –параметры (аргументы) отношения.
Имена собственные являются константами и в Прологе пишутся со строчной буквы.
Программа на Прологе для ответа на вопрос, кто является сестрой Ann имеет следующий вид:
Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:
Самое популярное на сайте:
Методология и методы психологии Методология и методы психологии. Требования к методам психологических исследований: валидность.
Средства ЛФК. Классификация физических упражнений в ЛФК и их характеристика Основное средство ЛФК — физические упражнения, применяемые в соответствии с задачами лечения, с учетом этиологии, патогенеза.
Этапы обучения двигательным действиям Учет закономерностей формирования двигательных умений и навыков определяет практические задачи обучения детей на каждом этапе в.
Причины, этапы и итоги перестройки (1985-1991) Причины, этапы и итоги перестройки (1985-1991) Причины перестройки Командная экономика не смогла далее провести модернизацию, т.
АЛГОРИТМ КОРМЛЕНИЯ НОВОРОЖДЕННОГО ЧЕРЕЗ ЗОНД Цель: Обеспечить ребенка необходимым количеством пищи при отсутствии сосательного и глотательного рефлексов.
Сейчас читают про:
Источник: studopedia.ru
Пролог. Лаб1-ИCиТ-Пролог (1). Занятие Разработка экспертной системы задание Введение в логическое программирование на языке Prolog
Единственный в мире Музей Смайликов
Самая яркая достопримечательность Крыма
Скачать 1.86 Mb.
Практическое занятие № 1.
Разработка экспертной системы
ЗАДАНИЕ № 1. Введение в логическое
программирование
на языке Prolog
Продолжительность выполнения задания: 0,5 ак. часа.
Целью задания является знакомство со средой Turbo Prolog и основами программирования на языке Prolog.
Теоретическая часть
Prolog (фр. Programmation en Logique) — это язык логического программирования, основанный на языке предикатов математиче- ской логики дизъюнктов Хорна — подмножестве логики предика- тов первого порядка. Существует несколько различных сред и компиляторов для программирования на языке Prolog, например:
Turbo Prolog — язык и система логического программирова- ния, разработанные компанией Borland в начале 1980-х гг.;
Visual Prolog — объектно-ориентированное расширение языка программирования PDC Prolog, развивавшегося из Turbo
Prolog, а также система визуального программирования;
SWI-Prolog — открытая реализация языка Prolog.
В данных лабораторных работах будет описываться работа в среде Turbo Prolog.
Программа, написанная на языке Prolog, состоит из нескольких основных частей: раздел доменов, раздел базы данных, раздел предикатов, раздел цели и раздел утверждений. Начала этих разде- лов отмечаются ключевыми словами domains, database, predi- cates, goal и clauses соответственно. Раздел domains содержит определения доменов, которые описывают различные классы объ- ектов (типы аргументов пользователя), которые используются в
7
программе кроме стандартных доменов. Раздел database содержит утверждения базы данных, которые являются предикатами дина- мической базы данных. Раздел predicates служит для описания используемых программой предикатов. В разделе goal формули- руется назначение создаваемой программы. Раздел clauses — это ядро программы, в него заносятся факты и правила, известные априорно (листинг 1.1 и рис.
1.1). Некоторые из этих разделов
(domains, database, goal) могут быть пропущены в программе.
Комментарии в языке Prolog обрамляются символами /* и */.
Листинг 1.1
Пример программы «Hello, World!»
predicates
hello
goal
hello.
clauses
hello :- write(«Welcome to Turbo Prolog!»),nl.
Рис. 1.1. Результат работы программы «Hello, World!»
Приведем пример описания доменов и предикатов. Рассмотрим отношение «любит» между двумя объектами: likes(«Mary», ap-
8
ples). Здесь likes является предикатом (термом предиката), а
Mary и apples — объектами этого предиката. Turbo Prolog требует указания типов объектов для каждого предиката программы. Для этого в разделе predicates необходимо задать тип объектов каждо- го из предикатов, например: likes(symbol, symbol). Это описание означает, что оба объекта предиката likes относятся к типу symbol, который является одним из базисных типов в Prolog
(табл. 1.1).
Таблица 1.1
Базисные типы в Turbo Prolog
Тип данных
Ключевое
слово
Диапазон значений
Примеры
использования
Символы сhar
Все возможные символы ‘A’, ‘b’, ‘#’
Целые числа integer от – 32768 до 32767
– 37, 5134, – 32750
Действительные числа real от – 2 63 до 2 63
–1
– 41245, 4578,
Строки string
Последовательность символов (не более 250)
«Hello!», «1+2=3»
Символические имена symbol
1. Последовательность букв, цифр и знака подчеркивания; первый символ — строчная буква.
2. Последовательность любых символов, заключенная в кавычки hello_world
«Hello world!»
Файлы file
Допустимое в DOS имя файла
Test.txt
Prolog позволяет конструировать свои собственные типы объ- ектов из базисных типов доменов. Например, в разделе программы domains могут появиться такие описания:
domains
person, thing = symbol
predicates
likes (person, thing)
9
Как было сказано ранее, в раздел clauses заносятся факты и прави- ла, причем каждый факт или правило завершается символом «точка»:
clauses
likes(«John»,camera). likes(«Tom»,computer). likes(«Kathy»,computer). likes(«Mary»,apple).
Рассмотрим особенности использования целей (goal). Цели бы- вают внутренние и внешние. Внутренние цели — это цели поис- ка, которые задаются в самой программе. Цель при этом может состоять из нескольких подцелей, разделенных запятой (логиче- ский союз « И » ) или точкой с запятой (логический союз «ИЛИ»).
Завершается цель точкой.
Для вывода на экран во внутренних целях используется встро- енный предикат write, аргументами которого могут быть строко- вые константы (заключенные в кавычки) и имена переменных; та- кие аргументы можно произвольно комбинировать. Встроенная операция nl (сокращение от «new line» — англ. новая строка) по- зволяет осуществлять перевод курсора на новую строку. Пример программы с внутренней целью представлен в листинге 1.2.
В формулировке запроса к программе можно использовать не- сколько переменных (это будут внешние цели). Тогда программа выдаст все возможные комбинации значений переменных (преди- кат write для этого использовать не надо).
Листинг 1.2
Пример программы с внутренней целью
domains
person, thing = symbol
predicates
likes (person, thing)
clauses
likes («John»,camera). likes («Tom»,computer). likes («Kathy»,computer).
goal
write («Что же любит Tom?»), nl, likes («Tom», X), write («Tom любит», X).
10
На рис. 1.2 представлен скриншот программы Turbo Prolog с активным редактором кода (Edit). Выполнить введенный код мож- но, выбрав пункт Run (ALT+R). Трансляция задается автоматиче- ски, т.е. нет необходимости прибегать к помощи специальной команды Compile. Результат работы программы представлен на рис.
1.3.
Рис. 1.2. Скриншот программы Turbo Prolog с активным редактором кода (Edit)
Рис. 1.3. Результат работы программы.
Рассмотрим факт student («Иванов», 14, 05, 1990). При таком за- дании факта оказывается непонятным назначение последних трех
11
объектов, которые представляют собой дату рождения студента
Иванова. Более определенно описать этот объект можно следую- щим образом: student («Иванов», birthday(14, 05, 1990)). Объект, представляющий собой другой объект или совокупность объектов, называется составным объектом (листинг 1.3 и рис. 1.4).
Листинг 1.3
Пример программы с составным объектом
domains
date=birthday(integer, integer, integer)
predicates
student (symbol, date)
clauses
student («Иванов»,birthday (14, 05, 1990)). student («Петров»,birthday (30, 12, 1991)). student («Сидоров»,birthday (29, 05, 1991)).
goal
student («Иванов»,X), write(«Дата рождения Иванова: «,X).
Рис. 1.4. Пример программы с составным объектом
Если необходимо определить только год рождения студента, то цель будет выглядеть так: student («Иванов», birthday (_,_,Y)),
12
write(«Год рождения Иванова: «,Y). Обратите внимание, что пере- менная, в определении значения которой нет необходимости, на- зывается анонимной переменной и обозначается знаком подчерки- вания (рис. 1.5).
Рис. 1.5. Пример программы с анонимной переменной
Представление данных часто требует наличия большого числа структур. В Prolog эти структуры должны быть описаны с помо- щью альтернативного описания доменов. Для разделения альтер- нативных доменов используется точка с запятой (листинг 1.4).
Листинг 1.4
Пример программы с альтернативным описанием доменов
domains
thing = misc_thing(whatever); book(author,title); record(artist, al- bum,type) person, whatever, author, title, artist, album, type = symbol
predicates
owns (person, thing)
clauses
owns («Иванов», misc_thing(«Piano»)). owns («Петров», book(«J.R.R. Tolkien»,»Return of the King»)). owns («Сидоров», record(«Nightwish»,»Nemo»,»metal»)).
13
Рис. 1.6. Пример программы с альтернативным описанием доменов
Если в коде программы не заданы цели (goal), то при нажатии
ALT+R курсор перейдет в окно диалога (dialog), где их также можно ввести и сразу же увидеть результат (рис. 1.6).
Рассмотрим, как осуществляется логический вывод. Унифика-
цией называется отождествление объектов Prolog при сопоставле- нии предиката с фактами и правилами. Если подобное отождеств- ление выполнено, то считается, что унификация завершена успешно.
При этом свободные переменные доказываемого предиката приоб- ретают конкретные значения. Этот процесс называется конкрети-
зацией.
Листинг 1.5
Пример программы с логическим выводом
predicates
father(symbol). mother(symbol). man(symbol).
clauses
father(bob). mother(ann). man(X):- father(X).
14
Результат логического вывода (листинг 1.5) зависит от вида вопроса. Если вопрос содержит только константы, то он называет- ся общим, и ответ на него будет «да» или «нет» в зависимости от результатов сопоставления с фактами и правилами программы
(рис. 1.7).
Если вопрос содержит переменные, то в процессе сопоставле- ния они будут конкретизированы. Полученные значения будут вы- ведены на экран (рис. 1.8), в противном случае будет дан ответ
«нет».
Если в программе, приведенной в листинге 1.5, сделать за- прос: man(X), то предикат man(X) сопоставляется с фактами базы знаний, после чего сопоставляется с головой правила man(X).
Поскольку сопоставление успешно, то переменная X конкретизи- руется значением «bob». Выполняется доказательство цели man(bob). Для доказательства изучается предикат правой части правила father(bob). Этот предикат сопоставляется с фактом базы данных. При сопоставлении с фактом father(bob) унификация за- вершается успешно, т.е. предикат father(bob) принимает значение
«истина», голова правила man(bob) принимает значение «исти- на». При этом переменная X конкретизируется значением «bob».
В конце работы программы на экране выдается сообщение
X =»bob».
Рис. 1.7. Результат логического вывода (вопрос содержит только константу)
15
Рис. 1.8. Результат логического вывода (вопрос содержит переменную)
В листинге 1.6 представлен код программы, полностью задаю- щей ближайшие родственные связи (рис. 1.9).
Листинг 1.6
Пример программы, задающей ближайшие родственные связи
domains
s = symbol
predicates
parent(s,s) female(s) male(s) mother(s,s) father(s,s) ancestor(s,s) child(s,s)
clauses
parent(pam,bob). parent(tom,bob). parent(tom,liz). par- ent(bob,ann). parent(bob,pat). parent(olga,pat). parent(olga,svetlana). par- ent(pat,jim). female(pam). female(olga). female(liz). female(ann). fe- male(pat).
16
Окончание Листинга 1
male(tom). male(bob). male(jim). child(Y,X) :- parent(X,Y). mother(X,Y) :- parent(X,Y), female(X). father(X,Y) :- parent(X,Y), male(X). ancestor(X,Z) :- parent(X,Z). ancestor(X,Z) :- parent(X,Y), ancestor(Y,Z).
Рис. 1.9. Результат работы программы «Родственные связи»
Задание
1. Написать программу — «Hello, world!».
2. Написать в Turbo Prolog программу с произвольными пре- дикатами, которая будет включать составные объекты и альтерна- тивные домены.
3. Описать отношения для следующих комбинаций «субъек- ты ― предметы»: субъекты ― марки автомобилей.
4. Реализовать пример родственных отношений (не менее 7 предикатов, не менее 15 правил, и 2–3 цели (например, «у кого мама — Ольга?»).
5. Определить родственное отношение «grandmother» («ба- бушка»).
17
Контрольные вопросы
1. Какие среды и компиляторы для программирования на языке Prolog вы знаете?
2. Какие разделы существуют в программе на языке Prolog?
3. Какие базисные типы существуют в языке Prolog?
4. Что такое составной объект в программе на языке Prolog?
5. Зачем нужны альтернативные домены в программе на язы- ке Prolog?
ЗАДАНИЕ № 2. Арифметические операции,
ввод данных пользователем, разветвление
Продолжительность выполнения задания: 0,5 ак. часа.
Целью задания является знакомство со способа- ми выполнения арифметических операций, методами обработки данных, введенных пользователем, а также с реализацией разветв- ления программы.
Теоретическая часть
Выполнение арифметических операций
Для выполнения арифметических операций необходимо соз- дать соответствующие предикаты в программе на языке Prolog.
Для осуществления основных арифметических действий можно воспользоваться несколькими предопределенными операторами.
Prolog может выполнять все четыре основные арифметические операции (сложение, вычитание, умножение и деление) между целыми и вещественными числами. Тип результата приведен в табл. 2.1.
Таблица 2.1
Арифметические операции
Операнд 1
Оператор
Операнд 2
Результат
1
2
3
4
Целое
+, –, *
Целое
Целое
Вещественное
+, –, *
Целое
Вещественное
Целое
+, –, *
Вещественное
Вещественное
Вещественное
+, –, *
Вещественное
Вещественное
19
Окончание листинга 2.3
go(X,Y):- X =6, X 16, Y=»university». answer:- input(X), go(X,Y), output(Y).
goal
answer.
Рис. 2.3. Пример программы с разветвлением
Задание
1. Написать простую программу-калькулятор, которая вы- полняет четыре арифметических действия над целыми числами, вводимыми пользователем.
2. Реализовать вычисление куба числа, вводимого пользова- телем.
3. Написать в Turbo Prolog программу, которая будет искать значение Z по введенным с клавиатуры значениям X и Y, при этом в зависимости от значения X должно происходить разветвление программы. Например, при X = 0,
Z = X*Y.
23
4. Написать программу, задающую отношение triangle(N, T), истинное, если T ― треугольное число с индексом N.
Контрольные вопросы
1. Как осуществляется логический вывод в программе на языке Prolog?
2. Как осуществляются арифметические операции?
3. Если к целому числу прибавить вещественное в программе на языке Prolog, какого типа будет результат?
4. Какие операторы в языке Prolog используются для пользовательского ввода?
5. Есть ли в языке Prolog операторы для разветвления программы?
ЗАДАНИЕ № 3. Организация повторений в языке
Prolog
Продолжительность выполнения задания: 0,5 ак. часа.
Целью задания является знакомство с принципом организации повторений в языке Prolog.
Теоретическая часть
Повторения и рекурсия
Зачастую в программах бывает необходимо выполнить одну и ту же задачу несколько раз. В Prolog существуют два способа реа- лизации правил, выполняющих одну и ту же задачу многократно.
Первый способ называется повторением, второй — рекурсией.
Правила Prolog, выполняющие повторения, используют откат, а правила, выполняющие рекурсию, используют самовызов.
Вид правила, выполняющего повторение, следующий: repetitive_rule:- , fail.
Конструкция в теле этого правила обо- значает предикаты, содержащие несколько утверждений, а также правила, определенные в программе. Встроенный предикат fail
(«неудача») вызывает откат, так что предикаты и правила выпол- няются еще раз.
Вид правила, выполняющего рекурсию, следующий: recursive_rule:- , recursive_rule.
Последним в теле данного правила является само же правило recursive_rule, т.е. тело правила содержит вызов самого себя.
Правила повтора и рекурсии могут обеспечивать одинаковый результат, хотя алгоритмы их выполнения неодинаковы. Каждый из них в конкретной ситуации имеет свои преимущества. Рекур- сия, например, может требовать больше системных ресурсов.
25
Источник: topuch.com