Основы языка программирования Пролог

Объекты рассуждения в Прологе называются термами – синтаксическими объектами одной из следующих категорий

· константы,

· переменные,

· функции (составные термы или структуры), состоящие из имени функции и списка аргументов-термов, имена функций начинаются со строчной буквы..

Переменная в Прологе служит для обозначения объекта на который нельзя сослаться по имени. Константа в Прологе служит для обозначения имен собственных и начинается со строчной буквы.

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

Специальным знаком «_» обозначается анонимная переменная, которая используется тогда, когда конкретное значение переменной не существенно для данного предложения. Анонимные переменные не отличаются от обычных при поиске соответствий, но не принимают значений и не появляются в ответах. Различные вхождения знака подчеркивания означают различные анонимные переменные.

Предложение- это фраза Хорна, в которой посылки связаны между собой логическим «И», а дизъюнкты- логическим «ИЛИ».

Простейшим типом предложения является факт. Любой факт имеет соответствующее значение истинности и определяет отношение между термами.

Факт является простым предикатом, который записывается в виде функционального терма, например:

мать(мария, анна).

отец(иван, анна).

Точка, стоящая после предиката, указывает на то, что рассматриваемое выражение является фактом.

Вторым типом предложений Пролога является вопрос или цель. Цель – это средство формулировки задачи, которую должна решать программа. Простой вопрос (цель) синтаксически является разновидностью факта, например:

Цель: мать (мария, юлия).

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

Цель: мать(X, юлия).

Сложные цели представляют собой конъюнкцию простых целей и имеют следующий вид:

Цель: Q₁, Q₂,…,Q_n, где запятая обозначает операцию конъюнкции, а Q₁, Q₂,…,Q_n – подцели главной цели.

Конъюнкция в Прологе истинна только при истинности всех компонент, однако, в отличие от логики, в Прологе учитывается порядок оценки истинности компонент (слева направо).

Пример 18.

Пусть задана семейная БД при помощи перечисления родительских отношений в виде списка фактов:

мать(мария, анна).

мать(мария, юлия).

мать(анна, петр).

отец(иван, анна).

отец(иван, юлия).

Тогда вопрос, является ли иван дедом петра, можно задать в виде следующей цели:

Цель: отец(иван, X), мать(X, петр).

На самом деле БД Пролога включает не только факты, но и правила, которые представляют собой не множество, а список. Для получения ответа БД просматривается по порядку, то есть в порядке следования фактов и предикатов в тексте программы.

Цель достигнута, если в БД удалось найти факт или правило, который (которое) удовлетворяет предикату цели, то есть превращает его в истинное высказывание. В нашем примере первую подцель удовлетворяют факты отец(иван, анна). и отец(иван, юлия). Вторую подцель удовлетворяет факт мать(анна, петр). Следовательно, главная цель удовлетворена, переменная X связывается с константой анна.

Третьим типом предложения является правило.

Правила – это предложения вида

H: - P₁, P₂,…, P_n.

Символ «: -» читается как «если», предикат H называется заголовком правила, а последовательность предикатов P₁, P₂,…, P_n называется телом правила. Приведенное правило является аналогом хорновского дизъюнкта ШP₁ЪШ P₂,…,ЪШP_n ЪH. Предикаты P₁, P₂,…, P_n часто назыавают посылками. Заголовок следует из тела правила. Заголовок истинен, если истинны все посылки в теле правила. В посылках переменные связаны квантором существования, а в заголовке - квантором всеобщности.

Пример 19.

Добавим в БД примера 18 правила, задающие отношение «дед»:

мать(мария, анна).

мать(мария, юлия).

мать(анна, петр).

отец(иван, анна).

отец(иван, юлия).

дед (X, Y): - отец(X, Z), мать(Z, Y).

дед (X, Y): - отец(X, Z), отец(Z, Y).

Тогда вопрос, является ли иван дедом петра, можно задать в виде следующей цели:

Цель: дед(иван, петр).

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

Очень часто правила в Прологе являются рекурсивными. Например, для нашей семейной БД предикат «предок» определяется рекурсивно:

предок(x, y): - мать(x, y).

предок(x, y): - отец(x, y).

предок(x, y): - мать(x, z), предок(z, y).

предок(x, y): - отец (x, z), предок(z, y).

Рекурсивное определение предиката обязательно должно содержать нерекурсивную часть, иначе оно будет логически некорректным и программа зациклится. Чтобы избежать зацикливания, следует также позаботиться о порядке выполнения предложений, поэтому практически полезно, а порой и необходимо придерживаться принципа: «сначала нерекурсивные выражения».

Программа на Прологе - это конечное множество предложений.

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