Поможем в ✍️ написании учебной работы

Имя

Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

Выберите тип работыЧасть дипломаДипломная работаКурсовая работаКонтрольная работаРешение задачРефератНаучно - исследовательская работаОтчет по практикеОтветы на билетыТест/экзамен onlineМонографияЭссеДокладКомпьютерный набор текстаКомпьютерный чертежРецензияПереводРепетиторБизнес-планКонспектыПроверка качестваЭкзамен на сайтеАспирантский рефератМагистерская работаНаучная статьяНаучный трудТехническая редакция текстаЧертеж от рукиДиаграммы, таблицыПрезентация к защитеТезисный планРечь к дипломуДоработка заказа клиентаОтзыв на дипломПубликация статьи в ВАКПубликация статьи в ScopusДипломная работа MBAПовышение оригинальностиКопирайтингДругое

Нажимая кнопку "Продолжить", я принимаю политику конфиденциальности

Факты в Прологе интерпретируются как положительные литеры. Правила интерпретируются как формула-импликация. Вопросы интерпретируются как отрицательные литеры.

Пример 3.4.1.Логическая интерпретация программы «Родственные отношения». Отношение родитель обозначим предикатным символом R. Отношение мужчина обозначим предикатным символом M. Отношение отец обозначим предикатным символом F. Программа интерпретируется как набор дизъюнктов.

R(пам, боб), R(том, боб), R(том, лиз),

R(боб, энн), R(боб, пат), R(пам, джим),

M(боб), M(том), M(джим),

ØR(X, Y)ÚØM (X)Ú F(X, Y) (получен из импликации R(X, Y)&M (X)É F(X, Y))

Ø F(X, боб) (вопрос «Кто является отцом Боба?»)

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

Пример 3.4.2.Логическое решение программы «Родственные отношения».

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

	R(пам, боб),
	R(том, боб),
	R(том, лиз),
	R(боб, энн),
	R(боб, пат),
	R(пам,джим),
	M(боб),
	M(том),
	M(джим),
	ØR(X,Y)ÚØM(X)ÚF(X,Y),
	Ø F(X, боб),
	ØR(X,Y)ÚØM(X),	из (11) и (10)	рекурсивный вызов
	ØM(пам),	из (12) и (1)	рекурсивный вызов
		резольвент нет	возврат к шагу 12
	ØR(X,Y)ÚØM(X),	возврат,
	ØM(том),	из (12) и (2)
	□.	из (13) и (8),	КОНЕЦ РАБОТЫ (успех)

3.5. Работа в пролог-системе

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

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

Описание инфиксных операций

Для записи арифметических операций в теории известны несколько форм представлений, а именно:

· инфиксная (естественная, для некомпьютерных представлений) (например, (a+b)*c);

· постфиксная (польская инверсная запись - ПОЛИЗ) (например, ab+c*), операция применяется к двум ближайшим предшествующим операндам;

· префиксная (например, *+abc), операция применяется к двум ближайшим следующим операндам;

· функциональная (например, *(+ (a,b),c)).

Разработаны алгоритмы для преобразований для различных систем из одной формы в другую. Нас будут далее интересовать инфиксная и функциональная формы записи. Первая – наиболее привычная для пользователя. Вторая - наиболее соответствует понятию «структура» в языке Пролог.

Инфиксная форма присуща не только арифметическим операциям. Так, например, можно определить атомы «имеет» и «поддерживает» в качестве инфиксных операторов, а затем записывать выражения вида: «питер имеет информацию» или «пол поддерживает стол», которые соответствуют следующим структурам: «имеет(питер, информацию)» и «поддерживает(пол, стол)». Далее мы увидим, что многие конструкции языка Пролог являются инфиксными формами некоторых структур.

Инфиксные выражения рассматриваются Прологом как еще один способ записи уже известных конструкций. Так, запись а + b, Пролог понимает, как +(а, b).

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

:-ор(600, xfx, имеет).

Первый аргумент задает приоритет операции (600). Второй – «xfx» обозначает одну из разновидностей инфиксной операции. Общее правило использование приоритета состоит в том, что оператор с самым низким приоритетом расценивается как главный функтор (чем приоритет выше, тем его номер меньше). Если мы хотим, чтобы выражения, содержащие + и *, понимались в соответствии с обычными правилами, то + должен иметь более низкий приоритет, чем *.

Существуют три группы разновидностей операций, обозначаемые спецификаторами:

(1) бинарные инфиксные операции трех типов: «xfx», «xfy», «yfx»,

(2) унарные префиксные операции двух типов: «fx», «fy»,

(3) унарные постфиксные операции двух типов: «хf», «yf».

Под «f» понимается инфиксная операция. Разницу между «x» и «y» поясним на примере. Выражение «а-b-с» для разных типов определения операции «-» понимается: для «xfx» - запись некорректна, для «xfy» - «а-(b-с)», для«yfx» - «(а-b)-с». Выражение «-- а» - для «fx» - запись некорректна, для «fy» - «-(- а)».

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

3.7. Списки в языке ПРОЛОГ

Список в Прологе- это последовательность, заключенная в квадратные скобки, составленная из произвольного числа элементов, разделенных запятыми например [a, b, c, d. e], [1, 15, 2, 101. 3], [энн, теннис, том, лыжи] и т.д.

Также как для арифметических выражений данное представление является внешним представлением стандартного прологовского объекта. Если список пустой, то он записывается как атом []. Если список не пустой, то он рассматривается как структура, состоящая из двух частей:

(1) первый элемент, называемый головой списка;

(2) остальная часть списка, называемая хвостом.

Например, для списка [a, b, c, d. e] a - это голова, а хвостом является список [b, c, d. e]. В общем случае, головой может быть любой прологовский объект; хвост же должен быть списком. Голова соединяется с хвостом при помощи специального функтора, который принято обозначать точкой «.».

Таким образом, список [a, b, c, d. e] может быть представлен как структура .(a, .(b, .(c, .(d, .(e, []))))).

Списки могут иметь неограниченный уровень вложенности. Например, список [[1, 2, 3], [b, [1, 3, 5], d], c, d] может быть представлен как структура .(.(1, .(2, .(3, []))), .(.(b, .(.(1, .(3, .(5, []))), .(d, []))), .(c, .(d, [])))).

В Прологе предусмотрено еще одно представления списка, а именно вертикальная черта "|", отделяющая голову от хвоста. Можно перечислить любое количество элементов списка, затем поставить символ "|", а после этого - список остальных элементов. Так, список [а, b, с] можно представить следующими различными способами: [а, b, с], [а | [b, с]], [a, b | [c]], [a, b, c | [ ]].

Пример 3.7.1.Принадлежность к списку

Отношение принадлежности «принадлежит( X, L)» (Х - объект, а L – список) формулируется словесно как «элемент Х встречается в L».

Определение предиката:

принадлежит(X, [X | Хвост ]).

принадлежит(X, [Голова | Хвост ]):-принадлежит(X, Хвост).

Словесная интерпретация:

Если элемент является головой списка, то он принадлежит списку.

Если элемент принадлежит хвосту списка, то он принадлежит списку.

Примеры применения:

?-принадлежит(b, [а, b, с])

Yes

?-принадлежит(b, [а, [b, с]])

No

?-принадлежит([b, с], [а, [b, с]])

Yes

?-принадлежит(X, [а, b, с])

X= а,

X= b,

X= с.

Пример 3.7.2.Сцепление (конкатенация)

Отношение конкатенации «конк(L1, L2, L3)» формулируется словесно как «список L3 является конкатенацией списков L2 и L3».

Определение предиката:

конк([], L, L).

конк([X | L1], L2, [X | L3]):-конк(L1, L2, L3).

Словесная интерпретация:

Любой список является конкатенацией пустого списка с самим собой.

Если L3 является конкатенацией списков L1 и L2, то это отношение сохранится после присоединения в качестве головы у спискам L1 и L2 одного и того же элемента.

Примеры применения:

Проверка отношения

?-конк( [а, b], [c, d], [a, b, c, d])

Yes

?-конк( [а, b], [c, d], [a, b, a, c, d] )

No

Операция конкатенации

?-конк( [a, b, с], [1, 2, 3], L ).

L = [a, b, c, 1, 2, 3]

Разбиение на подсписки

?- конк( L1, L2, [а, b, с] ).

L1 = [], L2 = [а, b, c];

L1 = [а], L2 = [b, с];

L1 = [а, b], L2 = [c];

L1 = [а, b, с], L2 = [ ].

Разбиение на подсписки до и после заданного элемента

?- конк( До, [май | После ], [янв, фев, март, апр, май, июнь, июль, авг, сент, окт, ноябрь, дек]).

До = [янв, фев, март, апр], После = [июнь, июль, авг, сент, окт, ноябрь, дек].

Нахождение элементов непосредственно предшествующих и следующих за заданным

?- конк(_, [М1, май, М2 | _], [янв, февр, март, апр, май, июнь, июль, авг, сент, окт, ноябрь, дек]).

М1 = апр, М2 = июнь.

?-L1 = [a, b, z, z, c, z, z, z, d, e], конк(L2, [z, z, z | _], L1).

L1 = [a, b, z, z, c, z, z, z, d, e], L2 = [a, b, z, z, c].

Использование в программах

Принадлежность к списку

принадлежит1(X, L):-конк(_, [X | _], L).

Подсписок

подсписок(S, L):- конк(_, L2, L), конк(S, _, L2).

Примеры применения:

?- подсписок(S, [а, b, с]).

S = [];

S = [a];

S = [а, b];

S = [а, b, с];

S = [b];

S = [b, с];

S = [с];

Упражнения 3.7.1.

Напишите предикат для вычеркивания из списка L его трех первых и трех последних элементов.

Упражнения 3.7.2.

Определите отношение последний(Элемент, Список) (последний элемент списка). (а) с использованием отношения конк, (b) без использования этого отношения.

Пример 3.7.3.Добавление элемента

Определение предиката:

добавить(X, L, [X | L]).

Словесная интерпретация:

Добавление элемента к списку в качестве головы.

Примеры применения:

Проверка отношения

?-добавить(a,[b, c, d], [a, b, c, d])

Yes

Добавление элемента

?-добавить(a,[b, c, d], L)

L=[a, b, c, d]

Разбиение на голову и хвост

?-добавить(X, L, [a, b, c, d])

X= a, L=[b, c, d]

Пример 3.7.4.Удаление элемента

Определение предиката:

удалить(X, [X | Хвост], Хвост).

удалить(X, [Y | Хвост], [Y | Хвост1]):- удалить(X, Хвост, Хвост1).

Словесная интерпретация:

Если элемент является головой списка, то удаляем голову.

Удаляем элемент из хвоста списка.

Примеры применения:

Удаление элемента всеми возможными способами

?- удалить(а, [а, b, а, а], L].

L = [b, а, а];

L = [а, b, а];

L = [а, b, а].

Проверка отношения

?- удалить(а, [а, b, а, а], [а, b, а]].

Yes

Добавление элемента всеми возможными способами

?- удалить(а, L, [1, 2, 3]).

L = [а, 1, 2, 3];

L = [1, а, 2, 3];

L = [1, 2, а, 3];

L = [1, 2, 3, а]

Разделение списка на элемент и остальной список

?- удалить(X,[a,b,c], L).

X =a, L= [b,c];

X =b, L= [a,c];

X =c, L= [a,b];

Использование в программах

Принадлежность к списку

принадлежит2(X, L):- удалить( X, L, _).

Пример 3.7.5.Перестановки

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

Определение предиката:

перестановка([], []).

перестановка([X | L], Р):- перестановка(L, L1), удалить(X, Р, L1).

Словесная интерпретация:

Перестановка пустого списка есть пустой список.

Если список не пуст, то получим перестановки его хвоста, а затем вставим голову в полученные перестановки всеми возможными способами.

Примеры применения:

?- перестановка([а, b, с], Р).

Р = [а, b, с];

Р = [а, с, b];

Р = [b, а, с];

Р = [b, с, а];

Р = [с, а, b];

Р = [с, b, а]

3.8. Арифметика в языке ПРОЛОГ

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

:- op( 700, xfx, [=, is, <,<>, >, <=, >=]).

:- op( 500, yfx, [+, -] ).

:- op( 500, fx, [+, -] ).

:- op( 400, yfx, [*, /, div] ).

Пример 3.8.1.Программа вычисления наибольшего общего делителя.

Определение предиката:

нод(X,X,X).

нод(X,Y,Д):-Х<Y, Y1 is Y-X, нод(X,Y1,Д).

нод(X,Y,Д):-Y<X, нод(Y,X,Д).

Примеры применения:

?-нод(24,45,5)

No

?-нод(24,45,X)

X=3

Рассмотрим второе предложение этого примера.

нод(X,Y,Д):-Х<Y, Y1 is Y-X, нод(X,Y1,Д).

Пролог видит его в следующем представлении

нод(X,Y,Д):-<(Х,Y), is(Y1,-(Y,X)), нод(X,Y1,Д).

Из примера видно, что арифметические операции присутствуют в качестве функторов в структурах. Операции сравнения, «is» работают в Прологе как встроенные предикаты следующим образом:

· если аргументами являются арифметические выражения (структуры с арифметическими операциями в качестве функторов), то активизируется процедура их вычисления;

· если некоторые переменные в арифметическом выражении не имеют значений, то предикат заканчивает работу «неудачей» (данная цель считается не достигнутой);

· первый аргумент предиката «is» (левая часть) может быть переменной, не имеющей значения, тогда после вычисления второго аргумента (правой части) происходит сопоставление аргументов (присваивание переменной значения вычисленного выражения);

· если сопоставления заканчивается «неудачей», то предикат «is» также заканчивается «неудачей»;

· если отношение сравнения не выполняется, то соответствующий предикат заканчивается «неудачей»;

· в остальных случаях предикаты заканчивают работу «успешно».

Пример 3.8.2.Длина списка.

Определение предиката:

Вариант 1.

длина([],0).

длина([X|Y],N):- длина(Y,N1), N is N1+1.

Вариант 2 (неверный).

длина1([],0).

длина1([X|Y],N+1):- длина(Y,N).

Примеры применения:

?- длина([1,2,3], N)

N=3

?- длина1([1,2,3], N)

N=0+1+1+1

?- длина1([1,2,3], N), N1 is N

N=0+1+1+1

N1=3