Функциональное программирование и интеллектуальные системы

Зюзьков В. М.
Логическое и функциональное программирование: Учебное пособие. -
Томск: Томский межвузовский центр дистанционного образования, 2000.
- 72 с.

3. Логическое программирование ......... 14
3.1. Контроль обучения ................. 14
3.2. Инсталляция SWI-Prolog'а .......... 14
3.3. Первое контрольное задание ........ 15
3.4. Второе контрольное задание ........ 19
3.5. Третье контрольное задание ........ 23

Первое контрольное задание

Задание состоит из двух задач, в которых требуется составить програм-мы на Прологе для написания простых предикатов. При составлении про-грамм (если не оговорено противное) можно использовать все встроенные предикаты Пролога. Тексты всех программ, если вы мыслите в духе логиче-ского программирования, получаются небольшие.
SWI-Prolog не имеет стандартного help'а для Windows, для этого ис-пользуется предикат help. Вызов help(<имя предиката>) выдает на экран ин-формацию об этом предикате. Вызов help(7) выдает на экран список всех встроенных предикатов с комментариями. Текстовый файл руководства по SWI-Prolog - pl\library\manual. Отладку предикатов можно осуществлять с помощью предиката трассировки trace(<имя предиката>), трассировка преди-ката отключается - trace(<имя предиката>, -all).

Пример задания с решением
Задача 1
Постройте предикат position_max(+L, -M, -N), который в списке L находит максимальное значение M и порядковый номер N этого значения.
Задача 2
Определите умножение целых чисел через сложение и вычитание.

Решение

Задача 1
Будем использовать метод накапливающего параметра. Для этого введем вспомогательный предикат position_max(+List, +I, +M0, +N0, -M, -N), где I равен номеру рассматриваемого элемента в исходном списке, M0 - текущее значение максимума, N0 - позиция текущего максимума.

position_max([X|T],M,N):-
position_max(T,1,X,1,M,N).
position_max([],_,M,N,M,N).

position_max([A|T],I,X,_,M,N):-
A>X,
K is I+1,
position_max(T,K,A,K,M,N).

position_max([A|T],I,X,Y,M,N):-
A= K is I+1,
position_max(T,K,X,Y,M,N).

?- position_max([3,2,5,1,4,3],M,N).
M = 5
N = 3
Yes

Задача 2
Определим предикат p(+X,+Y,?R), где X и Y сомножители, R - произведение.
Делаем рекурсию по второму аргументу предиката, используя рекурсивное определение X*Y=X*(Y-1)+X.

p(X,0,0).

p(X,Y,R):- Y>0,
Y1 is Y-1,
p(X,Y1,R1),
R is R1+X.

p(X,Y,R):- Y<0,
Y1 is -Y,
p(X,Y1,R).

Варианты заданий

Вариант 1
1. Определите возведение в целую степень через умножение и деление.
2. Напишите предикат p(+L, -N) - истинный тогда и только тогда, когда N - предпоследний элемент списка L, имеющего не менее двух элементов.

Вариант 2
1. Напишите предикат p(+X, +N, -L) - истинный тогда и только тогда, когда L - список из N раз повторенных элементов X.
2. Напишите предикат p(+L, -S) - истинный тогда и только тогда, когда S - список списков элементов списка L, например, p([a, b, c],[[a], [b], [c]]) - истина.

Вариант 3
1. Напишите предикат p(+L, -S) - истинный тогда и только тогда, когда L - список списков, а S - список, объединяющий все эти списки в один.
2. Напишите предикат p(+L, -S) - истинный тогда и только тогда, когда список S есть циклическая перестановка элементов списка L, например,
p([f, g, h, j], [g, h, j, f]) -истина.

Вариант 4
1. Напишите предикат p(+X, +N, +V, -L) - истинный тогда и только тогда, ко-гда список L получается после добавления X на N-е место в список V.
2. Напишите предикат p(+N, +V, -L) - истинный тогда и только тогда, когда список L получается после удаления N-го элемента из списка V.

Вариант 5
1. Напишите предикат p(+V, -L) - истинный тогда и только тогда, когда список L получается после удаления всех повторных вхождений элементов в список V, например, p([a, b, c, d, d, a], [a, b, c, d]) - истина.
2. Напишите предикат p(+V, -L) - истинный тогда и только тогда, когда список L получается после удаления из списка V всех элементов, стоящих на четных местах, например, p([1, 2, 3, 4, 5, 6], [1, 3, 5]) - истина.

Вариант 6
1. Напишите предикат p(+V, +X, -L) - истинный тогда и только тогда, когда список L получается из списка V после удаления всех вхождений X на всех уровнях, например, p([1, [2, 3, [1]], [3, 1]], 1, [[2, 3, []], [3]]) - истина.
2. Напишите обобщение предиката member, когда ищется элемент на всех уровнях в списке.

Вариант 7
1. Определите предикат p(+U, +V, -L) - истинный тогда и только тогда, когда список L есть список всех элементов списка U, не содержащихся в списке V.
2. Определите предикат p(+U, +V, -L) - истинный тогда и только тогда, когда L - список всех элементов, содержащихся либо в списке U, либо в списке V, но не одновременно в U и V.

Вариант 8
1. Определите предикат p(+V, -L) - истинный тогда и только тогда, когда L - список всех элементов списка V, встречающихся в нем более одного раза.
2. Напишите предикат subst(+V, +X, +Y, -L) - истинный тогда и только тогда, когда список L получается после замены всех вхождений элемента X в списке V на элемент Y.

Вариант 9
1. Напишите предикат p(+V, -L) - истинный тогда и только тогда, когда список L получается из списка V после удаления всех повторяющихся элементов, т. е. из списка получается множество.
2. Напишите предикат exists(+P, +L), который проверяет "Существует ли эле-мент списка L, удовлетворяющий предикату P?"

Вариант 10
1. Напишите предикат all(+P, +L), который проверяет "Для всех ли элементов списка L выполняется предикат P? "
2. Напишите предикат filter(+V, +P, -L) - истинный тогда и только тогда, когда список L есть список всех элементов из списка V, удовлетворяющих пре-дикату P ("фильтрация" списка).

Вариант 11
1. Используя предикаты "родитель"(Родитель, Отпрыск), "женщи-на"(Человек), "мужчина"(Человек) и "супруги"(Жена, Муж), определите от-ношения теща, шурин и зять.
2. Башня из кубиков может быть описана совокупностью фактов вида "на"(Кубик1, Кубик2), которые истинны, если Кубик1 поставлен на Кубик2. Определите предикат "выше"(Кубик1, Кубик2), который истинен, если Кубик1 расположен на башне выше, чем Кубик2. (Указание: "выше" является транзитивным замыканием отношения "на".)

Вариант 12
1. Напишите предикат gcd(+A,+B,-D) - истинный тогда и только тогда, когда D -наибольший общий делитель двух целых положительных чисел A и B.
2. Напишите программу для отношения double(+List, -ListList), в котором каждый элемент списка List удваивается в списке ListList, например, double([1,2,3],[1,1,2,2,3,2]) выполнено.

Вариант 13
1. Напишите новую версию предиката length(+L, -N), в котором при
подсчете количества элементов списка не учитывается пустой список. К при-меру, для списка [a,b,c,d,e] новая версия процедуры должна сообщить, что длина списка равна пяти, а для списка [a,[],c,d,[]] эта процедура должна давать длину, равную трем.
2. Пусть имеется список структур "client": [cli-ent(a,29,3),client(b,29,6),client(c,40,2)].
Первым аргументом каждой структуры служит имя клиента, вторым - суточ-ный тариф, а третьим - количество дней, на которое взята автомашина. Напишите правило, позволяющее вычислить итоговую сумму оплаты, объ-единяющую выплаты всех клиентов, данные о которых содержатся в списке.

Вариант 14
1. Опишите процедуру для предиката расщепить/4, которая берет список це-лых чисел L1 и целое число N и выдает списки L2 и L3 такие, что числа из исходного списка, меньшие, чем N, помещаются в список L2, а остальные - в список L3.
2. Напишите предикат для вычисления чисел Фибоначчи, используя метод накапливающего параметра.

Вариант 15
1. Напишите предикат digits(+N, -L) - истинный тогда и только тогда, когда L - список цифр натурального числа N.
2. Напишите предикат summa_digits(+N, -S) - истинный тогда и только тогда, когда S - сумма цифр натурального числа N.

3.4. Второе контрольное задание

Задание состоит из двух задач, в которых требуется составить програм-мы на Прологе для написания простых программ. При составлении программ (если не оговорено противное) можно использовать все встроенные предикаты Пролога. Тексты всех программ, если вы мыслите в духе логического про-граммирования, получаются небольшие.

Пример задания с решением
Задача 1
Сортировка списка простым обменом (по возрастанию).
Задача 2
Пусть бинарное дерево задается рекурсивной структурой tree(<левое подде-рево>,<корень>,<правое поддерево>) и пустое дерево задано термом nil. Составьте программу subtree(+S, +T), определяющую, является ли S поддере-вом T.

Решение

Задача 1
Заданный список L сортируется по следующему алгоритму:
(1) если L содержит два соседних элемента, нарушающих требуемое упоря-дочение, то эти элементы меняются местами, после чего к полученному спис-ку применяется этот же алгоритм;
(2) если в L не встречается ни одной неупорядоченной пары соседних эле-ментов, то список L отсортирован и тем самым является искомым списком.
Предикат ord(+L) проверяет является ли список L отсортированным.

ord([]).
ord([_]).
ord([X,Y|T]):-
X =< Y,
ord([Y|T]).

change(L,L):-
ord(L),!.
change(L,S):-
append(L1,[X,Y|L2],L),
X>Y,!,
append(L1,[Y,X|L2],Z),
change(Z,S).

Отсечения в данном случае ликвидируют многочисленные правильные отве-ты.

Задача 2
Для решения используется очевидная рекурсия.

subtree(X, X).
subtree(X, tree(L,_,_)):-
subtree(X,L).
subtree(X,tree(_,_,R)):-
subtree(X,R).

Варианты заданий

Вариант 1
1. Напишите предикат, аналогичный предикату subst (см. первое контрольное задание, вариант 8, задача 2), но производящий взаимную замену X на Y, т.е. X->Y, Y->X. 2. Напишите предикат, который определяет, является ли данное натуральное число простым. Воспользуйтесь более общей задачей: ispr(N, M) - "Число N не делится ни на одно число большее или равное M и меньшее N".
Имеем ispr(N, M) -истинно, во-первых, если N = M, и, во-вторых, если ис-тинно ispr(N,M+1) и N не делится на M.

Вариант 2
1. Сортировка списка простой вставкой (по возрастанию).
2. Сортировка списка простым выбором (по возрастанию).

Вариант 3
1. Напишите предикат p(+L, -N) - истинный тогда и только тогда, когда N - количество различных элементов списка L. 2. Напишите предикат p(+X, +Y, -Z) - истинный тогда и только тогда, когда Z есть "пересечение" списков X и Y, т.е. список, содержащий их общие элемен-ты, причем кратность каждого элемента в списке Z равняется минимуму из его кратностей в списках X и Y.

Вариант 4
1. Запрограммируйте предикат p(+A,+B), распознающий, можно ли получить список элементов A из списка элементов B посредством вычеркивания неко-торых элементов. Алгоритм: Если A - пустой список, то ответом будет "да". В противном слу-чае нужно посмотреть, не пуст ли список B. Если это так, то ответом будет "нет". Иначе нужно сравнить первый элемент списка A с первым элементом списка B. Если они совпадают, то надо снова применить тот же алгоритм к остатку списка A и остатку списка B. В противном случае нужно снова при-менить тот же алгоритм к исходному списку A и остатку списка B.
2. Напишите предикат p(+X, +Y, +L) - истинный тогда и только тогда, когда X и Y являются соседними элементами списка L.

Вариант 5.
1. Определите отношение sum_tree(+TreeOfInteger, -Sum), выполненное, если число Sum равно сумме целых чисел, являющихся вершинами дерева TreeOfInteger. 2. Определим операторы: :- op( 100, fy, ~). :- op( 110, xfy, &).
:- op( 120, xfy, v).

Булева формула есть терм, определяемый следующим образом: константы true и false - булевы формулы; если X и Y - булевы формулы, то и X v Y, X & Y, ~X - булевы формулы, здесь v и & - бинарные инфиксные операторы дизъюнкции и конъюнкции, а ~ - унарный оператор отрицания. Напишите предикат p(+T), определяющий, является ли данный терм T булевой форму-лой.

Вариант 6
1. Встроенный предикат functor(+Term, ?Functor, ?Arity) определяет для за-данного составного терма Term его функтор Functor и местность Arity. Встроенный предикат arg(+N, +Term, ?Value) определяет для целого числа N и заданного составного терма Term его N-ый аргумент Value. Определите предикаты functor1 и arg1 - аналоги предикатов functor и arg через предикат univ (=..)
2. Напишите предикат range(?M, ?N, ?L), истинный тогда и только тогда, когда L - список целых чисел, расположенных между M и N включительно (предикат должен допускать различное использование, когда не менее двух из трех аргументов конкретизованы). (Указание. Используйте предикаты var(+X) и nonvar(+X)).

Вариант 7
1. Напишите вариант программы plus(?X, ?Y, ?Z), пригодный для сложения, вычитания и разбиения чисел на слагаемые.
(Указание. Используйте для порождения чисел встроенный предикат between(+Low, +High, ?Value), который порождает все целые числа от нижней границы Low до верхней границы High.)
2. Напишите программу вычисления целочисленного квадратного корня из натурального числа N, определяемого как число I, такое, что I*I ? N, но (I+1)*(I+1) > N . Используйте определение предиката between/3 для генериро-вания последовательности натуральных чисел с помощью механизма возвра-тов.

Вариант 8
1. Напишите новую версию процедуры "предок", которая вырабатывает спи-сок представителей всех промежуточных поколений, располагающихся между предком и потомком. Предположим, например, что Генри является отцом Джека, Джек - отцом Ричарда, Ричард - отцом Чарльза, а Чарльз - отцом Джейн. При запросе о том, является ли Генри предком Джейн, должен
выдаваться список, характеризующий родственную связь этих людей, кон-кретно: [джек, ричард, чарльз].
2. Определите предикат p(+V, +N, -L) - истинный тогда и только тогда, когда L - список элементов списка V, встречающихся в нем не менее N раз. Про-верьте работу этого предиката на примере [a, a, b, a, c, b, c, a, b, b, d, a, b] для N=1,2,5,0.


3.5. Третье контрольное задание

Задание состоит из двух задач, в которых требуется составить более сложные программы на Прологе (как правило, требуется определить несколь-ко предикатов). При составлении программы (если не оговорено противное) можно использовать все встроенные предикаты Пролога. Текст программы, если вы мыслите в духе логического программирования и используете рекур-сию, получается небольшой.

Пример задания с решением
Задача 1
Определим операторы:
:- op( 100, fy, ~).
:- op( 110, xfy, &).
:- op( 120, xfy, v).

Булева формула есть терм, определяемый следующим образом: константы true и false - булевы формулы; если X и Y - булевы формулы, то и X v Y, X & Y, ~X - булевы формулы, здесь v и & - бинарные инфиксные операторы дизъюнкции и конъюнкции, а ~ - унарный оператор отрицания.
Напишите программу, распознающую логические формулы в конъюнктивной нормальной форме, т.е. формулы, являющиеся конъюнкцией дизъюнкций ли-тералов, где литерал - атомарная формула или ее отрицание.

Задача 2
Напишите предикат p(+N, -L) - истинный тогда и только тогда, когда список L содержит все последовательности (списки) из N нулей, единиц и двоек, в которых никакая цифра не повторяется два раза подряд (нет куска вида XX).

Решение

Задача 1
Из определения операций видно, что конъюнкция и дизъюнкция являются право ассоциативными, т. е. запрос
?- X & Y & Z = A & B
приводит к унификации X = A, Y & Z = B.
Определим два вспомогательных предиката literal(X) и dis(X), которые прове-ряют является ли X литералом и элементарной дизъюнкцией соответственно.
literal(true).
literal(false).
literal(~ X):-
literal(X).

dis(X):-
literal(X).
dis(X v Y):-
literal(X),
dis(Y).

con(X):- dis(X).
con(X & Y):-
dis(X),
con(Y).

?- con( true & (~ false v true v false) & ~ true).
Yes

Задача 2
p(1,[[0],[1],[2]]).
p(N,R):- N>1,
N1 is N-1,
p(N1,R1),
t(R1,R).

t([],[]).
t([X|T],Z):-
t(T,R1),
s(X,R),
append(R,R1,Z).

s([0|T],[[1,0|T],[2,0|T]]).
s([1|T],[[0,1T],[2,1|T]]).
s([2|T],[[0,2|T],[1,2|T]]).

Варианты заданий

Вариант 1
1. Напишите предикат p(+N, +K, -L) - истинный тогда и только тогда, когда L - список всех последовательностей (списков) длины K из чисел 1,2,...,N.
2. Напишите предикат p(+N, -L) - истинный тогда и только тогда, когда спи-сок L содержит все последовательности (списки) из N нулей и единиц, в которых никакая цифра не повторяется три раза подряд (нет куска вида XXX).



Вариант 2
1. Определите отношение ordered(+Tree), выполненное, если дерево Tree яв-ляется упорядоченным деревом целых чисел, т. е. число, стоящее в любой вершине дерева, больше любого элемента в левом поддереве и меньше любо-го элемента в правом поддереве. Определение структуры "дерево" см. раздел "Второе контрольное задание". Указание. Можно использовать вспомогательные предикаты ordered_left(+X, +Tree) и ordered_right(+X, +Tree), которые проверяют, что X меньше (боль-ше) всех чисел в вершинах левого (правого) поддерева дерева Tree и дерево Tree - упорядочено.
2. Определим операторы:
:- op( 100, fy, ~).
:- op( 110, xfy, &).
:- op( 120, xfy, v).

Булева формула есть терм, определяемый следующим образом: константы true и false - булевы формулы; если X и Y - булевы формулы, то и X v Y, X & Y, ~X - булевы формулы, здесь v и & - бинарные инфиксные операторы дизъюнкции и конъюнкции, а ~ - унарный оператор отрицания.
Напишите программу, распознающую логические формулы в дизъюнктивной нормальной форме, т.е. формулы, являющиеся дизъюнкцией конъюнкций ли-тералов, где литерал - атомарная формула или ее отрицание.

Вариант 3
1. Определим операторы:
:- op( 100, fy, ~).
:- op( 110, xfy, &).
:- op( 120, xfy, v).

Булева формула есть терм, определяемый следующим образом: константы true и false - булевы формулы; если X и Y - булевы формулы, то и X v Y, X & Y, ~X - булевы формулы, здесь v и & - бинарные инфиксные операторы дизъюнкции и конъюнкции, а ~ - унарный оператор отрицания. Напишите программу, задающую отношение negation_inward(+F1,-F2), кото-рое выполнено, если логическая формула F2 получается из логической фор-мулы F1 внесением всех операторов отрицания внутрь конъюнкций и дизъ-юнкций.

Вариант 4
1. Определите предикат occurances(+Sub,+Term,-N), истинный, если число N равно числу вхождений подтерма Sub в терм Term. Предполагается, что терм Term не содержит переменных. 2. Разработайте программу "Советник по транспорту". Выберите либо сеть, состоящую из городов, либо транспортную сеть маршрутов поездов или авто-бусов в пределах одного города. Вы должны информировать систему о том, откуда и куда Вы собираетесь добраться, а система должна выдавать реко-мендации о том, какими поездами, автобусами, самолетами и т. д. Вам следует воспользоваться, чтобы добраться до пункта назначения.

Вариант 5
1. Напишите предикат p(+S, -L), который переводит предложение S, пред-ставленное строкой, в список атомов L. Например, p('gfrtyre hjnki <> pi 876 h', [ gfrtyre, hjnki, '<>', pi, 876,h]) выполнено. Указание. Воспользуйтесь предика-том name/2.
2. Множественное число большинства английских существительных получа-ется путем добавления буквы "s" к форме единственного числа. Но если су-ществительное заканчивается буквой "y", следующей за согласной, множе-ственное число образуется путем замены буквы "y" на сочетание "ies"; если же существительное заканчивается буквой "o", следующей за согласной, множе-ственное число образуется путем добавления сочетания "es". Напишите ут-верждения для предиката множественное_число/2, которые задают все эти правила. Указание. Воспользуйтесь предикатом name/2.

Вариант 6
1. Простейшая система кодирования сообщений заключается в замене каждой буквы сообщения на букву, находящуюся на N-й по отношению к ней позиции в алфавите. Например, для N=2 буква "a" заменяется на "c", буква "y" на "a" и т.д. Зная, что коды ASCII букв от "a" до "z" изменяются от 97 до 122, напишите процедуру для предиката шифратор/3, который берет шифруемое слово и целое число и выдает слово, представляющее шифр данного слова, полученный с помощью указанного метода.
Указание. Воспользуйтесь предикатом name/2.
2. Напишите предикат предшествует/2, который берет два атома в качестве своих аргументов и успешно согласуется, если первый из них в лексико-графическом порядке предшествует второму.
Указание. Воспользуйтесь предикатом name/2.

Вариант 7
1. Одним из примеров использования предиката name/2 может служить гене-рация новых атомов для представления вновь вводимых объектов, например, abc1, abc2, abc3 и т.д. Эти имена характеризуются тем, что все они состоят из корня, определяющего тип именуемого объекта, и целочисленного суффикса для различения объектов одного типа. Напишите программу
новое_имя(+X, -Y). Последовательность имен создается с помощью возвра-тов. Указание. Воспользуйтесь предикатом int_to_atom(+N,-X), который кон-вертирует натуральное число N в атом X. 2. Построить программу "сжать", назначение которой - преобразование ан-глийских слов в их "звуковой" код. Этот процесс предусматривает "сжатие" примерно одинаково звучащих слов в одинаковый их код - своего рода, аб-бревиатуру этих слов. Слова "сжимаются" в соответствии со следующими правилами:
- первая буква слова сохраняется;
- все последующие за ней гласные, а также буквы "h", "w" и "y" удаляются;
- сдвоенные буквы заменяются одиночными;
- закодированное слово состоит не более чем из четырех букв, остальные бук-вы удаляются.
Примеры: сжать(barrington, brng) и сжать(llewellyn, ln) - выполнено.
Указание. Воспользуйтесь предикатом name/2.