Предок(Y,Z). clauses% Раздел фактов и правил

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

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

Родитель(пат,джим).

Родитель(боб,пат).

Родитель(боб,энн).

Родитель(том,лиз).

Предок(имя,имя)

clauses % Раздел фактов и правил

родитель(пам,боб).

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

предок(X,Z): — %Правило пр1: X - предок Z

предок(X,Z): — %Правило пр2: X – предок Z

В программе после знака % до конца строки записывается комментарий. Обратите внимание на обязательное наличие точки в конце каждого факта и правила. Наконец, о правилах в пролог-программах. Каждое правило состоит из головы (левая половина правила), в которой помещается определяемый предикат, и тела (правая половина правила), в котором помещается условная часть.

Голова и тело правила в программе связаны знаком: —, который определяет истинность утверждения при выполнении условия. Этот знак в программе можно заменить английским словом if (если). В правилах запятая (,) соответствует знаку И, а точка с запятой (;)– знаку ИЛИ. В языке Пролог ограничиваются только выражениями Хорна, и только к ним применяют метод резолюций. Выражение Хорна имеет вид:

где - литералы. Используя связку , теорему можно переписать так:

что в синтаксисе системы Турбо-Пролог записывается в другом виде:

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

Первое правило легко строится из рис.4.2а:

Для всех X и Z

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

X - родитель Z,

что сооветствует в программе записи:

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

Второе правило для предиката предок сложнее, поскольку построение цепочки отношений родитель (см. рис.4.2b) может вызвать некоторые трудности. Если длина цепочки строго фиксирована, то можно построить правило, записав в теле через запятые всю последовательность отношений, например, так:

Рис. 4.2. Пример отношения предок:

(а) X – ближайший предок Z; (б) X – отдаленный предок Z;

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

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

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

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

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

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

Для всех X и Y,

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

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

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

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

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

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

Дата добавления: 2014-01-04