1.8 ПЗ в ИС

4)Операции языка Пролог; обработка списков - принадлежность элемента списку, выбор общих элементов, выбор n-го элемента, соединение списков.

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

2.3.5. Операции

1. Арифметические операции: “+”, “-”, “”, “/”. Пример: расстояние1=расстояние2+расстояние3.

Порядок аргументов в выражениях значения не имеет.

2. Функции: X mod Y – остаток от деления X на Y;

X div Y - целая часть от деления X на Y;

abs(X) – абсолютная часть числа X;

exp(X) – e в степени X;

sgrt(X) – квадратный корень из X;

sin(X), cos(X), tg(X), arctg(X).

Приоритеты: 1) “+”, “-“; 2) “”, “/”; 3) mod, div; 4) одноместные “+”, “-“.

3. Логические операции:

• умножение – “,”,

• сложение – “;”,

• отрицание – “not” – предикат.

4. Операции отношения: “”, “”, “”, “”, “”, “” или “”.

Используем некоторые из перечисленных операций, например для вычисления факториала Y от X : предикат fact(X,Y). Так как Пролог обрабатывает все возможные варианты, надо указать условие останова поиска вариантов решения, например X1. Тогда программа вычисления факториала будет иметь следующий вид:

predicates

fact(real,real)

clauses

1⁰ fact(1,1).

2⁰ fact(X, Y):-

X1,

Z=X-1,

fact(Z,X1),

Y=XX1.

Запрос оформим как fact(5,X). Во время первого цикла решения задачи Пролог анализирует стек вопросов, состояние которого есть сам запрос. Очевидно, что исходное предложение-запрос после сравнения его с фактом 1⁰ и правилом 2⁰ программы может быть унифицировано только с правилом, так как в факте 1⁰ первый аргумент “1” не соответствует первому аргументу “5” запроса. После унификации имеем для программного правила X=5, Y=X. Далее стек вопросов должен быть обновлен условной частью правила 2⁰: X1,Z=X--1,fact(Z,X1),Y=XX1. Анализ составляющих стека с учетом предыдущих замен переменных дает: 51,Z=5-1=4, fact(4,X1),X=5X1 или, после отбрасывания из стека конкретных фактов, fact(4,X1),X=5X1.

В

18

о втором цикле решения задачи первая цель из стека вновь унифицируется только с правилом программы, что приводит к замене в нем X на 4 и Y на X1 и т.д. В дальнейшем состояние стека обновляется только новыми значениями своих аргументов: fact(3,X1.1),X1=4X1.1, где X1.1- новое значение аргумента X1 в fact(Z,X1); fact(2,X1.2),X1.1=3X1.2; fact(1,X1.3),X1.2=2X1.3. Новая первая цель fact(1,X1.3) унифицируется уже с фактом программы, что дает X1.3=1. После отбрасывания полученного конкретного факта fact(1,1) стека, являющегося решением его первой цели fact(1,X1.3), в нем остается: X1.2=2X1.3. Уравнение дает X1.2=21=2. Освобождение от указанного факта дает пустой стек. Последовательная подстановка X1.2, X1.1, X1 в соответствующие предыдущие состояния стека приводит к варианту ответа X=Y=120. Попытка найти другие решения задачи при унификации fact(1,X1.3) и правила программы приводит к замене в нем X=1, Y= X1.3 и к неудовлетворению неравенства X1 условной части правила. Работа программы закончена.

2.3.6. Обработка списков и строк символов

Список в Прологе представляется множеством элементов, разделенных запятой и ограниченных квадратными скобками. Пример:

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

Для разделения списка на части используется предикат "". Он делит список на "голову" и "хвост" (подсписок, являющийся исходным списком без элементов головы). Так, если 1) X=[a,b,c,d] и X=[YZ], то, например, Y=a (здесь в качестве головы берется только первый элемент исходного списка), Z=[b,c,d]; 2) X=[a] и X=[YZ], то Y=a, Z=[ ] - пустой подсписок.

Принадлежность элемента списку. Принадлежность элемента X списку Y записывается в виде предиката принадлежит(X,Y). Для определения истинности этого предиката вначале проверяется идентичность X и первого элемента списка Y. Если они совпадают, то можно записать: принадлежит (X,[X_ ]), где "_" - анонимная переменная, соответствующая остальной части списка Y за вычетом его первого элемента, равного X. Если идентичности X и первого элемента списка Y нет, просматривается хвост “_” списка Y на предмет наличия в нем X, что оформляется как принадлежит [X,_Z], где “_” – уже первый элемент списка Y, а Z – остальная его часть-хвост. Поскольку анализ хвоста проводится вначале тоже путем проверки идентичности X и первого элемента подсписка Z, то можно записать правило: принадлежит [X,_Z] :- принадлежит [X,Z]. Ясно, что программа приходит к решению первоначальной задачи: принадлежит(X,[X_ ]), где “_” – соответствует списку Z за вычетом его первого элемента. Программа работы оказывается рекурсивной:

1⁰ принадлежит(X,[X_ ]).

2⁰ принадлежит [X,_Z] :-

принадлежит [X,Z].

Пример. Имеется запрос: принадлежит(седло,[руль,рама,колесо, седло]). Процедура поиска решения имеет следующий порядок.

Первый цикл. Унификация начального состояния стека вопросов (запроса) и факта 1⁰ невозможна, так как требуется замена X=седло (первый аргумент в 1⁰) и X =руль (голова списка [X_ ]=[руль, рама,колесо, седло]). После унификации содержимого стека и правила 2⁰ имеем: X=седло, [ _Z]=[руль,рама,колесо,седло], т.е. “_”=[руль], Z=[рама,колесо, седло]. Содержимое стека обновляется: принадлежит(седло, [рама,колесо,седло]).

В

19

торой цикл. Унификация последнего содержимого стека и факта 1⁰ невозможна, так как седлорама. Унификация с предложением 2⁰ дает X=седло, Z=[колесо,седло]. Новое содержимое стека: принадлежит(седло, [колесо,седло]).

Третий цикл. Унификация литерала принадлежит(седло, [колесо,седло]) с фактом 1⁰ невозможна, так как седлоколесо. Унификация с правилом 2⁰ дает: X=седло, Z=[седло]. Содержимое стека: принадлежит(седло,[седло]).

Четвертый цикл. Унификация последнего литерала с фактом 1⁰ дает X=седло, “_”=[ ] и седло=седло. Вариант решения найден. Унификация с правилом 2⁰ невозможна, так как в [ ] нет элемента седло. Таким образом, других решений нет.

Выбор общих элементов в двух списках. Выбор общих элементов из двух списков X и Y сводится к поиску всех элементов Z, каждый из которых принадлежит как X , так и Y:

общий(X,Y,Z):-

принадлежит(Z,X),

принадлежит(Z,Y).

Выбор n-го элемента списка. Выбор n-го элемента E из какого-либо списка возможен последовательным вычитанием n-1 первых элементов из этого списка с одновременным уменьшением исходного числа N=n в счетчике С. Решение будет найдено, если элемент оставшегося частичного списка L будет первым :

1⁰ n(1,E,[E _ ]).

2⁰ n(N,E,[ _L]):-

С=N-1,

n (С, E,L).

Пример. Имеем запрос: n(3,E,[a,b,c,d]), где E – неизвестный аргумент. Порядок поиска третьего элемента E в списке [a,b,c,d]) следующий.

Первый цикл. Исходное состояние стека вопросов: n(3,E,[a,b,c,d]). Унификация его с фактом 1⁰ программы невозможна, так как 31. Унификация с правилом 2⁰ дает N=3, L=[b,c,d]. Новое состояние стека вопросов: n(2,E,[b,c,d]).

Второй цикл. Унификация литерала n(2,E,[b,c,d]) с фактом программы невозможна, так как 21. Унификация с правилом 2⁰ дает N=2, L=[c,d]. Новое состояние стека: n(1,E,[c,d]).

Т

20

ретий цикл. Унификация литерала n(1,E,[c,d]) с фактом 1⁰ дает E=c. Следовательно, последнее состояние стека становится равным n(1,c,[c,d]). Стек пустеет. Вариант решения E=c найден. Дополнительная унификация ближайшего состояния стека, содержащего нерешенные цели (n(1,E,[c,d])) уже с правилом 2⁰ ведет к последовательному сокращению L до пустого списка и, соответственно, к окончанию работы программы. Таким образом, других решений нет.

Соединение двух списков. Соединение двух списков X и Y может быть представлено как операция, обратная разделению списков. Функция присоединения называется append. Программа, реализующая эту функцию, имеет следующий вид:

1⁰ append([ ],L,L).

2⁰ append([XL1],L2,[XL3]):-

append(L1,L2,L3).

Пример. Введем запрос: append([a,b.c],[d,e,f],L), где L – неизвестный искомый список. В первом цикле решения задачи, так как [a,b.c][ ], унификация запроса (исходное состояние стека вопросов) возможна только с правилом 2⁰: [XL1]=[a,b.c] (т.е. X=a, L1=[b,c]), L2=[d,e,f], [XL3]=L. Новое состояние стека вопросов: append=([b,c],[d,e,f],L3).

Во втором цикле унификация последнего предложения возможна также только с правилом 2⁰. Вводя новые обозначения для переменных, имеем: X=X.1=b, L1=L1.1=[c], L2=L2.1=[d,e,f], [X1L3.1]=L3. Новое состояние стека: append=([c],[d,e,f],L3.1).

В третьем цикле аналогично изложенному получим X.2=c, L1.2=[ ], L2.2=[d,e,f], [X2L3.2]=L3.1. Состояние стека: append=([ ],[d,e,f],L3.2).

В четвертом цикле последний литерал унифицируется с фактом 1⁰ программы: L=[d,e,f] (второй аргумент) и L=L3.2 (третий аргумент). Следовательно, L3.2=[d,e,f] и состояние стека становится равным append=([ ],[d,e,f],[d,e,f]) – конкретный факт 1⁰. Освобождаем стек и двигаемся по цепочке целей назад: L3.1=[X2L3.2]=[c,d,e,f], L3=[X1L3.1]=[b,c,d,e,f], L=[XL3]=[a,b,c,d,e,f]. Исходное состояние стека становится конкретным фактом 1⁰. Вариант ответа найден. Дополнительная унификация предпоследнего стекового литерала append=([ ],[d,e,f],L3.2) уже с правилом 2⁰ невозможна, так как в данном литерале первый аргумент “[ ]” нельзя представить сочетанием головы и хвоста.

Данная программа позволяет решить обратную задачу: определить при известном списке одну из его частей: append(L,[d,e,f],[a,b,c,d,e,f]), где L – неизвестный присоединенный список. Последовательность поиска ответа такова.

Первый цикл. Унификация литерала append(L,[d,e,f],[a,b,c,d,e,f]) с фактом 1⁰ - append([ ],L,L) - невозможна, так как [d,e,f][a,b,c,d,e,f]. Унификация с правилом 2⁰ дает [XL1]=L, L2=[d,e,f], [XL3]=[a,b,c,d,e,f], X=a, L3=[b,c,d,e,f]. Новое состояние стека: append=(L1,[d,e,f],[b,c,d,e,f]).

Второй цикл. Как и в первом цикле, с учетом переименования имеем: [X.1L1.1]=L1, L2.1=[d,e,f], [X.1L3.1]=[b,c,d,e,f], X.1=b, L3.1=[c,d,e,f]. Состояние стека: append=(L1.1,[d,e,f],[c,d,e,f]).

Третий цикл. Аналогично: [X.2L1.2]=L1.1, L2.2=[d,e,f], [X.2L3.2]=[c,d,e,f], X.2=c, L3.2=[d,e,f]. Состояние стека: append(L1.2,[d,e,f],[d,e,f]).

Четвертый цикл. Последний литерал унифицируется с фактом 1⁰: [ ]= =L1.2. После унификации последнее состояние стека становится конкретным. Двигаемся назад по цепочке целей: L1.1=[ X.2L1.2]=[c], L1=[X.1L1.1]=[b,c], L=[XL1]=[a,b,c]. Один вариант ответа найден. Дополнительная унификация литерала append(L1.2,[d,e,f],[d,e,f]) с правилом 2⁰ невозможна, так как приведет к последовательному сокращению третьего списка в этом литерале и, в конце концов, к остановке работы интерпретатора.

Р

21

ассматриваемая база знаний дает возможность осуществить разложение списка на подсписки: append(L1,L2,[a,b,c,d,e,f]). Процедура поиска решений следующая.

Первый цикл. Унификация литерала append(L1,L2,[a,b,c,d,e,f]) с фактом 1⁰ дает: [ ]=L1, L=L2, L=[a,b,c,d,e,f], т.е. L2=[a,b,c,d,e,f]. Один вариант ответа найден: L1=[ ], L2=[a,b,c,d,e,f].

Второй цикл. Возврат к стеку append(L1,L2,[a,b,c,d,e,f]). Унификация этого литерала уже с правилом 2⁰ дает: [XL1.1]=L1, L2.1=L2, [XL3]=[a,b,c,d,e,f], X=[a], L3=[b,c,d,e,f]. Состояние стека вопросов: append(L1.1,L2.1,[b,c,d,e,f]).

Третий цикл. Унификация литерала append(L1.1,L2.1,[b,c,d,e,f]) с фактом 1⁰ дает [ ]=L1.1, L=L2.1, L=[b,c,d,e,f], т.е. L2.1=[b,c,d,e,f]. Возврат по цепочке целей: L2.1=L2=[b,c,d,e,f], L1=[XL1.1]=[a]. Найден второй вариант ответа: L1=[a], L2=[b,c,d,e,f].

Четвертый цикл. Возврат к стеку append(L1,L2,[a,b,c,d,e,f]). Поскольку все факты и правила просмотрены, увеличиваем длину головы до двух элементов. Унификация литерала append(L1,L2,[a,b,c,d,e,f]) с фактом 1⁰ не дает новых решений. Унификация с правилом дает следующее: [XL1.1]=L1, L2.1=L2, [XL3]=[a,b,c,d,e,f]), т.е. X=[a,b], L3=[c,d,e,f]. Новое состояние стека: append(L1.1,L2.1,[c,d,e,f]).

Пятый цикл. Унификация литерала append(L1.1,L2.1,[c,d,e,f]) с фактом 1⁰ дает: [ ]=L1.1, L=L2.1, L=[c,d,e,f], т.е. L2.1=[c,d,e,f]. Тогда в предыдущем состоянии стека L1=[XL1.1]=[a,b], L2=L2.1=[c,d,e,f]. Найден второй вариант ответа и т. д. Последовательно увеличивая длину головы списка, находим все варианты ответов:

L1 L2

[ ] [a,b,c,d]

[a] [b,c,d]

[a,b] [c,d]

[a,b,c] [d]

[a,b,c,d] [ ].

5)Обработка списков языком Пролог - выбор наименьшего и наибольшего элементов из списка, перевод одного списка в другой, удаление элемента, сортировка списка. Иерархическая модель.

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

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

1⁰ меньший([X],X).

2⁰ меньший([X,YZ],R):-

X<=Y,

меньший([XZ],R);

X>Y,

22

меньший([YZ],R).

Рассмотрим запрос: меньший([b,c,a,e],L), где L – наименьший элемент в списке [b,c,a,e]. Процедура поиска элемента:

Первый этап. Унификация с 1⁰ невозможна, так как [b,c,a,e] – список, а X – элемент. Унификация с 2⁰ допустима при [X,YZ]=[b,c,a,e], R=L, т. е. X=b, Y=c, Z=[a,e], R=L. Новое состояние стека: b<=c,меньший([b[a,e]],L) (слагаемое X>Y,меньший([YZ],R) правила 2⁰ не учитывается вследствие ложности неравенства X>Y). Первое неравенство не требует доказательства, поэтому в стеке остается: меньший([b[a,e]],L).

Второй этап. Унификация литерала меньший([b[a,e]],L) с 1⁰ невозможна. Унификация с 2⁰ дает: [X.1,Y.1Z.1]=[b[a,e]], R=L.1, т.е. X.1=b, Y.1=a, Z.1=[e], R=L.1. Новое состояние стека: b>a, меньший([a[e]],L.1). После удаления факта b>a в стеке остается: меньший([a[e]],L.1).

Третий этап. Унификация последнего предложения с литералом 1⁰ невозможна. Унификация с 2⁰ дает: [X.2,Y.2Z.2]=[a[e]], R=L.2, т.е. X.2=a, Y.2=e, Z.2=[ ], R=L.2. Состояние стека, так как a<e, равно: меньший([a[ ]],L.2).

Четвертый этап. Унификация литерала меньший([a[ ]],L.2) с фактом 1⁰ возможна при L.2=a. Возврат назад по цепочке целей к исходному состоянию стека дает ответ: L=R=a. Других решений нет.

Выбор наибольшего элемента. Аналогичен предыдущему поиску при замене знаков неравенств “”, “” соответственно на “” и “”.

Перевод одного списка в другой. Формально простой метод перевода заключается в поиске для каждого слова исходного текста соответствующего ему слова из словаря. Рассмотрим пример базы знаний:

1⁰ перевести([ ],[ ]).

2⁰ перевести([С_АФ_А],[С_РФ_Р]):-

словарь(С_А,С_Р),

перевести(Ф_А,Ф_Р).

4⁰ словарь(“I”,”я”).

5⁰ словарь(“study”,”изучаю”).

6⁰ словарь(“language”,”язык”).

7⁰ словарь(“PROLOG”,”Пролог”).

8⁰ словарь(“in”,”в”).

9⁰ словарь(“the university”,”университете”).

Здесь записано правило перевода 2⁰: выбрать первое слово С_А английской фразы Ф_А, найти ему соответствующее русское слово С_Р в словаре и поставить в начало русского перевода Ф_Р. Введем запрос: перевести([“I”, ”study”, ”language”, ”PROLOG”, ”in”, ”the university”], P). .Процедура перевода:

Первый цикл. Унификация запроса с фактом 1⁰ невозможна. Унификация с правилом 2⁰ дает: [С_АФ_А]=[“I”,”study”, ”language”,”PROLOG”,”in”,”the university”], [С_РФ_Р]=P, т.е. С_А=“I”, Ф_А=[”study”,”language”,”PROLOG”,”in”,”the university”]. Новое состояние стека вопросов: словарь=(“I”,Р), перевести([”study”,”language”, ”PROLOG”,”in”,”the university”],Ф_Р).

23

Второй цикл. Унификация литерала словарь=(“I”,Р) с фактом 4⁰ дает: ”я”=Р. В стеке остается: перевести([”study”,”language”,”PROLOG”,”in”,”the university”],Ф_Р).

Третий цикл. Унификация стекового литерала возможна только с правилом 2⁰: [С_А.1Ф_А.1] = [”study”, ”language”, ”PROLOG”, ”in”, ”the university”], [С_Р.1Ф_Р.1] = Ф_Р, т.е. С_А.1 = ”study”, Ф_А.1 = [”language”, ”PROLOG”, ”in” , ”the university”] и т.д. до исчерпания всех слов. При этом последнее состояние стека унифицируется с фактом 1⁰. Возврат по цепочке целей назад увеличивает длину искомой переменной P = =[С_РФ_Р], Ф_Р=[С_Р.1Ф_Р.1],… до следующей предельной величины: P= = [“я”, ”изучаю”, ”язык”, ”Пролог”, ”в”, “университете”]. Других решений нет.

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

1. если удаляемый элемент E совпадает с головой списка [EY], то надо оставить его хвост Y:

удалить(E,[EY],Y);

2. если удаляемый элемент E не совпадает с головой списка, то надо найти его в хвосте и удалить:

удалить(E,[XY],[XZ]):-

удалить(E,Y,Z).

Указанные факт и правило образуют программу удаления заданного элемента E из списка [XY].

Сортировка элементов списка. Используется метод последовательного сравнения смежных элементов: в списке находят наименьший элемент, если сортировка идет по возрастанию (или наибольший, если по убыванию), добавляют его в голову другого списка и удаляют из первого списка. Далее этот процесс продолжают с оставшимся подсписком до исчезновения в нем элементов:

1⁰ сортировать([ ],[ ]).

2⁰ сортировать(L,[MR]):-

меньший(L,M),

удалить(M,L,Q),

сортировать(Q,R),

!.

Пример запроса: сортировать([e,t,r,a,b],S), где S – искомый список.

Процедура сортировки повторяет вышеприведенные этапы.

Первый цикл. Унификация с правилом 2⁰ возможна при L=[e,t,r,a,b], S=[MR]. Новое состояние стека вопросов: меньший([e,t,r,a,b],M), удалить(M,[e,t,r,a,b],Q),сортировать(Q,R),!.

В

24

торой цикл. Унификация первого литерала меньший([e,t,r,a,b],M) с предложениями 1⁰, 2⁰ невозможна. Поэтому воспользуемся из библиотеки программ готовой процедурой поиска наименьшего элемента, рассмотренной ранее, что дает M=a. Цель удалить(M,[e,t,r,a,b],Q) имеет также свою известную программу решения: Q=[e,t,r,b]. Новое состояние стека: сортировать([e,t,r,b],R),!.

Третий цикл. Унификация предложения сортировать([e,t,r,b],R) возможна с правилом 2⁰: L.1=[e,t,r,b], [M.1R.1]=R и т. д. Последовательное выполнение приведенных шагов приведет к исчерпанию элементов исходного списка и к унификации с фактом 1⁰ очередного стекового литерала сортировать(Q.j,R.i) при Q.j=[ ], R.i=[ ]. Возврат по цепочке целей к S=[MR], R=[M.1R.1],… дает вариант ответа: S=[a,b,e,r,t]. Поскольку предикат “!” не позволяет исследовать другие варианты, последнее решение является окончательным и считается ответом на поставленный вопрос.