8 Лекция №7. Унификация и поиск с возвратом: программа с фактами и несколькими правилами

Время: 2 часа (90 мин.)

8.1 Основные вопросы

- обработка фактов и правил.

8.2 Текст лекции

Введём теперь в рассмотрение два новых предиката, определяющие пол людей:

male(person) – мужчина;

female(person) – женщина.

Эти предикаты являются унарными и используются для выражения свойств объектов.

Определим теперь отношение “сестра” предикатом и правилом:

sestra(person, person)

sestra(X, Y):-female(X), roditel(Z, X), roditel(Z, Y), X<>Y.

Приведенное правило необходимо понимать так: “Х является сестрой Y, если X – женщина, если у X и Y общий родитель Z и если X не равен Y”. Таким образом, правило в своей правой части содержит конъюнкцию условий, которые должны выполняться одновременно, чтобы выполнялась левая часть правила.

Дополним программу-2 новыми предикатами и правилом, рассмотренными выше:

/* Программа 3 */

domains

person = symbol

predicates

roditel(person, person)

rebenok(person, person)

male(person)

female(person)

sestra(person, person)

clauses

roditel(ola,sasha).

roditel(vita,sasha).

roditel(vita,kata).

roditel(sasha,ana).

roditel(sasha,vera).

roditel(vera,kola).

male(sasha).

male(vita).

male(kola).

female(ola).

female(kata).

female(ana).

female(vera).

rebenok(Y, X) :- roditel(X, Y).

sestra(X, Y):-female(X),

roditel(Z, X),

roditel(Z, Y),

X<>Y.

Зададим данной программе вопрос “Является ли ana сестрой vera?”:

Goal:sestra(ana, vera)

Турбо-Пролог отыскивает голову правила для отношения sestra и конкретизирует переменные X и Y (X=ana, Y=vera). Само правило принимает следующий частный вид:

sestra(ana, vera):-female(ana),

roditel(Z, ana),

roditel(Z, vera),

ana<>vera.

Далее Турбо-Пролог пытается удовлетворить условиям правой части правила, для чего последовательно решаются подзадачи, входящие в список условий.

Первой подзадачей является подзадача:

female(ana).

Поскольку такой факт в разделе clauses программы имеется, то данная подзадача считается решенной и Турбо-Пролог переходит к решению второй подзадачи:

roditel(Z, ana).

В результате унификации с соответствующим фактом из раздела программы clauses переменная Z конкретизируется и получает значение sasha(Z=sasha). Турбо-Пролог переходит к решению третьей подзадачи с конкретным значением Z:

roditel(sasha, vera).

Такой факт, в программе, имеется и поэтому Турбо-Пролог переходит к последней, четвёртой, подзадаче:

ana<> vera.

Это условие также выполняется и, таким образом, выполняются все условия правой части правила. Следовательно, выполняется и левая часть правила. Поэтому на поставленный вопрос система ответит утвердительно (YES).

Зададим теперь программе вопрос “Кто является сестрой sasha?”:

Goal:sestra(Kto, sasha)

В результате унификации данного вопроса с головой соответствующего правила получим его следующий частный вид:

sestra(Kto, sasha):-female(Kto),

roditel(Z, Kto),

roditel(Z, sasha),

Kto<>sasha.

Далее Тубо-Пролог решает подзадачи, определяемые правой частью правила, первой из которых является следующая подзадача:

female(Kto).

Турбо-Пролог просматривает факты с предикатом female и связывает свободную переменную Kto со значением ola. Поскольку, в данном случае, возможно более чем одно решение, Турбо-Пролог помещает маркер возврата у факта female(kata), следующего за фактом female(ola).

Следующей подзадачей, с уже конкретизированной переменной Kto, является подзадача:

roditel(Z, ola).

Поскольку в программе нет фактов roditel со вторым аргументом ola, Турбо-Пролог не может решить эту подзадачу. Происходит возврат к установленному ранее маркеру возврата и освобождение связанной переменной Kto. Далее Турбо-Пролог устанавливает новое значение для переменной Kto=kata, а маркер возврата помещается у следующего факта с данным предикатом. И вновь решается вторая подзадача с другим значением переменной Kto:

roditel(Z, kata).

Данная подзадача унифицируется с фактом roditel(vita, kata) и, т.о., переменная Z получает значение vita. Далее решается третья подзадача:

roditel(vita, sasha).

Такой факт в разделе clauses программы имеется, и, т.о., подзадача решена. Далее решается четвёртая подзадача:

kata<>sasha.

Неравенство выполняется, и система на поставленный вопрос определяет первый ответ:

Kto=kata

Турбо-Пролог возвращается к маркеру возврата для поиска других вариантов решений. Однако другие варианты решений отсутствуют и, соответственно, дополнительных ответов на поставленный вопрос не появляется. Система даёт ответ:

Kto=kata

1 Solution