1. Принципы логического программирования

1.2. Математическая основа языка Пролог

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

Формализм исчисления предикатов первого порядка оказался удобным для описания постановки задачи на языке, близком к естественному.

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

Дадим несколько определений.

Пусть имеется некоторое множество объектов, называемое предметной областью. Выражение P(X1, X2, …, Xn), где Xi, i=1,…,n – так называемые предметные переменные, а P принимает значения 0 или 1, называется логической функцией или предикатом. Предикат от n переменных называют n-местным.

Предикат P(X1, X2, …, Xn) задает отношение между элементами X1,X2,…,Xn и обозначает высказывание, что «X1,X2,…,Xn находятся между собой в отношении P». Например, если отношение родитель(X,Y) означает, что X является родителем для Y (но не наоборот!), то высказывание родитель(«царь Петр I», «царевич Алексей») является истинным, а отношение родитель(«царь Петр I», «царевна Софья») – ложным. Важно понимать, что имена отношений и их размерность («арность») произвольны и зависят только от целей их использования.

Из подобного рода элементарных отношений с помощью логических связок образуют более сложные отношения, которые в свою очередь являются предикатами, то есть могут принимать те же значения – «истина» или «ложь». В качестве связок используются конъюнкция (логическое И), дизъюнкция (логическое ИЛИ), импликация (логическое следование), отрицание, эквивалентность.

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

Все люди смертны.

Сократ – человек.

Теорема, логически вытекающая из этих двух аксиом:

Сократ смертен.

Эти аксиомы можно переписать так (в терминах исчисления предикатов):

Для всех X, если X – человек, то смертен X

И человек( Сократ )

Соответственно наш пример можно перевести на Пролог (пока еще без учета синтаксиса версии PDC Prolog):

смертен( Х) :- человек ( Х ).

человек( сократ ).

Здесь собственное имя «Сократ», представляющее строковую константу, записано с маленькой буквы, поскольку во всех версиях Пролога с большой буквы записывается имя переменной. При работе этой небольшой программы можно задать системе вопрос: является ли Сократ смертным, и система ответит «Да»:

? смертен( сократ ).

Да

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

Существуют отличия синтаксиса логики предикатов от языка PDC Prolog. Соответствие можно видеть в таблице 1.

Название операции	Обозначение в логике предикатов	Обозначение в языке PDC Prolog
и	&	запятая
или	v	точка с запятой или точка
если	=>	:-
не	~	not

В языке Пролог исчисление предикатов ограничено специальными выражениями, называемыми хорновскими дизъюнктами. Хорновской дизъюнкт имеет вид:

~P1 v ~P2 v … v ~ Pm v Pn,

где P1, P2, … Pm, Pn – предикаты (термы, логические формулы). В данной записи предикатов мы акцентировали внимание на внешнем представлении дизъюнкта в виде структуры, состоящей из предикатов, без перечисления их возможных аргументов. Как мы видели на примерах выше, предикат имеет аргументы, что, вообще говоря, в Прологе необязательно. (В математической логике предикат без аргументов называется высказыванием.)

В последнем выражении только формула Pn без отрицания, и в этом главная особенность хорновского дизъюнкта. Это выражение может быть переписано в виде:

P1 & P2 & … & Pm => Pn ,

и оно имеет следующую интерпретацию:

из P1 и P2 и … и Pm следует Pn.

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

В синтаксисе Пролога последнее выражение записывается:

Pn :- P1, P2, … , Pm.

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

1. Декларативный смысл: Pn истинно, если одновременно истинны P1, P2, … , Pm.

2. Процедурный смысл: для того, чтобы выполнить Pn, надо последовательно выполнить P1, P2, … , Pm.

Логика хорновских дизъюнктов эквивалентна полной теории предикатов первого порядка, применяемой для доказательства на основе опровержения. Механизм логического вывода использует метод резолюций, применяющийся для автоматического доказательства теорем, который был предложен Робинсоном (1965 г.) ¹. Процесс поиска доказательства на основе метода резолюции и составляет суть выполнения программы на Прологе. Однако знание этих понятий явно необязательно для того, чтобы начать программировать на Прологе. Поэтому мы сосредоточимся на прагматическом аспекте программирования на Прологе, опуская теоретическое обоснование, которое достаточно подробно изложено в литературе.