2018-02-13
239
Тема: Основи теорії предикатів.
Мета: Навчитися формулювати предикатні твердження з використанням кванторів.
Вступ. Предикат – це твердження, яке має параметри, тому деколи його називають предикатним твердженням. Таким чином, в залежності від конкретних значень цих параметрів предикат може бути або істинним, або хибним. Наприклад:
Автомобіль_біля_підїзду (Мерседес, Червоний)
Може бути істинним в якійсь ситуації, яка розглядається на момент застосування твердження. Якщо предикат формулювати не як твердження, а як запитання F: «який Автомобіль_біля_підїзду (x,y)?», то розв’язком такого предикату F(x,y) будуть всі значення комбінацій (x,y) при яких дане предикатне твердження у поточній ситуації буде вірним. У нашому прикладі, одним з можливих рішень буде x= Мерседес, y= Червоний.
Можна також вважати, що предикатне твердження F(x,y) задає деяку властивість F для заданих об’єктів (x,y), або вважати, що F задає множину деяких об’єктів із заданими властивостями (x,y). Наприклад, деякий об’єкт «Автомобіль_біля_підїзду» має властивість (або належить до множини x) «червоний», та водночас належить до множини y автомобілів «Мерседес», або, якщо запитати: «чим особливий червоний Мерседес?» – у відповідь можна отримати: «це Автомобіль_біля_підїзду».
Квантори. У теорії предикатів «існування деякого рішення x для предикатного твердження F» позначається як квантор існування: $(x). Його можна комбінувати в різних варіантах із запереченнями, наприклад: «не існує об’єкта F, який би мав властивість x» Ø$(F(x)). Якщо розв’язку x для предикатного твердження F не існує, то це позначається як Ø$(x)(F(x)). Якщо існує об’єкт F, який не має властивості x, то це позначається $(F(Ø x)). Якщо існує щось, але не об’єкт F з властивістю x, то це позначається як $(ØF(x)).
В деяких твердженнях необхідно умову сформулювати для всіх об’єктів, які мають певну властивість. Для цього існує квантор узагальнення, який читається «для всіх x» та позначається як "(x). Він пов’язаний з квантором існування так: Ø$(x)(F(x)) = "(x)(ØF(x)). Читається так: не існує жодного x, що володіє властивістю F, означає, що всі x не володіють властивістю F. Отже, квантори «для всіх» та «існує» при запереченні міняються місцями.
За допомогою предикатів можна формулювати розв’язки задач. При формулюванні розв’язку задачі квантори узагальнення задають приховані цикли перебору всіх комбінацій значень. В програмах на PRL кожне твердження за замовченням має квантор існування. Тому для використання кванторів узагальнення необхідно використовувати заперечення not, тобто, необхідно так сформулювати твердження, щоб в програмі спиратися на його заперечення.
Представлення задачі предикатами. Для розв’язку задачі необхідно описати її предикатними твердженнями. Основна проблема – уникнути зайвого перебору варіантів, а перебирати тільки ті варіанти, які дійсно ведуть до розв’язку задачі. Розглянемо приклад розв’язку простої ігрової задачі, в якій необхідно пішаками (охотниками) притиснути короля (вовка) до краю шахової дошки. Фігури ходять лише по чорних клітинках (рис.1), збивати фігури заборонено, в одній клітинці може бути тільки одна фігура, гравці ходять по черзі на одну клітинку, пішаки (1-4) ходять лише вперед, а вовк (W) – і вперед, і назад.
Оскільки варіантів дуже багато, необхідно одразу задати глибину перебору варіантів. Як показав експеримент, множина знайдених виграшних ходів перестає змінюватись після 16-го пів-ходу, тобто, після 8-го повного ходу. Така кількість варіантів займає в середньому біля 20 секунд обчислень на побутовому комп’ютері.
Нижче подана програма якраз і дає розв’язок ігрової ситуації, що представлена на рис.1. Стрілками показані ходи, що ведуть до виграшу 1-м або 2-м пішачком. Подальші виграшні ходи можна буде знайти після ходу вовка, тобто, після зміни ігрової ситуації.
Правило виграшу задається твердженням «знайти_виграшний_ хід_пішачка», яке складається з двох альтернатив:
Рис. 1. Ігрова ситуація, що розв’язується поданою програмою
.
1) необхідно знайти хід_пішачка при якому вовка можна просто приперти до краю дошки за допомогою умови not(можливий_хід_вовка(...)) і він не зможе походити;
2) якщо цього неможливо, то необхідно знайти хід_пішачка, який забороняє виграш вовка, який задається твердженням not(вовк_втік(...)).
Виграш вовка представляється твердженням вовк_втік(...). Воно має 2 альтернативи:
1) вовк виконує такий можливий_хід_вовка(рядок, стовпчик), після якого би вовк_вийшов_за_рядок_в_якому_є_останнй_пішачок(рядок) і гра би припинилась;
2) якщо швидко виграти не можливо, то вовк шукає такий хід, який забороняє виграшний хід пішачка за допомогою твердження not(знайти_виграшний_хід_пішачка(...)).
Оптимізація пошуку здійснюється за допомогою розділення ходів на ефективні та не ефективні. Таке розділення робиться із загальних міркувань, але якщо його не робити, час обчислень зростає приблизно у 4 рази. Для вовка не ефективними є ходи, які віддаляють вовка від пішачків на відстань більшу ніж 2 рядки. Для пішачків не ефективними є ходи, які роблять максимальну відстань між ними більшу ніж 3 рядки, або роблять хід, якщо перед ними є вовк. Фільтрація таких ходів здійснюється за допомогою тверджень велика_відстань_між_пішачками(на_рядок) та Перед_нами_вовк(...) для пішачків, а також, вовк_далеко_від_пішачків(на_кількість_кроків) для вовка, які відкидають не ефективні ходи.
Ігрова ситуація задається фактами Існує_Пішачок(...) та Координати_вовка(...). Для того, щоб знайти виграшний хід для пішачків в іншій ситуації, необхідно вручну поміняти дані у вказаних фактах і наново запустити програму. Для того, щоб знайти виграшний хід для вовка, необхідно у першому твердженні програми викликати предикат вовк_втік(...).
Програма для розв’язку ігрової ситуації:
Впіймати_вовка:- Глибина_перебору=16,
знайти_виграшний_хід_пішачка (Глибина_перебору,Пішачок_номер,йде_на_горизонталь,та_на_вертикаль),
write("Номер", Пішачок_номер, " йде на координати:",
йде_на_горизонталь, ",", та_на_вертикаль), fail.
Існує_Пішачок(1, 2,2). Існує_Пішачок(2, 4,2). Існує_Пішачок(3, 3,5).
Існує_Пішачок(4, 5,5). Координати_вовка(6,4).
знайти_виграшний_хід_пішачка(Глибина_перебору,Пішачок_номер,йде_на_горизонталь,та_на_вертикаль):-
хід_пішачка(Пішачок_номер,йде_на_горизонталь,та_на_вертикаль),
not(можливий_хід_вовка(на_довільний_рядок,на_довільний_стовпець)).
знайти_виграшний_хід_пішачка(Глибина_перебору,Пішачок_номер,йде_на_горизонталь,та_на_вертикаль):-
хід_пішачка(Пішачок_номер,йде_на_горизонталь,та_на_вертикаль),
Глибина_перебору1=Глибина_перебору-1,
not(вовк_втік(Глибина_перебору1,довільний_рядок,довільний_стовпчик)).
вовк_втік(Глибина_перебору,рядок,стовпчик):-
можливий_хід_вовка(рядок,стовпчик),
вовк_вийшов_за_рядок_в_якому_є_останнй_пішачок(рядок).
вовк_втік(Глибина_перебору,рядок,стовпчик):-
Глибина_перебору>0, Глибина_перебору1=Глибина_перебору-1,
можливий_хід_вовка(рядок,стовпчик),
not(знайти_виграшний_хід_пішачка(Глибина_перебору1, довільний_р,довільний_с)).
можливий_хід_вовка(рядок,стовпець):- можливий_хід_вовка_вперед(рядок,стовпець).
можливий_хід_вовка(рядок,стовпець):-
на_кількість_кроків=2, not(вовк_далеко_від_пішачків(на_кількість_кроків)),
можливий_хід_вовка_назад(рядок,стовпець).
можливий_хід_вовка_вперед(рядок,стовпець):-
Координати_вовка(р,с),
рядок=р-1, стовпець=с-1, рядок>0, стовпець>0,
not(Існує_Пішачок(довільний_номер,рядок,стовпець)),
suppose(Координати_вовка(рядок,стовпець)).
можливий_хід_вовка_вперед(рядок,стовпець):-
Координати_вовка(р,с),
рядок=р-1, стовпець=с+1, рядок>0, стовпець<9,
not(Існує_Пішачок(довільний_номер,рядок,стовпець)),
suppose(Координати_вовка(рядок,стовпець)).
можливий_хід_вовка_назад(рядок,стовпець):-
Координати_вовка(р,с),
рядок=р+1, стовпець=с-1, рядок<9, стовпець>0,
not(Існує_Пішачок(довільний_номер,рядок,стовпець)),
suppose(Координати_вовка(рядок,стовпець)).
можливий_хід_вовка_назад(рядок,стовпець):-
Координати_вовка(р,с),
рядок=р+1, стовпець=с+1, рядок<9, стовпець<9,
not(Існує_Пішачок(довільний_номер,рядок,стовпець)),
suppose(Координати_вовка(рядок,стовпець)).
хід_пішачка(Номер,на_рядок,і_на_стовпець):-
Існує_Пішачок(Номер,р,с),
на_рядок = р+1, на_рядок<9,
і_на_стовпець = с+1, і_на_стовпець<9,
not(Перед_нами_вовк(р,с)),
not(Існує_Пішачок(з_іншим_номером,на_рядок,і_на_стовпець)),
not(велика_відстань_між_пішачками(на_рядок)),
suppose(Існує_Пішачок(Номер,на_рядок,і_на_стовпець)).
хід_пішачка(Номер,на_рядок,і_на_стовпець):-
Існує_Пішачок(Номер,р,с),
на_рядок = р+1, на_рядок<9,
і_на_стовпець = с-1, і_на_стовпець>0,
not(Перед_нами_вовк(р,с)),
not(Існує_Пішачок(з_іншим_номером,на_рядок,і_на_стовпець)),
not(велика_відстань_між_пішачками(на_рядок)),
suppose(Існує_Пішачок(Номер,на_рядок,і_на_стовпець)).
велика_відстань_між_пішачками(рядок):-
Існує_Пішачок(Номер,останній_рядок,стовпець),
відстань = рядок-останній_рядок, відстань>3.
вовк_вийшов_за_рядок_в_якому_є_останнй_пішачок(рядок):-
not(існує_пішачок_нижче_даного_рядку(рядок)).
існує_пішачок_нижче_даного_рядку(рядок):-
Існує_Пішачок(Номер,рядок1,стовпець1),
рядок1<рядок.
вовк_далеко_від_пішачків(на_кількість_кроків):-
not(існує_пішачок_ближче_даної_відстані(на_кількість_кроків)).
існує_пішачок_ближче_даної_відстані(на_кількість_кроків):-
Координати_вовка(рядок_вовка,стовпець_вовка),
Існує_Пішачок(з_довільним_номером,рядок_пішачка,стовпець_пішачка),
поточна_відстань= рядок_вовка-рядок_пішачка,
поточна_відстань<на_кількість_кроків.
Перед_нами_вовк(рядок_пішачка,стовпець_пішачка):-
Координати_вовка(рядок_вовка,стовпець_вовка),
рядок_пішачка = рядок_вовка-1,
сусідні_стовпці(стовпець_пішачка,стовпець_вовка).
сусідні_стовпці(стовпець1,стовпець2):- стовпець1 = стовпець2+1.
сусідні_стовпці(стовпець1,стовпець2):- стовпець2 = стовпець1+1.
Завдання 1. Для закріплення матеріалу необхідно виконати вище подану програму та пояснити її.
Завдання 2. Зіграти гру до кінця, починаючи з ігрової ситуації, яка задана викладачем. Кожний хід протоколювати як умовне зображення ігрової дошки в текстовому або Word-документі. На зображенні обов’язково позначати можливі ходи, які знайшла програма, та вибраний Вами хід для пішаків та вовка.
Завдання 3. Знайти програмно виграшний хід для вовка у вигаданій Вами ситуації.
Завдання 4. Знайти у програмі переходи між кванторами існування та узагальнення.
