5102608(хаб)

К.р. Интеллектуальные информационные системы

Объем пояснительной записки 15 – 20 листов (включая листинг программы)

Оформление содержание и литература + текст программы, исходник и экзешник.

Выполнить все задания. (вариант 4)

СОДЕРЖАНИЕ

ВВЕДЕНИЕ . 3

ТЕОРЕТИЧЕСКАЯ ЧАСТЬ. 5

1. ЭКСПЕРТНЫЕ СИСТЕМЫ. 5

1. Определение и назначение. 5

2. Представление знаний. 6

3. Структура и функционирование экспертных систем. 7

4. Особенности создания экспертных систем. 9

5. Области и критерии применяемости экспертных систем. 10

ПРАКТИЧЕСКАЯ ЧАСТЬ. 12

1. РАБОТА С СИСТЕМОЙ Пролог-Д.. 12

1. Вариант WINDOWS. 12

2. Запуск системы Пролог-Д.. 15

2. ПРОГРАММЫ НА Прологе-Д -ЭТО ЛОГИЧНО.. 17

1.Логические основы работы системы Пролог-Д. 17

2. Процедурная семантика Пролога-Д или исполнение программы. 23

ПОСТРОЕНИЕ БАЗЫ ЗНАНИЙ.. 25

1. Факты и правила. 25

2.Арифметика и другие встроенные предикаты в Прологе-Д. 27

3. Рекурсия. 31

4.Графические возможности системы Пролог-Д.. 34

5. Обработка списков. 40

ОСОБЕННОСТИ РАБОТЫ С СИСТЕМОЙ Пролог -Д. 42

1. Комплект поставки системы Пролог-Д.. 42

2. Запуск системы Пролог-Д.. 42

3. Программа на Прологе-Д и принципы работы системы. 43

4. Версий для Windows95/NT.. 45

ЗАДАНИЕ. 46

ЛИТЕРАТУРА. 49

ВВЕДЕНИЕ.

Буквально на глазах искусственный интеллект вторгся во все направления компьютерной технологии. Системы искусственного интеллекта появились повсеместно – от большого бизнеса до армии. Искусственный интеллект делает профессиональные возможности человека безграничными.

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

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

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

Руководствуясь методическими указаниями студент должен выполнить курсовую работу по данной дисциплине.

Контрольная работа имеет цель:

- привить навыки работы с вычислительной техникой;

- закрепить знания, полученные в процессе изучения дисциплины.

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

Порядок выполнения работы:

1.   Ознакомится с методическими рекомендациями;

2.   Разработать для своего варианта теоретическое обоснование проблемы.

3.   Реализовать, для каждой задачи своего варианта, на языке Пролог-Д базу знаний, описывающую поставленную проблему.

4.   Разработать тестовую программу для демонстрации работы реализованных функций.

5.   Оформить отчет по работе.

Основой информационно-методическое обеспечение самостоятельной робот студента есть конспект лекций, рекомендованная из дисциплины учебная и методическая литература.

Содержание пояснительной записки:

1.     задание на контрольную работу

2.     для каждой задачи своего варианта

2.1.   назначение и область применения разрабатываемой программы (теоретическое обоснование проблемы).

2.2.   основные возможности и характеристики программы

2.3.   постановка задачи

2.4.   текст программы, результаты

2.5.   инструкция по работе с программой

3.     заключение и выводы

4.     литература.

ТЕОРЕТИЧЕСКАЯ ЧАСТЬ.

1. ЭКСПЕРТНЫЕ СИСТЕМЫ.

1. Определение и назначение.

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

По определению Комитета по Экспертным Системам Британского Компьютерного Общества, под экспертной системой понимается «воплощение в ЭВМ компонента опыта эксперта, основанного на знании, в такой форме, что машина может дать интеллектуальный совет или принять интеллектуальное решение относительно обрабатываемой функции». Желательная дополнительная характеристика (которую многие считают главной) - способность системы по требованию объяснить ход своих рассуждений понятным для спрашивающего образом.

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

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

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

2. Представление знаний.

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

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

·                    Конструктивные знания - это знания о наборах возможных структур объектов и взаимодействии между их частями. Получение этого типа знаний характерно для техники и большей части прикладных наук.

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

·                    Фактографические знания - это количественные и качественные характеристики объектов и явлений.

·                    Метазнания – это знания о порядке и правилах применения знаний.

Можно определить модель предметной области как

[МОДЕЛЬ ПРЕДМЕТНОЙ ОБЛАСТИ]=

[понятийные знания]+ [конструктивные знания],

а базу знаний -

[БАЗА ЗНАНИЙ]=

[модель предметной области]+ [процедурные знания]+

+ [метазнания] + [фактографические знания].

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

3. Структура и функционирование экспертных систем.

В архитектуре экспертной системы можно выделить три основных компонента: база знаний, машина вывода и интерфейс пользователя:

1. База знаний (БЗ).

2. Механизм вывода (МВ).

3. Система пользовательского интерфейса (СПИ).

База знаний - центральная часть экспертной системы. Она содержит факты, правила и эвристики, представляющие экспертные знания о предметной области. Можно представлять базу знаний состоящей из фактических знаний и знаний, которые используются для вывода других знаний. Утверждение "Джон Ф. Кеннеди был 35-м президентом Соединенных Штатов" - пример фактического знания. "Если у вас болит голова, то примите две таблетки цитрамона" - пример знания для вывода. Сама база знаний обычно располагается на диске или другом носителе.

Механизм вывода содержит принципы и правила работы. Механизм вывода "знает", как использовать базу знаний так, чтобы можно было получать разумно согласующиеся заключения (выводы) из информации, находящейся в ней. Когда экспертной системе задается вопрос, механизм вывода выбирает способ применения правил базы знаний для решения задачи, поставленной в вопросе. Фактически, механизм вывода запускает экспертную систему в работу, определяя какие правила нужно вызвать и организуя к ним доступ в базу знаний. Механизм вывода выполняет правила, определяет, когда найдено приемлемое решение и передает результаты программе интерфейса с пользователем.

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

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

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

Два подхода получили наибольшее распространение при создании машин (механизмов) логического вывода экспертных систем.

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

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

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

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

4. Особенности создания экспертных систем.



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

Опыт разработки экспертных систем позволяет выделить следующие этапы их создания:

·                    Идентификация - определение проблемы, ресурсов, целей, экспертов. Производится неформальное (вербальное) описание проблемы.

·                    Концептуализация - выделение ключевых понятий   системы, отношений и характеристик, достаточных для полного и детального описания рассматриваемой проблемы.

·                    Формализация - выражение введенных понятий на некотором формальном языке, построение модели исследуемой области.

·                    Этап выполнения - создание одного или нескольких прототипов.

·                    Этап тестирования - оценка выбранного метода представления знаний и работоспособности всей системы в целом на основе проверки прототипа.

·                    Этап опытной эксплуатации - проверка пригодности системы для конечного пользователя.

·                    Модификация системы - полное перепрограммирование или доведение прототипа до состояния программного продукта.

Известны три основные разновидности исполнения экспертных систем:

¨                 Экспертные системы, выполненные в виде отдельных программ, на некотором алгоритмическом языке,   база знаний которых является непосредственно частью этой программы. Как правило, такие системы предназначены для решения задач в одной фиксированной предметной области. При построении таких систем применяются как традиционные процедурные языки PASCAL, C и др., так и специализированные языки искусственного интеллекта LISP, PROLOG.

¨                 Оболочки экспертных систем - программный продукт, обладающий средствами представления знаний для определенных предметных областей. Задача пользователя заключается не в непосредственном программировании, а в формализации и вводе знаний с использованием предоставленных оболочкой возможностей. Недостатком этих систем можно считать невозможность охвата одной системой всех существующих предметных областей. Примером могут служить ИНТЕРЭКСПЕРТ, РС+, VP-Expert.

¨                 Генераторы экспертных систем - мощные программные продукты, предназначенные для получения оболочек, ориентированных на то или иное представление знаний в зависимости от рассматриваемой предметной области. Примеры этой разновидности - системы KEE, ART и др.



         5. Области и критерии применяемости экспертных систем.

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

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

В списке наиболее распространенных в настоящее время за рубежом экспертных систем и их оболочек можно выделить следующие наименования: INSIGT, LOGIAN, NEXPERT, RULE MASTER, KDS, PICON, KNOWLEDGE CRAFT, KESII, S1, TIMM и др.

В качестве критериев, по которым можно судить о возможности создания экспертной системы следует отметить следующие:

1.           Необходимость символьных рассуждений. Нет смысла разрабатывать экспертную систему для численных расчетов, например, для преобразований Фурье, интегрирования, решения систем алгебраических уравнений и др.

2.           Наличие экспертов, компетентных в избранном круге вопросов, которые согласны сотрудничать при создании экспертной системы.

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

4.           Необходимо четко ограничивать круг решаемых задач,   т.е. предметная область выбирается достаточно "узкой", чтобы избежать "комбинаторного взрыва"     объема информации необходимой для компетентного решения поставленной задачи.

5.           Необходима согласованность мнений экспертов о том,   как следует решать поставленные задачи, какие факты необходимо использовать и каковы общие правила вынесения суждений. В противном случае невозможно   расширить базу знаний за пределы опыта одного человека и осуществить сплав экспертных знаний из нескольких областей.

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

7.           Должна обеспечиваться возможность постепенного наращивания системы. База знаний должна легко расширяться и корректироваться, так как правила часто меняются с появлением новых фактов.

ПРАКТИЧЕСКАЯ ЧАСТЬ

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

Очевидно, что любую программу можно написать на машинно-ориентированном языке (ассемблере) или на универсальном языке высокого уровня (Си, Фортран, Бейсик, Паскаль), однако процесс программирования систем ИИ на специализированных средствах занимает в 2-3 раза меньше времени.

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

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

1. РАБОТА С СИСТЕМОЙ Пролог-Д

1. Вариант WINDOWS

Целесообразно, перед началом знакомства с системой вспомнить принципы работы в WINDOWS.

Рисунок 1.1.1. Экран системы Пролог-Д в MS Windows.

Для запуска системы достаточно при помощи мыши выбрать ярлык Пролога -Д или с помощью программ просмотра диска найти файл с программой prologw.exe и двойным нажатием левой клавиши мыши инициировать его исполнение.

На экране появится заставка системы Пролог-Д Windows (рисунок 1.1.1).

Изображенный на рисунке 1.1.1. интерфейс является стандартным для систем, работающих в среде Windows.

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

Если пользователь выбрал один из элементов меню, то появляется падающее меню данного элемента основного меню.

Падающее меню Файлы.

Система позволяет работать одновременно с нескольким файлами. Число файлов обрабатываемых одновременно ограничено только наличием ресурсов Вашего компьютера. Каждому файлу соответствует одно окно.

При выборе данного элемента меню на экране появляется следующее падающее меню, изображенное на рисунке 1.1.2.

.

Рисунок 1.1.2. Падающее меню, появляющееся при выборе элемента Файлы.

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

Элемент меню Открыть позволяет открыть или создать файл, который будет обрабатываться с помощью системы Пролог-Д. При выборе данного элемента появляется специальное окно: позволяющее выбрать интересующий Вас файл внутри данного каталога.

Элемент меню Сохранить позволяет записать обработанный файл в то же место.

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

Элемент меню Исполнение

Содержит элементы Исполнить, Прервать и Настройки. На рисунке 1.1.3 показана панель настроек.

Рисунок 1.1.3. Панель настроек режимов исполнения Пролог-программы.

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

Элемент меню Окна.

При выборе этого элемента появляется падающее меню, изображенное на рисунке 1.1.4.

Рисунок 1.1.4. Падающее меню, появляющееся при выборе элемента Окна.

Выбор элементов меню Каскад, Мозаика, Упорядочить и Свернуть все определяет взаимное расположение окон на экране.

Элемент меню Помощь

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

2. Запуск системы Пролог-Д

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

Для проверки работоспособности системы Пролог-Д и Ваших потенциальных возможностей, достаточно набрать вопрос - предложение, начинающееся с символа "?". Проще всего, если это предложение составлено из так называемых встроенных предикатов. Они предназначены для выполнения арифметических действий, вывода графики и других подобных операций. Встроенные предикаты, если они записаны в вопросе, должны выполняться одинаково, независимо от того, записана в память машины база знаний или нет, и какая это база знаний. В определенном смысле это напоминает непосредственный режим работы в языке БЕЙСИК. Например, если необходимо построить на экране отрезок, соединяющий две точки с координатами (10,10) и (200, 200), то достаточно задать вопрос:

?ЗАПИСЬ_В(“grp:”),ЛИНИЯ(10,10,100,100,1);<Enter>

Требуемый отрезок появится на экране. Для возврата в редактор достаточно нажать клавишу <Esc>.

Если необходимо вычислить число x=2*3+1, то для этого достаточно набрать на клавиатуре вопрос:

?УМНОЖЕНИЕ(2,3,1,x); (<Enter>)

ответ системы:

x=7

ДРУГИХ РЕШЕНИЙ НЕТ.

Для того чтобы попробовать более сложные примеры работы системы Пролог-Д рекомендуется набрать с помощью клавиатуры текст такой программы:

мама(Люся, Саша);(<Enter>)

папа(Сережа, Саша);(<Enter>)

бабушка(Надя, Саша);(<Enter>)

внук(x, y)<-бабушка(y, x);(<Enter>)

К ней можно задать вопрос:

?мама(x, Саша);(<Enter>),

означающий содержательно - "Как зовут маму Саши?" Ответ системы:

x = Люся

ДРУГИХ РЕШЕНИЙ НЕТ

Нажмите на клавишу <Esc> и база знаний вновь появится на экране. Можно попробовать задать еще несколько вопросов, например:

?бабушка(x, y); (<Enter>),

?внук(x, y); (<Enter>),

?папа(Сережа, x); (<Enter>).

О том, почему получается именно такие ответы рассказано в следующих разделах книги.

2. ПРОГРАММЫ НА Прологе-Д -ЭТО ЛОГИЧНО

1.Логические основы работы системы Пролог-Д.

Математическая логика является теоретической основой логического программирования. Цель данного раздела определить начальные понятия математической логики, необходимые для изложения принципов работы с системой Пролог-Д.

Для решения задачи с помощью Пролога-Д достаточно описать знания об этой задаче, а процесс построения решения при этом сводится к некоторой рутинной процедуре.

Описание знаний возможно осуществить с помощью совокупности дискретных объектов и отношений между ними. Объекты, если их соотнести с решаемой задачей, образуют ее предметную область. Например, если задача состоит в описании родственных отношений, то предметная область-множество людей, а если задача вычислительная, то предметной областью будет множество целых чисел.

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

Объекты, используемые в описании задачи, могут быть произвольными. Например, числовые или литеральные константы, переменные, принимающие значения из некоторого множества, функции.

1.Примерами констант могут быть:

1, 2, 33, 14565 - числовые константы;

ав, АНТ25, ПРОЛОГ - литеральные константы.

2.Примерами переменных могут быть:

x, y, z, X, ы, Й.

3.Примерами функций могут быть:

автор(Толстой, Казаки), Сумма(2,3).

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

Терм - это переменные, константы и функции вида:

f(t ₁,t ₂,...,t _n),     (t ₁,t ₂,...,t _n) Î® Dⁿ

где каждое t_i - терм, а f - n-арный функциональный символ или функтор. (арность - это число аргументов). Особенность функции в том, что она принимает значение элемента предметной области Dⁿ , или иными словами представляет собой некоторое отображение совокупности из n (n - ки) элементов из предметной области в элемент предметной области.

Отношения, определяемые над объектами, отличаются от функций. Отношение определяет совокупность элементов из предметной области и представляет собой отображение из D ⁿ в множество {ИСТИНА, ЛОЖЬ}. Например, отношение мама(x, y) определяет совокупность пар (x, y), таких, что элементы множества людей x и y находятся в отношении родства мама. Множество пар (x, y) это множество матерей и детей. В математической логике отношениям даются имена, называемые предикатными символами, а сами отношения называются предикатами в последнем примере предикатный символ-мама.

Более строго понятие предиката можно сформулировать следующим образом:

Предикат - это выражение вида     P(t₁,t₂,...,t_m),

где каждое t_i - терм, а P - m-арный предикатный символ. Формально предикат P(t₁,t₂,...,t_m) можно читать либо как "m - ка (t₁,t₂,...,t_m) принадлежит отношению Р", либо как высказывание Р справедливо для m-ки (t₁,t₂,...,t_m).

В логике имеется набор связок: &, Ú, ¬, <- , <->, которые читаются как "и", "или", "не", "если", "тогда и только тогда", соответственно. Связки можно применить для образования логических формул, объединяя предикаты и другие формулы. Необходимо отметить, что логические связки:, &, Ú, ¬, <- , <-> могут быть выражены друг через друга с помощью следующих соотношений, называемых формулами сокращения:

( A & B ) означает ¬ ( A <- B ),

( A \/ B )   означает ( ¬ A) <- B,

( A <-> B )         означает ( A <- B )&( B <- A ),

где А и В - суть формулы. Наряду со связками существуют кванторы общности (") и существования ($). Кванторы определяют пределы изменения переменных. Формула, стоящая после квантора называется областью действия этого квантора. Для кванторов тоже существуют формулы сокращения:

$x А                   означает (¬("x (¬А))).

Примерами формул служат выражения:

мама(x, y)&мама(y, z);

F1&F2ÚF3&¬F4, если F1,F2,F3,F4 - формулы.

Q(F1,F2), если F1 и F2 - формулы, а Q - квантор существования ($) или общности ( " ).

Таким образом, понятие формулы можно сформулировать таким образом:

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

С помощью этого понятия можно сформулировать понятие предложение:

Предложение - это формула, в которой каждая переменная находится в области действия квантора общности.

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

В качестве примера предложения можно привести выражение:

бабушка(x, y)<-мама(x, z)&мама(z, y).

Содержательно это предложение означает, что бабушка это мама мамы. Перед этим предложением стоят знаки кванторов общности по переменным x, y, z. Их присутствие означает, что формула выполнена для всех x, y, z.

Предложения, построенные в соответствии с введенными выше правилами образуют, язык логики первого порядка. В этом языке термы представляют собой объекты, а предикаты отношения между объектами. С помощью этого языка можно описать все задачи, решаемые на ЭВМ. На основе языка логики первого порядка можно построить различные языки логического программирования, различающиеся по правилам формирования предложения. Среди множества всевозможных предложений особое значение имеют предложения, содержащие связки "и" ( & ) и одну связку "если" ( <- ). Такие предложения называются дизъюнктами. Более точное определение. Дизъюнкт - это предложение вида:

A₁&A₂&...&A_k<-B₁&B₂&...&B_n,                     (2.1)

где A₁,A₂,...,A_k,B₁,B₂,...,B_n - предикаты или литеры.

Особое значение для Пролога-Д имеет понятие дизъюнкта Хорна.

Дизъюнктом Хорна называется такой дизъюнкт, у которого k = 0 или k = 1. При k = n = 0 получается пустой дизъюнкт, обозначаемый символом Л.

Если k = 0, то из формулы (1) получается дизъюнкт вида:

B₁&B₂&...&B_n,

Этот дизъюнкт называется вопросом.

Среди множества всех дизъюнктов особую роль играют те, для которых k=1. Если при этом еще и n=0, то такой дизъюнкт называется фактом:

A₁.

Если же n>0, дизъюнкт называется правилом:

A₁<- B₁&B₂&...&B_n,

где A - голова, а B₁&B₂&...&B_n, - цели, образующие тело правила.

Необходимо отметить свойство формул (2.1). Если воспользоваться, приведенными выше формулами сокращения, связывающими логические связки, то оказывается, что любой дизъюнкт можно преобразовать к такой формуле, что в записи ее будут использованы только связки Ú (или), ¬ (не).

Введенные определения позволяют установить следующую иерархию:

формула

½

предложение

½

дизъюнкт

½

дизъюнкт Хорна

/                  ½       ½       \

                   факт правило    вопрос      пустой

                                                                  дизъюнкт

Рисунок 2.1.1. Иерархия определений.

Базой знаний будет называться всякое (непустое) множество фактов и правил.

Записанная в базе знаний информация представлена в некоторой формально - логической системе и предназначена для изучения информации посредством применения определенного процесса рассуждений, базирующегося на логическом выводе. Эти рассуждения основаны на понятии логического следствия. Известно, что логическое следствие из заданной совокупности допущений или предположений истинно, если истинны эти предположения. Однако одна и та же формула может быть истинной или ложной в зависимости от ее содержательного значения. Например, логическая формула:

(x>y)<-(|x|>|y|),

где знак x>y - означает отношение "x больше y", а знак |x| - абсолютную величину x, истинна, если x и y принадлежат множеству положительных чисел и ложна, если x и y принадлежат множеству отрицательных чисел. В математической логике существует понятие интерпретации, а в разных интерпретациях одна и та же формула может принимать разные значения.

Для интерпретации множества предложений S выбирается множество объектов D, называемое областью интерпретации.

Интерпретация множества предложений S над D состоит из следующих трех соответствий:

1. Каждой константе (числовой или литеральной) ставится в соответствие некоторый элемент из D.

2. Каждому n-арному функтору из S сопоставляется отображение n-ки из Dⁿ в D.

3. Каждому n-арному предикатному символу из S сопоставляется отображение n-ки из Dⁿ в множество {ИСТИНА, ЛОЖЬ}.

Примером интерпретации для множества предложений, описывающих родственные отношения:

{мама(Саша, Оля), мама(Петя, Маша), сын(x, y)<-мама(y, x)}

являются следующие правила.

1. Область интерпретации D={Саша, Оля, Петя, Маша};

2. Функторы отсутствуют.

3. Отображение      а). мама(x, y)->{ИСТИНА, ЛОЖЬ},

                                    б). сын(x, y)->{ИСТИНА, ЛОЖЬ}.

Точное определение логического следствия, основано на понятии выполнимости формулы (предложения). Формула (предложение) выполняется в интерпретации над множеством D тогда и только тогда, когда это предложение в данной интерпретации принимает значение ИСТИНА. Соответственно множество предложений S выполняется в данной интерпретации тогда и только тогда, когда выполняется любое предложение из S. S логически влечет некоторое предложение s, тогда и только тогда, когда для любой интерпретации над любой областью D из выполнимости множества S следует выполнимость в ней s. Если вернуться к последнему примеру, то множество предложений:

S={мама(Саша, Оля), мама(Петя, Маша), сын(x, y)<-мама(y, x)} логически влечет s =сын(Маша, Петя). Это обозначается S ú= s. 30

Смысл отношения ú= состоит в том, что если S ú= s, то это происходит из-за внутренней структуры предложений множества S, независимо оттого, что могут обозначать составляющие их части в той или иной интерпретации. Использование интерпретаций это один способ получения понятия логического следствия, которое, в конечном счете, не зависит от этих интерпретаций.

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

Пусть S - некоторое множество дизъюнктов и U - дизъюнкт. Необходимо определить является ли U логическим следствием из S. Для этого множество S дополняется отрицанием ¬U. Если окажется, что объединение множеств S и {¬U} противоречиво, то U логически следует из S.

Предположим, что даны два дизъюнкта C₁ и C₂ из S, а L₁ и L₂ - комплементарные литеры из C₁ и C₂ соответственно (литеры U и ¬U называются комплементарными). Дизъюнкция C₁ и C₂ (C₁ÚC₂), в которой предварительно вычеркнуты литеры L₁ и L₂, называется резольвентой.

Принцип резолюции основан на том, что резольвента дизъюнктов C₁ и C₂ является логическим следствием C₁ и C₂. Если в результате многократного применения процесса построения резольвент получается пустой дизъюнкт, то множество дизъюнктов S противоречиво. Более того, для противоречивого множества дизъюнктов применениями процесса построения резольвент всегда можно получить пустой дизъюнкт (Л).

Иллюстрацией этого процесса может быть следующий пример.

Множество дизъюнктов S задано следующим образом:

PÚ¬Q₁Ú¬Q₂                                  (2.2)

PÚ¬Q₃                                           (2.3)

UÚ¬Q₃                                           (2.4)

UÚ¬PÚ¬R                                               (2.5)

R                                                    (2.6)

Q₁                                                  (2.7)

Q₃                                                  (2.8)

Для доказательства того, что U является логическим следствием из S, к множеству S добавляется дизъюнкт

¬U.                                                (2.9)

Тогда получаются резольвенты:

¬Q₃                                                (2.10)

из (2.9) и (2.4), а:

Л - пустой дизъюнкт                            (2.11)

из (2.10) и (2.8.).

Следует отметить, что возможен и другой логический вывод.

В данном примере U логически следует из S.

Предположим, что в рассматриваемом примере дизъюнкт (2.9) и предложение (2.4) имеют вид:

¬U(F(a))                                        (2.9')

U(x)\/¬Q₃(x)                                  (2.4')

Не существует какой-либо литеры в (2.9'), комплементарной какой-либо литере в (2.4'). Однако, после подстановки в (4') вместо x - F(a), получается:

U(F(a))Ú¬Q₃(F(a))                        (2.4'')

Теперь U(F(a)) и ¬U(F(a)) комплементарны друг другу. Следовательно, получается резольвента ¬Q₃(F(a)). Следующее определение вводит понятие подстановки.

Подстановка - это конечное множество вида:

(t₁/v₁,...,t_n/v_n),

где v_i - переменные, а t_i - термы.

В приведенном примере (2.9'), (2.4') использована подстановка (F(a)/x).

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

Унификацией двух выражений Е₁ и Е₂ с переменными v₁,...,v_n (или без них) называется нахождение такой подстановки (может быть и пустой), что выражения Е₁ и Е₂ совпадут. Такая подстановка называется унификатором. Если оказалось, что для данных термов не существует унификатора, то термы не унифицируемы.

2. Процедурная семантика Пролога-Д или исполнение программы.

База знаний и следующий за ней вопрос представляют собой программу на Прологе-Д.

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

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

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

Сущность метода резолюций можно проиллюстрировать на примере

P<-Q1,Q2;                           (3.1.)

P<-Q3;                                 (3.2.)

U<-Q3;                                 (3.3.)

U<-P,R;                               (3.4.)

R;                                         (3.5.)

Q1;                                       (3.6.)

Q3;                                       (3.7.)

?U;                                       (3.8.),

где выражения (3.1.)-(3.4.)-представляют собой запись правил, а (3.5.) - (3.8.) - запись фактов. Все вместе это предложения базы знаний. Обратите внимание, что предложения (3.1.)-(3.8.) записаны в иной форме, чем предложения (2.2.)-(2.9.). Обе эти записи эквивалентны. Система Пролог-Д среди предложений(3.1.) - (3.8.) отыскивает первое по порядку вхождение U. В данной программе таковым оказывается предложение (3.3.). Далее делается попытка удовлетворить условия правила (3.3.). Для этого вновь просматриваются предложения базы знаний с целью поиска первого предложения, определяющего Q3. Таковым предложением оказывается формула (3.7.).

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

ПОСТРОЕНИЕ БАЗЫ ЗНАНИЙ

1. Факты и правила.

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

Иными словами, создание информационно-логической модели описываемого на языке Пролог-Д этого явления или процесса. Основное назначение данного раздела состоит в описании методики разработки баз знаний, на примерах достаточно простых, заимствованных из традиционной практики. Первый шаг в направлении построения базы знаний состоит в выявлении объектов и соотношений между ними, отвечающих на вопрос: "Что дано?". Такую информацию целесообразно представлять в виде совокупности фактов. Классическим примером фактографии служит англо-русский словарь. Записанный средствами Пролога-Д он выглядит так:

русангл(мама, mammy);

русангл(небо, sky);

русангл(солнце, sun);

русангл(мальчик, boy);

русангл(круг, ring);

русангл(вокруг, arоund);,

и так далее. Последовательность фактов можно и продолжить, но уже сейчас достаточно слов, чтобы перевести на английский известную детскую песню. Подобные отношения представляют собой грамматическую конструкцию Пролога-Д, называемую фактом. Факт задается в виде функционалa: имя, и совокупность аргументов. В данном примере "русангл" - это имя факта оно определяет информацию, записываемую в нем. Русские и английские слова: мама, mammy, небо, sky, солнце, sky, мальчик, boy представляют собой аргументы факта, определяющего взаимно однозначное соответствие между русскими и английскими словами. Необязательно, чтобы факт имел два аргумента. Например, факт: мужчина(Николай); имеет один аргумент - Николай и имя - мужчина, а факт родился(Петров,Иван,10,сентябрь,1979); имеет пять аргументов - Петров, Иван, 10, сентябрь, 1979 и имя родился. Однако, с точки зрения синтаксиса языка Пролог-Д, необходим хотя бы один аргумент. Если факт в базе знаний имеет имя и не имеет аргументов, то система выдаст сообщение о синтаксической ошибке. Приведенный пример, по сути дела, уже является базой знаний на языке Пролог-Д. К этой базе знаний можно задавать различные вопросы:

?русангл(y,x); - если необходимо узнать, все слова, хранящиеся в базе знаний,

?русангл(мама, x); - если необходимо узнать как по английски мама?

?русангл(x, sky); - если необходимо узнать, что означает слово sky?

Для описания всего множества информации, вообще говоря, достаточно фактов. Однако если возможно задать некоторые связи и отношения между объектами, то удается сократить число фактов, и тем самым сделать базу знаний более лаконичной. Связи и отношения между объектами задаются правилами. При построении правил выделяется совокупность отношений, отвечающих на вопрос "Что известно?".

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

Например, в задаче о построении родственных отношений можно определить следующие правила:

бабушка(x,y)<-мама(x,z),мама(z,y); бабушка(x,y)<-мама(x,z),папа(z,y); дедушка(x,y)<-папа(x,z),папа(z,y); дедушка(x,y)<-папа(x,z),мама(z,y);

Глубина процесса декомпозиции в данном случае автоматически устанавливается. Она определена понятиями "мама", "папа".

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

родитель(x,y)<-мама(x,y);

родитель(x,y)<-папа(x,y);,

то бабушку и дедушку можно определить проще:

бабушка(x,y)<-мама(x,z),родитель(z,y);

дедушка(x,y)<-папа(x,z),родитель(z,y);.

Если, к только, что записанным правилам добавить несколько фактов, определяющих мам и пап, то получается база знаний, которая называется "семья":

мама(Саша,Петя);

папа(Сережа,Петя);

мама(Оля,Саша);

папа(Коля,Саша);

мама(Люда,Сережа);

папа(Петя,Сережа);

родитель(x,y)<-мама(x,y);

родитель(x,y)<-папа(x,y);

бабушка(x,y)<-мама(x,z),родитель(z,y);

дедушка(x,y)<-папа(x,z),родитель(z,y);.

В данном примере для определения понятия родитель(x,y) потребовалось более одного правила. По сути дела здесь использовано недетерминированное ветвление, дающее альтернативное определение этого отношения и используемое системой после того, как было применено первое отношение. Следует подчеркнуть, что в определении участвуют оба правила. В общем случае число правил не ограничено.

2.Арифметика и другие встроенные предикаты в Прологе-Д.

Системы логического программирования, к числу которых относится и Пролог-Д, не предназначены для вычислений. Традиционный для Пролога-Д подход при выполнении арифметических действий описан в упражнении 5 из предыдущего раздела. Однако для определения таким образом всех математических действий памяти компьютера будет недостаточно. Поэтому традиционные действия, связанные с выполнением арифметических операций осуществляются посредством специальных встроенных предикатов. В системе Пролог-Д для выполнения арифметических действий предусмотрен один встроенный арифметический предикат: УМНОЖЕНИЕ(Арг1,Арг2,Арг3,Арг4) Встроенный предикат УМНОЖЕНИЕ имеет четыре аргумента: целых, переменных, конкретизированных целыми, не конкретизированных переменных, допускает обратимость всех аргументов, однако, он может быть использован только в качестве цели в предложении. Предикат УМНОЖЕНИЕ предусматривает реализацию формулы: Арг1*Арг2+Арг3=Арг4.

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

СЛОЖЕНИЕ(X,Y,Z)<-УМНОЖЕНИЕ(1,X,Y,Z);

ВЫЧИТАНИЕ(X,Y,Z)<-УМНОЖЕНИЕ(1,X,Z,Y);

УМНОЖЕНИЕ(X,Y,Z)<-УМНОЖЕНИЕ(X,Y,0,Z);

ДЕЛЕНИЕ(X,Y,Z)<-УМНОЖЕНИЕ(Y,Z,0,X);

Во всех четырех случаях X,Y - суть операнды операций, а Z - результат. Например, СЛОЖЕНИЕ(X,Y,Z) реализует арифметическую операцию сложение: Z=X+Y. Более подробное описание синтаксиса встроенного предиката УМНОЖЕНИЕ приведено в описании синтаксиса. Предикат УМНОЖЕНИЕ позволяет описывать вычислительные задачи.

Пример 1. На Прологе-Д необходимо описать вычисление площади прямоугольника, имеющего стороны длиной a и b. Известна формула определяющая площадь прямоугольника Sпр. Sпр=a*b.

Предикат, который будет выполнен, если вычислена площадь прямоугольника должен иметь три аргумента-Длины сторон и величину площади. Имя предиката должно отражать его назначение, вероятно этому критерию удовлетворит имя площадь:

УМНОЖЕНИЕ(X,Y,Z)<-УМНОЖЕНИЕ(X,Y,0,Z);

площадь(a,b,S)<-УМНОЖЕНИЕ(a,b,S);.

Первый предикат УМНОЖЕНИЕ потребовалось определить для наглядности записи. Необходимо отметить, что предикат площадь обратим, это означает, что, пользуясь этим описанием можно вычислить не только площадь по заданным сторонам, но и любую (одну) сторону по другой стороне и площади. К базе знаний можно задать вопросы:

?площадь(10,20,S);

ответ системы Пролог-Д: S=200,

?площадь(a,20,100);

ответ системы Пролог-Д: a = 5. Более сложная задача представлена в нижеследующем примере.

Пример 2. На Прологе-Д необходимо описать вычисление объема параллелепипеда высотой h, в основании которого прямоугольник, имеющий стороны длиной a и b. Известна формула определяющая объема параллелепипеда Vпар. Vпар=a*b*h. Предикат, который будет выполнен, если будет вычислен объем параллелепипеда должен иметь четыре аргумента - длины сторон a, b, высоту h и величину объема. Имя предиката должно отражать его назначение, вероятно, этому критерию удовлетворит имя объем:

УМНОЖЕНИЕ(X,Y,Z)<-УМНОЖЕНИЕ(X,Y,0,Z);

объем(a,b,h,V)<-УМНОЖЕНИЕ(a,b,S), УМНОЖЕНИЕ (S, h, V);

Как и прежде предикат объем обратим, это означает, что, используя это описание можно вычислить, не только объем по заданным сторонам и высоте, но и любую (одну) сторону или высоту по высоте, стороне и объему. В качестве альтернативы, можно иначе записать объем, если воспользоваться формулой:

Vпар=Sосн*h.

Эту базу знаний предлагается написать самостоятельно.

К базе знаний можно задать вопросы:

?объем(10,20,5,V);

ответ системы Пролог-Д: V=200. Наряду с арифметическим предикатом существуют два предиката БОЛЬШЕ и НЕ. Встроенный предикат БОЛЬШЕ(Арг1,Арг2) предназначен для сравнения двух целых или переменных. Он имеет два аргумента: целых или переменных, конкретизированных целыми. Оба аргумента к моменту выполнения должны быть определены. Если эти требования не выполнены, то появится сообщение об ошибке: "Функция не может быть выполнена.". Предикат выполнен, если Арг1 > Арг2, иначе - не выполнен. Несмотря на то, что предикат БОЛЬШЕ один, его достаточно для описания всех возможных предикатов для сравнения числовой информации: равенство - РАВНО; меньше - МЕНЬШЕ; меньше и равно - МИР и так далее. Это показывает база знаний, приведенная ниже:

РАВНО(X,X);

МЕНЬШЕ(X,Y)<-БОЛЬШЕ(Y,X);

МИР(X,Y)<-НЕ(БОЛЬШЕ(X,Y);

В последнем предложении использован встроенный предикат НЕ, его синтаксис: НЕ(Арг1); Этот встроенный предикат имеет один аргумент, он обязательно должен быть предикатом. Предикат НЕ выполнен тогда и только тогда, когда предикат - аргумент не выполнен. А теперь несложный пример, иллюстрирующий применение БОЛЬШЕ и НЕ.

Пример 3. Опишите на языке Пролог-Д вычисление функции Хевисайда, определяемую формулой:

                          ì        0, если x<0;

       h(x)   =       í        0, если x=0;

                          î        1, если x>0.

База знаний должна содержать описание предиката меньше и равно, который выше уже был описаны, предикат, выполняющийся при вычислении функции Хевисайда, будет называться ХЕВИСАЙД. Этот предикат будет иметь два аргумента, первый это аргумент функции, а второй ее значение. Предикат ХЕВИСАЙД определяется через два альтернативных описания для всех значений x

МИР(X,Y)<-НЕ(БОЛЬШЕ(X,Y);

ХЕВИСАЙД(X,0)<-МИР(X,0);

ХЕВИСАЙД(X,1)<-БОЛЬШЕ(X,0);

К этой базе знаний можно задать различные вопросы.

?ХЕВИСАЙД(20,X);

ответ системы Пролог-Д: X=1. И, наконец, последний встроенный предикат - это предикат - "отсечение", предназначенный для управления логическим выводом. Этот предикат потребуется для решения следующих проблем:

1. Ограничение количества найденных решений.

2. Нахождение некоторого особенного решения задачи.

3. Ограничение объема поиска, с целью повышения эффективности работы компьютера. Предикат "отсечение" обозначается знаком восклицания - (!).

Необходимо отметить, что это традиционное обозначение отсечения в системах логического программирования. Если данный предикат использовать в качестве цели в предложении, то полученный при этом эффект можно проиллюстрировать дверью, через которую можно пройти только слева направо, но нельзя вернуться назад через эту дверь. Роль двери выполняет символ !. Как известно система Пролог-Д будет пытаться выполнять цели в предложении порядке просмотра слева направо, начиная от символа <- от первой до последней цели. Если какая-либо цель оказывается не выполненной, то осуществляется возврат и делается попытка найти альтернативные решения. Отсечение ограничивает возможность поиска альтернатив с того момента, как была просмотрена цель, обозначенная символом !. По этой причине, если не выполнены цели А,Б,В, возврат для нахождения альтернативных решений в предложении пример<-А,Б,В,!,Г,Д,Е; возможен, а, если не выполнены цели Г,Д или Е, то уже нет. Рубикон при движении слева направо перейден. Необходимо отметить важность этого предиката особенно при описании задач, допускающих множественные решения. Иллюстрация предиката отсечение на примере базы знаний мама. Действительно, у каждого человека не может быть две матери, поэтому, определив для данного человека имя матери, необходимо прекратить дальнейшие поиски.

мама(Саша,Петя)<-!;

мама(Наташа,Ваня)<-!;

мама(Оля,Петя)<-!;

мама(Катя,Даша)<-!;

мама(Люда,Сережа)<-!;

мама(Петя,Костя)<-!;

к базе знаний может быть задан вопрос

?мама(x,Даша); ответ системы Пролог-Д:

x=Kатя ДРУГИХ РЕШЕНИЙ НЕТ.

После нахождения первого решения поиск альтернатив не производится.

3. Рекурсия.

Существует огромное количество задач, в которых отношения между объектами можно определить, только используя сами определяемые соотношения. При этом получаются правила, называемые рекурсивными. Применение рекурсии для описания задач при работе с системами логического программирования широко распространенный прием. Рекурсия будет проиллюстрирована несколькими примерами построения программ, как вычислительных, так и логических. Первым примером будет пример вычисления наибольшего общего делителя (НОД) двух чисел. Предикат, который выполняется, если найден НОД двух данных чисел будет иметь имя нод и три аргумента: числа a,b и значение НОД - c. Для описания вычисления НОД используются следующие соображения. Во-первых, если, а=b, то c=a=b; Во-вторых, если, а>b, то необходимо вычислить НОД для чисел b и a-b; В-третьих, если b>a, то необходимо вычислить НОД для чисел a и b-a. Эти три утверждения естественным образом могут быть записаны на Прологе-Д.:

нод(а,а,а);

нод(а,b,c)<-БОЛЬШЕ(а,b),ВЫЧИТАНИЕ(a,b,d),нод(b,d,c);

нод(а,b,c)<-БОЛЬШЕ(b,а),ВЫЧИТАНИЕ(b,a,d),нод(a,d,c);

ВЫЧИТАНИЕ(X,Y,Z)<-УМНОЖЕНИЕ(1,X,Z,Y);

Если к этой базе знаний задать вопрос:

?нод(10,15,x);

ответ системы Пролог-Д:

x=5 ДРУГИХ РЕШЕНИЙ НЕТ

Предикат нод, определенный выше оказывается обратимым. В качестве второго примера рассматривается задача о вычислении элементов последовательности: 0, 1, 1, 2, 3, 5, 8, 13, 21 ,34, 55, 89, 144,... , известной как последовательность Фибоначчи. Каждый элемент ее определяется следующими правилами:

f0 =0,

f1 =1,

fn =fn-1+fn-2, при n>1

Первая формула соответствует утверждению о том, что значение нулевого элемента последовательности равно нулю. Это можно записать в виде факта: Фиб(0,0);. Вторая строка соответствует утверждению: первый элемент равен 1. На Прологе-Д это можно записать так: Фиб(1,1);. Третья строка представляет собой запись рекурсивного соотношения:

Фиб(N,X)<-БОЛЬШЕ(N,1),ВЫЧИТАНИЕ(N,1,М),

ВЫЧИТАНИЕ(N,2,К), Фиб(М,Y), Фиб(K,Z),

СЛОЖЕНИЕ(Y,Z,X);

ВЫЧИТАНИЕ и СЛОЖЕНИЕ - имена предикатов вычитание и сложение, определяемых с помощью правил:

СЛОЖЕНИЕ(X,Y,Z)<-УМНОЖЕНИЕ(1,X,Y,Z);

ВЫЧИТАНИЕ(X,Y,Z)<-УМНОЖЕНИЕ(1,X,Z,Y);.

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

?Фиб(10,X);

ответ системы Пролог-Д:

x=55 ДРУГИХ РЕШЕНИЙ НЕТ

Необходимо сказать, что такой путь решения данной задачи не самый лучший. Для нахождения N+1 числа Фибоначчи требуется 2* (N+1)-1 рекурсивное обращение. Однако этого можно избежать, если перейти к другой базе знаний, в которой предикат с именем "Фиб" определен как трехарный, то есть имеющий три аргумента, включающий в себя в качестве аргумента значения N-ого и N-1- ого элементов последовательности. Такая база знаний получается в результате перевода на язык Пролог-Д утверждений.

1. 0-ой элемент последовательности есть 0, а (-1) -ый элемент не определен. Фиб(0,x,0);.

Второй аргумент обозначен x. В данном случае значение x может быть любым.

2. 1-й элемент последовательности есть 1, а нулевой-0. Фиб(1,0,1);. 3. N -й член последовательности Фибоначчи определяется через (N-1) -Й член последовательности.

Фиб(N,F,f)<-БОЛЬШЕ(N,1),ВЫЧИТАНИЕ(N,1,M),Фиб (M,Ф,F), СЛОЖЕНИЕ (Ф, F, f);.

Обращение к этой базе знаний будет иметь вид:

?Фиб(10,F,f);.

ответ системы Пролог-Д:

F=55, f=34 ДРУГИХ РЕШЕНИЙ НЕТ

При работе с этой базой знаний для вычисления N - го числа Фибоначчи необходимо всего лишь N рекурсивных обращений. Для системы Пролог-Д характерна особенность, проявляющаяся при работе с рекурсивными программами. В общем случае, порядок предложений в базе знаний не имеет значения. Однако, в нижеследующем примере это не так

родитель(X)<- родитель(Y),отец(Y,Z);

родитель(Коля);

отец(Коля, Петя);

родитель(Петя);

В первом предложении голова имеет то же имя, что и одна из целей - "родитель". В процессе поиска ответа в этой базе знаний будет применено правило: предложение, стоящее первым, будет и применено первым - известное как принцип поиска в глубину. Это приведет к тому, что система будет обращаться только к первому предложению базы знаний и ответ на вопрос ?родитель(Петя); не будет найден никогда. Вместе с тем, небольшое изменение базы знаний, перестановка двух предложений местами, приводит к удачному поиску решения:

родитель(Коля);

родитель(X)<-родитель(Y), отец(Y,X);

отец(Коля, Петя);

?родитель(Петя);.

Неограниченно-повторное обращение к предложению может быть и более замаскированным так, как это получается в примере:

ВЫШЕ(А,В)<-НИЖЕ(В,А);

НИЖЕ(В,А)<-ВЫШЕ(А,В);

ВЫШЕ(Коля, Петя);

?НИЖЕ(Петя, Коля);.

Однако если третье предложение стоит на первом месте, то повторного обращения не произойдет и ответ будет найден. Такая ситуация называется петля. При вычислении элементов последовательности Фибоначчи, может появляться бесконечная петля при исполнении программы. В самом деле, если вопрос имеет вид:

?Фиб(0,x,y);,

то первый возможный результат x =_0, y =1. Далее в попытке отыскать следующее решение возникает бесконечная петля, так как будет отыскиваться Фиб(-1,x,y), Фиб(-2,...),... . Для контроля за подобной ситуацией необходима модификация базы знаний. Первые два предложения должны быть записаны в виде:

Фиб(0,x,1)<-!;

Фиб(1,1,1)<-!;,

тогда при поиске альтернативного решения после получения ответа на вопрос:

?Фиб(0,x,y); x=_0, y =1

будет получен результат:

ДРУГИХ РЕШЕНИЙ НЕТ.

Данный пример иллюстрирует первое возможное использование предиката "отсечение". И еще одно чисто эстетическое предложение. База знаний на Прологе-Д будет выглядеть лучше, если предложения с одинаковыми именами расположены в одном месте. Для сравнения приводится две базы знаний:

1.                                          2.

мама(Таня, Надя);                     мама(Таня, Надя);

бабушка(X,Y)<-мама(X,Z),                 мама(Надя, Катя);

мама(Z,Y),                                             бабушка(X,Y)<-мама(X,Z),

мама(Надя, Катя);                      мама(Z,Y);.

4.Графические возможности системы Пролог-Д

Когда речь идет о компьютерной графике, построение изображения на экране интерпретируется серией команд. Таким образом, всякое изображение ассоциируется с алгоритмом его построения. Однако, эта концепция не укладывается в принципы декларативного программирования, принятые в системе Пролог-Д. Если последовать этой концепции то необходимым становится описание элементов рисунка в виде совокупности графических объектов, соотношений и связей между ними. В этом случае описание последовательности действий художника - исполнителя становится излишним. В системе Пролог-Д определен набор графических примитивов, отображающих графические объекты и построенных таким образом, что с точки зрения синтаксиса каждый из них может быть только целью, и принимает значение "истина" (выполняется), если на экране появляется графическое изображение объекта. При записи в правиле нескольких графических примитивов и выполнении данного правила на экране появляется объединение графических образов в той последовательности, как они описаны в правиле. Во всех графических встроенных предикатах аргументами должны быть целыми или переменными, конкретизированными целыми, или не конкретизированными переменными. Если это требование не выполнено, то появится сообщение об ошибке. Параметр v - вертикальный размер, а h - горизонтальный размер экрана. Для стандартной платы видеоадаптера VGA v=349, h=639. В предикатах ТОЧКА, ЛИНИЯ, ОКРУЖНОСТЬ, ЗАКРАСКА последний параметр задает цвет. Как правило, если на этом месте стоит не конкретизированная переменная, то также выводится сообщение об ошибке. Для обозначения цвета при использовании видеоадаптера VGA принята кодировка цветов, изображенная в таблице 3.4.1. В системе Пролог-Д имеет место особенность использования встроенных предикатов, обусловленная спецификой графических средств системы IBM-PC. Для использования графики необходимо открыть графический файл с помощью предиката ЗАПИСЬ_В(“grp:”). После завершения работы необходимо открыть файл для вывода текста ЗАПИСЬ_В(“con:”).

0

черный

8

темно серый

1

синий

9

светло синий

2

зеленый

10

светло зеленый

3

голубой

11

светло голубой

4

коричневый

12

красный

5

фиолетовый

13

сиреневый

6

темно желтый

14

желтый

7

серый

15

белый

Таблица 3.4.1. Таблица кодирования цвета в системе Пролог-Д.

В системе Пролог-Д предусмотрены следующие встроенные графические предикаты:

1. ТОЧКА.

Синтаксис: ТОЧКА(Арг1,Арг2,Арг3)

Встроенный предикат ТОЧКА имеет три аргумента. Ниже приведены результаты выполнения в зависимости от типа аргумента.

ТОЧКА(ц1,ц2,ц3) Установить точку с координатами (ц1,ц2) и цветом ц3;

ТОЧКА(ц1,ц2,П3) П3 := цвет_точки(ц1,ц2);

ТОЧКА(ц1,П2,ц3) Рисовать линию с начальной точкой (ц1,0), конечной - (ц1,211) цветом ц3;

ТОЧКА(П1,ц2,ц3) Рисовать линию с начальной точкой (0,ц2), конечной - (255,ц2) цветом ц3;

ТОЧКА(П1,П2,ц3) Заполнить экран цветом ц3. В этих пяти случаях предикат истинен, иначе - выполнение программы прекращается и выводится сообщение об ошибке: "Невыполнимый предикат ТОЧКА".

2. ЛИНИЯ.

Синтаксис: ЛИНИЯ(Арг1,Арг2,Арг3,Арг4,Арг5).

Этот встроенный предикат имеет пять аргументов. Пятый аргумент всегда должен быть целым, арифметическим выражением или переменной, конкретизированной целым. Результаты выполнения приведены ниже:

ЛИНИЯ(ц1,ц2,ц3,ц4,ц) Рисовать линию с начальной точкой (ц1,ц2), конечной - (ц3,ц4), цветом ц

ЛИНИЯ(ц1,ц2,ц3,П4,ц) Рисовать закрашенный треугольник с вершинами (ц1,ц2), (ц3,0), (ц3,211) и цветом ц;

ЛИНИЯ(ц1,ц2,П3,ц4,ц) Рисовать закрашенный треугольник с вершинами (ц1,ц2), (0,ц4), (255,ц4) и цветом ц;

ЛИНИЯ(ц1,П2,ц3,ц4,ц) Рисовать закрашенный треугольник с вершинами (ц1,0), (ц1,211), (ц3,ц4) и цветом ц;

ЛИНИЯ(П1,ц2,ц3,ц4,ц) Рисовать закрашенный треугольник с вершинами (0,ц2), (255,ц3), (ц3,ц4) и цветом ц;

ЛИНИЯ(П1,П2,ц3,ц4,ц) | ЛИНИЯ(ц1,ц2,П3,П4,ц) |

ЛИНИЯ(ц1,П2,П3,П4,ц) | ЛИНИЯ(П1,ц2,П3,П4,ц) - Заполнение экрана цветом ц

ЛИНИЯ(П1,П2,ц3,П4,ц) | ЛИНИЯ(П1,П2,П3,ц4,ц) |

ЛИНИЯ(П1,П2,П3,П4,ц) | ЛИНИЯ(ц1,П2,ц3,П4,ц) - Вертикальный, закрашенный цветом ц прямоугольник, с вершинами (ц1,0), (ц1,211), (ц2,0), (ц2,211);

ЛИНИЯ(П1,ц2,П3,ц4,ц) Горизонтальный закрашенный цветом ц прямоугольник с вершинами (0,ц2), (255,ц2), (0,ц4), (255,ц4);

ЛИНИЯ(ц1,П2,П3,ц4,ц) Четырехугольник цветом ц с вершинами (ц1,0), (ц1,211), (0,ц4), (255,ц4);

ЛИНИЯ(П1,ц2,ц3,П4,ц) Четырехугольник цветом ц с вершинами (0,ц2), (255,ц2), (ц3,0), (ц3,211).

В этих шестнадцати случаях предикат истинен, иначе выполнение программы прекращается и выдается сообщение об ошибке.

3. ОКРУЖНОСТЬ.

Синтаксис: ОКРУЖНОСТЬ(Арг1,Арг2,Арг3,Арг4).

Встроенный предикат ОКРУЖНОСТЬ имеет четыре аргумента. Четвертым аргументом всегда должно быть целое, арифметическое выражение или переменная, конкретизированная целым. Ниже приведены результаты выполнения в зависимости от типов аргументов.

ОКРУЖНОСТЬ(ц1,ц2,ц3,ц) Окружность с центром (ц1,ц2), радиусом ц3, цветом ц;

ОКРУЖНОСТЬ(ц1,ц2,П3,ц) | ОКРУЖНОСТЬ(ц1,П2,П3,ц) |

ОКРУЖНОСТЬ(П1,ц2,П3,ц) Заполнение экрана цветом ц

ОКРУЖНОСТЬ(П1,П2,П3,ц) | ОКРУЖНОСТЬ(П1,П2,ц3,ц) |

ОКРУЖНОСТЬ(ц1,П2,ц3,ц) Вертикальный закрашенный цветом ц прямоугольник с вершинами: (ц1-ц3,0), (ц1-ц3,211), (ц1+ц3,0), (ц1+ц3,211);

ОКРУЖНОСТЬ(П1,ц2,ц3,ц) Горизонтальный закрашенный цветом ц прямоугольник с вершинами: (0,ц2-ц3), (255,ц2-ц3), (0,ц2+ц3), (255,ц2+ц3); В этих восьми случаях предикат истинен, иначе выполнение программы прекращается и выводится сообщение об ошибке: "Невыполнимый предикат ОКРУЖНОСТЬ"

4. ЗАКРАСКА.

Синтаксис: ЗАКРАСКА(Арг1,Арг2,Арг3,Арг4).

Встроенный предикат ЗАКРАСКА имеет четыре аргумента. Процедурно этот предикат означает закрасить цветом Арг3 внутри контура с граничным цветом Арг4 начиная с точки (Арг1,Арг2). Предикат всегда истинен. Все аргументы должны быть целыми, арифметическими выражениями или переменными, конкретизированными целыми. Если это условие не выполняется, то выполнение программы прекращается и выводится сообщение об ошибке: "Невыполнимый предикат ЗАКРАСКА".

Пример: закрашенный квадрат

рамка(x1',y1',x2',y2',цвет')<-ЛИНИЯ(x1',y1',x1',y2',цвет');

ЛИНИЯ(x1',y1',x2',y1',цвет');ЛИНИЯ(x1',y2',x2',y2',цвет');

ЛИНИЯ(x2',y1',x2',y2',цвет');

пример <- рамка(50,50,150,150,8),ЗАКРАСКА(100,100,15,8);

?пример;.

В качестве примера приводится описание угла, вершина которого находится в точке (x,y):

угол(x,y)<-ЛИНИЯ(x,y,10,10,1),ЛИНИЯ(x,y,150,50,1);

?угол(100,100);.

Сначала будет нарисован отрезок, соединяющий точки (100,100) и (10,10), а затем отрезок, соединяющий точки (100,100) и (50,50). Если бы пятым аргументом предикатов ЛИНИЯ было бы число равное нулю, то точки отрезков были бы не видимы. Не обязательно, чтобы описание всей картинки было записано в одном предложении. Часть описания может быть выделена в виде отдельного предложения. Программу предыдущего примера можно модифицировать:

угол(x,y)<-ЛИНИЯ(x,y,10,10,1),продолжение(x,y);

продолжение(x,y)<-ЛИНИЯ(x,y,50,50,1); ?угол(100,100);.

Новая программа будет выполнять те же самые функции, хотя и записывается в два предложения. Система Пролог -Д допускает возможность использования переменных в графических примитивах. В качестве примера приводится описание вектора, выходящего из точки A с кoординатами (x, y) в точку B координатами (s,t):

вектор(A(x,y),B(s,t))<-ЛИНИЯ(x,y,s,t,1);

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

В качестве примера приводится вопрос:

?ЛИНИЯ(0,0,x,0,1);.

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

квадр(x,y,z,t)<-ЛИНИЯ(x,y,x,t,1),ЛИНИЯ(x,y,z,y,1),

ЛИНИЯ(x,t,z,t,1), ЛИНИЯ(z,y,z,t,1);.

Аналогично определяется треугольник:

треуг(x,y,z,t)<-ЛИНИЯ(x,y,t,y,1),СЛОЖЕНИЕ(x,t,r),

ДЕЛЕНИЕ(r,2,f), ЛИНИЯ(x,y,f,z,1), ЛИНИЯ(f,z,t,y,1);

(Предикат с именем ДЕЛЕНИЕ - предикат деления первого аргумента на второй, частное в третьем, а предикат с именем СЛОЖЕНИЕ есть сложение первого аргумента со вторым, результат в третьем аргументе.) Oпределение дома длиной 20 единиц, высотой этажа 10 единиц и высотой крыши 20 единиц имеет вид:

дом(x,y)<-крыша(x,y,r,f),этаж(x,y,f);

этаж(x,y,f)<-СЛОЖЕНИЕ(y,20,z),квадр(x,y,f,z);

крыша(x,y,r,f)<-СЛОЖЕНИЕ(r,10,y),СЛОЖЕНИЕ(x,20,f),

треуг(x,y,r,f);

Вновь необходимо разделить это описание на две части: в одной части определяется крыша, а в другой, следующей, этаж. (Это, именно тот случай, когда дом начинают строить с крыши.) Использование рекурсивных определений дает возможность записать базу знаний более лаконично. Рекурсия может быть использована и для создания динамически изменяющегося графического объекта. Для этого на одном и том же месте последовательно фиксируется образ объекта, так, что его цвет попеременно меняется от цвета фона до цвета, определяемого в базе знаний. Например, описание летящей птицы, машущей крыльями. В предикате взмах описан взмах вниз и, затем, взмах вверх. Первому положению соответствует горизонтальное положение отрезка белого цвета, затем этот отрезок гасится, становится цветом фона. Положению вверх соответствует угол, состоящий из двух отрезков белого цвета, которые затем гасятся. Каждое из понятий вверх и вниз описывается отдельно, при этом производятся арифметические операции, необходимые для вычисления координат начала и конца отрезков. Периодическое повторение взмаха вверх и вниз осуществляется с помощью рекурсивного обращения к одному и тому же предикату птица. (Внимание! В некоторых вариантах транслятора может быть не предусмотрена обработка возникающей в данном примере эффекта концевой рекурсии, типа петли. Следствием этого может быть аварийный останов после нескольких десятков взмахов. Полное описание птицы, машущей крыльями, приведено ниже:

птица(x,y)<-взмах(x,y),птица(x,y);

взмах(x,y)<-вниз(x,y,1),вниз(x,y,0), вверх(x,y,1), вверх(x,y,0);

вниз(x,y,c)<-сдв(x,y,z,t,u,v), ЛИНИЯ(z,y,u,y,1);

вверх(x,y)<-сдв(x,y,z,t,u,v),ЛИНИЯ(x,y,z,t,1), ЛИНИЯ(x,y,u,v,1);

сдв(x,y,z,t,u,v)<-сдп(x,y,z,t),сдл(x,y,u,v);

сдп(x,y,z,t)<-СЛОЖЕНИЕ(x,5,z),СЛОЖЕНИЕ(t,5,y);

сдл(x,y,z,t)<-СЛОЖЕНИЕ(z,5,x),СЛОЖЕНИЕ(t,5,y);

Декларативность языка позволяет создавать достаточно сложные картины, используя известные принципы декомпозиции графического объекта на части и последующее их описание. Например, картина, содержащая дом, летящую птичку есть пример и описания сложного синтетического объекта, и использования рекурсии для определения динамического изменения объекта:

дом(x,y)<-крыша(x,y,r,f), этаж(x,y,f);

этаж(x,y,f)<-СЛОЖЕНИЕ(y,20,z),квадр(x,y,f,z);

крыша(x,y,r,f)<-СЛОЖЕНИЕ(r,10,y),СЛОЖЕНИЕ(x,20,f),

                          треуг(x,y,r,f);

треуг(x,y,z,t)<-ЛИНИЯ(x,y,t,y,1),ДЕЛЕНИЕ2(x,t,f),угол(x,y,z,t,f);

угол(x,y,z,t,f)<-ЛИНИЯ(x,y,f,z,1),ЛИНИЯ(f,z,t,y,1);

ДЕЛЕНИЕ2(x,t,f)<-СЛОЖЕНИЕ(x,t,r),ДЕЛЕНИЕ(r,2,f);

квадр(x,y,z,t)<-ЛИНИЯ(x,y,x,t,1),ЛИНИЯ(x,y,z,y,1),ч2(x,y,z,t);

ч2(x,y,z,t)<-ЛИНИЯ(x,t,z,t,1),ЛИНИЯ(z,y,z,t,1);.

птица(x,y)<-взмах(x,y),птица(x,y);

взмах(x,y)<-вниз(x,y,1),вниз(x,y,0),вверх(x,y,1),вверх(x,y,0);

вниз(x,y,c)<-сдв(x,y,z,t,u,v),ЛИНИЯ(z,y,u,y,1);

вверх(x,y)<-сдв(x,y,z,t,u,v),

ЛИНИЯ(x,y,z,t,1),ЛИНИЯ(x,y,u,v,1);

сдв(x,y,z,t,u,v)<-сдп(x,y,z,t),сдл(x,y,u,v);

сдп(x,y,z,t)<-СЛОЖЕНИЕ(x,5,z),СЛОЖЕНИЕ(t,5,y);

сдл(x,y,z,t)<-СЛОЖЕНИЕ(z,5,x),СЛОЖЕНИЕ(t,5,y);

В ответ на вопрос:

?дом(70,110),птица(120,50);

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

5. Обработка списков.

На практике часто встречаются задачи, связанные с перечислением объектов. Для описания таких объектов используются списки. Например, список учеников первого класса: [Саша,Петя,Дима,Ксюша,Лена,Оля,Катя].

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

[Челябинск(0),Миасс(2),Златоуст(5),Вязовая(5),Усть-Катав(2), Аша(2), Уфа(20),Абдулино(3),Самара(20),Сызрань(2),Инза(2),

Рузаевка(10), Потьма(2), Рязань(5), Москва(0)].

Примером списка, состоящего из списков, может служить прямоугольная таблица (матрица), представляющая собой список строк, каждая из которых список элементов в данной строке. Например, таблица: 23 45 56 2 78 89 66 45 56 12 3 75 2 3 6 5 2 1 56 2 5 8 9 22 23 22 33 5 6 9 1 33 может быть представлена следующим списком, состоящим из списков:

[[23,45,56,2,78,89,66,45],[56,12,3,75,2,3,6,5],

[2,1,56,2,5,8,9,22],[2,1,56,2,5,8,9,22],[23,22,33,5,6,9,1,33]].

Во всех примерах квадратные скобки означают, что данный объект представляет собой список. Список может быть определен двумя способами: перечислением элементов списка, то есть так, как это было сделано выше и определением головы и хвоста списка. Например, список [X|Y] определен именно таким путем. X - это голова списка, а Y - его хвост. Различные шаблоны определяют различное внутреннее представление.

Шаблону [x,y] соответствует внутреннее представление

СПИСОК

/       \

                   x       СПИСОК

                                      / \

                                      y     [ ]

Шаблону [x|y] соответствует внутреннее представление:

СПИСОК

/   \

x       y

Разные шаблоны - разные внутренние представления - обуславливают различия в унификации. Используя представление списка можно решить ряд задач.

5.1. Принадлежность элемента списку.

Эту задачу можно описать с помощью следующих выражений:

а). Основной случай можно сформулировать следующим образом:

терм Р принадлежит списку [X..Y], если P=X..

б). Рекурсивная ситуация описывается с помощью высказывания "терм Р принадлежит списку [X..Y], если Р принадлежит Y". На языке Пролог-Д эти два высказывания можно записать в виде двух предложений:

принадлежит(P,L)<- равно(L,[X|Y]),равно(P,X);

принадлежит(P,L)<- равно(L,[X|Y]),принадлежит(P,Y);.

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

элемент(P,[P|T]);

элемент(P,[X|Y])<- элемент(P,Y);.

5.2. Склеивание двух списков.

Эту задачу можно описать с помощью следующих выражений:

а). основная ситуация состоит в том, что если к пустому списку [ ] добавить список Р, то в результате получится Р.

б). рекурсивная ситуация состоит в том, что можно список Р добавить к концу списка С, если Р будет добавлен к хвосту С и затем присоединен к голове В. На Прологе-Д эти предикаты можно записать так:

добавить([],[P],[P]);

добавить(C,P,B)<- равно(C,[X,Y]),добавить(Y,P,Z),                                        равно(B,[T,Z]);.

Пользуясь вышеупомянутым свойством процедурной семантики Пролога-Д, эту программу тоже можно упростить:

присоединить([],[P],[P]);

присоединить([X|Y],P,[X|T])<-присоединить(Y,P,T);.

Например, если задан вопрос к этой базе знаний:

?присоединить(L,[Джим |R],[Джек, Билл, Джим, Тим, Джим, Боб];,

то будут получены ответы:

L=[Джек, Билл] R=[Тим, Джим, Боб] L=[Джек, Билл, Джим, Тим] R=[Боб].

ОСОБЕННОСТИ РАБОТЫ С СИСТЕМОЙ Пролог -Д.

1. Комплект поставки системы Пролог-Д

Система Пролог-Д для Windows. На дискете (в архиве, в рабочей директории) должны быть файлы:

PROLOGW.EXE – транслятор (интерпретатор),

PROLOGW.HLP - справка,

BORLANDMM.DLL – системная библиотека,

CP3245MT.DLL – системная библиотека.

2. Запуск системы Пролог-Д

Систему, работающую под управлением Windows95/NT, запускают путем инициации мышью ярлыка, соответствующего вызову программы prologw.exe..

3. Программа на Прологе-Д и принципы работы системы.

3.1. Программа.

Синтаксис: Программа ::= БазаЗнанийВопрос

3.2. База знаний.

Синтаксис: БазаЗнаний ::= {Предложение}*

Предложение::= Факт ¦ Правило ¦ Комментарий

Комментарий::= "{СимволASCII}*"

База знаний на Прологе-Д состоит из множества фактов и правил.

3.3. Факты.

Синтаксис:

Факт ::= Предикат;

Предикат ::= Имя(Аргумент{,Аргумент}*) ¦ Имя

Имя ::= БукваСимвол{Символ}*   Константа::= Целое ¦ Словосочетание

В данной версии Пролога-Д длина имени предикатного символа не ограничена. Аргументом может быть любой терм. Аргументов может и не быть. Факты описывают объекты и отношения между ними. Декларативно Факт P0 означает, что P0 безусловно истинно. Процедурно означает, что факт P0 всегда выполнен.

3.4. Правила.

Синтаксис: Правило::= Предикат<-Цель{,Цель}*;

Цель ::= Предикат ¦ !

Правило описывает отношения между объектами. Предикат, стоящий слева от знака импликации <- называется головой, а предикаты, стоящие справа - целями или посылками. Правило может иметь любое число целей. (Правило без целей - это факт). Декларативно правило P0<-P1,..,Pn; читается так: P0 истинный, если P1, .. , Pn истинны. Процедурно это значит, что для удовлетворения P0 необходимо последовательно удовлетворить P1, .. , Pn.

3.5. Вопрос.

Синтаксис: Вопрос::= ?Цель{,Цель}*; Процедурно вопрос означает исполнение программы на Прологе-Д.

3.6. Запуск программы на Прологе-Д.

Для запуска программы в системе Пролог-Д, работающей под управлением Windows необходимо выбрать элемент меню Исполнение. В этом случае последовательно выполняются все вопросы в порядке следования сверху вниз.

3.7. Правила логического вывода.

В данной версии Пролога-Д реализована SLD-резолюция с правилами вычислений "сначала - в глубину" и "замкнутый мир". Эти правила можно сформулировать так:

1. Цель может унифицироваться с фактом или головой правила.

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

3. Подцели правила удовлетворяются слева направо.

4. Если для некоторой подцели нет ни одного предложения, с которым ее можно унифицировать, то подцель считается ложной.

3.8. Печать результатов.

Печать результатов происходит в окно вывода, которое появляется после ввода вопроса. Если в вопросе нет переменных, то в зависимости от того, является ли вопрос логическим следствием из фактов и правил базы знаний, система делает заключение: ДА или НЕТ. Если в вопросе есть переменные, то процедура логического вывода, встроенная в Пролог, либо делает опровержение, либо выводит значения переменных, подстановка которых делает вопрос логическим следствием из базы знаний.

Решение выводится в виде: <имя> = <значение>.

Отыскиваются все альтернативные решения сразу. Сообщение: ДРУГИХ РЕШЕНИЙ НЕТ свидетельствует о том, что все возможные решения напечатаны. Может оказаться, что некоторые переменные в вопросе остались не конкретизированными.

В этом случае решение выводится в виде: <имя> = _<число>.

3.9. Приостановка вывода.

В том случае, когда альтернативных решений много, возникает необходимость приостановить вывод. Это осуществляется нажатием клавиш <Ctrl>+<Break>. Для возобновления вывода нужно нажать <ESC>.

3.10. Возврат в редактор.

Для возврата в редактор из окна вывода служит клавиша <ESC>.

3.11. Режим электронного задачника.

Нажатием клавиш <Ctrl>+<F8>; включается режим электронный задачник, допускающий второй символ комментария $; режим индицируется символом $ в правом нижнем углу экрана. Нажатием клавиш <Shift>+<Ctrl>+<F8>; электронный задачник, допускающий третий символ комментария @; режим индицируется символом @ в правом нижнем углу экрана.

4. Версий для Windows95/NT

4.1. Особенности кодировки

В версии для MS Windows95/NT используется Windows–кодировка (кодовая страница 1251), стандартным расширением для файлов с Пролог-программами является prw, но система позволяет читать и prl-файлы с программами, созданными в версии для MS-DOS, осуществляя соответствующую перекодировку.

4.2. Встроенные предикаты

Обращение к встроенным функциям ввода ВВОДСИМВ и ВВОДЦЕЛ инициирует появление дополнительного окна для ввода строки или числа. При этом можно вставлять данные из буфера.

4.3. Использование памяти

В версии для MS Windows системе доступна не только вся оперативная память компьютера, но и виртуальная память на жестком диске, что позволяет решать очень сложные задачи типа сортировки длинных списков или построения интерпретаторов языков программирования.

ЗАДАНИЕ

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

Тема1: Логические основы работы системы Пролог-Д.

1. Логические основы работы.

1.1.2. Опишите на языке логики первого порядка свойства отношения равенство.

Тема2: Построение базы знаний

1.Факты и правила.

2.1.2. Опишите на языке Пролог-Д состав своей семьи.

2.Арифметика и другие встроенные предикаты в

Прологе-Д.

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

2.2.3. Опишите вычисление площади круга и длины окружности. Какова точность вычислений этих величин? Можно ли вычислить радиус круга по длине окружности?

3. Рекурсия

2.3.2. Написать на языке Пролог-Д базу знаний, описывающую вычисление суммы чисел натурального ряда.

2.3.4. Описать вычисление наименьшего общего кратного.

4. Графические возможности системы Пролог-Д

2.4.2. Используя рекурсивное определение, напишите базу знаний, описывающую многоэтажный дом.

5 Обработка списков

2.5.2. Напишите базу знаний, описывающую обращение списка. (первый элемент становится последним).

Методические указания составлены по следующим литературным источникам

1.    Абдикеев Н.М. Проектирование интеллектуальных систем в экономике. Учебник / М.: Экзамен, 2004 – 526с.

2.    Алексеев М.Н., Бешенков С.А., Гейн А.Г., Григорьев С.Г. Информатика и информационные технологии: практические работы / Миасс, 2000 - 42 с.

3.    Бешенков С.А., Гейн А.Г., Григорьев С.Г. Информатика и информационные технологии. Екатеринбург: Уральский рабочий, 1995 - 134 с.

4.    Бешенков С.А. Школьная информатика: новый взгляд, новый     курс// Педагогическая информатика. N2. 1993 с. 5-10

5.    Гаврилова Т.А., Хорошевский В.Ф., Базы знаний       интеллектуальных систем. Учебник/ Санкт-Петербург:Питер, 2000- 382 с.

6.    Григорьев С.Г., Морозова Е.В. Информатика и информационные технологии: Сборник задач / ЛБЛ-Балтика. Санкт-Петербург, 1996 – 32 с.

7.    Маковик В. Стандарт интерфейса пользователя // Компьютер пресс.- N 1 1993- c. 33-37.

8.    Мендельсон Э. Введение в математическую логику: Пер. с англ./ Под ред. С.И. Адяна.- 3-е изд.- М.: Наука, Главная редакция физико-математической литературы, 1984- 320 c.

9.    Романов В.П. Интеллектуальные информационные системы в экономике. Учебник / М.: Экзамен, 2003 – 494с.

0	черный	8	темно серый
1	синий	9	светло синий
2	зеленый	10	светло зеленый
3	голубой	11	светло голубой
4	коричневый	12	красный
5	фиолетовый	13	сиреневый
6	темно желтый	14	желтый
7	серый	15	белый