 |
Язык Prolog как реализация продукционной модели данных
|
|
|
|
ЛАБОРАТОРНАЯ РАБОТА 1.
РАЗЛИЧНЫЕ СПОСОБЫ
ПРЕДСТАВЛЕНИЯ ЗНАНИЙ
Задание по лабораторной работе:
1.Необходимо описать факты и правила согласно индивидуальному заданию и выполнить четыре запроса в системе SWI_Prolog,
2. Представление базы знаний с помощью семантической сети по программе
3. Представление базы знаний с помощью фреймов на бумаге.
Индивидуальные варианты:
1. Флэш — собака. Ровер — собака. Бутси — кошка. Стар — лошадь.
Флэш черная. Бутси коричневая. Ровер рыжая. Стар белая.
Домашнее животное: собака или кошка.
Животное: домашнее или лошадь.
У Тома есть собака не черного цвета.
У Кейта есть лошадь или что-то черного цвета.
Запросы:
Ровер рыжая?
Определить клички всех собак.
Определить владельцев чего—либо.
Определить владельцев животных небелого цвета.
2. Бутси — коричневая кошка. Корни — черная кошка. Мактэвити — рыжая кошка.
Флэш, Ровер и Спот — собаки; Ровер — рыжая, а Спот — белая. Флэш — пятнистая собака.
Все животные, которыми владеют Том и Кейт, имеют родословные.
Том владеет всеми черными и коричневыми животными.
Кейт владеет всеми собаками не белого цвета, которые не являются собственностью Тома.
Алан владеет Мактэвити, если Кейт не владеет Бутси и если Спот не имеет родословной.
Запросы:
Какие животные не имеют хозяев?
Найдите всех собак и укажите их цвет.
Укажите всех животных, которыми владеет Том.
Перечислите всех собак Кейта.
3. Определить родственные отношения: СЫH, ДОЧЬ, ОТЕЦ, МАТЬ, МУЖЧИHА и ЖЕHЩИHА.
Описать факты для некоторых из них.
Запросы:
Определить всех сыновей определенной матери.
Определить всех детей определенной пары родителей.
Определить родителей определенного человека.
|
|
|
Является ли определенный человек женщиной?
4. Мэри любит персики. Мэри любит кукурузу. Мэри любит яблоки.
Бет любит то, что любит Мэри, если это — фрукт и если он красный.
Бет любит то, что любит Мэри, если это кукуруза.
Персики — фрукт. Яблоки — фрукт.
Цвет персиков желтый. Цвет апельсинов оранжевый. Цвет яблок красный.
Цвет яблок красный. Цвет яблок желтый.
Запросы:
Что любит Бет?
Любит ли Мэри кукурузу?
Какие фрукты известны?
Какого цвета фрукты, которые любят Бет и Мэри?
5. Задано дерево родственных связей:
Пам Том Кроме того, определить отношения
/ ПОЛ, РЕБЕHОК, РОДИТЕЛЬ_РОДИТЕЛЯ и
/ МАТЬ.
/
Боб Лиз Запросы: Кто родитель Пат?
/ Есть ли у Лиз ребенок?
/ Кто потомки Пат?
/ Является ли Пам матерью Боба?
Энн Пат
/
/
/
Джим
6. Медведь большой. Слон большой. Кот маленький. Медведь коричневый.
Кот черный. Слон серый. Любой черный или коричневый предмет является темным.
Запросы:
Кто одновременно большой и темный?
Есть ли коричневые маленькие слоны?
Есть ли большие и темные медведи?
Есть ли черный кот?
7. Мэри, Сьюзи и Джейн работают в дневную смену. Сэм, Джейн, Боб и Патриция работают в вечернюю смену. Знают друг друга те, кто работает в одну смену.
Запросы:
Знают ли друг друга Мэри и Джейн?
Кто работает в дневную смену?
Есть ли кто—то, кто работает в обе смены?
Есть ли кто—то, кто не знает друг друга?
8. Можно совершить такие виды путешествий:
Компания Из В Вид транспорта
Амтрак Hью-Йорк Бостон Поездом
Транзит Hью-Йорк Принстон Поездом
Амтрак Бостон Портленд Поездом
Грейхаунд Бостон Портленд Автобусом
Амтрак Hью-Йорк Вашингтон Поездом
Пиплз Hью-Йорк Вашингтон Самолетом
Пиплз Бирлингтон Hью-Йорк Самолетом
Любые две транспортные компании являютя конкурентами, если они обслуживают один и тот же маршрут.
Можно путешествовать из одного города в другой, если возможно путешествие из одного города в другой через промежуточный (третий) город.
|
|
|
Запросы:
Являются ли Амтрак и Пиплз конкурентами?
Какие компании дают возможность путешествовать из Hью—Йорка в Вашингтон?
Можно ли путешествовать из Бирлингтона в Портленд?
Определить всех конкурентов.
9. Определить факты о принадлежности студента определенной студенческой группе. Считается, что два студента знают друг друга, если они учатся в одной группе.
Запросы:
Кого знает определенный студент?
Определить состав определенной группы.
В каких группах учатся люди с определенным именем?
Знает ли один студент другого?
10. Имеются факты о маршрутах движения автобусов между двумя разными городами, в которых указаны: номер маршрута, названия двух городов, день и время отправления и прибытия. Известны также фамилии водителей, работающих на определенных маршрутах. Можно попасть из одного города в другой, если существуют автобусные маршруты из первого города во второй или из первого города в промежуточный и из промежуточного во второй (причем подходят и дни, и часы отправления).
Запросы:
Можно ли проехать из одного города в другой?
Указать автобусы, выходящие из определенного города в определенный день и время их отправления.
Перечислить фамилии водителей определенного маршрута.
Указать дни и часы отправления определенного маршрута.
11. Есть факты об отцах некоторых людей и о братьях некоторых людей. Определить отношение ДЯДЯ.
Запросы:
Определить братьев конкретного человека.
Кто является отцом конкретного лица?
Определить, связаны ли два человека отношением ОТЕЦ.
Определить, является ли один человек дядей другого.
12. Определить отношения РОДИТЕЛЬ, ЖЕHЩИHА как набор фактов, правила:
РАЗЛИЧHЫ, СЕСТРА (определяемое через РОДИТЕЛЬ, ЖЕHЩИHА и РАЗЛИЧHЫ) и ТЕТЯ (определяемое через РОДИТЕЛЬ и СЕСТРА).
Запросы:
Кто является родителями определенного человека?
Определить всех детей определенных родителей.
Определить, есть ли сестры у определенного человека.
Определить, есть ли тетя у определенного человека.
13.Экспертная система для определения породы собак.
Правила
| Порода собак | NN свойств |
| Английский бульдог | 1,3.5,7 |
| Бигл | 1,3,6,7 |
| Большой Дан | 1,5,6,7,8 |
| Американский Фокс | 1,4,6,7 |
| Кокер-спаниель | 2,3,5,6,7 |
| Ирландский сеттер | 2,4,6 |
| Колли | 2,4,5,7 |
| Сен-бернар | 2,5,7,8 |
Свойства
|
|
|
| Номер | Значение |
| Короткая шерсть | |
| Длинная шерсть | |
| Высота более 22 см | |
| Высота более 30 см | |
| Опущенный хвост | |
| Удлиненные глаза | |
| Хорошая порода | |
| Вес свыше 100 фунтов |
Определить породу любых 4 собак
14. Экспертная система о животных.
Описать базу знаний в виде фактов и правил и выполнить 4 запроса для определения животных
· Если животное имеет шерсть или кормит детенышей молоком, то это млекопитающее
· Если животное имеет перья или (животное летает и откладывает перья), то это птица
· Если животное млекопитающее и (животное ест мясо или (животное имеет острые зубы и имеет когти)), то это хищник
· Если животное хищник и имеет рыжевато-коричневый цвет и имеет темные пятна, то это гепард
· Если животное хищник и имеет рыжевато-коричневый цвет и имеет черные полосы, то это тигр
· Если животное птица и не может летать и плавает, то это пингвин
· Если животное птица и летает хорошо, то это альбатрос
15.Имеются следующие факты и правила:
- Иван, Елена, Татьяна, Игорь – студенты;
- студент получает зачет, если он отчитается по лабораторным занятиям;
- Иван отчитается по лабораторным занятиям только вместе с Игорем;
- Елена и Татьяна отчитались по лабораторным занятиям и пойдут вечером на дискотеку;
- если Игорь пойдет на дискотеку вместе с Татьяной, то он отчитается по лабораторным занятиям;
- Игорь пойдет вечером на дискотеку, если у него будет свободное время.
Сформировать следующие запросы:
- Кто пойдет вечером на дискотеку?
- Кто получит зачет?
- Кто не отчитался по лабораторным работам?
- Игорь отчитался по лабораторным работам?
16. Дан список сотрудников некоторого предприятия:
| Имя: | Иван | Елена | Джон | Мария | Том | Эрик | Билл | Марк |
| Возраст: | 22 | 25 | 40 | 22 | 32 | 22 | 32 | 43 |
Определив правило «А старше Б», сформировать следующие запросы:
- Сколько лет Тому?
- Работают ли на предприятии люди, которым 22 года?
- Кто старше Джона?
- Кто из работающих на предприятии являются ровесниками?
17. Дан список сотрудников некоторого предприятия:
|
|
|
| Имя: | Иван | Елена | Джон | Мария | Том | Эрик | Билл | Марк |
| Возраст: | 22 | 25 | 40 | 22 | 32 | 22 | 32 | 43 |
Определив правила «А старше Б» и «А и Б являются ровесниками», сформировать следующие запросы:
- Сколько лет Тому?
- Работают ли на предприятии люди, которым 22 года?
- Кто старше Джона?
- Кто из работающих на предприятии являются ровесниками?
Такие понятия как "интеллект", "интеллектуальность", у специалистов различного профиля (системного анализа, информатики, нейропсихологии, психологии, философии и др.) могут несколько различаться, причем это не несет в себе никакой опасности.
Примем следующую "формулу интеллекта":
"Интеллект = цель + факты + способы их применения",
или, в несколько более "математическом", формализованным виде:
"Интеллект = цель + аксиомы + правила вывода из аксиом".
При поиске наиболее удобных, рациональных средств и форм информационного обмена человек чаще всего сталкивается с проблемой компактного, однозначного и достаточно полного представления знаний.
Знания - система понятий и отношений для такого обмена. Можно условно классифицировать знания в предметной области на понятийные, конструктивные, процедурные, фактографические знания и метазнания.
Понятийные знания - набор понятий, используемых при решении данной задачи, например, в фундаментальных науках и теоретических областях наук, т.е. это понятийный аппарат науки.
Конструктивные знания - наборы структур, подсистем системы и взаимодействий между их элементами, например, в технике.
Процедурные знания - методы, процедуры (алгоритмы) их реализации и идентификации, например, в прикладных науках.
Фактографические - количественные и качественные характеристики объектов и явлений, например, в экспериментальных науках.
Метазнания - знания о порядке и правилах применения знаний (знания о знаниях).
Представление знаний есть процесс, конечная цель которого - представление информации (семантического смысла, значения) в виде информативных сообщений (синтаксических форм): фраз устной речи, предложений письменной речи, страниц книги, понятий справочника, объектов географической карты, мазков и персонажей картины и т.п.
Для этого необходимо пользоваться некоторой конструктивной системой правил для их представления и восприятия (прагматического смысла). Назовем такую систему правил формализмом представления знаний. Неформализуемые знания - это знания, получаемые с применением неизвестных (неформализуемых) правил, например, эвристик, интуиции, здравого смысла и принятия решений на их основе.
|
|
|
Человек пользуется естественным формализмом - языком, письменностью. Язык, языковые конструкции развиваются благодаря тому, что человеческие знания постоянно нуждаются в языковом представлении, выражении, сжатии, хранении, обмене. Мысль, которую нельзя выразить в языковой конструкции, не может быть включена в информационный обмен. Язык - форма представления знаний. Чем многообразнее язык народа, чем больше знаний он может отражать, тем богаче культура народа. В то же время, предложения и слова языка должны иметь однозначный семантический смысл. Особую роль играет язык математики как язык наук (не только точных, но и гуманитарных), формализации знаний, основа изложения системы знаний в естественных науках. Свой язык имеют химия, физика, экономика, информатика и т.д. Языки наук часто пересекаются и взаимообогащаются при исследовании междисциплинарных проблем.
Использование языковых систем и диалектов повышает надежность информационного обмена, снижая возможность неправильного истолкования передаваемой информации и уровень шумов в сообщениях. Главное назначение языка науки - создавать и использовать типовые, "стандартные" формы изложения, сжатия и хранения знаний, ликвидация полисемии (смысловой многозначности) естественного языка. Полисемия, обогащая естественный язык, делая его богаче и выразительнее, тем не менее, является в информационном обмене источником семантического шума, смысловой неоднозначности, а часто - и алогичности, неалгебраичности.
Одной из важных форм (методов) формализации знаний является их представление классом (классификация).
Классификация - выделение некоторого критерия (некоторых критериев) распределения и группировка систем или процессов таким образом, что в одну группу попадают лишь те системы (процессы), которые удовлетворяют этому критерию (значению критерия). Классификация - это метод научной систематики, особенно важный на начальном этапе формирования базовых знаний научного направления. Классификация, установление эквивалентности объектов, систем позволяет решать такие важные задачи информатики как фиксация знаний, поиск по образцу, сравнение и др.
Пример. Такими системами являются классификационная система К. Линнея в ботанике, систематика живых организмов, таблица элементов Д. Менделеева, систематика экономических систем, механизмов, "табель о рангах", введенная Петром Первым в 1722 г. Эта табель подразделяла чины на 14 рангов. Каждому чину соответствовала определенная должность. Первые 6 рангов статской и придворной служб и первый обер-офицерский чин в армии давали право на получение потомственного дворянства, что способствовало формированию дворянской бюрократии. Таким образом, "табель о рангах" выполняла социально-экономическую классификацию определенной (определяющей) части общества, социально-экономическое стимулирующее упорядочивание.
Указанные выше классификационные системы - иерархические структуры (модели) представления знаний. Отдельные понятия, факты, знания, связаны между собой отношениями индуктивного (от частного к общему), дедуктивного (от общего к частному) или индуктивно-дедуктивного вывода и формализуются соответствующими формальными структурами: древовидными, морфологическими, реляционными и др.
Пример. Рассмотрим систему "Фирма". Опишем всех сотрудников фирмы в лексикографически упорядоченном списке с именем "Сотрудники", указывая табельный номер, ФИО, год рождения, образование, специальность, разряд, стаж работы. Этот список дает нам знание о коллективе, его возрастных и профессиональных качествах и др. Составим другой список - "Заработная плата", где укажем для каждого сотрудника условия оплаты, величину их заработка (стоимости единицы времени их работы). Этот список дает нам знания о системе оплаты фирмы, ее финансового состояния и др. Оба списка содержат необходимый объем знаний о трудовом коллективе, если цель исследования этой системы - начисление заработной платы.
Для компьютерного представления и обработки знаний и данных о предметной области (об объектах, процессах, явлениях, их структуре и взаимосвязях), они должны быть формализованы и представлены в определенном формализованном виде.
При традиционном способе реализации математической модели, знаний, заложенных в ней, строится моделирующий алгоритм (моделирующая программа), т.е. знания процедурно зависят от метода (алгоритма) обработки. В интеллектуальных системах (в системах искусственного интеллекта, в частности) знания о предметной области представлены в виде декларативной (описательной) модели формирования базы знаний и соответствующих правил вывода из нее и явно не зависят от процедуры их обработки. Для этого используются специальные модели представления знаний, например, продукционные, фреймовые, сетевые и логические. При обработке модели знаний используются процедуры логического вывода, называемые также механизмом или машиной вывода. Обычно в базе знаний зафиксированы общие закономерности, правила, описывающие проблемную среду и предметную область.
Процедуры вывода позволяют на основании общих правил вывести решение для заданной конкретной ситуации, описываемой некоторыми исходными данными. Цепочка логического вывода строится по мере приближения к решению, в зависимости от введенных на каждом шаге данных и выведенных к этому шагу новых знаний. Конкретные формы организации дедуктивного вывода зависят от того, в какой форме представлены знания в базе знаний (на каком языке представления знаний).
Продукционная модель
Продукционная модель, или модель, основанная на правилах, позволяет представить знания в виде предложений типа:
ЕСЛИ посылка, ТО заключение.
Посылка и заключение – это некоторые высказывания.
Здесь необходимо ввести понятия высказывания и исчисления высказываний.
Высказывание есть утвердительное предложение, которое либо истинно, либо ложно, но не то и другое вместе.
Примеры высказываний: «Снег белый», «Прохоров – декан».
Исчисление высказываний – формальная логическая система. Множество ее базовых элементов составляют логический алфавит T из множества высказываний, обозначаемых строчными латинскими буквами (иногда с индексами) и называемых атомами и четырех элементарных логических функций (связок):
«отрицание» — ~, —, not, не;
«конъюнкция» — Щ, &, and, и;
«дизъюнкция» — Ъ, ч, or, или;
«импликация» — ®;
Исчисление высказываний дает возможность строить составные высказывания из простых, соединяя их логическими связками.
Значение истинности высказывания зависит от его структуры и от значений истинности составляющих ее простых высказываний (табл. 3.1).
Таблица 3.1
| P | Q | - P | P Щ Q | P Ъ Q | P ® Q |
| И | И | Л | И | И | И |
| И | Л | Л | Л | И | Л |
| Л | И | И | Л | И | И |
| Л | Л | И | Л | Л | И |
Расширением исчисления высказываний является исчисление предикатов.
В логике предикатов по сравнению с логикой высказываний имеется еще три логических понятия: термы, предикаты и кванторы.
Термы описывают понятия изучаемой предметной области, а предикаты — свойства этих понятий, а также их поведение и отношения между ними.
Кроме того, имеется два квантора: " — всеобщности и $ — существования. Если x терм, то ("x) читается как «для всех x», «для каждого x», «для любого x», тогда как ($x) читается как «существует x», «для некоторых x», «по крайней мере для одного x».
Запишем следующие утверждения:
1. Каждое рациональное число есть вещественное число.
2. Существует число, которое является простым.
3. Для каждого числа x существует такое число y, что x<y.
Обозначим «x есть простое число» через предикат P(x), «x есть рациональное число» через Q(x), «x есть вещественное число» через R(x) и «x меньше y» через предикат МЕНЬШЕ (x, y).
Тогда указанные выше утверждения могут быть записаны соответственно выражениями:
("X) (Q(X)® R(X)),
($X) P(X),
("X) ($Y) МЕНЬШЕ (X, Y).
Следует обратить внимание, что терм, начинающий с заглавной буквы – это переменная, вместо котолрой может быть подставлена любая константа.
Переменная, к которой применяется квантор, называется связанной, а переменная, к которой не применен квантор, называется свободной.
Определим область действия квантора, входящего в выражение, как то выражение, к которому этот квантор применяется. Так, область действия квантора существования в выражении 3 есть МЕНЬШЕ (X, Y), а область действия квантора всеобщности в выражении 3 есть ($Y) МЕНЬШЕ (X, Y).
Пример атомарных предикатов:
является (ласточка, птица)
отец (X, джон)
Пример предикатной формулы, соответствующей сложному предложению:
имеет (ласточка, крылья), владеет (ласточка, гнездо) →
является (ласточка, птица)
где является (_,_); имеет (_,_); владеет (_ _) — атомарные предикаты.
Подставляя вместо «ласточка» переменную, получим формулу более общего вида. Однако из вышеприведенной конструкции предикатной формулы позволяет сформулировать утверждение не только о конкретном объекте, которым является ласточка, но и обо всех объектах из класса птиц:
имеет (Х, крылья), владеет (Х, гнездо) ®является (Х, птица)
Однако предикат, который содержит переменные; например,
имеет (Х, крылья)
не может быть оценен, т.е. нельзя определить ложь он или истина, пока вместо переменной не будет поставлена константа.
Однако иногда можно определить значения предиката, связав переменные кванторами.
Программные средства, оперирующие со знаниями, представленными правилами, получили название продукционных систем (или систем продукции) и впервые были предложены Постом в 1941 г.
Система продукции, реализованная в виде модели представления знаний экспертной системы, состоит из трех элементов:
1. Набор фактов и правил, образующих базу знаний;
2. Рабочая память, где хранятся факты из базы знаний, а также результаты выводов, получаемых на основе фактов и правил;
3. Механизм логического вывода, использующий правила в соответствии с содержимым рабочей памяти.
Конфигурацию системы продукции упрощенно можно представить рисунок.
Рис.
На простом примере рассмотрим упрощенно механизм функционирования системs продукции.
Допустим, что факты, записанные в базу знаний, имеют вид:
Намерение (отдых).
Место отдыха (горы).
Кроме того, имеются правила:
Намерение (отдых), Дорога (ухабистая)®Использовать (джип).
Место отдыха (горы) ®Дорога (ухабистая).
Допустим, что требуется определить истинность или ложность предиката
Использовать (джип).
Возможна прямая и обратная цепочка рассуждений.
В том и другом случае факты переписывются из базы знаний в рабочую память.
При прямой цепочке рассуждений в базе знаний отыскивается правило, в котором анализируемый предикат находится в заключении. При этом проверяется истинность посылки. Если посылка истинна, то она переписывается в рабочую область, и процесс вывода закончен. В противном случае отыскивается следующее правило и так до тех пор, пока будет доказана либо истинность, либо ложность заданного предиката.
Для рассматриваемого примера последовательность логического вывода будет следующей:
1. Механизм вывода анализирует правила, начиная с него, определяет наличие факта
Намерение (отдых)
в рабочей памяти и отсутствие в ней факта
Дорога (ухабистая).
2. Посылка правила 1 считается ложной, механизм вывода переходит к следующему правилу (в нашем случае к правилу 2).
3. Посылка правила 2 признается истинной, так как факт
Место отдыха (горы)
присутствует в рабочей памяти и механизм вывода считает заключение правила 2 истинным.
4. Заключение правила 2
Дорога (ухабистая)
заносится в рабочую память.
5. После просмотра всех правил происходит вторичное их применение, начиная с правила 2, за исключением тех, которые уже были применены (в примере это правило 2).
6. При повторном рассмотрении правила 1 его посылка становится истинной ввиду доопределения рабочей памяти, и механизм вывода выполняет его заключение.
7. Заключение
Использовать (джип)
переносится в рабочую память, а правило 1 исключается из дальнейшего согласования.
8. Правил для сопоставления не остается, система останавливается, то есть. доказана истинность анализируемого предиката.
Способ, при котором на основании фактов исследуется возможность применения правила, пригодного для подтверждения, называется обратным выводом.
Для пояснения этого способа обратимся к тому же примеру. Целью запроса также является доказательство истинности предиката
Использовать (джип).
Считая, что рабочая память содержит факты
Намерение (отдых)
и
Место отдыха (горы),
ищем правило, которое в качестве заключения содержит анализируемый предикат.
Последовательность вывода следующая:
• Определяется правило, в котором в заключительной части содержится предикат
Использовать (джип).
Это правило 1.
• Исследуется возможность применения правила 1 для подтверждения истинности предиката.
• Поскольку факт
Намерение (отдых)
из посылки правила 1 занесен в рабочую память, то для достижения цели достаточно подтвердить факт
Дорога (ухабистая).
• Факт
Дорога (ухабистая)
принимается за новую цель, и необходимо найти правило, подтверждающее этот факт.
• Исследуется возможность применения правила 2. Посылка этого правила является истинной, так как факт
Место отдыха (горы)
имеется в рабочей памяти.
• Ввиду возможности применения правила 2, рабочая память пополнится фактом
Дорога (ухабистая)
и появляется возможность применения правила 1 для подтверждения цели
Использовать (джип).
Итак, и в этом случае истинность анализируемого предиката доказана.
В более сложных случаях, если правила содержат переменные, то в процессе вывода им ставится в соответствие некоторые константы из фактов и таким образом получается результат.
ЯЗЫК PROLOG КАК РЕАЛИЗАЦИЯ ПРОДУКЦИОННОЙ МОДЕЛИ ДАННЫХ
|
|
|
