Иван Братко - Программирование на языке Пролог для искусственного интеллекта

родительродителя( 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.

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

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

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

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

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

Давайте добавим к нашей программе о родственных связях еще одно отношение — предок. Определим его через отношение родитель. Все отношение можно выразить с помощью двух правил. Первое правило будет определять непосредственных (ближайших) предков, а второе — отдаленных. Будем говорить, что некоторый является отдаленным предком некоторого Z, если между X и Z существует цепочка людей, связанных между собой отношением родитель-ребенок, как показано на рис.1.5. В нашем примере на рис. 1.1 Том — ближайший предок Лиз и отдаленный предок Пат.

Рис. 1.5. Пример отношения предок: (а) X — ближайший предок Z; (b) X — отдаленный предок Z.

Первое правило простое и его можно сформулировать так:

Для всех X и Z,

X — предок Z, если

X — родитель Z.

Это непосредственно переводится на Пролог как

предок( X, Z) :-

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

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

предок( X, Z) :-

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

предок( X, Z) :-

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

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

предок( X, Z) :-

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

родитель( Yl, Y2),

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

предок( X, Z) :-

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

родитель( Y1, Y2),

родитель( Y2, Y3),

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

...

Рис. 1.6. Пары предок-потомок, разделенных разным числом поколений.

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

Существует, однако, корректная и элегантная формулировка отношения предок — корректная в том смысле, что будет работать для предков произвольной отдаленности. Ключевая идея здесь — определить отношение предокчерез него самого. Рис 1.7 иллюстрирует эту идею: