Алгоритм вычисления целей(работы пролог машины).

Алгоритм исп.программу(факты и правила).

факты и правила – это хорновские дизъюнкты, все они имеют по одной положительной летере. Факт – одна положительная литера, а правило – одна

Список целей – хорновский дихъюнкт, который не имеет ни одной положительной литеры.

Цели(G₁,G₂,..G_m)

Вычислить

Просмотр

Программа: факты и правила

Успех или неудача

Подстановка

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

Сам алгоритм пролог машины можно представить двумя взаимно – рекурсивными процедурами – вычислить и просмотр.

Процедура “вычислить” последовательно перебирает цели(?литеры?) из целевого дизъюнкта, а процедура “просмотр” для заданной целевой литеры целей подбирает факты или правила с которой можно выполнить правила резолюции.

Алгоритм на выходе имеет признак – успех или неудача. В случае успеха на выходе будет еще подстановка, которая является опровержением целевого дизъюнкта.

Рассмотрим алгоритм, функцию “вычислить”. Эта функция рекурсивная, её базовый случай - если список целей пуст (на входе пустой дизъюнкт), то алгоритм успешно завершает работу. Иначе, в общем случае выбирается первая литера G₁ и для неё запускается процедура “просмотр“.

О процедуре просмотр. Для литеры G1 она должна найти дизъюнкт в программе, с которым можно выполнить резолюцию. Эта процедура просматривает последовательно факты и правила в программе пока не найдет предложение C, голова которого сопоставима с целью G₁.

Т.е. предложение C будет иметь вид

H :- B₁,B₂,…B_n.

H – голова правила, B_1..n – тело правила.

Факт – это правила у которого нет тела.

Это предложение такое что G1 и H сопоставимы.

(Берем 2 предиката….Получаем множество уравнений, запускаем алгоритм Эмбрана…..)

Если сопоставимы, то далее строим резольвенту.

Поскольку в каждом правиле переменные локальные, а правило может вызываться несколько раз, может быть рекурсивным, в правиле все переменные переименовываются, т.е. получают новые имена, которых раньше не было.

(При применениях правил будем ставить ‘, ‘’, ‘’’, и т.д на бумаге. А пролог машина каждый раз генерирует новые имена…G-125,….G-126….и т.п.)

Мы уже получаем новое правило:

H’ :- B1’, B2’,…Bn’ - это правило с переименованными переменными. Далее сопоставляем G1 и H’ и находим подстановку сигма.

Здесь работает алгоритм Эмбрана.

Теперь можно построить резольвенту. Получается новый список целей B1’,B2’…Bn’ (это правила) и цель от целевого дизъюнкта G2,…..Gn. Получается множество литер B1’,B2’…Bn’, G2,…..Gm (вместо G1 тело правила…).

Далее к резольвенте мы должны применить подстановку сигма, т.е. конкретизировать новый список целей. Получаем новый список целей B1’’,B2’’,….Bn’’,G2’,….Gm’ и с этим новым списком целей мы опять вызываем процедуру вычислить, с новым списком целей.

Процедура вычислить может выдать неуспех, в этом случае процедура просмотр должна возобновить свою работу с предложения, следующего за предложением C. Если просмотрена вся программа и соответствие не найдено, то процедура просмотр выдает неудачу, которая приводит к неудаче процедуры вычислить и она должна пересогласовать предыдущую цель. Если ничего пересогласовать не удается, то процедура вычислить завершается с неудачей.

Таким образом, в пролог машине заложен перебор фактов и правил.

Пример.

Берем программу и рассмотрим по шагам.

Факты и правила

1) большой(медведь).

2) большой(слон).

3)маленький(кот).

4)бурый(медведь).

5)черный(кот).

6)серый(слон).

7)темный(X) :- черный(Х).

8)темный(Х) :- бурый(Х).

Цель

?- темный(Х), большой(Х).

Рассмотрим, как будет пролог машина отвечать на поставленный вопрос

темный(Х), большой(Х).

Большой(кот).

Большой(медведь)

черный(Х), большой(Х).

бурый(Х), большой(Х).

7)темный(Х’):-

Черный(Х’).

Сигма = {X’ / X}

8)темный(Х’):-

бурый(Х’).

Сигма = {X’ / X}

4)бурый(медведь).

Сигма={X/ медведь}

5)черный(кот).

Сигма={X/ кот}

Успех

1)Большой(медведь)

Неудача

Таким образом работа пролог машина.

Л/Р будет посвящена тому, что мы исследуем как работает пролог машина. В прологе есть отладчик, который позволяет по шагам проследить работу программы.