ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 31.03.2021
Просмотров: 6826
Скачиваний: 51
341
мая также унификацией или согласованием). Операция сопоставления может быть успешной, а
может закончиться неудачно. Определяется операция сопоставления так:
• константа сопоставляется только с равной ей константой;
• идентичные структуры сопоставляются друг с другом;
• переменная сопоставляется с константой или с ранее связанной переменной (и становится
связанной с соответствующим значением);
• две свободные переменные
могут сопоставляться (и связываться) друг с другом. С момен-
та связывания они трактуются как одна переменная: если одна из них принимает какое-либо зна-
чение, то вторая немедленно принимает то же значение.
Примеры: 5
сопоставляется с 5, «имеет» сопоставляется с «имеет», «сергей» не сопоставля-
ется с «юрий», «имеет(сергей,машина)» не сопоставляется с «имеет(сергей, телевизор)», «име-
ет(сергей,машина)» сопоставляется с «имеет(Х,машина)»,
в этом случае переменная Х получает в
качестве значения атом «сергей».
Факты -
это предикаты с аргументами-константами, обозначающие отношения между
объектами или свойства объектов, именованные этими константами. Факты в программе считают-
ся всегда и безусловно истинными и таким образом служат основой доказательства, происходяще-
го при выполнении программы.
Пример 1.
Факты, описывающие телефонные номера:
телефон(иванов,т561532).
телефон(петров,т642645).
телефон(сидоров,т139833).
Это означает: телефон Иванова - 56-15-32 и т.п. Заметим, что перед цифрами номера идет
буква ''т". Она делает номер телефона литерной константой, так как числа 561532,642645, 139833
слишком велики, чтобы быть числовыми константами.
Пример 2,
Факты, описывающие студентов:
нравится(сергей,рэп).
нравится(юрий,джаз).
носит(сергей,блейзер).
носит(юрий,пиджак).
Это означает: «Сергею нравится рэп», «Юрию нравится джаз» и т.п.
Правила
-
это хорновские фразы с заголовком и одной или несколькими подцелями-
предикатами. Правила имеют форму
<голова правила> : - <список подцелей>
где знак : - читается «если», а список подцелей состоит из отдельных подцелей, разделен-
ных знаком «запятая» (читаемым как «и»). Правила позволяют определить новые отношения меж-
ду объектами на основе уже объявленных с помощью фактов. В качестве аргументов в предикатах
правила могут использоваться не только константы, но и переменные. На переменные в правилах
действуют кванторы общности, поэтому правила очень концентрированно и лаконично выражают
конструкции логического вывода. Так, к фактам примера 2 можно добавить следующее утвержде-
ние:
крутойпарень(Х):- нравится(Х,рэп),носит(Х,блейзер).
Это означает «любой Х - крутой парень, если Х нравится рэп и Х носит блейзер». Еще при-
меры правил:
ест(Х,Y): - пища(Y), любит(Х,Y). («Каждый Х ест любой Y, если Y - пища,
и Х любит Y»)
владелец(А,В) : - купил(А,В). («Любой А есть владелец каждого В, если А купил В»)
342
В Прологе все предложения программы - факты, правила, вопрос - заканчиваются точкой.
Отметим, что в Прологе вместо оператора присваивания имеется более общий и мощный
механизм задания значений переменных. Переменные в Прологе получают свои значения в ре-
зультате сопоставления с константами в фактах и правилах. До тех пор. пока переменная не полу-
чила какого-либо значения, она называется «свободной». Когда переменная примет значение, она
становится «связанной». Однако, она остается связанной только в течение времени, необходимого
для получения одного ответа на запрос, после этого Пролог «развязывает» ее, возвращается и
ищет альтернативные решения. Это очень важный момент: нельзя хранить информацию, задавая
значения переменных. Переменные служат частью процесса сопоставления, а не «хранилищем»
информации. Область действия переменной -ровно одно предложение (правило или запрос про-
граммы).
Вопрос
-
отправная точка логического вывода, происходящего при выполнении программы.
На любой вопрос компьютер будет пытаться дать ответ «Да» или «Нет» в зависимости от того. со-
гласуется или нет утверждение, стоящее в вопросе, с фактами и правилами базы знаний. Вопрос,
не содержащий переменных, является общим: «имеет ли место факт... ?». Так, например, к базе
знаний примера 1 можно поставить вопрос
?-телефон(иванов,т123456).
и ответ будет «Нет», так как константа т123456 не согласуется ни с одним фактом.
Если к базе знаний (пример 3)
нравится(сергей ,рэп).
нравится(юрий,джаз).
носит(сергей,блейзер).
носит(юрий,пиджак).
крутойпарень(Х) : - нравится(Х,рэп),носит(Х,блейзер).
задать вопрос
?-крутойпарень(юрий).
то будет получен ответ «Нет». В самом деле, в результате резолюции утверждение в этом вопросе
согласно правилу заменится конъюнкцией утверждений
нравнтся(юрий,рэп), носит(юрий,блейзер).
(переменная Х в правиле получила значение «юрий»). Эти утверждения не согласуются с осталь-
ными фактами базы знаний. Для вопроса
? - крутойпарень(сергей).
будет получен ответ «Да», так как в этом случае противоречий при согласовании вопроса и базы
знаний не возникает.
Вопрос, в котором имеются переменные, является частным: «для
каких значений
перемен-
ных факт ... имеет место ?». В процессе сопоставлений при выполнении программы переменные
получат значения тех констант (конкретизируются), для которых сопоставление запроса, в целом,
успешно, и будут выведены на экран. Так, в ответ на вопрос
? - телефон(иванов,Х).
к базе знаний примера 1 на экране появится сообщение Х=т561532 и будет дан ответ «Да».
Если к базе знаний примера 3 задать вопрос в форме
343
?- крутойпарень(А).
то свободная переменная А в вопросе сопоставляется со свободной переменной Х в правиле и со-
вмещается с ней, т.е. становится одним и тем же. В результате резолюции согласно правилу про-
изойдет
замена
крутойпарень(А)
на
нравится(А,рэп), носит(А,блейзер),
а затем предикат «нравнтся(А.рэп)» успешно согласуется с фактом «нравится(сергей,рэп)>>, и при
этом переменная А конкретизируется значением «Сергей»; от вопроса теперь остается «но-
сит(сергей,блейзер)», а в базе знаний имеется соответствующий факт. Ответ: «Да» и на экране
появится значение присутствовавшей в вопросе переменной А:
А=сергей.
Отметим, что машина «не понимает» используемых в программе имен: «нравится», «но-
сит», «сергей» и т.д. Мы могли бы вместо них использовать любые другие обозначения. Для ин-
терпретатора Пролога существенны только совпадения и различия имен, а также связи между пре-
дикатами, устанавливаемые с помощью конъюнкций и импликаций. Осмысленные имена мы бу-
дем использовать только для того, чтобы облегчить чтение и понимание программ самим себе.
Однако, в Прологе существуют предопределенные имена (встроенные предикаты), которые позво-
ляют выполнить арифметические операции, сравнения, графические построения, ввод-вывод и
другие полезные операции как побочный продукт выполнения программы. Встроенные предикаты
Arity-Prolog описаны в справке по системе программирования, вызываемой нажатием клавиши F1.
Аналогичный набор встроенных предикатов имеется в других версиях языка Пролог.
7.2. АЛГОРИТМ ВЫПОЛНЕНИЯ ПРОГРАММ НА ПРОЛОГЕ
Факты и правила программы на Прологе являются описанием отношений и связей между
объектами некоторой предметной области, т.е. записью условия некой логической задачи, кото-
рую предстоит решить. Описанные отношения и связи рассматриваются статически. Такой подход
к программе называется декларативным. Порядок следования фактов, правил и подцелей в прави-
лах не влияет на декларативный смысл программы.
Вместе с тем, программу можно рассматривать с точки зрения последовательности сопос-
тавлений, конкретизации переменных и резолютивных выводов, происходящих при ее выполне-
нии. Такой подход называется процедурным. Процедурный смысл программы обязательно должен
учитываться при программировании на Прологе. Так, факт можно рассматривать как полностью
определенную процедуру, для выполнения которой больше ничего не нужно. Правило
А:-В1,В2,...,Вn.
можно рассматривать как определение процедуры А, утверждающее, что для ее выполнения надо
определить Bl, B2, ... , Вn. Процедуры Bl, B2, ... , Вn должны выполняться в определенном порядке
- слева направо. Если выполнение очередной процедуры завершается успешно, то происходит пе-
реход к следующей процедуре. Если же по какой-либо причине очередная процедура выполняется
неуспешно, то происходит переход к следующему варианту описания этой процедуры, и порядок
поиска такого варианта в Прологе задан - сверху вниз. Поиск подходящих для согласования фак-
тов и правил в базе знаний происходит последовательно сверху-вниз, и если подходящих фактов
не найдено - ответ отрицательный. Эта стратегия согласования называется «сверху-вниз» и «замк-
нутый мир».
Рассмотрим процесс выполнения программы более подробно на примере.
344
Программа 112
а : - b, с, d.
b : - е, f.
с. d. е. f.
? - а.
Выполнение программы начинается с применения метода резолюций к целевому и одному
из предложений программы для получения их резольвенты. Подходящее предложение программы
подбирается перебором сверху-вниз так, чтобы сопоставление его заголовка с целевым предложе-
нием было успешным. В результате резолюции получается новое целевое предложение и метод
резолюции применяется к нему и к другому предложению программы. Процесс продолжается до
тех пор, пока не будут согласованы с фактами все возникшие при резолюции подцели, табл. 3.6.
Таблица 3.6
К процессу выполнения программы на Прологе
Номер шага
резолюции
Целевое
предложение
Исходное пред-
ложение
Резольвента
1
?-а.
a:-b,c,d.
?-b,c,d.
2
?-b,c,d.
b:-c,f.
?-e,f,c,d.
3
?-е,f,с,d
e. ?-f,c,d.
4
?-f,c,d.
f. ?-c.d.
5
?-c,d.
c. ?-d.
6
?-d.
d. Пустая
При выполнении логического вывода, если необходимо, происходит конкретизация пере-
менных. Рассмотрим пример.
Программа 113
любит(юрий,музыку).
любит(сергей,спорт).
любит(А,книги):-читатель(А),любопытный(А).
любит(сергей,книги).
любит(сергей,кино).
читатель(юрий).
любопытный(юрий).
?- любит(X,музыку), любит(X,книги).
Двойной запрос в этой программе может быть представлен целевым деревом:
Вначале, просматривая программу сверху вниз. Пролог находит первое предложение, соот-
ветствующее первой подцели запроса:
345
Переменная Х конкретизируется значением «юрий». Начинается согласование 2-й подцели
запроса с условием Х=юрий. 1-е и 2-е предложения программы не соответствуют подцели. В 3-ем
предложении:
любит(А,книги):-читатель(А), любопытный(А).
аргумент А заголовка есть переменная, поэтому она может соответствовать
X, т.е. получает
значение А=юрин; вторые аргументы совпадают. Теперь тело правила образует новое множество
целей для согласования. Получаем целевое дерево:
Затем Пролог будет искать факты, соответствующие новым подцелям. Последнее результи-
рующее дерево:
Рассмотрим еще один пример.
Программа 114
любит(оля,чтение).
любит(света,бадминтон).
любит(для,бадминтон).
любит(лена,плавание).
любит(лена,чтение).
?- любит(X,чтение), любит(X,плавание).
Запрос означает: есть ли люди, которым нравится и чтение, и плавание? Сначала Пролог
ищет факт, сопоставимый с первой частью вопроса: любит(Х, чтение). Подходит первый же факт
программы
любит(оля,чтение).
и переменная Х связывается значением «оля». В то же время Пролог фиксирует в списке
фактов указатель, показывающий состояние процедуры поиска. Далее Пролог пытается согласо-
вать вторую часть запроса при условии Х = оля, т.е. ищет с самого начала программы факт «лю-
бит(оля, плавание)». Такого факта в программе нет, и поиск заканчивается неуспешно. Тогда Про-