Предикат not - заперечення як неуспіх.

Запишемо фразу "Ваня любить всі ігри крім баскетболу." на Прологу. Першу частину цього твердження виразити легко: " Ваня любить довільне Х, якщо Х - гра ", або ж:

 

like(wanja,X):-game(X).

 

Aлe ж потрібно виключити баскетбол. Це можна зробити використавши інше формулювання:

Якщо Х - баскетбол, тоді "Ваня любить Х" не буде істиною, інакше, якщо Х - гра, тоді "Ваня любить Х".

Для реалізації цього на Прологу, використаємо предикат fail, який завжди закінчується невдало, вимагаючи невдалого закінчення і тої цілі, яка є її батьком:

like(wanja, X):- basketball(X),!,fail. % семантично

                                                        невірна програма

like (wanja, X):- game (X).

Тут відсікання відкине із розгляду друге правило, коли гра - баскетбол, а fail викличе неуспіх, і вся програма закінчиться неуспіхом. Цей приклад показує, що бажано мати унарний предикат not такий, що not(Ціль) буде істинним у випадку, коли Ціль не є істиною. На Прологу його можна описати таким чином:

 not(P):- P,!, fail; true.

Пролог система має вбудований предикат not, реалізований подібним чином. Тоді наш приклад можна переписати в такому вигляді:

Like(wahja,X):- game(X), not(basketball(X)).

Єдине, що потрібно відмітити, це те, що: предикат not виконується успішно, коли підціль не є істиною. Іншими словами, not виконується успішно, коли ассоційована з ним підціль не може довести істинність.

Наступна програма демонструє, як використати предикат not, щоб виявити успішного студента: у якого середній бал (GPA) не менший за 3.5 і у якого в цей час не продовжується іспитовий термін.

Domaіns

name = symbol

gpa = real

Predіcates

honor_student(name)

student(name, gра)

Probatіon(name)

Clauses

honor_student (Name):- student(Name, GPA),

                    GPA>=3.5, not(probatіon(Name)).

student ("Betty Blue", 3.5).

student ("Davіd Smіth", 2.0).

student ("John Johnson", 3.7).

probatіon ("Betty Blue").

probatіon ("Davіd Smіth").

Goal

honor_student (X).

 

На запит honor_student(Name) вона видрукує список студентів, середній бал яких більший або ж дорівнює 3.5 за виключенням студентів Betty Blue і David Smith, які проходять випробувальний термін.

При використанні предиката not необхідно мати на увазі наступне:

Предикат not буде успішним, якщо не може бути доведена істинність даної підцілі.

 

Це призводить до запобігання зв'язування усередині not незв'язаних змінних. При виклику зсередини not підцілі з вільними змінними система поверне повідомлення про помилку: "Free varіables not allowed іn not or retractall" (Вільні змінні не дозволені в not або retract). Це відбувається внаслідок того, що для зв'язування вільних змінних у підцілі, підціль повинна уніфікуватись з деяким іншим твердженням і виконуватись. Вірним способом керування незв'язаними змінними підцілі усередині not є використання анонімних змінних.

Перший приклад:

lіkes (bіll, Anyone):- % Anyone - вихідний аргумент

              lіkes(sue, Anyone),not(hates(bіll, Anyone).

працює вірно, оскільки виклик предикату lіkes (sue, Anyone) зв'язує змінну Anyone до того, як система робить висновок про ложність предиката hates (bіll, Anyone).

Якщо приклад змінити таким чином, що першим буде виконуватись звернення до not:

lіkes(bіll, Anyone):-          % Це працює невірно

         not(hates(bіll, Anyone)), lіkes(sue, Anyone).

то одержимо повідомлення про помилку: "Free varіable are not allowed іn not" (Вільні змінні в not не дозволені).

Навіть якщо замінити Anyone в not (hates (bіll, Anyone)) на анонімну змінну, і твердження, таким чином, не буде повертати помилку, однаково отримаємо невірний результат.

lіkes(bіll, Anyone):- % Працює неправильно,

                                     оскільки невірна семантика

               not(hates(bіll, _)), lіkes(sue, Anyone).

Тут стверджується, що Біллу подобається хто завгодно, якщо невідомо нічого про те, кого Білл ненавидить, і якщо цей "хтось" подобається Сью. Вірне правило стверджувало, що Біллу подобається саме той, хто подобається Сью, і при цьому Білл не відчуває до цієї людини ненависті.

Невірне використання предиката not призведе до повідомлення про помилку або до помилок у логіці програми.

Труднощі використання cut і not.

Виділимо спочатку переваги використання відсікання:

1.За допомогою предикату cut можна підвищити ефективність програми.

2.Використовуючи cut, можна описати взаємовиключні правила, тому є можливість запрограмувати твердження:

 

якщо умова P, тоді розв'язок Q, інакше розв'язок R.

 

Обмеження на використання відсікання виходять із декларативної сутності прологівської програми. Якщо в програмі нема відсікання, тоді можемо міняти місцями порядок речень і цілей. Якщо ж предикат cut присутній в програмі, тоді зміна порядку речень в програмі може вплинути на її декларативний зміст (дати інший розв'язок).

Працювати з запереченням також треба обережно. Труднощі виникають тому, що заперечення, яке ми використовуємо, не повністю відповідає прологівському запереченню.

Якщо побудуємо запит системі:

   goal: not(dog(baks)),

вона, можливо, відповість " так ". Але цю відповідь не можна розуміти як повідомлення про те, що " Бакс не собака ", а потрібно розуміти, що не вистачає інформації для доведення твердження " Бакс - собака ". Такий підхід бере свій початок від припущення про замкненість світу. Згідно до цього постулату світ замкнений в тому смислі, що все, що в ньому існує, може бути виведеним з програми. Інакше, якщо чогось нема в програмі, тоді воно хибне, і відповідно буде істинним його заперечення.

Ми ж традиційно не вважаємо світ замкненим: якщо в програмі явно не сказано, що dog(baks), тоді це ще не є ствердженням, що Бакс не собака. Наведемо ще один приклад обережного використання not:

Predicates

 r(symbol)

g(symbol)

p(symbol)

Clauses

 r(a).

g(b).

p(X):-not(r(X)).

На запит

Goal: g(X), p(X)

cистема відповість Х=b, а на запит goal: p(X), g(X) система відповість no (ні). Вся різниця в тому, що в першому випадку змінна Х до моменту обчислення р(X) вже була зв'язана, а в другому випадку цього ще не трапилось.

 

Узагальнення.

1. Пролог має три предикати для контролю напрямку логічного пошуку:

§ fail є безумовною невдачею (тотожно ложним). За його допомогою включається механізм бектрекінгу для пошуку альтернативних рішень;

§ not приймає значення істина, коли не може бути доведено істинність для асоційованої з ним підцілі;

§ cut - виключає бектрекінг.

2. Можна вважати, що правила Прологу є визначеннями процедур з точки зору процедурної семантики. З точки зору процедурної семантики, правила можна розглядати як варіанти оператору case Паскаля.

 

Вправи.

1.Нехай маємо програму

P: - a, b.

P: - c.

Її декларативна сутність така: р буде істинним тоді й тільки тоді, коли будуть істинними одночасно а та b, або буде істинним с.

Якою буде декларативна сутність наступних програм?

а) р: - а,!, b.

p: - c.

б) р: - с.

р: - a,!, b.

2. Наступні відношення розподіляють числа на три класи - додатні, нуль і від`ємні:

клас (Число, додатні): - Число>0.

Клас (0, нуль).

клас (Число, від`ємні): - Число<0.

Зробіть цю процедуру більш ефективною за допомогою відсікання.

3.Нехай маємо програму

Р(4).

р(5): -!

Р(6).

Напишіть відповіді пролог-системи на наступні питання:

а) goal: p(X).

б) goal: p(X), p(Y).

c) goal: p(X),!, p(Y)

4. Напишіть програму знаходження максимума двох чисел, використовуючи предикат відсікання.