Алгоритмы Пролога

Область действия имен.

Использование дизъюнкции и отрицания.

Чистый Пролог разрешает применять в правилах и целях только конъюнкцию, однако, язык, используемый на практике, допускает применение дизъюнкции и отрицания в телах правил и целях. Для достижения цели, содержащей дизъюнкцию, Пролог–система сначала пытается удовлетворить левую часть дизъюнкции, а если это не удается, то переходит к поиску решения для правой части дизъюнкции. Аналогичные действия производятся при выполнении тела правил, содержащих дизъюнкцию. Для обозначения дизъюнкции используется символ «;».

В Прологе отрицание имеет имя «not» и для представления отрицания какого-либо предиката P используется запись not(P). Цель not(P) достижима тогда и только тогда, когда не удовлетворяется предикат (цель) P. При этом переменным значения не присваиваются. В самом деле, если достигается P, то не достигается not(P), значит надо стереть все присваивания, приводящие к данному результату. Наоборот, если P не достигается, то переменные не принимают никаких значений.

В Прологе программист свободен в выборе имен констант, переменных, функций и предикатов. Исключения составляют резервированные имена и числовые константы. Переменные от констант отличаются первой буквой имени: у констант она строчная, у переменных - заглавная.

Область действия имени представляет собой часть программы, где это имя имеет один и тот же смысл:

· для переменной областью действия является предложение (факт, правило или цель), содержащее данную переменную;

· для остальных имен (констант, функций или предикатов) – вся программа.

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

· в задаваемом вопросе допускается только один предикат, он и является целью, удовлетворяемой предложением из БД;

· если цель есть атомарный предикат, то она удовлетворяется либо фактом, в том случае, когда он соответствует цели; либо правилом, в том случае, когда его заголовок соответствует цели, а предикаты, входящие в тело, могут стать истинными при присваивании термов некоторым переменным;

· если цель представляет собой конъюнкцию предикатов, то она удовлетворяется, когда посредством присваивания термов переменным, будут последовательно (в текстуальном порядке) удовлетворены все входящие в цель предикаты.

Отметим, что в Прологе не проводится синтаксического различия между предикатом и функцией (составным термом), а также между нечисловой константой и функцией без аргументов. Следовательно, суть действия состоит в том, что ищется попарное соответствие между термами, один из которых является целью, а другой принадлежит БД.

Дата добавления: 2015-06-27