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

Концепция логического программирования (ЛП)

ЛП – программирование в терминах целей.
Процедурные языки -

Пролог: набор механизмов

Сопоставление образцов
Древовидное представление структур данных
Автоматический возврат
Программирование в терминах логики:
Декларативная

Пример области знаний «Логика»

Если Дэвид интересуется логикой, то он либо запишется

Пример «Логика» Оформление знаний в логике высказываний

Высказывания Обозначение
Дэвид интересуется логикой D
Дэвид запишется

Пример «Логика» Оформление знаний в логике предикатов

Предикат Обозначение
X интересуется Y D(X,Y)
X запишется

Модель на Прологе

строится в терминах:
объектов и утверждений
(предикатов)
Простые Структуры
объекты Факты Правила
(Термы) (Сложные Вопросы
термы)

Простые объекты (термы)

Константы
Атомы (со строчной буквы или в кавычках)
Char (отдельный

Утверждения (предикаты)

Факт – безусловно истинное утверждение.
отсутствие факта означает его неудачное выполнение!
Правило

Факты
<предикат>(объект1,…,объектN).
константы
Совокупность фактов – база данных.

Пример. Дерево родственных отношений

Иван

Ольга

Елена

Петр

Алла

Борис

Вера

Игорь

Егор

Пример. Предикаты.

родитель(иван, ольга).
родитель(иван, петр).
родитель(елена, ольга).
родитель (ольга, вера).
родитель (ольга, игорь).

Пример. Вопросы.

? – родитель(иван, ольга). ==> Yes
? – родитель (Х, вера).

Правила

[A] : – [B].
A – заголовок / голова предложения
В –

Пример «Логика» Оформление знаний на Прологе

Предикат Обозначение
X интересуется Y D(X,Y)
X запишется в

Пример. Правила родственных отношений

отпрыск(X,Y):-родитель(Y,X).
женщина(елена).
женщина(ольга).
мужчина(петр).
мужчина(борис).
мать(X,Y):-родитель(X,Y),женщина(Х).
отец(X,Y):-родитель(X,Y),мужчина(Х).
сестра(X,Y):- родитель(Z,X), родитель(Z,Y), женщина(Х).
имеет_ребенка(X):-родитель(Х,_).

Переменные в предложениях.
Диапазон имени переменной – одно предложение!
Разные предложения – разные

Процедура

Набор правил с одним именем предиката, сгруппированных в одном месте.
A:- B,C. ИЛИ
A:-

Пример. Процедура родственных отношений

кузина(X,Y):-родитель(X1,X),родитель(X2,Y),
сестра(X1,X2),женщина(Х).
кузина(X,Y):-родитель(X1,X),родитель(X2,Y),
брат(X1,X2),женщина(Х).
можно
кузина(S,Y):- женщина(S),родитель(X1,S),
родитель(X2,Y),сестра(X1,X2),

Унификация термов

Два терма унифицируемы (сопоставимы), если:
термы абсолютно одинаковы (константы);
1-й терм –

Поиск решения

Резольвента – множество целей, которые необходимо выполнить.
Поиск (начало – с

Пример поиска решения

Программа
p(X):-q(X),s(X),r(X).
p(X):-u(X).
q(a).
q(b).
s(c).
s(b).
r(a).
u(d).
u(a).
?- p(a).

Поиск решения
Начальная резольвента: p(a).
1-е предложение: p(X):-q(X),s(X),r(X).
Унификация: X=a.
Новая резольвента:

Общая структура программы

[include «файл, добавляемый к модулю»]
[global domains]
[Domains]
<описание сложных термов>
[global predicates]
Predicates
<описание

Predicates

<предикат>(тип_арг1, …, тип_аргN).
Можно:
<предикат>(тип_арг1 комментарий1, … ,
тип_аргN комментарийN)
Допустимо многократное объявление

Пример программы «Семейные отношения»

predicates
parent(Symbol parent, string child)
man(string)
woman(symbol)
mother(SYMBOL, SYMBOL)
father(SYMBOL, SYMBOL)
sister(string,string)
brother(string,string)
kuzina(string,string)
clauses
parent(ivan,peter).
parent(ivan,olga).
parent(elena,olga).
parent(peter,alla).
parent(olga,vera). …

man(«ivan»).
man(peter). …
woman(olga).
woman(alla). …
mother(X,Y):-parent(X,Y),woman(X).
father(X,Y):-parent(X,Y),man(X).
sister(X,Y):-parent(Z,Y),parent(Z,X),woman(X).
brother(X,Y):-parent(Z,Y),parent(Z,X),man(X).
kuzina(X,Y):-woman(X),
parent(X1,X),parent(X2,Y),sister(X1,X2).
kuzina(S,Y):-woman(X),
parent(X1,S),parent(X2,Y),brother(X1,X2).
goal
kuzina(vera,alla).

Сложные термы
Структуры
Перечислимые термы
Списки

Структуры

S(X1, X2, …, XN)
S – имя структуры (функтор).
Xi – компоненты

Сложные термы (описание)

Перечислимые термы
T = k1; k2; … kN
T – имя

«Семейные отношения», структуры данных

domains
pol = man; woman
date = day(integer day, integer