Visual prolog 10 как работать

Урок 3. Основные разделы программы

В языке Visual Prolog используются следующие разделы программы:
• (class) facts – объявление предикатов, описывающих факты (а также внутренних баз данных и фактов-переменных);
• (class) predicates – объявление предикатов (служит для описания используемых программой предикатов, этот раздел является обязательным);
• domains – определение типов данных (содержит определения доменов, которые описывают различные типы объектов, используемых в программе, если используются стандартные типы, то раздел может не использоваться);
• constants – объявление констант;
• clauses – определение фактов или правил (в раздел заносятся факты и правила статической базы данных, которая и является собственно программой, этот раздел является обязательным);
• goal – цель программы (в разделе формулируется цель (запрос) созданной программы. Составными частями при этом могут являться некие подцели, из которых формируется единая цель программы, этот раздел является обязательным и может быть только один в проекте в файле main.pro).

Для примера рассмотрим следующий код программы: В данном примере используются почти все основные разделы программы.
Язык Visual Prolog – типизированный, поэтому предикаты необходимо объявлять. В объявлении предиката указывается его имя, ставится знак двоеточия, а затем в круглых скобках через запятую перечисляются имена доменов (типов данных) аргументов: Словом familyDB обозначено имя базы данных. В объявлениях предикатов можно использовать комментарии специального вида. Слова Name и Gender в этом объявлении обозначают комментарии. Компилятор их игнорирует. Такие комментарии пишутся в одно слово с прописной буквы.

Предикаты объявляются в разделах class facts (если определяются только в виде фактов) или class predicates, а определяются в разделе clauses. Цель программы формулируется в разделе goal, который находится в файле main.pro. Обычно в разделе goal только вызывается некоторый предикат, который используется для составления запросов. В данном примере и всюду далее таким предикатом является run .
Раздел open имплементации класса main следует изменить следующим образом (см. урок 1): Вывод решений для запроса, например для цели ?- father(X, Y) , организуется с помощью предиката fail . Этот предикат имеет значение ложь. Он вынуждает программу вернуться для поиска других решений.

Ключевое слово nondeterm в объявлении предиката означает, что область истинности этого предиката может содержать более одного элемента или не содержать ни одного. Ключевое слово anyflow означает, что некоторые аргументы предиката могут быть как входными, так и выходными. Последовательность (i,o) – означает, что первый аргумент предиката входной, а второй – выходной, ну и последовательность (o,o) – соответственно означает, что оба аргумента предиката – выходные, они возвращают некоторые значения.

Предикат init инициализирует консоль.

Для ввода и вывода в консоли используются буфер ввода и буфер вывода, соответственно. Предикат clearInput очищает буфер ввода, предикат clearOutput очищает буфер вывода. Предикат readLine считывает содержимое буфера ввода в строку ( string ) и при этом полностью очищает содержимое этого буфера. В данном случае программа просто ожидает ввода любого символа.

Структура программы на Visual Prolog

Программа на Visual Prolog имеет следующую обобщенную структуру:

domains /* .

predicates /* .

clauses /* .

предложения (правила и факты) */

goal /* .

подцель _2, и т. д. */

В разделе clauses вы размещаете факты и правила, с которыми будет работать Visual Prolog, пытаясь разрешить цель программы.

Программы на языке Пролог состоят из двух типов фраз: фактов и правил, называемых предложениями.

— Факты — это отношения или свойства, о которых известно, что они имеют значение "истина".

Факты имеют общий вид:

property(objectl, object2, . objectN)

relation(objectl, object2, . objectN)

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

Правилаимеют общую форму заголовок:- тело, которые выглядят так:

relation(object,object. object):-relation(object. object), relation(obj ect. obj ect).

Прологе все правила имеют 2 части: заголовок и тело, разделенные специальным знаком :-.

— Заголовок — это факт, который был бы истинным, если бы были истинными несколько условий. Это называется выводом или зависимым отношением.

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

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

Различия между этими понятиями несущественны, и, поэтому, часто используется обобщенный термин отношение.

В разделе predicates вы объявляете предикаты и домены (типы) аргументов этих предикатов. Имена предикатов должны начинаться с буквы (желательно строчной), за которой следует последовательность букв, цифр и символов подчеркивания (до 250 знаков). В именах предикатов нельзя использовать символы пробел, минус, звездочка, слэш. Объявление предиката имеет следующую форму:

predicateName(argumentTypel OptionalNamel, argumentType2 OptionalName2, < . >; argumentTypeN OptionalNameN)

Здесь argument_type1, . argument_typeN — либо стандартные домены, либо домены, объявленные в разделе domains. Объявление домена аргумента и описание типа аргумента — суть одно и то же. Имена аргументов OptionalNamel будут игнорироваться компилятором.

В разделе domains объявляются любые нестандартные домены, используемые для аргументов предикатов. Домены в Прологе являются аналогами типов в других языках. Основные стандартные домены Visual Prolog: char, byte, short, ushort, word, integer, unsigned, long, ulong, dword, real, string И symbol.

Основная форма объявления доменов имеет вид:

myDomainl, . . ., myDomainN = <standardDomain>

Форма объявления составных доменов имеет следующий вид:

myDomainl. myDomainN = <compoundDomain_l>;

<compoundDomain_2>; < . >; <compoundDoma i n_M>

Домены позволяют задавать разные имена различным видам данных. В программах Visual Prolog объекты в отношениях (аргументы предикатов) принадлежат доменам, причем это могут быть как стандартные, так и описанные вами специальные домены.

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

Таблица 1 — Основные стандартные предикаты

Домен	Описание и реализация
short	Короткое, знаковое, количественное. Все платформы 16 бит (-32 768-32 767)
ushort	Короткое, беззнаковое, количественное, Все платформы 16 бит (0—65 535)
long	Длинное, знаковое, количественное, Все платформы 32 бит (-2 147 483 648-2 147 483 647)
ulong	Длинное, беззнаковое, количественное, Все платформы 32 бит (0-4 294 967 295)
integer	Знаковое, количественное, имеет платформо-зависимый размер, Платформы 16 бит (-32 768-32 767), Платформы 32 бит (-2 147 483 648-2 147 483 647)
unsigned	Беззнаковое, количественное имеет платформо-зависимый размер. Платформы 16 бит (0—65 535) Платформы 32 бит (0-4 294 967 295)
byte	Все платформы 8 бит (0— 55)
word	Все платформы 16 бит (0-65 535)
dword	Все платформы 32 бит (0-4 294 967 295)
char	Символ, реализуемый как беззнаковый byte. Синтаксически это символ, заключенный между двумя одиночными кавычками: ‘ а’
real	Число с плавающей запятой, реализуемое как 8 байт в соответствии с соглашением IEEE; эквивалентен типу double в С. Синтаксически числа с необязательным знаком (+ или -), за которым следует несколько цифр DDDDDDD, затем необязательная десятичная точка (.) и еще цифры ddddddd, за которыми идет необязательная экспоненциальная часть (е(+ или -)ddd): <+\|-> DDDDD <.> DDDDDDD <е <+\|-> DDD> Примеры действительных чисел (real): 42705. 9999. 86.72 9111.929437521е238. 79.83е+21 Здесь 79.83е+21 означает 79.83х10 21 , как и в других языках. Допустимый диапазон чисел: от 1×10"" 307 до 1х10 +зое (от 1е-307 до 1е+308). При необходимости, целые автоматически преобразуются в real
string	Последовательность символов, реализуемых как указатель на байтовый массив, завершаемый нулем, как в С. Для строк допускается два формата: 1. Последовательность букв, цифр и символов подчеркивания, причем первый символ должен быть строчной буквой. 2. Последовательность символов, заключенных в двойные кавычки.
symbol	Последовательность символов, реализуемых как указатель на вход в таблице идентификаторов, хранящей строки идентификаторов. Синтаксис — как для строк

В разделе goal вы задаете внутреннюю цель программы; это позволяет программе быть скомпилированной, запускаться и выполняться независимо от среды визуальной разработки (VDE).

Правила имеют форму:

HEAD: — <Subgoall>, <Subgoal2>, . <SubgoalN>.

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

Оператор Пролога :- (if) отличается от if, используемых в других языках: правило Пролога работает в соответствии с условной формой тогда/если, тогда как этот оператор в других языках работает в соответствии с условной формой если/тогда.

Пролог всегда ищет решение, начиная с первого факта и/или правила, и просматривает весь список фактов и/или правил до конца.

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

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

Анонимные переменные позволяют "привести в порядок" наши программы. Если вам нужна только определенная информация запроса, можно использовать анонимные переменные для игнорирования ненужных значений. В Прологе анонимные переменные обозначаются символом подчеркивания (_). Анонимная переменная может быть использована на месте любой другой перемен ной и ей никогда не присваивается значение.

Хорошим стилем программирования является включение в программу комментариев, объясняющих все то, что может быть непонятно кому-то другому (или даже вам, спустя полгода). Если вы подберете подходящие имена для переменных, предикатов и доменов, то вам понадобится меньше комментариев, т. к. программа будет объяснять себя "сама".

Многострочные комментарии должны начинаться с символов /* (косая черта, звездочка) и завершаться символами */ (звездочка, косая черта). Для установки одно строчных комментариев можно использовать либо эти же символы, либо начинать комментарий символом процента (%).

/* Это первый пример комментария */ % Это второй пример комментария

А эти три строчки — пример многострочного комментария

/*Вы также можете поместить комментарий Visual Prolog /*внутри комментария */ как здесь*/

СТРУКТУРА ПРОГРАММЫ НА ЯЗЫКЕ PROLOG

Обычно программа Visual Prolog включает три или четыре основных раздела. Это раздел выражений clauses, раздел описания предикатов predicates, раздел доменов domains и раздел цели goal.

Раздел clauses

В разделе выражений clauses программист размещает все включаемые в программу факты и правила.

Выражения, относящиеся к определенному предикату, должны размещаться в разделе clauses вместе. Последовательность определяющих предикат выражений называется ПРОЦЕДУРОЙ.

Фактом называют отношение или свойство, о котором известно, что оно имеет значение истина. Например:

Pred1(1).

pred3(computer(ibm,ps_2)).

Правилом же является конструкция, содержащая некоторые условия:

pred4(Arg1,Arg2. ArgN) if

pred5(. ) and pred6(. ) and . predN(. ).

pred4(Arg1,Arg2. ArgN) :- pred5(. ), pred6(. ), . , predN(. ).

где «:-» соответствует «if», а «,» соответствует «and».

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

Раздел predicates

Если программист определяет в разделе clauses свой собственный предикат, то он ДОЛЖЕН объявить его в разделе predicates. В противном случае Visual Prolog не будет знать, о чем идет речь. Когда объявляется предикат, Прологу сообщается о том, к каким доменам принадлежат аргументы этого предиката.

Предикаты определяются фактами и правилами. В разделе predicates просто перечисляется каждый предикат с указанием доменов аргументов.

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

Общий вид определения предиката:

pred(dom1,dom2. domN)

pred – имя предиката (имя отношения) (формально оно относится к типу symbol), dom – тип данных конкретного аргумента (всего аргументов в предикате N – это число аргументов предиката, его называют арностью предиката (от термина arity, и иногда пишут pred/N).

Predicates

Run

Sum(real,real,real).

Parent(string,string).

Student(string).

В этом же разделе можно задать тип детерминизма предиката, вставляя перед объявлением предиката ключевые слова procedure, determ, failure или erroneous. С другой стороны, можно определить недетерминированный предикат – вставляя перед его объявлением ключевые слова nondeterm или multy. Если предикат объявляется как детерминированный, то компилятор выдает предупреждение или ошибку, если найдет недетерминированные предложения для этого предиката. Режимом детерминизма для предикатов по умолчанию является determ.

Раздел domains

Домены в Прологе подобны типам в Паскале. Они дают возможность присваивать различным видам информации, которая в противном случае выглядела бы одинаково, отличные имена. В программе Visual Prolog объекты в отношении (аргументы предиката) принадлежат доменам; это могут быть домены стандартные или специальные, определяемые программистами.

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

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

Domains

selector = integer% тип selector для целых чисел

list_str = string* % список со строковыми данными

computer = name(string,list_sel,selector,integer) % описание структуры

Раздел goal

В Visual Prolog предусмотрен раздел goal, который должен включаться в программу.

Важно отметить то, что содержание раздела goal аналогично правилу. Это попросту список подцелей. Но между разделом goal и правилом есть два отличия:

1. После ключевого слова goal не следует знак :- (если).

2. При запуске программы на выполнение Visual Prolog отрабатывает цель автоматически.

Visual Prolog как бы вызывает цель (обращается к разделу goal), а программа выполняется, пытаясь удовлетворить тело целевого правила. Если достигаются все подцели раздела goal, то программа успешно завершается. Если же в процессе выполнения программы какая-либо подцель не достигается, то и программа заканчивает работу неудачно. Хотя, если смотреть на программу извне, разница между этими двумя случаями не обязательно должна быть видна; программа просто завершается.

Другие разделы программы

Раздел facts

Программа на Visual Prolog представляет собой совокупность фактов и правил. Иногда в процессе выполнения программы может возникнуть потребность видоизменения (модификации, удаления или добавления) некоторых фактов, с которыми работает программа. В таком случае факты образуют ДИНАМИЧЕСКУЮ или ВНУТРЕННЮЮ базу данных; она может изменяться в процессе выполнения программы. В Visual Prolog для объявления в программе фактов, которые должны стать частью динамической (или изменяющейся) базы данных, предусмотрен специальный раздел — facts.

Такой раздел базы данных объявляется с помощью ключевого слова facts, куда включаются объявления фактов, предназначенных для организации динамической базы данных (БД). В Visual Prolog имеется несколько встроенных предикатов, существенно облегчающих использование динамической БД.

Раздел constants

В программе на Visual Prolog можно объявить и использовать символические константы. Раздел объявления констант начинается ключевым словом constants, после которого следуют сами объявления с соблюдением следующего синтаксиса:

<Идентификатор> – это имя константы, а <Макроопределение> – это то, что этому имени соответствует. Каждое <Макроопределение> заканчивается символом новой строки, так что в одной строке может размещаться только одно описание константы. На объявленные таким образом константы можно затем ссылаться в программе.

Рассмотрим следующий пример:

Constants

нуль = 0

один = 1

два = 2

сотня = (10*(10-1)+10)

пи = 3.141592653

еда = мясо

красный = 4

Перед компиляцией программы Visual Prolog заменит каждую константу действительной строкой, которую она представляет.

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

— определение константы не может ссылаться само на себя;

— в программе может быть несколько разделов constants, но константы должны объявляться до их использования;

— идентификаторы констант являются глобальными и могут объявляться только один раз. Несколько объявлений одного и того же идентификатора приведут к выдаче сообщения Constant identifier can only be declared once (Идентификатор константы может быть объявлен только один раз).

Разделы global

Visual Prolog позволяет объявить в программе некоторые домены, предикаты и выражения ГЛОБАЛЬНЫМИ (в отличие от ЛОКАЛЬНЫХ). Это можно сделать, сформировав в самом начале программы отдельные разделы globaldomains, globalpredicates и globalfacts.

ПРАКТИЧЕСКИЕ ЗАДАНИЯ

1. Наберите в окне редактора следующую программу:

Domains

num1, num2, rez = real

Predicates

Sum(num1,num2,rez)

Clauses

sum(Num1,Num2,Rez):-Rez=Num1+Num2.

Как видно, данная программа предлагает найти сумму двух чисел. Входящими параметрами здесь являются Num1, Num2, а выходящим – Rez.

Добавьте в программу правило нахождения суммы трёх чисел – sum(Num1,Num2,Num3,Rez). Не забудьте при этом объявить новый предикат.

2.Опишите на Прологе свое дерево родственных отношений на примере рис.1:

Маша Витя

Петя Света Таня Ваня

Юра Катя

Рис.1. Дерево родственных отношений.

Факты должны быть:

parent/2 (т.е. 2-й арности)

КОНТРОЛЬНЫЕ ВОПРОСЫ

Какова структура Пролог-программ?
Какие разделы программ относятся к основным?
Что содержится в разделе DOMAINS?
Что содержится в разделе PREDICATES?
Что такое «арность»?
Для чего предназначен раздел CLAUSES?
Опишите раздел GOAL.
Перечислите дополнительные разделы программ. Дайте их краткую характеристику.

ЛАБОРАТОРНАЯ РАБОТА №2

Тема: Создание программ на логическом языке в среде Visual Prolog.

Цель:Научиться писать простейшие программы на языке Пролог.

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

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

В логической модели знаний, которая используется в языке Пролог, база знаний (БЗ) состоит из фактов и правил.

Описание фактов – достаточно простая задача, так как факт определяет свойство объекта или отношение (связь) между объектами. Любое имя, используемое в Прологе, должно состоять не более чем из 250 символов, первый из которых при этом должен обязательно быть строчной буквой (кроме имён переменных) желательно латинского алфавита (от a до z). Пробелы в записи имени недопустимы, однако можно использовать подчерк (_) в качестве разделителя компонент.

Наибольшую трудность представляет описание правил. Правила используются в тех случаях, если необходимо показать, что некоторый факт зависит от других фактов (условий). Правила обладают большей общностью, чем факты. Это объясняется тем, что в правилах обычно содержаться переменные. Важно помнить, что переменная используется для обозначения не одного конкретного объекта, а различных объектов. Область действия переменной – одно правило. Кроме того, переменная обозначает один и тот же объект по всему правилу. Вот почему в процессе логического вывода все вхождения одной переменной в правиле заменяются одним и тем же значением. Имена переменных должны задаваться с заглавной буквы или с символа подчёркивания «_». Существует и особый вид переменной, которая называется анонимной и обозначается символом «_» (и только!). Она используется в качестве аргумента предиката в случае, когда конкретное значение переменной несущественно. Значения таких переменных не выводятся на печать. Следует заметить, что если в одном правиле используется несколько анонимных переменных, то все они разные.

Например, если нас интересует, является ли кто-либо мамой, но нам не нужно знать их детей (см. лабораторную работу №1), то нужно задать цель:

Пролог при этом выдаст имена всех матерей, которые найдёт в базе данных согласно правилу:

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

ФОРМУЛИРОВКА ЦЕЛЕЙ

Существует два вида целей:

Ø подтвердить справедливость факта. Ответом системы на такие запросы выступает логическое Yes или No. В естественном языке такие цели соответствуют конструкции вопроса типа: «Действительно ли, что … ?»;

Ø перечислить все значения переменных, указанных в запросе. В естественном языке аналогом этих целей выступают вопросы, начинающиеся со слов Что? Кто? Сколько? Где? и т.д., ответы на которые требуют уточнения кое-каких деталей касательно объекта, указанного в вопросе.

При формулировке правил и целей допускается использование отрицания, конъюнкции, дизъюнкции, а также операций сравнения (<,<=,>,>=,<>,=).

МОДЕЛИРОВАНИЕ РАССУЖДЕНИЙ

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

Пусть программа на Прологе содержит следующие утверждения (факты и правила)(фразы, заключенные в «/*..….*/», воспринимаются Прологом как коментарий):

знает(мария,хор)./* Мария знает хор*/

(1) знает(мария,сольфеджио). /* Мария знает сольфеджио*/

(2) знает(мария,информатика). /* Мария знает информатику*/

(3) знает(мария,алгебра). /* Мария знает алгебру*/

знает(мария,геометрия). /* Мария знает геометрию*/

/*Иван знает те же курсы, что и Мария, при условии, что эти курсы изучаются в университете */

знает(иван,X):- знает(мария,X),университет_курс(X).

университет_курс(информатика)./*информатика изучается в университете*/

университет_курс(алгебра). /*алгебра изучается в университете*/

университет_курс(геометрия). /*геометрия изучается в университете*/

музыка_курс(сольфеджио). /*сольфеджио изучается в музучилище*/

музыка_курс(хор). /*хор изучается в музучилище*/

и цель:

знает(иван,X)./*какие курсы знает Иван?*/

Пролог ищет факты и головы правил, сопоставимые с целью. Два факта сопоставимы (или соответствуют друг другу), если выполняются следующие три условия сопоставления фактов:

1. имена отношений одинаковы (побуквенное совпадение);

2. отношения имеют равное количество аргументов;

3. аргументы, расположенные в одинаковых позициях, сопоставимы.

Правила сопоставления аргументов:

3.1. Имена конкретных объектов сопоставимы, если они совпадают;

3.2. Переменная сопоставима с именем конкретного объекта;

3.3. Переменная сопоставима с другой переменной.

Пролог просматривает утверждения в том порядке, в каком они вводились в БЗ. Поэтому сначала сравниваются цель

Первые аргументы несопоставимы. Следовательно, попытка сопоставить цель и факт неуспешна. Пролог продолжает сопоставлять цель со всеми фактами для отношения «знает». Результаты этих сопоставлений неуспешны, так имя объекта «мария» несопоставимо с именем «иван». Пролог переходит к правилу. Цель и голова правила сопоставимы, так как их переменные свободны (неозначенные переменные называются свободными). Теперь факты правой части правила становятся подцелями. Первой подцелью является

Это новая подцель, поэтому Пролог снова начинает просмотр БЗ с первого факта для отношения «знает» и находит

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

Вторая подцель есть:

так как переменная Х имеет значение «хор». Все сопоставления этой подцели с фактами БЗ неуспешны. Поэтому первая попытка доказать цель завершилась неудачей.

Пролог выполняет откат к указателю (1). Переменная Х становится свободной из-за неуспешного доказательства цели. В точке, определяемой указателем отката, Пролог находит утверждение

и устанавливает указатель отката (2) на следующий факт для предиката «знает». Переменная Х принимает значение «сольфеджио».

не может быть доказана, следовательно, доказательство цели снова привело к неудаче. Переменная Х освобождается, а для доказательства цели будет сделана следующая попытка. Пролог выполняет откат в точку (2). Теперь первая подцель сопоставляется с фактом

Х получает значение «информатика», а указатель отката устанавливается в точку (3). Вторая подцель принимает вид:

Успешное сопоставление этой подцели доказывает цель. Следовательно, ответ на поставленный вопрос формулируется так: «Иван знает информатику». Цель успешно доказана, поэтому переменная Х становится свободной и может быть вновь означена при поиске других решений.

ПРАКТИЧЕСКИЕ ЗАДАНИЯ

1. Описать БЗ «Библиотека», содержащую факты:

Ø О читателях – студентах:

Фамилия	Курс	Фамилия	Курс
Иванов	Анисимов
Петров	Тихонов
Сидоров	Травкин
Ковалёв	Жданов
Антонов	Галкин

Ø О книгах, невозвращённых читателями в срок

Название книги	Номер книги	Год издания	Фамилия студента
Физика	Иванов
Химия	Петров
Физика	Антонов
Химия	Тихонов
Химия	Галкин
Математика	Галкин

Ø Добавить к БЗ правило, позволяющее определить:

какие книги (название, номер) не возвращены студентами заданного курса;
кто из студентов не вернул книги, изданные до 1990 года;
кто из студентов не вернул книги заданной тематики (например, по химии).

1. перечислить фамилии студентов 3-го курса, которые пользуются услугами библиотеки;

2. перечислить фамилии студентов 2-го и 4-го курсов, которые пользуются услугами библиотеки;

3. какие книги (название и номер) не возвращены студентами 2-го курса?

4. Кто из студентов не вернул книги, изданные до 1990 года?

5. Кто из студентов не вернул книги по физике?

2. Описать БЗ «Компьютеры».

Факты базы знаний содержат следующую информацию.

— какие фирмы изготавливают вычислительные системы и их составные части:

Фирмы-изготовители	Название изделия
Mem1, Mem2	Внутренняя память
Disk1, Disk2	Диски
Pr1	Процессоры
Comp1, Comp2	Компьютеры
Net1, Net2	Вычислительные сети

— услугами каких фирм-поставщиков пользуются фирмы-изготовители. (Одна и та же фирма может быть изготовителем и поставщиком, например, Comp1.) (рис.2)

Определить отношение «конкурент». Две фирмы конкурируют, если они выпускают одинаковые устройства.

Определить отношение «использует изделие», которое устанавливает связь между фирмами-поставщиками и фирмами-изготовителями. Например, фирма Comp1 использует изделия от фирм Mem1, Disk1, Disk2, Pr1, а фирма Net1 – от Mem1, Disk1, Disk2, Pr1, Comp1 (рис.2).

Comp1 Mem1 Comp2 Mem2

Рис.1. Взаимодействие фирм-поставщиков и фирм-изготовителей.

Получить ответы на следующие вопросы:

1. Какие фирмы производят внутреннюю память?

2. Изделиями каких фирм пользуется фирма Net2?

3. Какие фирмы конкурируют между собой?

4. Какие фирмы по изготовлению компьютеров конкурируют между собой?

5. Диски каких фирм использует фирма Comp1?

6. Какие фирмы поставляют изделия для фирмы Comp2?

7. Внутреннюю память каких фирм использует фирма Net2?

3. Индивидуальное задание. Разработать программу, содержащую простую базу данных с использованием правил для получения информации в результате поиска по образцу среди совокупности фактов в заданной предметной области для заданного количества объектов и учитываемых параметров (таблица 1).

Указание:тип объектов, характеристики учитываемых параметров, а также характеристики образца выбрать самостоятельно.

Таблица 1.

№ варианта	Наименование предметной области	Количество объектов	Количество учитываемых параметров
«Поиск жилья» (для фирмы по торговле недвижимостью)
«Поиск преступника» (для органов внутренних дел)
«Выбор места для отдыха» (для бюро путешествий)
«Выбор подарка» (для супермаркета)
«Поиск работы» (для службы занятости)
«Подбор книг» (для библиотеки)
«Выбор автомобиля»
«Выбор компьютера»
«Поиск преступника»
«Выбор подарка»
«Выбор места для проведения отпуска»
«Выбор жилья»
«Выбор авиакомпании для путешествия по заданному маршруту»
«Выбор загородного дома»
«Выбор подарка»
«Поиск преступника»
«Выбор автомобиля»
«Выбор компьютера»
«Подбор книг» (для библиотеки)
«Выбор загородного дома»
«Поиск работы»
«Отбор кинофильма для предварительного показа на кинофестивале»
«Выбор места для отдыха»
«Выбор загородного дома»
«Выбор облицовочных материалов для ремонта квартиры»

КОНТРОЛЬНЫЕ ВОПРОСЫ

Что входит в базу знаний Пролога?
Что описывают факты в Прологе?
Как формируются правила на Прологе?
Как задаются имена в Прологе?
Объясните суть переменных в Прологе.
Что такое «анонимная переменная»?
Как классифицируются в Прологе вопросы в зависимости от получаемого результата?
Каковы условия сопоставимости фактов в Прологе?
Каковы правила сопоставления?
Объясните принцип отката в Прологе.

ЛАБОРАТОРНАЯ РАБОТА №3

Тема:Контроль механизма бэктрекинга при поиске решений.

Цель:Научиться использовать встроенные предикаты fail,cut и not.

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

В Прологе существуют два специальных предиката, которые позволяют контролировать механизм бэктрекинга: предикат fail, заставляющий запускать механизм бэктрекинга, и cut (обозначается с помощью символа “!”), предназначенный для отмены бэктрекинга.

Domains

name = symbol

Predicates

Father(name, name)

Everybody

Clauses

Father(leonard, katherine).

Father(carl, jason).

Father(carl, marilyn).

Everybody :-

Father(X, Y),

write(X, " is ", Y, "’s father\n"),

Fail.

Goal

Everybody.

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

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

ОТМЕНА БЭКТРЕКИНГА. ПРЕДИКАТ cut

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

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

1. Если известно заранее, что полный перебор вариантов никогда не будет способствовать рациональному поиску решения, то использование cut («зелёное» отсечение) останавливает просмотр альтернативных значений.

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

Другими словами, предикат cut ограничивает автоматичный перебор. Во многих задачах возникает проблема либо ограничения бэктрекинга, либо его полной остановки.

Рассмотрим для начала программу, процесс выполнения которой содержит ненужный перебор. Пусть необходимо реализовать функцию y=f(x), которая задана в следующем виде:

— если х<10, то у=10;

— если 10<=х и х<20, то у=20;

— если 20<=х, то у=30.

На Прологе её можно выразить программой:

Predicates

F(integer,integer).

Clauses

f(X,10):- X < 10.

f(X,20):- X >= 10, X < 20.

f(X,30):- X >= 20.

Проанализируем, что будет делать программа, если задать вопрос:

Цель: f(5,Y), Y > 20.

При обработке первой цели f(5,Y), Y примет значение 10, поэтому другая подцель станет 10>20. она завершается неудачей. Однако очевидно, что и весь список подцелей, который будет проверяться благодаря бэктрекингу, тоже будет завершаться неудачей.

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

Predicates

F(integer,integer).

Clauses

f(X,10):- X < 10.

f(X,20):- X >= 10, X < 20.

f(X,30):- X >= 20.

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

Цель: f(22,Y),

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

Predicates

F(integer,integer).

Clauses

f(X,10):- X < 10.

f(X,20):- X < 20.

F(X,30).

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

цель: a(X),b(Y). c(X,Y,Z).

При исполнении этого типа запроса Пролог-система пройдет через предикат cut только в том случае, когда подцели a(X)иb(Y)будут удовлетворены. После того, как подцель cut будет выполнена, система не сможет вернуться назад для повторного просмотра подцелей «а» и «b», если подцель «с» не удовлетвориться при текущих значениях X и Y.

Приведём ещё один пример использования cut:

Predicates

buy_car(symbol, symbol)

Car(symbol, symbol,integer)

Colors(symbol, symbol)

Clauses

buy_car(Model, Color) :- car(Model, Color, Price),

colors(Color, sexy).

Price < 25000.

Car(corvette, red, 26000).

Car(porsche, red, 24000).

Colors(red, sexy).

Colors(black, mean).

Colors(green,preppy).

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

Для пояснения работы предиката cut вернёмся к процессу управления выводом в Прологе. Пусть Пролог-программа выглядит следующим образом:

Р: — a,b.

P: — c,d.

Эту программу, используя понятие процедуры, можно прочитать так. При выполнении процедуры р выполняются процедуры a и b. Если они завершаются успешно, тогда и процедура р считается успешно завершённой. В случае, если это не так, выполняются процедуры c и d. Иначе процедура р завершается неуспехом.

Такой алгоритм обработки можно реализовать на дереве типа И/ИЛИ (рис.1), где /\ обозначает «ИЛИ», а Aозначает узел типа «И»:

Рис.1 Иллюстрация дерева типа «И/ИЛИ»

Вершина типа «И» будет успешной только в том случае, когда её вершины-потомки успешны. Вершина типа «ИЛИ» будет успешной тогда, когда хотя бы одна из её вершин- потомков успешна.

Согласно со стратегией поиска в глубину, которая используется в Прологе, проводиться последовательный перебор дерева «И/ИЛИ» сверху-вниз, слева-направо. Это соответствует отделению самой левой подцели запроса и выполнению правил программы сверху-вниз.

Если при просмотре дерева какой-то из потомков вершины «ИЛИ» является успешным, то обработка других вершин-потомков (поддерева, которое находится правее) приостанавливается и считается, что эта вершина типа «ИЛИ» стала успешной.

Если какая-нибудь из вершин-потомков вершины типа «И» становится неуспешной, то и обработка других вершин-потомков завершается неуспешно.

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

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

Одним из способов устранения указанного недостатка является использование предиката cut.

а(x): — b(x), ! , c(x).

A(x): — d(x).

b(c).

B(f).

C(e).

C(f).

D(g).

Это типичное «красное» отсечение.

На запрос а(Z)программа даст только один ответ – Z=e, так как она не будет возвращаться к вариантам, возникшим до обращения к cut (при обработке подцелей a(Z) и b(Z)).

Если же извлечь предикат cut из первого правила и создать запрос a(Z), то получим три ответа Z=e, Z=f, Z=g.

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

Like(wanja,X):-game(X).

Однако необходимо исключить баскетбол. Это можно сделать, воспользовавшись иной формулировкой:

Если Х – баскетбол, тогда „Ваня любит Х” не будет истиной, иначе, если Х – игра, то „Ваня любит Х”.

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

like(wanja, X):- basketball(X). fail.

Like(wanja, X):- game(X).

Тут отсечение отбросит рассмотрение другого правила, если игра – баскетбол, а fail вызовет неуспех.

Этот пример показывает, что желательно иметь унарный предикат not, такой, что not(Цель) будет истиной в случае, когда Цель является ложью. На Прологе его можно описать так:

not(P):- P. fail;

True.

Пролог-система имеет встроенный предикат not, реализованный подобным образом.

Тогда пример можно переписать следующим образом:

Like(wahja,X):- game(X),

Not(basketball(X))

Важно отметить: предикат not выполняется успешно, когда подцель не является истиной, т.е. тогда, когда ассоциированная с ним подцель не может дать истину.

Следующая программа показывает использование предиката not.

Domains

name = symbol

gpa = real

Predicates

honor_student(name)

student(name, gpa)

Probation(name)

Clauses

honor_student(Name):-

Student(Name, GPA),

GPA>=3.5,

Not(probation(Name)).

student("Betty Blue", 3.5).

student("David Smith", 2.0).

student("John Johnson", 3.7).

probation("Betty Blue").

probation("David Smith").

На запрос honor_student(Name)она выдаст список студентов, средний балл которых больше или равен 3,5 за исключением студентов Betty Blue и David Smith, которые проходят практику.

Цель: not(dog(baks)),

она возможно ответит „да”. Однако этот ответ нельзя рассматривать как утверждение о том, что „Бакс не собака”. Просто системе не достаточно информации для подтверждения высказывания „Бакс — собака”. Такой подход берёт своё начало от предположения о замкнутости мира. Согласно данному предположению мир замкнут в том смысле, что всё существующее в нем либо указано в программе, либо может быть выведено из неё. И в другом случае, когда чего-то нет в программе (или не может быть выведено), то оно является ложным, и следовательно будет истинным его отрицание.

Мы же традиционно не считаем мир замкнутым: если в программе явно не указано, что dog(baks), то это не означает, что мы хотим сказать: Бакс не собака.

Visual prolog 10 как работать