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

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

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

• Предложения Пролога состоят из головы и тела . Тело — это список целей , разделенных запятыми. Запятая понимается как конъюнкция.

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

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

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

имеетребенка( 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 иллюстрирует эту идею:

Для всех X и Z,

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

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

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

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

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

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

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

предок( Y, Z).

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