Лабораторна робота 1
Тема: Теорія предикатів та мова логічного програмування TURBO-PROLOG.
Мета роботи: Зрозуміти концепцію предикату
та принципи логічного програмування.
Теоретичні відомості
Програма на мові логічного програмування не задає алгоритм обробки даних. Вона декларує логічні зв'язки між деякими подіями, властивостями, об'єктами, діями. Зв'язок представляється як предикат, який містить вказані логічні поняття: події властивості, об'єкти, дії у вигляді своїх змінних. Наприклад, X=Y+Z можна розглядати як предикат, в якому права частина відома, а ліва - не відома. Тоді, для істинності предиката необхідно прирівняти праву і ліву частини рівняння. Якщо відомі обидві частини рівняння, то цей предикат можна трактувати як логічну умову, яка може бути істиною. Сам предикат також має чітке логічне визначення в абстрактних поняттях тих змінних, з якими він оперує. В даному прикладі, цей предикат можна назвати “додавання двох змінних”.
Логічні умови, які накладаються на змінні в тілі предикату визначають його істинність. Програма є просто множиною предикатів, які посилаються один на одний і всі вони закінчуються крапкою. Кожен з них в залежності від того, які змінні визначені, а які - ні, можна трактувати так:
Якщо відомі X, Y, Z,... то чи виникне подія f(X,Y,Z,...)? (або чи збережеться властивість f(X,Y,Z,...)?, або чи існуватиме об'єкт f(X,Y,Z,...)? і т.д.)
Якщо відомо, що подія f(X,Y,Z,...) відбулася (або є властивість f(X,Y,Z,...), або якщо об'єкт f(X,Y,Z,...) існує), то якими повинні бути X, Y, Z,... ? Звичайно, розв'язок системи предикатних рівнянь може існувати, і вбудований механізм інтерпретації логічних програм його знайде, але під час програмування краще про нього не думати.
Фактично, програма складається з множини розділів, а кожний розділ складається з множини визначень, характерних для даного розділу. Якщо програма немає інших розділів крім “goal”, то її виконання не відрізняється від звичайного лінійного алгоритму, наприклад:
goal X=5, Y=6, Z=X+Y, write(“ Z=“,Z).
Отже, в “goal” задається мета програми - обчислити деякий предикат. В розділі “clauses” задається логічна модель задачі, яка складається з фактів і правил. Кожний факт має відповідну логічну інтерпретацію в поняттях, на яких базується модель задачі. Правило фактично задає опис алгоритму вирішення задачі у вигляді переліку інших простіших задач, які необхідно розв'язати.
При складанні програми на декларативній мові, такій як PROLOG, існує два шляхи. Перший - це взагалі забороняється конкретне алгоритмічне мислення, яке заважає помітити логічні зв'язки і сформулювати визначення у вигляді правил. Коректність програми повинна повністю забезпечуватись правильними визначеннями логічних понять та предикатів, з якими працює програма. Наведемо приклад програми для знаходження кращого ходу для гри в “сірники” (подивіться текст програми).
Умова гри: на столі знаходиться N сірників. Кожен з гравців може брати 1, 2 чи 4 сірника з загальної купи. Програє той, хто бере останнім, і на столі більше не буде сірників. Для складання логічних рівнянь необхідно сформулювати такі поняття у вигляді предикатів, як можливий хід “can_take_matches( кількість сірників, що можна брати)” і умова виграшу “win( скільки необхідно взяти щоб виграти, загальна кількість сірників)”.
Як можна бачити з програми, розділ domains містить визначення типів даних; розділ “predicates” - опис форми предикатів (які виражають поняття, події, зв'язки, тощо) та типів даних, які в предикатах зустрічаються. Розділ clauses являє собою тіло програми, тому що в ньому визначаються самі логічні умови і зв’язки, які складають логічну модель задачі. Як можна бачити з цього розділу, кожний логічний вираз закінчується крапкою. Можливі два типи виразів:
1. P(X1,X2,...,Xn). - “факти”
2. P(X1,X2,...,Xn):-Q1,Q2,...,Qm. - “правила”
При виконанні предикатів цих типів кожний раз утворюється покоління змінних, яке зникає після того, як програма зустріла крапку кінця предикату. Отже, змінні в предикатах розрізняються лише на протязі виконання даного предикату.
Перший тип предикатів називається фактом. Факт задає жорсткі зв'язки між значеннями своїх змінних. Однойменні факти групуються один біля одного і розглядаються як альтернативи (з умовою “або”): якщо є два факту з одним іменем та різними значеннями змінних, то комбінації значень при уточненні змінних можуть братись повністю з одного, або повністю з другого факту. Наприклад, в поданій нижче програмі факти “can_take_matches” вказують на можливість взяти 1, 2 або 4 сірників.
Вирази другого типу, які містять підстрочу “:-” називаються правилами. Позначення “:-” між головою і тілом правила використовується як зв'язка “якщо”, “тоді, коли”, “необхідно” і т.д. Зміст правила виражається в наступному. Для того, щоб предикат P був істинним, необхідно, щоби були істинними всі предикати, які перелічені в правій частині правила. В нашому прикладі - це правило win(X,N), яке визначає умову виграшу. Прочитати це правило можна так: для того, щоб виграти в ситуації з N сірниками, необхідно взяти X сірників, після чого на столі залишиться Z=N-X сірників, яке більше нуля і при даному Z виграш неможливий, що виражено вбудованою функцією not( ). Знак підкреслення в предикаті win(_,Z) означає довільне значення пропущеної змінної, тобто: 1, 2 або 4.
Як не дивно, формулювання понять, які використовуються в алгоритмічних мовах, найбільш важке для декларативних мов програмування. Розглянемо предикат утворення циклу: cycle( змінна циклу, початкове значення, кінцеве значення), який наведений у програмі. Він складається з двох альтернативних правил: присвоїти значення змінній циклу або спробувати перейти до нового значення. Шаблон cycle(N,Y,N) означає, що якщо 1-й параметр не відомий, а 2-й і 3-й відомі, то першому параметру буде присвоєно значення третього параметра, оскільки вони позначені одною змінною N.
Розділ goal вказує кінцеву мету - знайти всі розв’язки задачі від 1 до 12 сірників.
domains
m = integer /* Введено новий тип m - сірники (не число, а тип !) */
/* інші можливі типи: real, string, symbol, char або визначається користувачем */
predicates
can_take_matches(m). /* об'являються назви предикатів і */
win(m,m). /* типи змінних, які в них входять */
cycle(m,m,m). /* can_take_matches - “можна взяти” win - “можна виграти”,
cycle - “цикл” як поняття алгоритмічної мови */
clauses
cycle(N,Begin_value,N):- N>=Begin_value. /* змінна циклу та її границі */
cycle(N,X,Y):- Y>X, N2=Y-1, cycle(N,X,N2). /* умова продовження циклу: якщо кінцеве значення більше початкового, то створюється нова змінна N2 яка активізує нову ітерацію альтернатив - присвоїти конкретне значення змінній циклу чи продовжувати цикл */
can_take_matches(1). /* об'являються факти, які вірні */
can_take_matches(2). /* при даних значеннях змінних - */
can_take_matches(4). /* задаються альтернативи виконання */
win(X,N):- can_take_matches(X), /* умова виграшу: X - дозволені значення */
Z=N-X, /* N - кількість на даний момент */
Z>0, /* Z - кількість, що залишилась після ходу */
not(win(_,Z)). /* логічне заперечення виграшу протилежної сторони */
/* Знак “_” означає будь-який хід. Предикат вигляду: win...:-...not(win...) задає розв'язок класичної задачі при антагоністичній грі, коли йде боротьба за ресурси по правилах, які однакові для кожної з сторін. Предикат not(win...) задає обмеження на хід, при якому суперник не отримує виграшу, який гарантується при правильній грі. */
goal /* мета програми формулюється як звичайне правило: */
cycle(N,1,12), /* для всіх значень N від 1 до 12 виконати наступне: */
win(X,N),nl, /* знайти розв'язок задачі для N сірників */
write(“ Якщо на столі “,N,” сірників, то для виграшу необхідно взяти “),
write(X,” сірника. “), fail. /* знайти всі можливі рішення */
В цій програмі предикат win(X,N) означає знаходження такого значення X, яке дає гарантований виграш при N сірниках. В процесі розв’язку N=12 лише на початку. В процесі пошуку рішення послідовно будуть виконуватись предикати в правій частині правила win(X,N). Алгоритм знаходження рішення дуже простий. Якщо предикат can_take_matches(X) може бути істинним при деякому X=1, то змінній X присвоюється значення 1 і виконання переходить до наступного предикату. Якщо при даному X=1 можна виконати і наступний предикат, то програма йде далі - робить крок вперед. Якщо на даному кроці рішення не існує, то програма робить крок назад (back tracking) і намагається знайти інше рішення (альтернативу) для попереднього предикату, тобто X=2 для can_take_matches(X). При новому значенні змінних програма робить крок вперед. Якщо всі предикати правила win при деяких значеннях змінних вірні, то задача win(X,12) вирішена при X=2. Пам’ятайте, що всі змінні зберігають свої значення лише на протязі виконання одного правила.
Ключове слово fail завжди хибне і викликає back tracking. Воно дає можливість не зупинятись на знайденому рішенні, а перебрати всі можливі варіанти. В процесі вирішення задачі виконання програми пройде через предикат “win” рівно стільки разів, скільки існує рішень. Предикат “write” вірний завжди і немає альтернативних рішень, тому його можна не враховувати.
Перейдемо до індивідуального завдання. Зрозуміло, що так як елемент “І-НЕ” має один вихід і як мінімум два входи, то відповідний предикат буде оперувати мінімум трьома змінними. Наприклад, можна ввести факт: not_and(1,1,0). Тоді логічну функцію можна записати як правило: my_funct(X,Y,P):-not_and(X,Y,Z),not_and(X,Z,P). Кома завжди означає логічне “І”.
Порядок виконання роботи:
Запустити запропоновану програму, записати таблицю виграшних ходів при заданому N.
Ввести в програму ще одне альтернативне визначення:
win(X,X):-can_take_matches(X). Запустити. Порівняти таблицю виграшних ходів з попередньою. Які зміни відбулися в умові гри при існуванні даного альтернативного визначення?
Закоментувати в програмі весь розділ “goal” та запустити програму в діалоговому режимі. На запит “Goal:” відповісти win(X,11), win(2,12). Записати відповіді.
Скласти свою програму, яка би видавала таблицю істинності для деякої вашої логічної функції. Схема функції має складатися з довільної кількості елементів “І-НЕ”, але не менше ніж з 3-х елементів.