Логічне програмування:Іспит
Матеріал з USIC Wiki
|
Ця стаття відноситься до групи довідкових статей для студентів ФІН. |
Формальна логіка як основа логічного програмування. Метод резолюцій.
Для будь-якої системи логічного програмування характерним є те, що для виконання програми (побудови виведення результату) використовується вмонтована система автоматичного пошуку. Механізм пошуку логічного висновку Прологу бере свій початок від методу резолюцій Робінсона.
Правило резолюції виведення логічного висновку працює наступним чином. Дві фрази можуть резольвувати між собою, коли одна з них має позитивний, а друга - негативний літерал з одним і тим самим позначенням предикату та однаковою кількістю аргументів і в разі, якщо аргументи обох літералів можуть бути уніфіковані (погоджені). Наприклад, фраза P(a,b) o Q(c,d) і фраза Q(c,d) o R(b,c) дають резольвенту P(a,b) o R(b,c). Якщо ж аргументом відношення є змінна, то вона уніфікується з константою, а резольвента буде мати дану константу на місцях попереднього розташування змінної.
Розглянемо дві фрази спеціального вигляд.
Р(а) - висловлювання без умови і oР(а) - умова без висловлювання. Наявність цих двох фраз в одній теорії є протиріччям. Якщо вони резольвуються між собою, тоді отримана резольвента називається порожньою фразою.
Якщо при резолюції двох фраз, що входять до складу теорії, отримується порожня фраза, то теорія буде непослідовною.
Бази даних та бази знань в Пролозі.
- Програма на мові Пролог це набір фактів і (можливо) правил. Якщо програма містить тільки факти, то її називають база даних. Якщо вона містить ще і правила, то часто використовують термін база знань. Функції для роботи з внутрішніми базами даних: asserta(z) – додати факт на початок бази, assertz(z) –додавання в кінець, retract – видалення факту з бази, retract_all – видалення всіх фактів з бази, consult(file) – імпорт з зовнішнього файлу фактів.(можна див. п.8)
Бектрекінг, ітерація та рекурсія в Пролозі.
Часто при вирішенні конкретних задач буває необхідно переглядати всі можливі шляхи розв’язку задачі. Якщо розглянутий шлях не дає відповіді, необхідно переглянути альтернативний. Такий підхід дістав назву бектрекінг.
Пролог реалізує бектрекінг таким чином. На початку пошуку розв’язання поставленої проблеми він ставить маркер на місце проглядання та вибирає першу підціль. Якщо її розв’язання завершиться невдачею, тоді Пролог повертається до точки, відміченої маркером і намагається знайти альтернативну підціль. При поверненні в точку бектрекінгу, він звільняє усі змінні, зв’язані після входу в дану точку.
Розглянемо програму:
likes(john, wine).
likes(lance, skiing).
likes(Z,books) :-reads(Z),is_inquisitive(Z).
likes(lance, books).
likes(lance, films).
reads(john).
is_inquisitive(join).
Задамо системі запитання у вигляді мети, яка складається з двох підцілей:
likes(X,wine), likes(X,books)
Пролог починає виведення згідно з основним принципом бектрекінгу. Підцілі повинні задовольнятися послідовно зверху вниз.
Пролог визначає яка підціль буде використовуватись для задоволення відповідного фрагменту предикату згідно з другим принципом бектрекінгу. Фрагменти предикату розглядаються в тому порядку, в якому вони розміщені в програмі - послідовно зверху вниз.
Підціль likes(X, wine) відповідає факту likes(john, wine). Тому Х зв’язується з john. Потім Пролог робить спробу задовольнити наступну підціль справа. Виклик другої підцілі розпочинає новий пошук з Х = john. Перший пункт likes(john,wine) не відповідає підцілі likes(X,books), тому що wine не є тим же, що й books. Тому Пролог намагається підібрати наступний пункт. Подальший пошук визначається третім правилом бектрекінгу. Коли підціль відповідає голові, тоді наступним повинно задовольнятися тіло даного правила. Тіло правила у свою чергу створює нові підцілі, котрі повинні бути задоволені.
І нарешті, четвертий принцип бектрекінгу такий. Мету буде задоволено, коли будуть знайдені відповідні факти для кожного рівня дерева мети.
Управняючі структури ! (cut) fail. Зелене та червоне відтинання.
Cut(!)
Предикат cut виробляє значеня “істина”, яке означає успіх і позначається “!”. Він розміщується в тілі правила як підціліь. Коли обробка досягає cut, він є завжди успішним і тому викликається наступна за ним ціль. Через те, що cut був пройдений, неможливо провести бектрекінг підцілей, які розміщені перед cut у оброблюваному пункті й тому неможливо перейти до інших пунктів, що визначають поточний предикат.
Існує два основних правила використання cut:
1. Якщо ви знаєте попередньо, що певні варіанти ніколи не дадуть поштовху в знаходженні розв’язку, то використання cut(зелений cut) відкидає перегляд альтернативних шляхів.
2. Коли логіка програми потребує використання cut для відкидання перегляду альтернативних підцілей, тоді його називають червоним відтинанням.
Іншими словами, предикат cut обмежує автоматичний перебір. Для багатьох задач виникає проблема, або ж обмеження бектрекінгу, або ж виключення його зовсім.
Розглянемо спочатку програму, процес обчислень якої містить непотрібний перебір. Нехай потрібно реалізувати функцію y=f(x), яка визначається так:
якщо х < 10, тоді у = 10 ;
якщо 10 <= х і х < 20, тоді у = 20;
якщо 20 <= х, тоді у = 30.
На Пролозі її можна виразити програмою:
f(X,10):- X < 10.
f(X,20):- X >= 10, X < 20.
f(X,30):- X >= 20.
Проаналізуємо, що буде робити програма, коли їй задати запит:
goal: f(5,Y), Y > 20.
При обчисленні першою цілі f(5,Y), Y набирає значення 10, тому друга підціль стане 10 > 20. Вона завершується невдачею. Але зрозуміло, що й весь список підцілей, який буде перевірятись завдяки бектрекінгу, також буде завершуватись невдачею.
Усі три правила обчислення функції f є взаємовиключними. Тому ми знаємо, що коли успіх настав у одному з них, немає потреби перевіряти інші, бо вони приречені на невдачу. Отже, якщо в якійсь точці програми настав успіх, для відміни непотрібного перебору, ми повинні явно вказати Пролог-системі, що не потрібно робити повернення з цієї точки. Це можна зробити за допомогою предикату cut(!). Попередня програма набере вигляду:
f(X,10):- X < 10,!.
f(X,20):- X >= 10, X < 20,!.
f(X,30):- X >= 20.
Предикат cut не дозволяє робити повернення з тих точок програми, в яких він знаходиться, - програма стала ефективнішою. Але якщо ми побудуємо запит типу
goal: f(22,Y),
тоді Пролог-система зробить три перевірки, і тільки після цього зв'яже з У значення 30. Але ж наші перевірки взаємовиключні. Тому для підвищення ефективності, ми можемо запропонувати такий варіант програми:
f(X,10):- X < 10,!.
f(X,20):- X < 20,!.
f(X,30).
У цьому випадку предикат відтинання змінює і декларативну сторону програми.
Пролог запускає бектрекінг, коли чергове співставлення завершується невдачею. Предикат fail виробляє значення “хибність”, що позначає невдачу і примушує спрацьовувати бектрекінг. У наступному прикладі показано використання даного предикату для знаходження всіх можливих розв’язків.
father(leonard, katherine).
father(carl, jason).
father(carl, marilyn).
everybody :-father(X, Y),write(X, " is ", Y, "'s father\n"),fail.
Зазначимо, що даремно використовувати підціль у тілі правила після fail. Враховуючи те, що значення fail є “хибність” (невдача), тому немає шляхів, що досягають підціль, яка знаходиться після предикату fail.
Прості та складені об’єкти Прологу.
Обєкти даних: прості обєкти(змінні, константи:атоми, числа), структури.
- Атом - последовательность букв, цифр и знака "подчеркивание", обязательно начинающаяся со строчной буквы; последовательности специальных знаков ":-", "?-", "=", ">" и других.
- Числа в Прологе бывают целыми и вещественными. Не все целые числа могут быть представлены в машине, поэтому диапазон целых чисел ограничен интервалом между некоторыми минимальным и максимальным числами, определяемыми конкретной реализацией Пролога. Обычно реализация допускает диапазон хотя бы от -16 383 до 16 383, а часто, и значительно более широкий.
- Синтаксис вещественных чисел зависит от реализации. Мы будем придерживаться простых правил, видных из следующих примеров: 3.14, -0.0035, 100.2. При обычном программировании на Прологе вещественные числа используются редко. Причина этого кроется в том, что Пролог - это язык, предназначенный в первую очередь для обработки символьной, а не числовой информации. Переменные - это цепочки, состоящие из букв, цифр и символов подчеркивания. Они начинаются с прописной буквы или с символа подчеркивания. Если переменная встречается в предложения только один раз, то нет необходимости изобретать ей имя. Можно использовать так называемую "анонимную" переменную, которая записывается в виде одного символа подчеркивания. Если анонимная переменная встречается в вопросе, то ее значение не выводится при ответе системы на этот вопрос. Лексический диапазон имени - одно предложение. Это значит, что если, например, имя Х15 встречается в двух предложениях, то оно обозначает две разные переменные. Однако внутри одного предложения каждое его появлений обозначает одну и ту же переменную. Для констант ситуация другая: один и тот же атом обозначает один и тот же объект в любом предложении, иначе говоря, - во всей программе.
Структурные объекты (или просто структуры) - это объекты, которые состоят из нескольких компонент. Эти компоненты, в свою очередь, могут быть структурами. ля того, чтобы объединить компоненты в структуру, требуется выбрать функтор. Все структурные объекты можно изображать в виде деревьев (пример см. на рис. 2.2). Корнем дерева служит функтор, ветвями, выходящими из него, - компоненты. Если некоторая компонента тоже является структурой, тогда ей соответствует поддерево в дереве, изображающем весь структурный объект.
Цикли в Пролозі.
Пролог реалізує тільки два типи повторних дій: бектрекінг і рекурсію. В програмі 6.1 показано використання бектрекінгу для реалізації циклу. На поставлений запит будуть друкуватись усі можливі розв’язки.
country(england).
country(france).
country(germany).
country(denmark).
print_countries :- country(X),
write(X),nl,fail.
print_countries.
Перша фраза говорить: "Знаходячи розв'язок предикату cоuntry(x), надрукувати країну Х і перейти на новий рядок.” Потім викликається предикат fail. В цьому випадку fail означає: якщо розв'язок поставленої цілі ще може бути знайдений, тоді повернутись і пошукати альтернативний розв'язок.
Вмонтований предикат fail завжди має хибне значення, але ми могли б форсувати бектрекінг, використавши якийсь інший, завжди хибний предикат типу 10 = 3 + 4, або country(abracadabra) .
Таким чином, будуть надруковані усі країни і процес обробки системою першої фрази завершиться. Після цього, почнеться обробка другої фрази того ж предикату print-countries. Вона нічого не робить, а тільки завершує успіхом роботу системи. Кінцеве виведення буде мати вигляд:
england
france
germany
denmark Yes
Якби не було другої фрази, виведення завершувалось - No, а все інше виведення залишилось без змін.
Хвостова рекурсія в Пролозі.
Есть вариант рекурсии, который использует практически столько же оперативной памяти, сколько итерация в императивных языках программирования. Это так называемая хвостовая или правая рекурсия. Для ее осуществления рекурсивный вызов определяемого предиката должен быть последней подцелью в теле рекурсивного правила и к моменту рекурсивного вызова не должно остаться точек возврата (непроверенных альтернатив). То есть у подцелей, расположенных левее рекурсивного вызова определяемого предиката, не должно оставаться каких-то непроверенных вариантов и у процедуры не должно быть предложений, расположенных ниже рекурсивного правила. Пример. Попробуем реализовать вычисление факториала с использованием хвостовой рекурсии. Для этого понадобится добавить два дополнительных параметра, которые будут использоваться нами для хранения промежуточных результатов. Третий параметр нужен для хранения текущего натурального числа, для которого вычисляется факториал, четвертый параметр - для факториала числа, хранящегося в третьем параметре. Запускать вычисление факториала мы будем при первом параметре равном числу, для которого нужно вычислить факториал. Третий и четвертый аргументы будут равны единице. Во второй аргумент по завершении рекурсивных вычислений должен быть помещен факториал числа, находящегося в первом параметре. На каждом шаге будем увеличивать третий аргумент на единицу, а второй аргумент умножать на новое значение третьего аргумента. Рекурсию нужно будет остановить, когда третий аргумент сравняется с первым, при этом в четвертом аргументе будет накоплен искомый факториал, который можно поместить в качестве ответа во второй аргумент. Вся процедура будет выглядеть следующим образом:
fact2(N,F,N,F):-!. /* останавливаем рекурсию, когда третий
аргумент равен первому*/
fact2(N,F,N1,F1):-
N2=N1+1, /* N2 - следующее натуральное число
после числа N1 */
F2=F1*N2, /* F2 - факториал N2 */
fact2(N,F,N2,F2).
/* рекурсивный вызов с новым натуральным
числом N2 и соответствующим ему
посчитанным факториалом F2 */
Остановить рекурсию можно, воспользовавшись отсечением в базисе рекурсии, как это было сделано выше, или добавив в начало второго предложения сравнение N1 с N.
Внутрішні бази даних Прологу. Розв’язок переборних задач за допомогою внутрішніх баз даних.
Внутрішні бази даних
Відношення є основним поняттям Прологу, яке дає можливість зручно працювати з реляційними базами даних (РБД). Внутрішні РБД (або далі просто БД, оскільки мова у статті піде лише про них) описуються в мові Пролог у розділі database та являють собою звичайні предикати, над якими можна здійснювати спеціальні операції.
Приклад 1. Визначення бази даних person, в якій містяться відомості про день народження людини. person(name, surname, date, month, year).
Над БД можна виконувати наступні стандартні операції за допомогою вмонтованих предикатів:
asserta (person(john, smith, 3, june, 1960)) – додати на початок БД person відомість про те, що Джон Сміт народився 3 червня 1960 року.
assertz ( person (john, smith, 3, june, 1960)) – додати ту ж інформацію в кінець БД.
retract ( person (john, smith, 3, june, 1960)) – знищення інформації про Джона Сміта з БД.
retractall (person (_ , _, _, _, _)) – повне знищення інформації у БД person.
Приклад. Наступна програма визначає БД, яка містить цілі числа та за допомогою предикату fill(X) заповнює її цілими числами від 0 до X.
fill(-1) :- !.
fill(X) :- asserta (d(X)), X1 = X – 1, fill(X1).
Бектрекінг грає дуже важливу роль при програмуванні на Пролозі. За його допомогою можна уникати циклічних та рекурсивних структур при програмуванні.
Приклад. Предикат друку елементів у БД d.
print_d :- d(X), write(X), nl, fail.
При запуску предиката print_d на виконання невидимий умовний маркер встановлюється на початок тіла print_d та починає рухатися вправо. Якщо чергова виконана підціль виконується, то маркер рухається направо за цю підціль; якщо результатом виконання підцілі э хиба, то Пролог намагається знайти альтернативну піпціль. Якщо всі альтернативи для даної підцілі були розглянуті, то маркер рухається вліво на одну підціль. У вище наведеному прикладі умовний маркер буде пробігати по тілу предикату print_d стільки разів, скільки елементів є у БД d (тобто скільки є альтернатив при уніфікації змінної X у предиката d(X)).
Переборні задачі.
Переборними будемо називати задачі, які можна розв’язати методом генерування всіх можливих значень відповіді та знаходженням серед них тих, що задовольняють умові задачі. Для знаходження відповіді спочатку необхідно заповнити внутрішню БД певними значеннями (які іноді знаходяться математичним шляхом), а потім викликати сам предикат розв’язку задачі. В кожному з наступних прикладів буде сказано як заповнювати БД.
Приклад. Написати предикат gentwo(integer), який генерує всі двозначні числа.
Двозначне число має вигляд , де А, В – цифри, при чому А > 0. Оскільки А та В є цифрами, то вони можуть приймати значення від 0 до 9. Занесемо у БД d(integer) ці значення за допомогою команди fill(9) перед викликом gentwo. В тілі предикату необхідно уніфікувати змінні А та В з усіма можливими їх значеннями та утворити з них двозначне число.
/* fill (9) */
gentwo (X) :- d(A), A>0, d(B), X = 10*A + B.
Приклад. Знайти всі двозначні числа, які дорівнюють сумі квадрату його десятків та кубу одиниць.
З умови задачі випливає, що для двозначного числа повинна виконуватися рівність: 10*А + В = А2 + В3.
/* fill(9) */
task5 (X) :- d(A), A>0, d(B), X = 10*A + B, X = A*A+B*B*B.
Графи в Пролозі.
Граф определяется как множество вершин вместе с множеством ребер, причем каждое ребро задается парой вершин. Если ребра направлены, то их также называют дугами. Дуги задаются упорядоченными парами. Такие графы называются направленными. Ребрам можно приписывать стоимости, имена или метки произвольного вида, в зависимости от конкретного приложения. На рис. 6.18 показаны примеры графов.
В Прологе графы можно представлять различными способами. Один из них - каждое ребро записывать в виде отдельного предложения. Другой способ - весь граф представлять как один объект. В этом случае графу соответствует пара множеств - множество вершин и множество ребер. Каждое множество можно задавать при помощи списка, каждое ребро - парой вершин. Для объединения двух множеств в пару будем применять функтор граф, а для записи ребра - функтор р. G1 = граф( [a, b, c, d], [р( а, b), р( b, d), р( b, с), p( c, d)] ).
Если каждая вершина графа соединена ребром еще по крайней мере с одной вершиной, то в представлении графа можно опустить множество вершин, поскольку оно неявным образом содержится в списке ребер. Еще один способ представления графа - связать с каждой вершиной список смежных с ней вершин. В этом случае граф превращается в список пар, каждая из которых состоит из вершины- плюс ее список смежности.
G1 = [ a->[b1, b->[a, c, d], c->[b, d], d->[b, c] ].
Експертні системи і Пролог.
К первому этапу развития экспертных систем наибольшее распространение получили экспертные системы на правилах, которые способны лишь повторить логический вывод эксперта - это экспертные системы первого поколения. Экспертные системы относящиеся ко второму поколению называют партнерскими или усилителями интеллектуальных способностей человека. Их общими отличительными чертами является: способность развиваться и само обучаться, т.е. эволюционировать.Общая структура экспертных систем Чтобы проводить экспертизу компьютерная программа должна быть способна:
1. Решать задачи посредством логического вывода.
2. Получать в процессе решения достаточно надежные результаты.
3. Выводить заключения в период сеанса работы с пользователями, с необходимыми пояснениями, каким образом были получены эти заключения
4. По мере возможности использовать дополнительную информацию поступающую во время консультации. В общем виде экспертную систему можно представить в виде совокупности 3-х основных блоков:
- База знаний (БЗ)
- Механизм вывода (МВ)
- Система пользовательского интерфейса (СПИ).
База знаний - содержит знания относящиеся к конкретной прикладной области: факты, правила, методы эвристики, различные идеи относящиеся к способам решения задач к данной предметной области. Механизм вывода - содержит принципы и правила работы экспертной системы. Он выбирает способ применения правил, выполняет правила и определяет, когда найдено приемлемое решение и передает результаты в систему пользовательского интерфейса. Система пользовательского интерфейса - это часть экспертной системы, которая непосредственно взаимодействует с пользователем и обеспечивает бесперебойный обмен информацией между пользователем и системой. Кроме того СПИ позволяет пользователю наблюдать за процессом решения задач.
Представление знаний. Оболочка экспертной системы в принципе не зависит от ее приложения. Разумным способом разработки экспертных систем для нескольких приложений сводятся к созданию универсальной оболочки, после чего достаточно подключить конкретную базу знаний. При этом база знаний должна удовлетворять одному и тому же формализму, которой оболочка понимает. В качестве кандидата на использование в экспертной системе можно рассматривать, в принципе, любой непротиворечивый формализм, в рамках которого можно описывать знания о некоторой проблемной области. Однако самым популярным формальным языком представления знаний является язык правил типа "если-то" (или кратко: "если-то"-правил), называемых также продукциями. "Если-то"-правила обычно оказываются весьма естественным выразительным средством представления знаний. Кроме того, они обладают следующими привлекательными свойствами: Модульность: каждое правило описывает небольшой, относительно независимый фрагмент знаний; Возможность инкрементного наращивания: добавление новых правил в базу знаний происходит относительно независимо от других правил; Удобство модификации (как следствие модульности): старые правила можно изменять и заменять на новые относительно независимо от других правил; Применение правил способствует прозрачности системы.
Безкоштовні реалізації Прологу
- B-Prolog [1] (BSD-подібна ліцензія)
- GNU Prolog [2] (GNU GPL)
- Open Prolog для Маків [3] ("Open Prolog is not copy protected.")
- POPLog - IDE для Prolog, Lisp, ML [4] (XFree86-style Open Source licence)
- Strawberry Prolog із потужною підтримкою Win32 COM [5] (Пропрієтарна ліцензія, доступна безкоштовна версія)
- SWI-Prolog з графічною бібліотекою [6] (GNU Lesser GPL)
- Tricia для Маків [7] (public domain)
- Visual Prolog [8] (Пропрієтарний софт, є безкоштовна версія)
- XSB - логічно-орієнтована СУБД з підтримкою Прологу [9] (GNU GPL)
На керованих платформах:
