4.2.2.6. Логическое программирование

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

Типичным представителем языков программирования задач математической логики является Prolog. Само название Prolog есть сокращение, означающее программирование в терминах логики.

Пролог-программа состоит из предложений трех типов: факты, правила и вопросы.

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

Например,

• простое_число (3).

Это - высказывание, структура которого описана предикатом

P₁(x):=”x - простое число”.

• частное_от_деления(6, 2, 3).

Это - высказывание, структура которого описана предикатом

P₃(x, y, z):=”z есть частное от деления числа x на y”.

• студент_университета,_обучающийся_по_специальности (Петров, КГТУ, прикладная информатика").

Это - высказывание, структура которого описана предикатом

P₆(x, y, z):= "студент x университета y, обучающийся по специальности z”.

• :

отец (игорь, святослав).

отец (святослав, владимир).

отец (владимир, борис).

отец (владимир, глеб). / родословная русских

дед (игорь, владимир). князей X века /.

дед (святослав, борис).

дед (святослав, глеб).

брат (борис, глеб).

Это - высказывания, структура которых описана предикатами

P₄(X, Y):=”X – отец Y”, P₅(X, Y):=”X – дед Y”, P₆(X, Y):=”X – брат Y”.

Структуру высказывания или функциональную зависимость между предметными постоянными описывают термы.

Множество фактов формирует базу данных о предметной области.

Правила есть суждения, истинность которых зависит от истинности условий: “если истинны условия (посылки, цели), то истинно и заключение (вывод)”. Это – известное правило m.p.

На языке Prolog правила записывают так:

<заключение>:-

<условия>”.”

Символ “:-“ соответствует символу обратной импликации ””.

Левую часть правила называют головой предложения, а правую – телом предложения. В теле предложения перечисляют условия, а в голове - заключение.

Если дано несколько условий, и они имеют между собой конъюнктивную связь, то перечень условий описывают так:

<условие>{“,”<условие>}”.”,

если дизъюнктивную, - так:

<условие>{“;”<условие>}”.”.

Голова предложения всегда сдвинута влево относительно перечня условий. Каждое условие начинается с новой строки.

На языке Prolog эти правила записывают так:

<заключение>:-

<условие_1>”,”

<условие_2>”;”

<условие_3>”.”

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

Например, в базе знаний могут быть правила:

дед(X, Y):-

отец(X, Z),

отец (Z, Y).

брат(X, Y):-

отец (Z, X),

отец(Z, Y).

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

Пример:

?-дед (святослав, Y). /“Кому Святослав является дедом?”/.

В базе знаний есть правило:

дед(X, Y):-

отец(X, Z),

отец (Z, Y).

Выполняя подстановку в условия фактов из базы данных, получим:

отец (святослав, владимир).

отец (владимир, борис).

отец (владимир, глеб).

Следовательно, ответ на поставленный вопрос:

дед (святослав, борис, глеб). /”Святослав дед Борису и Глебу”/

Пример:

?-брат(X, Y). /”Есть ли братья среди русских князей X века”/.

В базе знаний есть правило:

брат(X, Y):-

отец (Z, X),

отец(Z, Y).

Выполняя подстановку в условия фактов из базы данных, получим:

отец (владимир, борис).

отец (владимир, глеб).

Следовательно, ответ на поставленный вопрос:

брат (борис, глеб). /”Борис и Глеб – братья”/.

Рассмотренный метод обобщает механизм унификации. Аргументы вызова - это имена переменных, которые подставляют на место формальных параметров. Формальными параметрами могут быть термы.

Например, для родословной русских князей X века имеем:

• дед (игорь, владимир):-

отец (игорь, святослав),

отец (святослав, владимир).

Это - высказывание о том, что если ‘игорь’ был отцом ‘святослава’, а ‘святослав’ – отцом ‘владимира’, то ‘игорь’ был дедом ‘владимиру’.

• дед (святослав, борис), дед(святослав, глеб):-

отец (святослав, владимир),

отец (владимир, борис);

отец (святослав, владимир),

отец (владимир, глеб).

Это есть высказывание о том, что ‘святослав’ был отцом ‘владимира’ и дедом ‘борису’ и ‘глебу’.

• брат(борис, глеб):-.

родитель(владимир, борис),

родитель(владимир,глеб).

Это есть высказывание о том, что если ‘владимир’ был отцом ‘бориса’ и отцом ‘глеба’, то ‘борис’ и ‘глеб’ были братьями.