Программирование на языке Пролог для искусственного интеллекта - страница 9
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. Рекурсивная формулировка отношения >предок.
Ключевым моментом в данной формулировке было использование самого отношения >предок в его определении. Такое определение может озадачить - допустимо ли при определении какого-либо понятия использовать его же, ведь оно определено еще не полностью. Такие определения называются рекурсивными. Логически они совершенно корректны и понятны; интуитивно это ясно, если посмотреть на рис. 1.7. Но будет ли в состоянии пролог-система использовать рекурсивные правила? Оказывается, что пролог-система очень легко может обрабатывать рекурсивные определения. На самом деле, рекурсия — один из фундаментальных приемов программирования на Прологе. Без рекурсии с его помощью невозможно решать задачи сколько-нибудь ощутимой сложности.
Возвращаясь к нашей программе, можно теперь задать системе вопрос: "Кто потомки Пам?" То есть: "Кто тот человек, чьим предком является Пам?"