Чтение онлайн

на главную

Жанры

Неизвестно

Шрифт:

родитель( боб, пат) ==> предок( боб, пат)

Эту запись можно прочитать так: из родитель( боб, пат) следует предок( боб, пат) на основании правила пр1. Далее, нам известен факт родитель( том, боб). На основании этого факта и выведенного факта предок( боб, пат) можно заключить, что, в силу правила пр2, наше целевое утверждение предок( том, пат) истинно. Весь процесс вывода, состоящий из двух шагов, можно записать так:

родитель(боб, пат) ==>

предок( боб, пат)

родитель(том, боб) и предок( боб, пат) ==>

предок( том, пат)

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

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

?- предок( том, пат).

система попытается достичь этой цели. Для того, чтобы это сделать, она пробует найти такое предложение в программе, из которого немедленно следует упомянутая цель. Очевидно, единственными подходящими для этого предложениями являются пр1 и пр2.

Рис. 1. 9. Первый шаг вычислений. Верхняя цель истинна, если истинна нижняя.

Это правила, входящие в отношение предок. Будем говорить, что головы этих правил сопоставимы с целью.

Два предложения пр1 и пр2 описывают два варианта продолжения рассуждений для пролог-системы. Вначале система пробует предложение, стоящее в программе первым:

предок( X, Z) :- родитель( X, Z).

Поскольку цель - предок( том, пат), значения переменным должны быть приписаны следующим образом:

X = том, Z = пат

Тогда исходная цель предок( том, пат) заменяется новой целью:

родитель( том, пат)

Такое действие по замене одной цели на другую на основании некоторого правила показано на рис. 1.9. В программе нет правила, голова которого была бы сопоставима с целью родитель(том, пат), поэтому такая цель оказывается неуспешной. Теперь система делает возврат к исходной цели, чтобы попробовать второй вариант вывода цели верхнего уровня предок( том, пат). То есть, пробуется правило пр2:

предок( X, Z) :-

родитель( X, Y),

предок( Y, Z).

Как и раньше, переменным X и Z приписываются значения:

X =

том, Z = пат

В этот момент переменной Y еще не приписано никакого значения. Верхняя цель предок( том, пат) заменяется двумя целями:

родитель( том, Y),

предок( Y, пат)

Этот шаг вычислений показан на рис. 1.10, который представляет развитие ситуации, изображенной на рис. 1.9.

Рис. 1. 10. Продолжение процесса вычислений, показанного на рис. 1.9.

Имея теперь перед

собой

две

цели, система пытается достичь их в том порядке, каком они

записаны. Достичь первой из них легко, поскольку она

соответствует

факту из программы. Процесс установления соответствия - сопоставление (унификация) вызывает приписывание переменной Y значения

боб

. Тем самым достигается первая цель, а оставшаяся превращается в

предок( боб, пат)

Для достижения этой цели вновь применяется правило пр1. Заметим, - что это (второе) применение правила никак не связано с его первым применением. Поэтому система использует новое множество переменных правила всякий раз, как оно применяется. Чтобы указать это, мы переименуем переменные правила пр1 для нового его применения следующим образом:

предок( X ', Z ') :-

родитель( X ', Z ').

Голова этого правила должна соответствовать нашей текущей цели предок( боб, пат). Поэтому

X ' = боб, Z ' = пат

Текущая цель заменяется на

родитель( боб, пат)

Такая цель немедленно достигается, поскольку встречается в программе в качестве факта. Этот шаг завершает вычисление, что графически показано на рис. 1.11.

Рис. 1. 11. Все шаги достижения цели предок( том, пат). Правая

ветвь демонстрирует, что цель достижима.

Графическое представление шагов вычисления на рис. 1.11 имеет форму дерева. Вершины дерева соответствуют целям или спискам целей, которые требуется достичь. Дуги между вершинами соответствуют применению (альтернативных) предложений программы, которые преобразуют цель, соответствующую одной вершине, в цель, соответствующую другой вершине. Корневая (верхняя) цель достигается тогда, когда находится путь от корня дерева (верхней вершины) к его листу, помеченному меткой "да". Лист помечается меткой "да", если он представляет собой простой факт. Выполнение пролог-программы состоит в поиске таких путей. В процессе такого поиска система может входить и в ветви, приводящие к неуспеху. В тот момент, когда она обнаруживает, что ветвь не приводит к успеху, происходит автоматический возврат к предыдущей вершине, и далее следует попытка применить к ней альтернативное предложение.

Поделиться:
Популярные книги

Сердце Дракона. Предпоследний том. Часть 1

Клеванский Кирилл Сергеевич
Сердце дракона
Фантастика:
фэнтези
5.00
рейтинг книги
Сердце Дракона. Предпоследний том. Часть 1

Возвышение Меркурия. Книга 12

Кронос Александр
12. Меркурий
Фантастика:
героическая фантастика
попаданцы
аниме
5.00
рейтинг книги
Возвышение Меркурия. Книга 12

Тринадцатый III

NikL
3. Видящий смерть
Фантастика:
фэнтези
попаданцы
аниме
5.00
рейтинг книги
Тринадцатый III

Para bellum

Ланцов Михаил Алексеевич
4. Фрунзе
Фантастика:
попаданцы
альтернативная история
6.60
рейтинг книги
Para bellum

Ваше Сиятельство 5

Моури Эрли
5. Ваше Сиятельство
Фантастика:
городское фэнтези
аниме
5.00
рейтинг книги
Ваше Сиятельство 5

Кровавая весна

Михайлов Дем Алексеевич
6. Изгой
Фантастика:
фэнтези
9.36
рейтинг книги
Кровавая весна

На границе империй. Том 6

INDIGO
6. Фортуна дама переменчивая
Фантастика:
боевая фантастика
космическая фантастика
попаданцы
5.31
рейтинг книги
На границе империй. Том 6

Убивать чтобы жить 2

Бор Жорж
2. УЧЖ
Фантастика:
героическая фантастика
боевая фантастика
рпг
5.00
рейтинг книги
Убивать чтобы жить 2

Инцел на службе демоницы 1 и 2: Секса будет много

Блум М.
Инцел на службе демоницы
Фантастика:
фэнтези
5.25
рейтинг книги
Инцел на службе демоницы 1 и 2: Секса будет много

Идеальный мир для Социопата 3

Сапфир Олег
3. Социопат
Фантастика:
боевая фантастика
6.17
рейтинг книги
Идеальный мир для Социопата 3

Последний Паладин. Том 3

Саваровский Роман
3. Путь Паладина
Фантастика:
юмористическое фэнтези
попаданцы
аниме
5.00
рейтинг книги
Последний Паладин. Том 3

Идеальный мир для Лекаря 16

Сапфир Олег
16. Лекарь
Фантастика:
боевая фантастика
юмористическая фантастика
аниме
5.00
рейтинг книги
Идеальный мир для Лекаря 16

Рота Его Величества

Дроздов Анатолий Федорович
Новые герои
Фантастика:
боевая фантастика
8.55
рейтинг книги
Рота Его Величества

Сумеречный Стрелок 3

Карелин Сергей Витальевич
3. Сумеречный стрелок
Фантастика:
городское фэнтези
попаданцы
аниме
5.00
рейтинг книги
Сумеречный Стрелок 3