Упражнения

1.1.  Считая, что отношение родитель определено так же, как и раньше в данном разделе (см. рис. 1.1), найдите, какими будут ответы пролог-системы на следующие вопросы:

(a)  ?-  родитель( джим, X).

(b)  ?-  родитель( X, джим).

(c)  ?-  родитель( пам,X), родитель( X, пат).

(d)  ?-  родитель( пам, X), родитель( X, Y),

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

1.2.   Сформулируйте на Прологе следующие вопросы об отношении родитель:

(a)  Кто родитель Пат?

(b)  Есть ли у Лиз ребенок?

(c)  Кто является родителем родителя Пат? 

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 — женщина.

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

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

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

Рис. 1.3.   Графы отношений родительродителя, мать и отпрыск, определенных через другие отношения.

Такие отношения как родитель, отпрыск и мать можно изобразить в виде диаграмм, приведенных на рис. 1.3. Они нарисованы с учетом следующих соглашений. Вершины графа соответствуют объектам, т.е. аргументам отношений. Дуги между вершинами соответствуют бинарным (двуместным) отношениям. Дуги направлены от первого аргумента к второму. Унарные отношения на диаграмме изображаются просто пометкой соответствующих объектов именем отношения. Отношения, определяемые через другие отношения, представлены штриховыми дугами. Таким образом, любую диаграмму следует понимать так: если выполнены отношения, изображенные сплошными дугами, тогда и отношение, изображенное штриховой дугой, тоже выполнено. В соответствии с рис. 1.3, отношение родительродителя можно сразу записать на Прологе:

родительродителя( X, Z) :- родитель( X, Y),

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

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

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

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

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

На рис. 1.4 показано отношение сестра:

Для любых X и Y

  X является сестрой Y, если

  (1)  у X и Y есть общий родитель, и

  (2)  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.