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

Теоретической основой языка Пролога является раздел символьной логики, называемый исчислением предикатов. Название Пролог (Prolog) произошло от словосочетания «программирование при помощи логики» (PROgramming in LOGic).

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

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

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

Программирование на языке Пролог состоит их 3-х этапов:

1. Определение фактов предметной области.

Факты могут описывать свойства объектов и отношения между объектами. Например, факт «нравится ellen tennis» можно записать так:

likes(ellen, tennis).

Этот факт включает в себя два объекта, обозначенных словами ellen и tennis, и отношение, обозначенное словом likes (нравится). Каждый факт и каждое правило предметной области должны заканчиваться точкой. Имена объектов, список которых в каждом факте заключен в круглые скобки, называются аргументами. Имя отношения – называется предикатом. Таким образом, likes – предикат с двумя аргументами.

2. Определение правил.

Правило – это факт, истинность значения которого зависит от истинности других фактов. Правила позволяют получать новые факты исходя из уже имеющихся. Общий вид правила: A :- B1, ..., Bn. (n>0)

Здесь A – заголовок правила, Bi – тело правила. Символ «:-» читается «если».

Возможны два варианта прочтения данного правила:

• декларативное прочтение – «A истинно, если истинны Bi»;

• процедурное прочтение – «чтобы решить задачу A, сначала надо решить подзадачу B1, затем подзадачу B2, ..., затем подзадачу Bn»

Таким образом, для выполнения цели в заголовке правила, необходимо вначале выполнить (согласовать) все подцели из тела правила.

Например, правило «Тому нравится футбол, если футбол является видом спорта» на Прологе можно записать следующим образом:

likes(tom, football) :- sport(football).

Цель likes(tom, football) будет истинной в том случае, если выполняются все подцели из тела правила. В данном случае подцель sport(football).

3. Формулировка вопросов об объектах предметной области и отношениях между ними.

Имея некоторую совокупность фактов, мы можем обращаться к Прологу с вопросами о них.

Например, пусть имеется следующая совокупность фактов:

likes(ellen, tennis).

likes(tom, football).

likes(tom, swimming).

Теперь мы можем задать системе вопрос «нравится ли тому футбол»:

?- likes(tom, football)

yes

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

Переменные

До сих пор мы рассматривали отношения, аргументами которых выступали конкретные объекты – константы, такие как, ellen, tennis, и т.д. Такие объекты называются атомами. Аргументами отношений могут выступать также абстрактные объекты – переменные. Переменные используются для задания общих правил и формулировки общих вопросов. Переменные должны начинаться с большой буквы. Например, правило «биллу нравится то же, что и тому» на Прологе можно записать так:

likes(bill, X) :- likes(tom, X).

В этом правиле объект X – переменная, объекты bill и tom – константы (начинаются с маленькой буквы). Если Вы хотите, чтобы константа начиналась с большой буквы, необходимо заключить ее в двойные кавычки, например: «Bill».

Переменная может также встречаться в запросе. Если в запрос переменная не входит, то ответом будет либо да (yes), либо нет (no). Если же в запрос входит переменная, то Пролог найдет все значения этой переменной и вернет ответ. Например, вопрос «что нравится биллу» можно записать на Прологе следующим образом:

?- likes(bill, What). % What переменная

Пролог найдет все значения переменной What, которые удовлетворяют вопросу, и вернет ответ:

What = football

What = swimming

2 Solutions

Иногда возникает необходимость в использовании переменной, имя которой не будет потом нигде употребляться. Например, если необходимо определить «нравится ли что-то тому» и при этом не важно, что именно, можно использовать анонимную переменную. Анонимная переменная обозначается одиночным знаком подчеркивания: «_». Например, вопрос «нравится ли что-то тому» на Прологе можно записать так:

?- likes(tom, _).

yes

Вопрос «нравится ли эллен теннис и нравится ли тому теннис» можно задать следующим образом:

?- likes(ellen, tennis), likes(tom, tennis).

Запятая между подцелями likes читается как «и». Пролог пытается согласовать каждую подцель по очереди. Сочетая возможности конъюнкции и использования переменных, можно строить достаточно содержательные вопросы. Например, вопрос «существует ли что-нибудь такое, что нравится обоим эллен и тому» на Прологе можно записать так:

?- likes(ellen, X), likes(tom, X).

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