Назад | Содержание| Вперёд 1. 2. Расширение программы-примера спомощью прав...

Назад | Содержание| Вперёд

1. 2. Расширение программы-примера спомощью правил

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

женщина( пам).

мужчина( том).

мужчина( боб).

женщина( лиз).

женщина( пат).

женщина( энн).

мужчина( джим).

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

пол( пам, женский).

пол( том, мужской).

пол( боб, мужской).

. . .

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

отпрыск( лиз, том).

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

Для всех X и Y

Yявляется отпрыском X, если

Xявляется родителем Y.

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

отпрыск( Y, X) :- родитель(X, Y).

Это предложение можно прочитать еще и так:

Для всех X и Y,

если X - родитель Y, то

Y -отпрыск X.

Такие предложения Пролога, как

отпрыск( Y, X) :-родитель( X, Y).

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

родитель( том, лиз).

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

условную часть (правая половина правила) и

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

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

отпрыск( Y, X) :-родитель( X, Y).

голова тело

Если условие родитель( X, Y) выполняется(оно истинно), то логическим следствием из негоявляется утверждение отпрыск( Y, X).

На приведенном ниже примере проследим, как вдействительности правила используются Прологом.Спросим нашу программу, является ли Лизотпрыском Тома:

? - отпрыск( лиз,том).

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

X = том и Y = лиз

После конкретизации мы получаем частный случайнашего общего правила. Вот он:

отпрыск( лиз, том) :-родитель( том, лиз).

Условная часть приняла вид:

родитель( том, лиз)

Теперь пролог-система попытается выяснить,выполняется ли это условие (является ли оноистинным). Для этого исходная цель

отпрыск( лиз, том)

заменяется подцелью

родитель( том, лиз)

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

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

Для всех X и Y

Xявляется матерью Y, если

Xявляется родителем Y и

Х -женщина.

На Пролог это переводится в виде такогоправила:

мать( X, Y) :- родитель( X,Y), женщина( X).

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

Рис. 1. 4. Определениеотношения сестра.

Граф на рис. 1.4 можно перевести на Пролог так:

сестра( X, Y) :-

родитель( Z, X),

родитель( Z, Y),

женщина( X).

Обратите внимание на способ, с помощью котороговыражается требование "у X и Y есть общийродитель". Была использована следующаялогическая формулировка: "некоторый Z долженбыть родителем X и этот же самый Z должен бытьродителем Y". По-другому, менее красиво, можнобыло бы сказать так: "Z1 - родитель X, Z2 - родительY и Z1 равен Z2".

Теперь можно спросить:

?- сестра( энн, пат).

Как и ожидается, ответ будет "yes" (да) (см.рис. 1.1). Мы могли бы заключить отсюда, чтоопределенное нами отношение сестраработает правильно. Тем не менее в нашейпрограмме есть маленькое упущение, котороеобнаружится, если задать вопрос: "Кто являетсясестрой Пат?"

?- сестра( X, пат).

Система найдет два ответа, один из которыхможет показаться неожиданным:

X = энн;

X = пат

Получается, что Пат - сестра себе самой?!Наверное, когда мы определяли отношение сестра,мы не имели этого ввиду. Однако ответ Прологасовершенно логичен, поскольку онруководствовался нашим правилом, а это правилоничего не говорит о том, что, если X - сестра Y, то X иY не должны совпадать. Пролог (с полным правом)считает, что X и Y могут быть одним и тем жеобъектом и в качестве следствия из этого делаетвывод, что любая женщина, имеющая родителя,является сестрой самой себе.

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

различны( X, Y)

достигается тогда и только тогда, когда X и Y неравны. Усовершенствованное правило дляотношения сестра примет тогдаследующий вид:

сестра( X, Y) :-

родитель( Z, X),

родители( Z, Y),

женщина( X),

различны( X, Y).

Некоторые важные моменты этого раздела:

Пролог-программы можно расширять, добавляя в них новые предложения.

Прологовские предложения бывают трех типов:

факты

правила

вопросы

Факты содержат утверждения, которые

являются всегда, безусловно верными.

Правила содержат утверждения, истинность которых зависит от некоторых условий.

С помощью вопросов пользователь может спрашивать систему о том, какие утверждения являются

истинными

Предложения Пролога состоят из

головы

тела

Тело

- это список

целей

, разделенных запятыми. Запятая понимается как конъюнкция.

Факты - это предложения, имеющие пустое тело. Вопросы имеют только тело. Правила имеют голову и (непустое) тело.

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

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

имеетребенка( X) :- родитель( X, Y).

можно прочитать двумя способами:

(а) Для всех X и Y,

если X - отец Y, то

X имеет ребенка.

(б) Для всех X,

X имеет ребенка, если

существует некоторый Y, такой, что

X - родитель Y.

Упражнения

1. 3. Оттранслируйтеследующие утверждения в правила на Прологе:

(a) Всякий, кто имеет ребенка, -счастлив (введите одноаргументное отношение счастлив).

(b) Всякий X, имеющий ребенка, укоторого есть сестра, имеет двух детей (введитеновое отношение иметьдвухдетей).

Посмотреть ответ

1. 4. Определите отношение внук,используя отношение родитель. Указание:оно будет похоже на отношение родительродителя(см. рис. 1.3).

Посмотреть ответ

1. 5. Определите отношение тетя(X, Y) через отношение родитель и сестра.Для облегчения работы можно сначала изобразитьотношение тетя в виде диаграммы по типутех, что изображены на рис. 1.3.

Посмотреть ответ

Назад | Содержание| Вперёд

Оглавление