Определение предикатов на основе правил

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

female( pam).

male( tom).

male( bob).

female ( liz) .

female( pat) .

female( ann} .

male( jim).

В этом случае введены предикаты male и female. Эти предикаты являются унарными (или одноместными). Бинарные предикаты типа parent определяют связь между парами объектов. С другой стороны, унарные отношения могут использоваться для объявления простых свойств объектов, которые они могут иметь или не иметь. Первое из приведенных выше унарных предложений можно прочитать таким образом: Пэм — женщина. Вместо этого информацию, объявленную в двух унарных отношениях, можно передать с помощью одного бинарного отношения. В таком случае приведенная выше часть программы примет примерно такой вид:

sех( pam, feminine).

sex( tom, masculine).

sex( bob, masculine).

В качестве следующего дополнения к программе введем предикат offspring (отпрыск), обратный предикату parent. Предикат offspring можно определить таким же образом, как и parent, предоставив список обычных фактов о предикате offspring, и в качестве каждого факта указать такую пару людей, что один из них является сыном или дочерью другого, например:

вffspring( liz, tom).

Но предикат offspring можно определить гораздо более изящно, используя то, что он является противоположным parent и что parent уже было определено. Этот альтернативный способ может быть основан на следующем логическом утверждении:

Для всех X и Y Y является сыном или дочерью X, если X является родителем Y.

Такая формулировка уже более близка к синтаксису языка Prolog. Соответствующее предложение Prolog, которое имеет тот же смысл, выглядит таким образом:

offspring( Y, X) :- parent( X, Y) .

Это предложение можно также прочитать так:

Для всех X и Y, если X является родителем Y, то Y является сыном или дочерью X.

Предложения Prolog, такие как ospring(Y, X) :- parent( X, Y). называются правилами. Между фактами и правилами существует важное различие. Такие факты, как parent( tom, liz), представляют собой логические утверждения, которые всегда и безусловно являются истинными. С другой стороны, правила представляют собой утверждения, которые становятся истинными, если удовлетворяются некоторые условия. Поэтому принято считать, что правила состоят из следующих частей:

• условие (правая часть правила);

• заключение (левая часть правила).

Если условие parernt(X, Y) является истинным, то его логическим следствием становится offspring( Y, X).

Применение правил в языке Prolog иллюстрируется в следующем примере. Зададим программе вопрос, является ли Лиз дочерью Тома:

?- offspring( liz, tom).

Поскольку в программе отсутствуют факты о дочерях и сыновьях, единственным способом поиска ответа на этот вопрос является использование правила с определением предиката offspring. Данное правило является общим в том смысле, что оно применимо к любым объектам X и Y; но его можно также применить и к таким конкретным объектам, как liz и tom. Чтобы применить правило к объектам liz и tom, вместо Y необходимо подставить liz , а вместо X — tom. Это действие называется конкретизацией переменных (в данном случае — X и Y), которое выполняется следующим образом:

X = tom и Y = liz

После конкретизации будет получен частный случай общего правила, который выглядит следующим образом:

offspring( liz, tom) :- parent( tom, liz ) .

Часть с обозначением условия принимает вид parent( tom, liz).

После этого система Prolog пытается определить, является ли истинной часть с обозначением условия. Поэтому первоначальная цель:

offspring( liz, tom) заменяется подцелью parent( tom, liz)

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

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

Для всех X и Y, X является матерью Y, если X является одним из родителей Y и X - женщина.

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

mother( X, Y) :- parent( X, Y), female(X).

Запятая между двумя условиями указывает на конъюнкцию этих условий; это означает, что оба условия должны быть истинными.

Предикат grandparent (родитель родителя) можно непосредственно записать на языке Prolog следующим образом:

grandparent(X, Z) :- parent(X, Y) , parent( Y, Z).

Схема предиката sister имеет следующее определение:

Для любого X и Y X является сестрой Y, если

1) X и Y имеют общего родителя и

2) X - женщина.

На язык Prolog этот предикат описывется следующим образом:

sister( X, Y) :- parent( Z, X), parent( Z, Y) , female(X).

Теперь системе можно задать вопрос:

?- sister( ann, pat).

Ответом должно быть "yes", как и следовало ожидать. Поэтому можно сделать вывод, что предикат sister в том виде, в каком он определен, действует правильно. Но в рассматриваемой программе имеется незаметный на первый взгляд недостаток, который обнаруживается при получении ответа на вопрос о том, кто является сестрой Пэт:

?- sister( X, pat) .

Prolog находит два ответа, и один из них может оказаться неожиданным.

X = ann;

X = pat

Итак, Пэт является сестрой самой себя?! По-видимому, такой исход не подразумевался при определении предиката sister . Но согласно правилу, касающемуся сестер, ответ системы Prolog является полностью обоснованным. В правиле о сестрах нет упоминания о том, что X и Y не должны быть одинаковыми, если X рассматривается как сестра Y. Поскольку это требование не предъявляется, система Prolog предполагает, что X и Y могут быть одинаковыми, и поэтому приходит к заключению, что любая женщина, имеющая родителя, является сестрой самой себя.

Чтобы исправить приведенное выше правило о сестрах, необходимо дополнительно указать, что X и Y должны быть разными. Такую задачу можно решить несколькими способами, но на данный момент предположим, что системе Prolog уже известно отношение different и условие different( X, Y) удовлетворяется, если и только если X и Y не равны. Поэтому усовершенствованное правило для отношения sister может выглядеть следующим образом:

Sister( X, Y) :-parent( Z, X),parent( Z, Y),female( X),different( X, Y) .

На основании изложенного в этом разделе можно сделать следующие важные выводы.

• Программы Prolog можно дополнять, вводя новые предложения.

• Предложения Prolog относятся к трем типам: факты, правила и запросы.

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

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

• В процессе вычисления переменные можно заменять другими объектами.

В таком случае переменная становится конкретизированной.