Правила и логический вывод

Урок о правилах — главной силе Prolog: как из имеющихся фактов автоматически выводить новые знания.

Правило — это условное утверждение вида «голова истинна, если истинно тело»; оно позволяет выводить новые факты из уже известных.

Факты описывают то, что мы знаем напрямую: parent(tom, bob). Но в базе нет факта «Том — дедушка Анны», хотя по-человечески это очевидно: Том — родитель Боба, Боб — родитель Анны. Записывать вручную всех дедушек, тётей и кузенов — безумие. Вместо этого мы один раз формулируем правило, и Prolog сам выведет любую бабушку из фактов о родителях. В этом и состоит сила логического программирования.

Синтаксис правила: head :- body

Правило состоит из двух частей, соединённых оператором :-:

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

Слева от :- — голова (head), то, что мы определяем. Справа — тело (body), условия. Оператор :- читается как «если» (его иногда называют «neck», шея). Всё правило читается так: «X — дедушка/бабушка Z, если X — родитель некоторого Y, и этот Y — родитель Z».

Переменные X, Y, Z с заглавной буквы связывают части между собой: один и тот же Y в обоих условиях значит «один и тот же человек посередине». Это промежуточное звено — ребёнок дедушки и родитель внука одновременно.

Конъюнкция: запятая — это «И»

Запятая между условиями в теле — это конъюнкция, логическое «И». Чтобы голова стала истинной, должны выполниться оба условия одновременно. В grandparent обязаны найтись и parent(X, Y), и parent(Y, Z) с общим Y. Если хоть одно не выполнится — всё правило для этих значений ложно.

Возьмём базу из прошлых уроков и добавим правило:

parent(tom, bob).
parent(tom, liz).
parent(bob, ann).
parent(bob, pat).

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

Теперь спросим, чьим дедушкой является Том:

?- grandparent(tom, Z).

Вывод:

Z = ann ;
Z = pat ;
false.

Заметьте: фактов grandparent в базе не было ни одного. Prolog вывел их, собрав цепочку из двух фактов parent. Это и есть логический вывод.

Дизъюнкция: точка с запятой — это «ИЛИ»

Иногда условие выполняется одним из нескольких способов. Точка с запятой ; в теле правила — это дизъюнкция, логическое «ИЛИ»: достаточно, чтобы выполнилась хотя бы одна из частей. Опишем «родителя» как «отца или мать»:

father(F, C) :- parent(F, C), male(F).
mother(M, C) :- parent(M, C), female(M).

is_parent(P, C) :- father(P, C) ; mother(P, C).

Правило is_parent истинно, если P — отец C или мать C. На практике дизъюнкцию ; часто заменяют двумя отдельными правилами с одной головой — это считается более читаемым стилем:

is_parent(P, C) :- father(P, C).
is_parent(P, C) :- mother(P, C).

Оба варианта эквивалентны: несколько правил с одинаковой головой Prolog тоже трактует как «ИЛИ» — он пробует их по очереди.

Пример посложнее: sibling

Опишем отношение «брат или сестра» (sibling). Двое — сиблинги, если у них есть общий родитель:

sibling(A, B) :- parent(P, A), parent(P, B), A \== B.

Читается так: «A и B — сиблинги, если существует родитель P, который является родителем и A, и B, причём A и B — разные люди». Условие A \== B (читается «не равно») отсеивает случай, когда человек оказывается «братом» самому себе.

?- sibling(ann, X).

Вывод:

X = pat ;
false.

У Анны и Пат общий родитель Боб — значит, они сиблинги. Без условия A \== B Prolog сначала выдал бы X = ann (тот же общий родитель делает Анну «сестрой» самой себе) — типичная ловушка, которую и закрывает проверка на неравенство.

Как работает под капотом

Когда приходит запрос grandparent(tom, Z), Prolog не находит готовых фактов grandparent, зато находит правило. Он раскрывает голову правила: цель grandparent(tom, Z) унифицируется с головой grandparent(X, Z), при этом X связывается с tom. Теперь, чтобы доказать голову, нужно доказать тело — и Prolog заменяет исходную цель на две новые подцели: parent(tom, Y), parent(Y, Z).

Дальше он решает их слева направо. Сначала parent(tom, Y) даёт Y = bob. С этим связыванием вторая подцель становится parent(bob, Z) и даёт Z = ann — первое решение. По нажатию ; срабатывает откат: вторая подцель выдаёт Z = pat. Когда у bob дети кончатся, откат вернётся к первой подцели и попробует следующий Y — но liz детей не имеет, ветка обрывается. Так правило разворачивается в дерево подцелей:

grandparent(tom, Z)
  └ parent(tom, Y), parent(Y, Z)
      ├ Y = bob → parent(bob, Z)
      │             ├ Z = ann   ✓
      │             └ Z = pat   ✓
      └ Y = liz → parent(liz, Z)  → нет решений

Важно: правило не создаёт и не сохраняет новые факты в базе. Оно выводит ответ заново при каждом запросе. Знание о дедушках живёт в правиле, а не в виде записанных фактов — это экономит память и держит базу непротиворечивой.

Частые ошибки

• Путаница :- и направления. Слева — что доказываем (вывод), справа — при каких условиях. Перепутав стороны, получите бессмыслицу вроде «если дедушка, то родитель».
• Несвязанная промежуточная переменная. Если в grandparent написать два разных имени вместо общего Y, связь «через одного человека» порвётся, и правило выведет неверные пары.
• Забытое условие неравенства. В sibling без A \== B каждый окажется собственным братом или сестрой.
• Путаница запятой и точки с запятой. Запятая — это «И» (нужны все условия), ; — это «ИЛИ» (достаточно одного); подмена меняет смысл правила.
• Ожидание, что правило «запишет» факты. Правило ничего не добавляет в базу — оно лишь выводит ответ на лету по запросу.

Итоги

• Правило head :- body читается «голова истинна, если истинно тело».
• Запятая в теле — конъюнкция «И» (нужны все условия), ; — дизъюнкция «ИЛИ» (достаточно одного).
• Общие переменные (например Y) связывают условия в цепочку через один и тот же объект.
• Правила выводят новые отношения (grandparent, sibling) из фактов о родителях, не сохраняя их в базе.
• Под капотом цель раскрывается в подцели, решаемые слева направо с унификацией и откатом.