Лекции пролог

Структура логического программирования и алгоритм унификации.

Структура логического программирования.

Предикат - это выражение вида P(x1,…,xk), где Р-предикатный символ, а в скобках располагаются термы.

Терм - это есть константа, переменная или составной терм. Составной терм - это выражение вида f(x1,..xs), где f - функциональный символ, а x1-xs термы.

Константа - это число или атом.

Атом - цепочка символов, начинающаяся с маленькой буквы.

Переменная - последовательность символов, начинающаяся с большой буквы.

В отличие от переменной атом обозначает конкретный объект. А переменная, в от-личие от атома, обозначает указание на неопределенный (неизвестный) объект.

Далее мы не будем различать терм и предикат.

Примеры терма: 0, s(0), s(s(0))…

Пример составного терма: plus(var(X),mult(z,Y)). C использованием составных тер-мов можно структурировать данные.

Пример составного терма, все простые термы которого - атомы:

course(monday,10,12, иванов, иван, иванович, 5, 7, математический анализ, fpm, 1). Значение этого терма: с 10 до 12 часов в понедельник преподаватель иванов иван Иванович в 5 корпусе 7 аудитории читает лекцию по математическому анализу для студентов первого курса факультета ФПМИ.

Посмотрим, эффективно ли использование такого предиката, если мы хотим задать цель (вопрос): занята ли 7 аудитория в 5 корпусе в понедельник с 10 до 12? Тогда цель выглядит следующим образом:

Goal: course(monday, 10, 12, _ , _ , _ , 5 , 7 , _ , _ , _). (*)

(В этом примере нам абсолютно не важно, кто - лектор, что он читает и у кого, ва- жен только сам факт, что аудитория занята. Все "неважные" компоненты предиката за-даны знаком "_").

Очевиден недостаток: нам приходится задавать много знаков "_".

Все дело в том, что предикат course пока не структурирован. Покажем пример структурирования на следующей программе:

domains

time1=time(symbol,integer,integer)

lect1=lector(symbol,symbol,symbol)

place1=place(integer,integer)

student=student(symbol,integer)

predicates course(time1,lect1,place1,symbol,student1)

clauses …

Раздел domains нашей программы - это раздел описания типов. В этой программе мы ввели 4 типа:

time1=time(день недели, с … часа, до … часа)

lect1=lector(фамилия, имя, отчество)

place1=place(корпус, аудитория)

student1=student(факультет, курс)

Раздел predicates описывает те предикаты, с которыми мы будем работать в разделе clauses. В нашей программе мы описали предикат course:

сourse(time1,lect1,place1,название предмета (symbol),student1).

Теперь, для преподавателя выделено не три поля в предикате, а одно; для времени лекции не три поля - а одно; для потока и места проведения лекции не по 2 поля - а по одному. Согласно введенным предикатам-типам, цель (*) перепишется так:

Goal: course(time(monday, 10, 12),_ ,place(5,7 ), _ , _).

Предложения в программе, которые имеют и заголовок и тело, называются правилами. Если у предложения только заголовок, то это - факт. Если в предложении отсутствует заголовок, то это - вопрос.

Goal - цель - любой предикат.

Goal: B1,B2,…,Bn.

В этой цели Bi - подцели.

Алгоритм унификации.

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

Подстановкой Q называется конечное множество пар вида:

Q={X1=t1,…,Xn=tn}; в равенстве Xi=ti - Xi-переменная, ti - терм XiXj (ij) и Xi не входит в терм для Xj при ij. Например: Q={X=анна, Y=жанна} - верная подстановка; Q={X=p(0), Y=S(X)} - неверная подстановка.

Результат применения подстановки Q к терму t обозначается tQ и представляет со-бой терм, полученный заменой каждого вхождения переменной Xi в терм t на ti для лю-бой пары Xi=ti из Q.

Терм t называется общим примером термов t1 и t2, если существуют такие подстановки Q1, Q2, что t=t1Q1=t2Q2.Терм S называется более общим, чем терм t, если t является примером S, а терм S не является примером t.

Пусть t=plus(X,mult(Y,var(a)));

Q={X=int(1), Y=plus(B,C)}.

Применим подстановку Q к терму t: S=tQ=plus(int(1),mult(plus(B,C),var(a))).

Терм S называется алфавитным вариантом терма t, если они являются примера-ми друг друга. Алфавитные варианты совпадают с точностью до переименования переменных.

Унификатором двух термов называется подстановка Q, которая делает термы одинаковыми. Если существует унификатор двух термов, то они называются унифицируемыми. Между унификатором и общим примером существует взаимосвязь:

Наибольший общий унификатор (НОУ)- унификатор, соответствующий наиболее общему примеру. Если два терма унифицируемы, то существует единственный НОУ.

Алгоритм унификации находит НОУ двух термов, если такой существует (то есть, если термы унифицируемы). Если термы неунифицируемы, то система сообщает об отказе.

Алгоритм использует еще 2 дополнительные переменные.

S - стек S={t1=S1,t2=S2,…}, где ti,Si - термы.

F - логическая переменная, отвечающая за отказ программы.

На входе в алгоритм: Q=, на выходе - Q=НОУ.

Опишем алгоритм унификации пошагово.

1. Вход: на вход подаются 2 терма: t1 и t2.

2. Q=, S={t1=t2}, F=false

3. Если S или F=false, то 4, иначе 5.

4. Из стека выбирается очередное равенство Si=Sj и анализируется.

   1. Если Si-переменная, не входящая в в Sj, то необходимо заменить все вхождения Si в стеке S и подстановке Q на Sj и добавить Si=Sj в подстановку Q.

   2. Если Sj-переменная, не входящая в в Si, то необходимо заменить все вхождения Sj в стеке S и подстановке Q на Si и добавить Sj=Si в подстановку Q.

   3. Если Si,Sj одинаковые константы или переменные, то ничего не делать.

   4. Si=f(X1,…,Xn) - составной терм; Sj=f(Y1,…,Yn) - составной терм; то есть функторы и арность этих предикатов совпадают, в этом случае в подстановку ничего не добавляется, а в стек добавляются равенства: Xi=Yi, i=1,n.

   5. Если ни один из первых 4 случаев не прошел, то F=true.

Отправиться в пункт 3.

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

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

Метод резолюций.

Рассмотрим клаузу: A:-B1,…,Bn, которая может быть записана как дизъюнкция выражений: A(B1)…  (Bn).

Правило резолюции применяется к двум дизъюнктам, например:

A(B)| B(C)| - применение правила резолюции - AC

AB(C)(D)| (B)D(B)F | - применение правила резолюции - A(B)F.

Результат применения правила резолюции называется резольвентой. Для получения резольвенты необходимо иметь 2 дизъюнкта:

1 дизъюнкт - целевое утверждение, которое имеет вид :-B1,B2,…,Bn.

2 дизъюнкт - одно из правил логической программы.

Так, например, если целевое утверждение :-B,D а правило программы B:-A,M,N , то результатом применения правила резолюции будет целевое утверждение :-A,M,N,D.

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

Работа интерпретатора логических программ.

Некоторое целевое утверждение будем обозначать буквой G, а логическую программу буквой P.

На входе интерпретатор имеет логическую программу GP.

Результатом работы является утверждение GQ, если GQ - это пример G, выводимый из программы P.

При входе в программу резольвенте присваивается значение целевого утверждения: R=G. После этого начинается цикл (пока резольвента не пуста): из резольвенты R произвольным образом выбирается Ri - подцель. В программе ищется правило A, но не произвольное, а такое, что:

A:-B1,…,Bm.

- причем термы A и Ri унифицируемы с НОУ Q. Если такое правило не может быть найдено, то происходит досрочный выход из цикла (данное целевое утверждение не может быть доказано), иначе:

• удалить Ri из резольвенты

• добавить в резольвенту B1,…,Bm

• применить подстановки Q в резольвенте и цели G

Пример работы интерпретатора логических программ:

Пусть программа имеет вид:

daughter(X,Y):-parent(Y,X),wom(X).

parent(ivan,galya).

parent(ivan,semen).

wom(galya).

wom(ira).

wom(sveta).

Зададим следующее целевое утверждение: Goal: daughter(X,ivan).

Результатом поиска ответа на этот вопрос должен быть ответ: чему равен Х (ожидаемый ответ, очевидно, Галя).

Итак, в начальный момент времени резольвента равна: R0={daughter(X,ivan)}

Ищем в программе заголовок, сопоставимый с функтором цели. Этот заголовок присутствует в программе только один раз. Имеем два терма:

T1=daughter(X,Y).

T2=daughter(X,ivan).

Эти два терма унифицируемы подстановкой Q={Y=ivan}

Теперь из резольвенты исключается терм T2 и помещаются подцели из правила, сунифицированного с ним.

R1={parent(ivan,X),wom(X)}.

Сначала рассматривается первый терм в R1:

T1=parent(ivan,X).

T2=parent(ivan,galya).

Эти два терма унифицируемы подстановкой Q={X=galya}

Теперь из R1 удаляется первый терм, второй терм конкретизируется подстановкой Q и превращается в терм wom(galya):

R21={wom(galya)}, но в программе есть такой факт, поэтому результат работы интерпретатора - выдача сообщения: X=galya.

Однако, еще не все, интерпретатор находит второй факт, унифицируемый с термом parent(ivan,X) - parent(ivan,semen). Эти два терма унифицируются подстановкой X=se-men и резольвента становится равной R={wom(semen)} - для такого терма в программе нет ни правил, ни фактов, поэтому изначальная цель G терпит на этой ветке неудачу.

В результате своевременного применения подстановки, исходная цель приняла вид: G = daughter(galya,ivan).

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

Для вышеприведенных программы и целевого утверждения:

daughter(X,ivan)

|

|Y=ivan

|

parent(ivan,X), wom(X)

| |

|X=galya |

| |

wom(galya) wom(semen)

TRUE FALSE

Деревья поиска.

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

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

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

Пример: доказать целевое утверждение дочь(Х, иван), изобразить дерево поиска.

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

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

дочь(Х, иван)

Y=иван

род(иван, Х), жен(Х)

Х=галя Х=семен

жен(галя) жен(семен)

true false

Порядок правил влияет на результат работы программы.

Упражнение:

дочь(X,Y):-жен(Х), род(Y,X)

жен(галя)

жен(ира)

жен(света)

род(иван, галя)

род(иван, семен)

Цель G : дочь(Х, иван).

Дерево поиска: дочь(Х, иван)

Y=иван

жен(Х), род(Y, Х)

Х=галя Х=ира Х=света

жен(галя) жен(ира) жен(света)

true false false

Х=галя

Использование рекурсии в логическом программировании.

прарод(X,Y):-род(X,Z), род(Z,Y).

прапрарод(X,Y):-род(X,Z1), род(Z1,Z2), род(Z2,Y).

Определим рекурсивное отношение предок:

предок(X,Y):-род(X,Z), предок(Z,Y).

предок(X,Y):-род(X,Y).

Факты: родитель(a,b), родитель(b,c).

1. предок(X,Y):-родитель(X,Y).

предок(X,Y):-родитель(X,Z), предок(Z,Y).

2. предок(X,Y):-родитель(X,Z), предок(Z,Y).

предок(X,Y):-родитель(X,Y).

3. предок(X,Y):-родитель(X,Y).

предок(X,Y):- предок(Z,Y), родитель(X,Z).

4. предок(X,Y):-предок(Z,Y), родитель(X,Z).

предок(X,Y):-родитель(X,Y).

Дерево поиска для 1:

предок(a,s)

x=a,y=s x=a,y=s

родитель(a,s) родитель(a,z), предок(z,s)

z=b

s=b, true предок(b,s)

x=b,y=s x=b,y=s

родитель(b,s) родитель(b,z), предок(z,s)

z=c

s=c, true предок(c,s)

x=c,y=s x=c,y=s

родитель(c,s) родитель(c,z), предок(z,s)

false false

Два решения: s=b, s=c. Дерево поиска для 2 симметрично; решения: s=с, s=b.

Упражнение: построить дерево поиска для 3 и 4.

Значения логической программы.

Значением логической программы P называется множество выводимых из P основных единичных целей.

V(P)- значение программы.

Основная цель - цель, которая не содержит переменных.

Неосновная цель - содержит переменные ( экзистенциальные цели).

Программа называется корректной относительно некоторого подразумеваемого значения М, если V(P)М.

Программа называется полной относительно некоторого подразумеваемого значения М, если М  V(P).

Полная программа вычисляет все, что требуется. Корректная программа не вычисляет ничего лишнего. Если программа полная и корректная, то М=V(P).

Рекурсивные типы данных.

Унарные:

Натуральные числа:

0 - ноль

S(0)=1

S(S(0))=2

…

S^m(0)=m

natural(0).

считается, что 0 натуральное число

natural(S(x)):-natural(x).

S(x) натуральное, если x натуральное.

natural(N) - неосновная цель, выдаст все натуральные числа.

Утверждение: программа natural полна и корректна относительно множества натуральных чисел.

Доказательство: полнота: какое бы nN ни взяли, оно должно генерироваться программой

natural(S^m(0))

natural(S^m-1(0))

…

natural(S(0))

natural(0)

true

корректность (по идукции): поставим неосновную цель natural(N). База индукции: при n=0 N=0, т. е. 0 - натуральное число. Предположение: для n-1 x - натуральное число, тогда и для n S(x) - натуральное число.

Пример: сложение двух натуральных чисел

plus(0,X,X):-natural(X).

plus(S(X),Y,S(Z)):-plus(X,Y,Z).

или

plus(X,0,X):-natural(X).

plus(X,S(Y),S(Z)):-plus(X,Y,Z).

Упражнение: доказать корректность и полноту программы.

domains

natural=0;s(natural) -рекурсивный тип данных

predicates

plus(natural, natural, natural).

Программу сложения натуральных чисел можно применять по-разному.

1. проверить, является ли третий аргумент суммой первых двух

plus(S(0),S(0),S(S(0)))? Yes, 1+1=2

2. сложение натуральных чисел

plus(S(0),S(S(0)),X)? X=3

3) операция вычитания

plus(X,S(0),S⁴(0))? X=3

4. задана сумма, слагаемые неизвестны

plus(X,Y,S³(0))? 4 решения: (0,3),(3,0),(2,1),(1,2)

4. цель накладывает условия

plus(X,X,S⁴(0))? X=2

Программа умножения натуральных чисел:

(X+1)Y=XY+Y

mult(0,X,0).

mult(S(X),Y,Z):-mult(X,Y,Z1), plus(Z!,Y,Z).

Программа возведения в степень (число, степень, результат):

X^N+1= X^NX

potens(0,S(X),0).

potens(S(X),0,S(0)).

potens(X,S(N),Y):- potens(X,N,Y1), mult(Y1,X,Z).

Программа вычисления факториала:

(N+1)!=N!(N+1)

factorial(0,S(0)).

factorial(S(N),F):-factorial(N,F1), mult(F1,S(N),F).

Бинарный тип данных - списки.

Список - последовательность произвольного числа элементов. В логическом программировании список обозначается [].

Например: [a,b,c], [1,2,3,4], ["Аня","Оля"].

В списке выделяют две части: первый элемент и оставшуюся часть.

[ голова | хвост ] голова-элемент списка, хвост-список

<функтор> ( голова | хвост )

[ a | [b,c] ], [ 1 | [2,3,4] ], [ "Аня" | ["Оля"] ]

[] - пустой список.

1. Программа принадлежности элемента списку:

member(X,[X|List]).

member(X,[Y|List]):-member(X,List).

member(b,[a,b,c,b])? yes

member(X,[a,b,c])? X=a, X=b, X=c

Список - частный случай двоичного дерева.

Списки используют для представления множеств, но в списке имеет значение порядок элементов, кроме того один и тот же объект может встретиться в списке несколько раз.

2. Подсписки

sublist(sub,list).

Префикс - подсписок, начинающийся с начала списка.

Суффикс - начинается с любого не первого элемента.

list

prefix

suffix

prefix(pre,list).

suffix(suf,list).

sublist(sub,list):-prefix(pre,list),suffix(sub,pre).

prefix

suffix

Sub

List

или

sublist(sub,list):- suffix(suf,list),prefix(sub,suf).

3. Соединение двух списков - аналог программы сложения натуральных чисел:

List1

List2

List

append([],list,list).

append([X|X_S],Y_S, [X|Z_S]):-append(X_S,Y_S,Z_S).

Нарисовать дерево поиска решений append([a,b],[c,d],[a,b,c,d])

append([a,b],[c,d],[a,b,c,d])

X=a, X_S=[b],Y_S=[c,d],Z_S=[b,c,d]

append([b],[c,d],[b,c,d])

X=b, X_S=[],Y_S=[c,d],Z_S=[c,d]

append([],[c,d],[c,d])

true

Программу можно использовать различными способами:

1. конкатенация списков

append([a,b],[c,d],list)?

2. проверка того, что третий список является конкатенацией первых двух

3. нахождение разности двух списков, например неизвестен первый аргумент

append(list1,[c,d],[a,c,d])? list1=[a]

4. нахождение множественного решения, когда неизвестны первые два аргумента

append(list1,list2,[a,b,c])?

1) list1=[] list2=[a,b,c]

2) list1=[a] list2=[b,c]

3) list1=[a,b] list2=[c]

4) list1=[a,b,c] list2=[]

Упражнение: построить дерево поиска решений.

4. Программа обращения списков.

reverse (List,Tsil).

Существует две стратегии обращения списков:

1. наивное обращение

reverse ([ ],[ ]).

reverse ([X | Xs],Ys) :– reverse (Xs,Y1s), append (Y1s,[X],Ys).

2. обращение с накоплением (обращение с добавлением)

reverse (Xs,Ys) :– reverse (Xs,[ ],Ys).

reverse ([X | Xs],Acc,Ys) :– reverse (Xs,[X¦Acc],Ys).

reverse ([ ],Acc,Acc).

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

По эффективности оптимальным является обращение списка с накоплением.

Упр. Нарисовать дерево поиска решений для обеих стратегий для цели: reverse([a,b],[b,a])?

5. Определение длины списка.

Length([ ],Ø).

Length([X|Xs],N):–length (Xs,N1), N=N1+1.

6. Удаление элемента из списка.

Delete(List,El,List1).

List=[a,b,c,b].

El=b.

List1=[a,c] – удалены все вхождения элемента ‘b’.

1. текущий элемент совпадает с искомым;

2. текущий элемент не совпадает с искомым;

3. список окончен.

delete ([X|Xs],X,Ys):–delete (Xs,X,Ys).

delete ([X|Xs],Y,Ys):–X<>Y, delete (Xs,Y,Ys).

delete ([ ],Y,[ ]).

Вопрос: изменится ли значение программы, если из 2-го правила убрать условие X<>Y?

7. Выделение элемента из списка.

Программа из п.6 не может иметь несколько решений. Когда возможно только одно решение, предикат называется детерминированным. Недетерминированный предикат имеет несколько решений. Предикат из п.7 – недетерминированный.

select (X,[X|Xs],Xs).

select (X,[Y|Ys],[Y|Zs1]) :– select (X,Ys,Zs).

1-й аргумент – выделяемый аргумент.

2-й аргумент – список, из которого выделяется аргумент.

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

8. Сортировка списков.

Упорядочивание элементов списка по возрастанию от меньшего к большему.

Существует две стратегии:

• наивная сортировка – «образовать и проверить»

• «разделяй и властвуй»

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

Для этого генерируются всевозможные перестановки.

sort (Xs,Ys):– perestanovka (Xs,Ys), ordered (Ys).

ordered ([X,Y|List]):– X<Y, ordered([Y|List]).

Отношение перестановки генерирует n! решений.

perestanovka(Xs,[Z|Zs]):– select(Z,X,X1s), perestanovka(X1s, Zs).

2. «разделяй и властвуй» – список разделяется на две части, каждая часть независимо сортируется, затем части объединяются.

А) сортировка вставкой: механизм разделения, объединения вставкой.

Б) разбиение: List1 – все меньшие элементы

List2 – все большие элементы

Затем производится объединение этих частей простой склейкой.

Сортировка вставкой.

sort ([X|Xs], Ys):– sort (Xs,X1s), insert (X,X1s,Ys).

sort([ ],[ ]).

Insert() – вставить, не изменяя порядка.

insert(X,[ ],[X]).

insert(X,[Y|Ys],[Y|Zs]):– Y<X, insert(X,Ys,Zs).

insert(X,[Y|Ys],[,XY|Ys]).

Алгоритм быстрой сортировки.

(по стратегии «разделяй и властвуй»)

quicksort ([X|Xs],Ys):– partition(Xs, X, Littles, Bigs), quicksort(Littles, Ls), quicksort(Bigs, Bs), append(Ls,[X|Bs],Ys).