Логическое программирование. ПРОЛОГ. Принцип работы программ.

Логическое программирование возникло в эру ЭВМ как естественное желание автоматизировать процесс логического вывода, поэтому оно является ветвью теории формальных систем. Логическое программирование (в широком смысле) представляет собой семейство таких методов решения задач, в которых используются приемы логического вывода для манипулирования знаниями, представленными в декларативной форме [1]. Как писал Джордж Робинсон в 1984 году, в основе идеи логического программирования лежит описание задачи совокупностью утверждений на некотором формальном логическом языке и получение решения с помощью вывода в некоторой формальной (аксиоматической) системе. Такой аксиоматической системой являются исчисление предикатов первого порядка, поэтому в узком смысле логическое программирование понимается как использование исчисления предикатов первого порядка в качестве основы для описания предметной области и осуществления резолюционного логического вывода.

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

Программа на Прологе включает в себя постановку задачи в виде множества фраз Хорна (раздел clauses) и описание цели (раздел goal), - формулировку теоремы, которую нужно доказать, исходя из множества правил и фактов, содержащихся в этой постановке. Процесс поиска доказательства основан на методе линейной резолюции (дизъюнкты подбираются в порядке их следования в тексте программы).

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

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

16) Факты, правила, вопросы. Сопоставление в ПРОЛОГе.

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

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

Область действия имени представляет собой часть программы, где это имя имеет один и тот же смысл: • для переменной областью действия является предложение (факт, правило или цель), содержащее данную переменную;

• для остальных имен (констант, функций или предикатов) – вся программа. Специальным знаком «_» обозначается анонимная переменная, которая используется тогда, когда конкретное значение переменной не существенно

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

Факт является простым предикатом, который записывается в виде функционального терма, состоящего из имени отношения и объектов, заключенных в круглые скобки, например: мать(мария, анна). отец(иван, анна). Точка, стоящая после предиката, указывает на то, что рассматриваемое выражение является фактом.

Вторым типом предложений Пролога является вопрос или цель. Цель – это средство формулировки задачи, которую должна решать программа. Простой вопрос (цель) синтаксически является разновидностью факта, например: Цель: мать (мария, юлия). В данном случае программе задан вопрос, является ли мария матерью юлии. Если необходимо задать вопрос, кто является матерью юлии, то цель будет иметь следующий вид: Цель: мать(X, юлия). Сложные цели представляют собой конъюнкцию простых целей и имеют следующий вид: Цель: Q1, Q2,…,Qn, где запятая обозначает операцию конъюнкции, а Q1, Q2,…,Qn – подцели главной цели. Конъюнкция в Прологе истинна только при истинности всех компонент, однако, в отличие от логики, в Прологе учитывается порядок оценки истинности компонент (слева направо).

Пример 15. Пусть задана семейная БД при помощи перечисления родительских отношений в виде списка фактов: мать(мария, анна). мать(мария, юлия). мать(анна, петр). отец(иван, анна). отец(иван, юлия). Тогда вопрос, является ли иван дедом петра, можно задать в виде следующей цели: Цель: отец(иван, X), мать(X, петр).

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

Правило позволяет вывести один факт из других фактов. Иными словами, правило – это заключение, для которого известно, что оно истинно, если одно или несколько других найденных заключений или фактов являются истинными. Правила – это предложения вида H: - P1, P2,…, Pn. Символ «: -» читается как «если», предикат H называется заключением, а последовательность предикатов P1, P2,…, Pn называется посылками. Приведенное правило является аналогом хорновского дизъюнкта H ∨ P1 ∨ P2,…, ∨ Pn.

Заключение истинно, если истинны все посылки. В посылках переменные связаны квантором существования, а в заключении - квантором всеобщности. Пример 16. Добавим в БД примера 15 правила, задающие отношение «дед»: мать(мария, анна). мать(мария, юлия). мать(анна, петр). отец(иван, анна). отец(иван, юлия). дед (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).