Язык Prolog. Правила. Рекурсивные правила.

Язык Prolog. Правила. Рекурсивные правила

Последним и самым мощным видом выражений в Прологе являются правила обобщающие понятие факта. Например, для построения семейной БД можно перечислить родительские отношения при помощи списка фактов: мать(каролина,юлия). мать(каролина, альбертина). Выражать фактами отношения внуков с дедами необходимости нет, ибо они могут быть выведены из отношений предшествования «Х является дедом Y, если существует субъект Z, отец которого Х и который сам отец или мать Y». На Прологе это высказывание записывается в виде двух правил: дед(Х,Y):-отец(Х,Z), мать(Z,Y). дед(Х,Y):-отец(Х,Z), отец(Z,Y)., где символ «:-» читается «если» («при условии, что»).

Вообще правило выглядит так: Н:-Р1,Р2, … , Рn, где Н,Р1,Р2, … , Рn - простые предикаты. Это выражение читается следующим образом: «Н если (Р1 и Р2 …и Рn)». Предикат Н называется заголовком правила, а последовательность Р1,Р2, … , Рn - телом правила.

Приведённые только что правила являются аналогом предложения Н, если (Р1 Р2 … Рn), или выражения (Р1 Р2 … Рn)Н или формулы ¬Р1 Р2 … РnН, которые суть различные записи хорновских дизъюнктов. Приведённое правило похоже, кроме того, на объявление процедуры в языке программирования.

Заголовок правила дед(Х,Y) объявлен как и тело правила отец(Х,Z), мать(Z,Y). Это правило указывает на то, что вопрос, имеющий форму ? - дед(андре,каролина). преобразуется в вопрос ? - отец(андре,Z), мать(Z,каролина). Наличие правила (как и факта) в БД означает общезначимость соответствующей формулы. Считается, что все переменные в правиле связаны кванторами общности. Например, правило дед(Х,Y):-отец(Х,Z), мать(Z,Y). толкуется как .

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

Н истинно, если Р1 и Р2 …и Рn истинны (правило),

Н истинно (факт или правило без тела),

Р1 и Р2 …и Рn истинны? (вопрос или правило без заголовка).

Рассмотрим следующую БД:

мать(каролина,юлия).

мать(каролина, альбертина).

мать(мари,проспер).

мать(анна,каролина).

отец(проспер,юлия).

отец(проспер,альбертина).

отец(альфонс,проспер).

отец(андре,каролина).

дед(Х,Y):-отец(Х,Z), мать(Z,Y).

дед(Х,Y):-отец(Х,Z), отец(Z,Y).

бабка(Х,Y):-мать(Х,Z), мать(Z,Y).

бабка(Х,Y):-мать(Х,Z), отец(Z,Y).

Отношения мать и отец заданы фактами, а отношение дед и бабка определяются с помощью правил.

На вопрос ? - дед(альфонс,юлия). ответов среди фактов нет (ни один факт не соответствует предикату вопроса). Но заголовки некоторых правил соответствуют этому предикату.

Цель заголовка какого-либо правила считается достигнутой (как и для факта) при совпадении имени предиката, числа аргументов в нём и констант стоящих на соответствующих местах предиката. Так, например факт дед(альфонс,юлия) обеспечивает реализуемость (удовлетворение, достижение) цели дед(Х,Y). Переменным из заголовка правила присваиваются значения: Х=альфонс, Y=юлия. Новой целью будет далее тело с новыми значениями переменных отец(альфонс,Z),отец(Z,юлия). Эта последовательность предикатов обрабатывается как последовательность подцелей. Их достижение обеспечивается присваиванием Z=проспер.

В итоге получаем последовательность вопрос-ответ

? - дед(альфонс,юлия).

- - - > да

Значение внутренней (отсутствующей в вопросе) переменной не входит в ответ. Это вполне естественно, ибо вопрос «да-нет» и переменные X, Y, Z нужны только для вычисления (нахождения) ответа.

Рекурсивные правила

База данных семья должна отвечать на вопрос является ли Х предком Y. Определение предиката «быть предком» рекурсивно. Для предков по женской линии соответствующие правила на Прологе записываются так. предок(Х,Y):-мать(Х,Y). предок(Х,Y):-мать(Х,Z),предок(Z,Y). Такие рекурсии разрешается использовать, иначе язык был бы слишком примитивным. Рекурсивное определение предиката обязательно должно содержать базис, т.е. нерекурсивную часть, иначе оно будет логически некорректным и программа зациклится. Чтобы избежать зацикливания, надлежит, кроме того, позаботиться о порядке выполнения, а следовательно, и порядке написания соответствующих выражений. Поэтому практически полезно, а порой и необходимо придерживаться принципа: «сначала нерекурсивные выражения».

Друзья! Приглашаем вас к обсуждению. Если у вас есть своё мнение, напишите нам в комментарии.