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

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

имеетребенка( 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. 

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 иллюстрирует эту идею:

Для всех X и Z,

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

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

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

 (2)  Y — предок Z.

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

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

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

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

Рис. 1.7.  Рекурсивная формулировка отношения предок.