ПОНЯТИЕ ПРАВИЛА И РЕКУРСИИ. ВСТРОЕННЫЕ ПРЕДИКАТЫ.

Цель работы:

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

Правила

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

Пример.Известно, что бабушка человека - это мама его мамы или мама его папы. Соответствующие правила будут иметь вид:

Бабушка(X,Y):-

Мать (X,Z), Мать (Z,Y).

Бабушка(X,Y):-

Мать (X,Z),Отец (Z,Y).

Символ ": -" означает "если", и вместо него можно писать if.

Символ "," - это логическая связка "и" или конъюнкция, вместо него можно писать and.

Первое правило сообщает, что X является бабушкой Y, если существует такой Z, что X является мамой Z, а Z - мамой Y. Второе правило сообщает, что X является бабушкой Y, если существует такой Z, что X является мамой Z, а Z - папой Y.

Дерево вывода.

Графическим способом отображения правила является дерево вывода. Оно состоит из вершин и ребер и изображает цели, снимаемые в процессе вычисления. Корень дерева, как правило, совпадает с запросом. Вершины изображают цели, снимаемые в процессе вычисления. Правила, входящие в дерево, обозначаются закрашенным кружком, факты незакрашенным. Деревом вывода для процедуры является совокупность деревьев вывода для отдельных правил в процедуре (рис 2.1).

Рис 2.1. Дерево вывода для правила Бабушка

Рекурсия

В отличие от традиционных языков программирования, в которых основным средством организации повторяющихся действий являются циклы, в Turbo Prolog для этого часто используется рекурсия . Она позволяет использовать в процессе определения предиката его самого.

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

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

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

Для всех X и Z,
X - предок Z, если
X - родитель Z.

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

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

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

предок( 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).

. . .

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

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

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

Для всех 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).

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

Любая рекурсивная процедура должна включать в себя базис и шаг рекурсии.

Базис рекурсии - это предложение, определяющее некую начальную ситуацию или ситуацию в момент прекращения. Как правило, в этом предложении записывается некий простейший случай, при котором ответ получается сразу даже без использования рекурсии. Так, в приведенной выше процедуре, описывающей предикат предок, базисом рекурсии является первое правило, в котором определено, что ближайшими предками человека являются его родители. Это предложение часто содержит условие, при выполнении которого происходит выход из рекурсии или отсечение.

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

<имя определяемого предиката>:-

[<подцели>],

[<условие выхода из рекурсии>],

[<подцели>],

<имя определяемого предиката>,

[<подцели>].