Prolog

Факты содержат утверждения, которые

являются всегда, безусловно верными.

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

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

истинными

.

Предложения Пролога состоят из

головы

и

тела

.

Тело

- это список

целей

, разделенных запятыми. Запятая понимается как конъюнкция.

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

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

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

        имеетребенка( 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.  Пример отношения предок:

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

между собой отношением родитель-ребенок, как показано на рис.1.5. В нашем примере на рис. 1.1   Том - ближайший предок Лиз и отдаленный предок Пат.

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

    Для всех 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.  Рекурсивная формулировка отношения предок.