Лабораторная работа №1
Логические модели представления знаний
Цель работы: Получить навыки разработки простейших логических моделей представления знаний с использованием языка логического программирования Prolog
Теоретические сведения
Языки представления знаний (ЯПЗ) специально ориентированы на создание ЭС, и каждый из них имеет собственные средства представления знаний (с ориентацией на модели фреймов, продукций и др.) и механизм поиска логического вывода. Среди лингвистических средств данной группы следует отметить такие языки, как Prolog, LogLisp, Planer и др. Данные языковые средства требуют участия инженера знаний и программистов при разработке конкретных ЭС. Наиболее распространенным в Европе и Японии из средств данного уровня является язык Prolog, в котором знания представляются посредством предложений (логических формул) вида: R:-(Q1,Q2,...,Qn), где R, Qk(1£k£n) – атомарные формулы. В смысловом отношении предложения данного вида утверждают истинность R –заключения при условии истинности всех их Qk посылок, т.е. в эквивалентном виде данные предложения принимают следующий привычный вид: IF Q1&Q2&...&Qn. THEN R (1£k£n).
Рассмотрим синтаксис языка Турбо ПРОЛОГ и структуру программы для того, чтобы можно было самостоятельно разработать небольшую учебную программу.
Программа на Турбо-Прологе имеет следующую обобщенную структуру:
Domains
/*...объявление доменов... */
Predicates
/*...объявление предикатов... */
Goal
/*...подцель_1,
подцель_2,
и т.д.... */
Clauses
/*...предложения (факты и правила)... */
В секции clauses размещаются факты и правила, с которыми будет работать Турбо-Пролог, пытаясь разрешить цель программы.
В секции predicates объявляются предикаты и типы (домены) аргументов этих предикатов. Имена предикатов должны начинаться с буквы (желательно строчной), за которой следует последовательность букв, цифр и символов подчеркивания (до 250 знаков). В именах предикатов нельзя использовать символы пробела, минуса, звездочки, обратной (и прямой) черты. Объявление предиката имеет следующую форму:
Predicates
predicateName (argument_type1, argument_type2,..., argument_typeN)
Здесь argument_type1,..., argument_typeN - либо стандартные домены, либо домены, объявленные в секции domains. Объявление домена аргумента и описание типа аргумента - суть одно и то же.
В секции domains объявляются любые нестандартные домены, используемые для аргументов предикатов. Домены в Прологе являются аналогами типов в других языках. Основными стандартными доменами Турбо-Пролога являются - char, integer, real, string и symbol. Основная форма объявления доменов имеет следующий вид:
Domains
argument_type1,..., argument_typeN = <стандартный домен>
argument_1,..., argument_N = <составной домен 1>;
<составной домен 2>;
<...>;
<составной домен N>;
В секции goal задается внутренняя цель программы; это позволяет программе запускаться независимо от среды разработки. Если внутренняя цель включена в программу, то Турбо-Пролог выполняет поиск только первого решения, и связываемые с переменными значения не выводятся на экран. Если внутренняя цель не используется, то в процессе работы будет вводиться в диалоговом окне внешняя цель. При использовании внешней цели Турбо-Пролог ищет все решения и выводит на экран все значения, связываемые с переменными.
В Турбо-Пролог включено более 200 встроенных стандартных предикатов и более дюжины стандартных доменов: в случае использования этих предикатов и доменов нет необходимости объявлять их.
Арность (размерность) предиката - это число принимаемых им аргументов; два предиката с одним именем могут иметь различную арность. Предикаты с различными версиями арности должны собираться вместе, причем и в секции predicates и в секции clauses; однако предикаты с различной арностью рассматриваются как абсолютно разные.
Правила имеют форму:
ЗАГОЛОВОК:- <Подцель1>, <Подцель2>,..., <ПодцельN>.
Для разрешения правила Пролог должен разрешить все его подцели, создав при этом соответствующее множество связанных переменных. Если же одна из подцелей ложна, Пролог возвратится назад и просмотрит альтернативные решения предыдущих подцелей, а затем вновь пойдет вперед, но с другими значениями переменных. Это процесс называется "поиск с возвратом".
Рассмотрим пример. Пусть дано генеалогическое древо родственных отношений (рисунок 1). Из его содержания мы можем определить, по крайней мере, два факта: кто кому приходится родителем и пол людей, участвующих в родственных отношениях. Это то, что дано и является безусловно верным. Поэтому это факты. Запишем их на языке Prolog.
Тот факт, что bob является родителем tom на Прологе запишется так:
| |||
 | |||
Рис. 1
Все 7 предложений объявляют об факте – наличие отношения «Родитель».
После ввода такой программы в пролог-систему, ей можно задавать вопросы (цели). Например, является ли bob родителем pat?
Goel: parent(bob, pat)
Данный факт будет найден в программе и система ответит «Yes».
Можно задать и более интересные вопросы. Например, кто является родителем kate?
Goel: parent(X,kate)
Пролог-система найдет факт, в котором kate находится на месте второго аргумента и присвоит X значение первого аргумента: Х=tom.
Кто дети bob?
Goel: parent(bob, X)
На этот вопрос система найдет два ответа (2 решения достижения цели): X=pat X=tom
Зададим более общий вопрос: Кто чей родитель?
Goel: parent(X,Y)
Система будет находить все пары родитель-ребенок:
X=bob Y=tom
X=bob Y=pat
X=ann Y=tom
X=ann Y=pat
X=pat Y=olga
X=pat Y=jon
X=tom Y=kate
Можно задать и более сложный вопрос: Кто является родителем родителя jon?
Достигать цель будем в два этапа, поскольку в нашем примере существует факт «Родитель», а по заданию необходимо определить отношение «родитель родителя».
Во-первых, определим, кто родитель jon. Пусть это Y.
Во-вторых, определим, кто родитель Y. Пусть это Х.
Такой вопрос задается на Prolog в виде последовательности двух простых предложений скрепленных конъюнкцией (логическое «И»).
Goel: Parent(Y,jon), parent(X,Y).
Здесь «,» - знак конъюнкции, показывающий обязательное наличие истинности в двух вопросах. Если поменять порядок этих двух предложений, то логический смысл останется прежним.
Спросим, кто внуки bob?
Goel: parent(bob,X), (X,Y).
Получим ответ:
X=pat Y=olga
X=pat Y=jon
X=tom Y=kate
Спросим, есть ли у pat и tom общий родитель?
Очевидно, что вопрос должен состоять из двух этапов: во-первых, спросим, какой Х является родителем pat? Во-вторых, является ли тот же X родителем tom?
Goel: parent(X,pat),(X,jon)
X=bob
X=ann
Подведем некоторые итоги по пройденному на данный момент материалу.
Резюме:
1. На прологе легко определить отношение, указав объекты, для которых это отношение выполняется.
2. пользователь может задавать вопросы к программе, касающиеся отношений, определенных в программе.
3. пролог-программа состоит из предложений, каждое предложение заканчивается «.»
4. аргументы отношения могут быть конкретными объектами, как в нашем примере ann, jon, tom и т.д. – это константы или абстрактными объектами, такие как Х или Y – это переменные. Константы надо писать с маленькой буквы, а переменные с заглавной.
5. вопрос к программе называется целью. Вопросы могут состоять из одной или более целей, которые разделяются «,» - конъюнкцией. Пролог рассматривает вопросы, как цели к которым нужно стремиться.
6. ответ на вопрос может оказаться положительным или отрицательным в зависимости от того, может ли цель быть достигнута или нет. В случае положительного ответа – цель достижима или успешна, при отрицательном ответе – недостижима или имеет неуспех.
7. если на вопрос существует несколько ответов, Пролог найдет все.
Из дерева родственных отношений, представленного на рисунке 1 очевиден еще один факт – это пол людей, участвующих в отношении «Родитель».
Для разнообразия введем в программу унарное (одноместное) отношение. Отношение «Родитель», введенное выше – бинарное - отношение между двумя объектами.
Male(bob).
Male(tom).
Male(jon).
Female(ann).
Female(pat).
Female(olga).
Female(kate).
Более никаких фактов (исходных данных) из представленного рисунка 1 взять не возможно.
Далее будем расширять программу с помощью правил, то есть таких предложений, результат выполнения которых зависит от того, выполняется условие или нет, в то время как факт не зависит от условия, а является всегда безусловной истиной.
Из сказанного следует, что правило имеет условную часть – тело предложения и часть вывода – голову предложения.
Введем отношение «ребенок», которое обратно отношению «родитель». Чтобы правильно записать правило, необходимо сначала правильно его сформулировать: предложение-правило должно начинаться с условной части «ЕСЛИ» и завершаться выводом «ТО». Сформулируем правило «ребенок»:
Для всех X и Y, ЕСЛИ Х является родителем Y, ТО Y является ребенком Х.
На прологе запишется это так:
Child(Y,X):-parent(X,Y).
Здесь «:-» - обозначение условия ЕСЛИ
Введем отношение «мать». Сформулируем: Для всех X и Y ЕСЛИ Х является родителем Y и Ч – женщина, ТО Х является матерью Y.
Знак «,» указывает, что оба условия должны быть истинными.
Введем отношение «сестра». Сформулируем: Для любого X и Y ЕСЛИ у X и Y есть общий родитель и Х – женщина, то Х является сестрой Y.
Подведем итоги:
1. Пролог-программу можно расширять, добавляя в нее правила.
2. Пролог предложения могут быть трех видов: факты, правила, цели.
3. Факты содержат утверждения, которые являются всегда безусловно верными.
4. правила содержат утверждения, истинность которых зависит от истинности условий
5. Предложения Пролога состоят из головы и тела. Тело – список целей, разделенных «,» - конъюнкция или «;» - дизъюнкция.
6. Факты – это предложения, имеющие пустое тело. Цели (вопросы) имеют только тело. Правила имеют голову и непустое тело.
7. По ходу вычислений вместо переменной может быть подставлен другой объект. Говорится, что переменная конкретизируется.
Последовательность выполнения работы
1. По дереву родственных отношений, указанному в варианте задания выпишите факты
2. Написать правила, которые указаны в варианте задания.
3. Протестировать программу, проверить все правила.
Варианты задания для выполнения лабораторной работы
Вариант 1
 | |||
| |||
Вариант 2
| |||
 | |||
Вариант 3
 | |||
| |||
Вариант 4
 | |||
| |||
|
Содержание отчета по лабораторной работе
1. Дерево родственных отношений
2. Листинг программы
3. Результаты проверки правил.