МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ

ГОМЕЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

им. Ф. СКОРИНЫ

Кафедра математических проблем управления

Практикум

"Программирование на языке Пролог"

(для специальностей H.01.01 - математика;

H.08.01 - прикладная математика)

Гомель 2001г.

Составители:

Е.И.Сукач, к.т.н. доцент кафедры “Математические проблемы управления”;

Т.Я. Каморникова, ассистент кафедры “Математические проблемы управления”.

Рецензенты:

А. В. Сементовский, к.ф.-м.н. доцент кафедры “Высшая математика” Белорусского государственного университета транспорта;

М. И. Жадан, к.ф.-м.н. доцент кафедры “ЭВМ и программирование”.

Утверждено и рекомендовано к изданию научно-методическим советом Гомельского государственного университета имени Ф.Скорины 28 марта 2001 года, протокол № 7.

Данные методические указания могут быть использованы пользователями ПК для получения базовых знаний по логическому программированию на языке Пролог.

Практикум может быть полезен студентам математических и инженерно-технических специальностей при изучении курсов “Базы знаний и экспертные системы” “Экспертные и интеллектуальные системы”, “Методы построения экспертных систем” и др.

© ГГУ им. Ф.Скорины, 2001

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ 4

1.Основные элементы языка Пролог. Структура программы на языке Пролог. 5

2. Структуры. Состав логических операций в Прологе. Решение логической задачи в TP. 9

3. Использование рекурсии. Построение программ с использованием основных структур данных Пролога - списков. 14

4. Использование механизма отсечения для оптимизации поиска решения в программах на Прологе. 20

5. Управление стратегией вывода в экспертных системах с помощью обратной цепочки рассуждений. 26

6. Управление стратегией вывода в экспертных системах с помощью прямой цепочки рассуждений. 32

7.Управление стратегией выбора в экспертных системах с помощью эвристик. 35

38

8. Получение вывода экспертными системами в условиях неопределённости. 39

9. Организация в экспертных системах ответов на вопросы “Почему” и “Как”. 48

РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА. 56

Введение

Данное методическое пособие предназначено для студентов, изучающих язык логического программирования Пролог. Оно предназначено помочь выработать стиль программирования, обеспечивающий автоматизацию различных форм логических рассуждений, а так же построение экспертных систем (ЭС).

Пролог существенно отличается от языков, традиционно используемых в программировании. Он не отностится к алгоритмическим языкам. Своё название Пролог получил от слов “ПРОграммирование на языке ЛОГики”. Теоретической основой Пролога является раздел символьной логики, называемый исчислением предикатов. Прологу присущ ряд свойств, что делает его мощным средством в области логического программирования. К таким свойствам относятся механизм вывода с поиском и возвратом, встроенный механизм сопоставления с образцом, и простая, но выразительная структура данных с возможностью её изменения.

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

Таким образом, все вышеупомянутые свойства Пролога в совокупности делают его оптимальным языком для создания несложных, но мощных программ ЭС.

Несмотря на то, что в пособии используется Турбо Пролог, оно может быть полезным и для работы с другими версиями Пролога, поскольку не содержит описания низкоуровневых (машинных) свойств Турбо Пролога.

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

Практикум может быть использован при проведении практических и лабораторных занятий по спецкурсам “Базы знаний и ЭС ”, “Основы проектирования ПО интеллектуальных систем”.

1.Основные элементы языка Пролог. Структура программы на языке Пролог.

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

Основные конструкции языка: факты, вопросы и правила. Все они описываются с помощью предикатов.

Предикат – это функция от одного или нескольких переменных, принимающая значения “истина” или “ложь”.

Факт – это конкретные сведения, записываемые в форме предикатов с конкретными аргументами-значениями. Под фактами (фактическими знаниями) подразумеваются знания "А - это А". N-местные предикаты определяют отношения между объектами. Одноместные предикаты используются для объявления наличия простых свойств у объектов. Например, двухместный предикат, описывающий факт "Ваня является родителем Васи” выглядит следующим образом: родитель(вася, ваня).

А предикат “Вася является мужчиной” на языке Пролог запишется следующим образом: мужчина(вася).

Здесь “родитель” и “мужчина” – имена предикатов, а “вася” и “ваня” – значения аргументов приведенных предикатов.

Проавило – это правило логического вывода с утверждением и одним или несколькими предусловиями, записываемое в виде предикатов. Под правилами (знаниями для принятия решения) подразумеваются знания вида "ЕСЛИ - ТО". Правло имеет заголовок и тело, которые разделяются специальным символом “:—”. Заголовок правила имеет точно такую же форму, как и факт. Тело правила состоит из одного или нескольких подцелей, которые разделяются запятой. В конце правила ставится знак завершения – точка. Правило утверждает, что отношение в заголовке правила имеет место, если имеют место все отношения в теле правила. С помощью правил выражаются общие законы, которые управляют рассматриваемым отношением. Например, правило вида “Для всех X и Y, если X родитель Y, то Y отпрыск X” на Прологе запишется следующим образом:

отпрыск (Y, X):— родитель(X,Y).

А правило “Для всех X, если Х имеет по какому-либо предмету двойку, то Х – двоечник” запишется следующим образом:

двоечник(Х):— оценка(Х,_,2).

Здесь X и Y – переменные, “2”-конкретное значение аргумента предиката, знак “_” означает неопределённое значение , которое несущественно для поиска ответов на вопросы.

Каждый факт и каждое правило в программе называется утверждением. Правило – это утверждение, имеющее заголовок и тело. Факт – это утверждение, имеющее заголовок и пустое тело.

После того как программа загружена, можно задавать вопросы относительно тех отношений, которые в ней описаны.

Вопрос – это запрос к программе, записываемый в форме одного или нескольких предикатов с указанием в качестве аргументов переменных и конкретных значений. Вопрос представляет собой цель, которая должна быть согласована (доказана) в процессе работы программы. Цель в простейшем случае представляет собой: 1.факт который необходимо доказать; 2. предикат, для которого необходимо найти значения переменных, прикоторых он является истинным. Например, цели могут быть следующими:

?-родитель(вася, ваня).

?- отпрыск (Y, X).

Цель может быть согласована, если она сопоставляется с заголовком какого-либо утверждения программы. Если сопоставление происходит с заголовком утверждения, имеющего пустое тело (т.е. фактом), цель согласуется немедленно. Если же сопоставление происходит с заголовком правила, цель согласуется только тогда, когда каждая подцель в теле правила будет согласована после вызова её в качестве цели. Подцели вызываются в том порядке, в котором они записаны. Операция сопоставления, при которой переменной внутри предиката (у которой в данный момент не было значения) присваивается соответствующее значение, в результате чего оба предиката становятся одинаковыми, называется операцией унификации. Существует два уровня смысла программ на прологе: декларативный и процедурный. Декларативный смысл касается только отношений, определенных в программе, то есть он определяет, что должно быть результатом работы программы. Процедурный смысл: как этот результат был получен, то есть как отношения реально обрабатываются Пролог-системой.

Механизм вывода в Прологе. Вопрос к системе – это всегда последовательность, состоящая из одной или нескольких целей. Достичь цели –это значит показать, что она логически следует из фактов и правил программы. Программы на Прологе похожи на гипотезы о проблемной области, а вопросы похожи на теоремы, которые необходимо доказать.

Рассмотрим механизм вывода программы:

родитель(ира, ваня). /* Ира - родитель Вани*/

родитель(вася, ваня). /* Вася - родитель Вани*/

родитель(вася, лиза). /* Вася - родитель Лизы*/

родитель(ваня, таня). /* Ваня - родитель Тани*/

родитель(ваня, катя). /* Ваня - родитель Кати*/

родитель(катя, дима). /* Катя - родитель Димы*/

женщина(ира). /* Ира – женщина*/

женщина(лиза). /* Лиза – женщина*/

женщина(таня). /* Таня – женщина*/

женщина(катя). /* Катя – женщина*/

мужчина(ваня). /* Ваня – мужчина*/

мужчина(вася). /* Вася – мужчина*/

мужчина(дима). /*Дима – мужчина*/

отпрыск (Y, X):— /*Y - отпрыск X, если

родитель(X,Y). X – родитель Y*/

мать(X,Y): — /* X – мать Y, если Х – родитель Y и

родитель(X,Y), Х – женщина*/

женщина (Х).

родитель_родителя(X,Z): — /* X- родитель родителя Z, если

родитель(X,Y), X- родитель Y и Y- родитель Z*/

родитель(Y,Z).

cестра (X, Y): — /* X- сестра Y, если

родитель(Z,X), X и Y имеют общего родителя

родитель(Z,Y),

женщина(X,Y), X – женщина

различны(X,Y). X отличается от Y*/

/*Для предиката “предок” используется два правила. Первое правило описывает ближайших предков, а второе - отдалённых.*/

предок(X,Z): — /* Правило 1: X - предок Z*/

родитель(X,Z).

предок(X,Z): — /* Правило 2: X - предок Z*/

родитель(X,Y),

предок(Y,Z).

? – предок(вася, катя). /*цель*/

Пролог-система строит цепочку доказательства, начиная с целей. Применяя правила, она подменяет текущие цели новыми, до тех пор, пока эти новые цели не окажутся простыми фактами.

Шаг 1. Пролог-система пробует найти такое предложение в программе, из которого немедленно следует упомянутая цель. Подходящими для этого являются правила 1 и правило 2 предиката “предок”. Вначале система использует правило 1. При этом исходная цель “предок (вася, катя) заменяется новой целью “родитель (вася, катя)”. Такого факта нет, следовательно цель неуспешна.

Шаг 2. Система делает возврат к исходной цели, чтобы использовать правило 2. Переменным приписываются значения: X=вася, Z=катя. В этот момент переменной Y не приписано никакого значения. Цель ”предок (вася, катя)” заменяется двумя целями: “родитель (вася, Y)” и “предок (Y, катя)”. Имея две цели система пытается достичь их в том порядке, в каком они записаны. Достичь первой из них легко, поскольку она соответствует факту из программы. Процесс унификации вызывает приписывание переменной Y значение ”ваня”. Тем самым достигается первая цель, а оставшаяся цель превращается в цель “предок (ваня, катя)”. Для достижения этой цели применяется правило 1 предиката предок. Заметим, что это (второе) применения правила никак не связано с его первым применением. Текущая цель заменяется на цель “родитель (ваня, катя). Она немедленно достигается.

Таким образом, корневая цель достигается тогда, когда находится путь от корня дерева к его листу помеченному меткой “да”. Лист помечается меткой “да”, если он представляет собой простой факт. Выполнение программы состоит в поиске таких путей. В процессе поиска система может входить в ветви, приводящие к неуспеху. В таких случаях происходит возврат к предыдущей вершине и следует попытка применить к ней альтернативное предложение.

Упражнение: Реализовать в среде Турбо Пролога простейшую программу с заданным ключевым словом. Использовать 3-4 предиката для описания информации о своих родственниках. Определить подходящие 3-4 правила. Найти решение для нескольких целей. Составить протокол вывода решения для одной из целей.

Ключевые слова: дедушка; бабушка; тетя; дядя; внук; шурин; золовка; правнучка; брат; сестра; двоюродная сестра; отчим.