Програмування на мові CLIPS

Министерство загального характеру і професійного образования.

Російської Федерации.

Кубанський Державний Технологічний Университет.

Курсова робота на тему:

ПРОГРАМУВАННЯ НА МОВІ CLIPS.

Роботу виконав студент групи 01;

КТ-22 факультета.

КТАС Мариненко А.

А.

Краснодар 2001.

СОДЕРАЖНИЕ.

. А.1. Коротка історія CLIPS 3.

. А.2. Правила і функції в CLIPS.

. А.3. Обектно-ориентированные кошти на CLIPS.

. А.4. Завдання «Правдолюбці і брехуни» 15.

. А.5 Стиль програмування мовою CLIPS 66.

А.1. КОРОТКА ІСТОРІЯ CLIPS.

Назва мови CLIPS — абревіатура від З Language Integrated Production System. Мова було розроблено на центрі космічних досліджень NASA.

{NASA's Johnson Space Center} у середині 1980;х років та значною мірою подібний з мовами, створеними з урахуванням LIPS, зокрема OPS5 і ART. Використання З як мовою реалізації пояснюється лише тим, що компілятор LISP не підтримується частиною поширених платформ, і навіть складністю інтеграції LISP-кода в докладання, що використовують відмінний від LIPS мову програмування. Хоча час над ринком вже з’явилися програмні кошти на завдань штучного інтелекту, розроблені мовою З, фахівців із NASA вирішили створити цілковито такий продукт самостійно. Розроблена ними система нині доступний у весь світ, і треба сказати, що у своїх можливостей вона поступається безлічі значно більше дорогих комерційних продуктов.

Перша версія є, власне, інтерпретатор що породжують правил. Процедурний язик, і объективно-ориентированное розширення CLIPS Object-Oriented Language {COOL} були у цей програмний продукт лише у 90-х роках. Існуюча нині версія може експлуатуватися на платформах UNIX, DOS, Windows і Macintosh. Вона є добре документованим загальнодоступним програмним продуктом і доступна через мережу FTR з безлічі університетських сайтів. Вихідний код програмного пакета CLIPS поширюється цілком і може бути встановити будь-який платформі, підтримує стандартний компілятор мови З. Однак я рекомендував користуватися офіційної версією для певної платформи, оскільки такі версії оснащені користувальницьким інтерфейсом, які мають меню команд і вбудований редактор.

Це Додаток організовано так. У розділі А.2. розглянуті основні функції мови, опис правив і процедурного мови. У розділі А.3. представлені методи роботи з об'єктами і показано, як використовувати в поєднані із правилами і процедурами. У розділі А.4. описаний приклад, демонструє деякі прийоми програмування правил, а розділ А.5. резюмуються характеристики цього програмного продукту і пропонуються теми ще поглибленого изучения.

А.2. ПРАВИЛА І ФУНКЦІЇ У CLIPS.

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

Основними компонентами мови описи правил є база фактів (fact base) й базу правил (rule base). Там покладаються такі функції: — база фактів є вихідне стан проблеми; - база правил містить оператори, які перетворять стан проблеми, наводячи його до решению.

Машина логічного висновку CLIPS зіставляє ці факти і що правил і з’ясовує, які з правил можна активізувати. Це виконується циклічно, причому кожен цикл складається з трьох кроків: 1) зіставлення фактів і керував; 2) вибір правила, що підлягає активізації; 3) виконання дій, запропонованих правилом.

Такий трехшаговый циклічний процес іноді називають «циклом распознование — действие».

А.2.1. Факты.

Відразу після запуску CLIPS-приложения виконання на екрані з’явиться запрошення, який сповіщає користувача, що він працює із интерпретатором.

CLIPS>

У режимі інтерпретатора користувач може застосовувати багато команд. Факти можна включити до бази фактів безпосередньо з командної рядки з допомогою команди assert, например:

CLIPS> (assert (today is Sunday)).

CLIPS> (assert (weather is warm)).

Для кращого сприйняття тесту Додатка ми далі будемо виділяти текст, запроваджуваний користувачем, напівжирним щрифтом, а запити, й відповіді інтерпретатора — звичайним моноширинным шрифтом.

Для виведення списку фактів, наявних у базі, використовується команда facts:

CLIPS>(facts) f-1 (today is Sunday) f-2 (weather is warm).

Останніх версіях CLIPS, зокрема, у тому, яка працює у операційній середовищі Windows, такі команди як facts, можна викликати з допомогою меню.

Для видалення фактів з убозівської бази використовується команда retract.

CLIPS> (retract 1).

CLIPS> (facts) f-0 (today is Sunday).

Ці самі команди, assert і retract, використовують у виконуваної частини правил (укладанні правила) і з допомогою виконується програмне зміна бази фактів. Часто доводиться користуватися й інший командою інтерпретатора, clear, яка очищає базу фактів (зазвичай, ця команда доступна у одному з випадаючих меню).

CLIPS> (clear).

CLIPS> (facts).

У тексті програми факти можна включати у базу за одиночці, а цілим масивом. І тому в CLIPS є команда deffacts.

(deffacts today.

(today is Sunday).

(weather is warm).

).

Вислів deffacts має формат, аналогічний выражениям у мові LISP. Вислів починається з команди deffacts, потім наводиться ім'я списку фактів, який программисти збирається визначити (у нашій прикладі - today), а й за ним йдуть елементи списку, причому їх кількість не обмежується. Цей масив фактів потім видалити з убозівської бази командою undeffacts.

CLIPS> (undeffacts today).

Вислів deffacts можна вводити й у командний рядок інтерпретатора, але записати їх у текстовий файл з допомогою редактора CLIPS чи іншого текстового редактора. Завантажити цей файл в подальшому можна з допомогою команди у меню File або з командної строки.

CLIPS> (load «my file»).

Проте після завантаження файла факти не передаються відразу ж на базу фактів CLIPS. Команда deffacts просто вказує інтерпретатора, що існує масив today, який містить багато фактів. Власне завантаження виконується командою reset.

CLIPS> (reset).

Команда reset спочатку очищає базу фактів, та був включає у неї факти із усіх раннє завантажених масивів. Вона також додає до бази єдиний системно певний факт: f-0 (initial-fact).

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

Можна простежити, як виконується команда reset, якщо перед виконанням наведених вище команд встановити режим спостереження середовища розробки. Треба лише викликати команду Watch з меню Execution і встановити ній прапорець Facts.

А.2.2. Правила.

У мові CLIPS правила мають наступний формат:

(defrule.

< необов’язковий коментар >

< необов’язкове оголошення >

< предпосылка₁ >

…

< предпосылка_m >

=>

< действие₁ >

…

< предпосылка_n >

).

Например:

(defrule chores.

«Things to do on Sunday».

(salience 10).

(today is Sunday).

(weather is warm).

=>

(assert (wash car)).

(assert (chop wood).

).

У цьому вся прикладі Chores — довільно обраний ім'я правила. Передумови в умовної частини правила.

(today is Sunday).

(weather is warm) сопоставляются потім інтерпретатором з базою фактів, а дії, перелічені в виконуваної частини правила (вона розпочинається після пари символів =>), уставлять до бази два факта.

(wash car).

(chop wood) у разі, якщо правило буде активізовано. Наведений з тексту правила комментарий.

«Things to do on Sunday».

«Що робити у неділю» допоможе надалі згадати, навіщо цього правила включено в програму. Выражение.

(salience 10) свідчить про ступінь важливості правила. Нехай наприклад, у програмі є інше правило.

(defrule fun.

«Better things to do on Sunday».

(salience 100).

(today is Sunday).

(weather is warm).

=>

(assert (drink beer)).

(assert (play guitar)).

).

Оскільки передумови обох правил однакові, то, при виконанні обумовлених умов вони «конкурувати» за увагу інтерпретатора. Перевагу віддадуть правилу, яка має параметр salience має як високе значення, у разі - правилу fun. Параметру salience може бути присвоєно будь-яке целочисленное значення буде в діапазоні [-10 000, 10 000]. Якщо параметр salience у визначенні правила опущений, йому за вмовчанням присвоюється значення 0.

Зазвичай, у визначенні правила присутні і які змінюються. Якщо, наприклад, правило.

(defrule pick-a-chore.

«Allocating chores to days».

(today is? day).

(chore is? job).

=>

(assert (do ?job on? day)).

) буде зіставлять з фактами.

(today is Sunday).

(chore is carwash) то разі активізації воно включить до бази новий факт.

(do carwash on Sunday).

Аналогічно, правило.

(defrule drop-a-chore.

«Allocating chores to days».

(today is? day).

?chore.

(retract ?chore).

) скасує виконання робіт з дому (a chore). Зверніть увагу, що обидві примірника перемінної ?day маємо отримати один і той ж значення. Змінна ?chore внаслідок зіставлення повинна щось одержати посилання факт, який ми ж збираємося вилучити з бази. Отже, якщо це правило буде зіставлять з базою фактів, у якій содержатся.

(today is Sunday).

(do carwash on Sunday) то, при активізації правила з убозівської бази буде винесений факт.

(do carwash on Sunday).

З подробицями виконання процесу сосоставления в інтерпретаторі CLIPS ви зможете познайомитися в Керівництві користувача, а тут лише відзначимо, що факт.

(do carwash on Sunday) буде сопоставлен із будь-ким із представлених нижче образцов.

(do? ? Sunday).

(do? on ?).

(do? on? when).

(do $?).

(do $? Sunday).

(do ?chore $?when).

Врахуйте, що префікс $? є ознакою сегментной перемінної, пов’язаного з сегментом списку. Наприклад, у наведеному вище прикладі змінна $?when була й с.

(on Sunday).

Якщо за префіксами? і $? годі було ім'я зміною, вони розглядаються як універсальні символи підстановки, яким відповідно то, можливо сопоставлен будь-який елемент чи сегмент списка.

А.2.3. Спостереження за процесом интерпретации.

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

(defrule start.

(initial-fact).

=>

(printout t «hello, world» crlf).

).

Виконайте команду reset. І тому введіть цю команду в командної рядку интерпретатора.

CLIPS> (reset).

Або виберіть в меню команду Execution=>Reset, або натисніть (останніх два варіанта можливі в версії, яка працює під Windows).

Потім запустіть інтерпретатор. І тому введіть цю команду run в командний рядок интерпретатора.

CLIPS> (run).

Або виберіть в меню команду Execution=>Run, або натисніть (останніх два варіанта можливі в версії, яка працює під Windows).

У відповідь програма повинна вивести повідомлення hello, world, знайоме всім програмістам світу. Для повторного запуску програми повторіть команди reset і run.

Якщо меню Execution=>Watch раніше було встановлено прапорець Rules чи перед запуском програми виконання запровадити в командну стоку команду watch rules, то, на екрані з’явитися результат транссировки процесу выполнения.

CLIPS> (run).

FIRE 1 start: f-0 hello, world.

У цьому вся повідомленні в рядку, що починається з FIRE, виведено інформація про активізованому правилі: start — це правила, а f-0 — ім'я факту, який «задовольнив» умова у тому правилі. Команда watch дозволяє організувати кілька різних режимів трасування, з деталями яких можете познайомитися в Керівництві користувача. Якщо перед запуском програми ви ввели.

CLIPS> (dribble-on «dribble.dp»).

TRUE.

Те виведений протокол трасування буде збережено в файлі dribble.clp. Збереження протоколу припиниться після введення команда.

CLIPS> (dribble-off).

TRUE.

Це дуже зручний опція, особливо у етапі освоєння языка.

А.2.4. Використання шаблонов.

Для визначення фактів можна використовувати як спискові структури, а й шаблони, що нагадують прості записи. (Шаблони в CLIPS немає нічого спільного з шаблонами З++.) Шаблону виглядає так:

(deftemplate student «a student record».

(slot name (type STRING)).

(slot age (type NUMBER) (default 18)).

).

Кожне визначення шаблону складається з довільного імені шаблону, необов’язкового коментарю та певної кількості визначень слотів. Слот включає полі даних, наприклад name, і тип даних, наприклад STRING. Можна вказати і значення за умовчанням, як і наведеному вище примере.

Якщо програму включено наведене вище визначення шаблону, то выражение.

(deffacts students.

(student (name fred)).

(student (name freda) (age 19)).

) призведе до того що, що до бази фактів після виконання команди reset буде добавлено.

(student (name fred) (age 18)).

(student (name freda) (age 19)).

А.2.5. Визначення функций.

У мові CLIPS функції конструюються приблизно таке ж, як і мові LIPS. Суттєва різниця у тому, що перемінні повинен мати префікс ?, як і показано у наведеному нижче определении.

(deffunction hypotenuse (?a ?b).

(sqrt (+ (* ?a ?a) (* ?b ?b)).

).

Формат визначення функції в CLIPS следующий:

(deffunction (…).

…

).

Функція повертає результат останнього висловлювання на списке.

Іноді виконання функції має побічні ефекти, як і наведеному нижче примере.

(deffunction init (?day).

(reset).

(assert (today is? day)).

).

Відтак після запуску функції виконання командой.

CLIPS> (init Sunday).

Буде виконано команда reset і, отже, очищена база фактів, потім у неї включений новий факт (today is Sunday).

А.3. ОБ'ЄКТНО-ОРІЄНТОВАНІ ЗАСОБИ У CLIPS.

Використання объектно-ориентированных засобів у CLIPS дозволяє значно спростити програмування правил, бо відновлення даних можна використовувати механізму передачі і методи обробки повідомлень методами класів. У розділі ми продемонструємо, як це робиться з прикладу, який моделює правила роботи з напівавтоматичним пистолетом.

Передусім визначимо клас pistol, у якому перераховані властивості, необхідних моделирования.

(defclass pistol.

(is-a USER).

(role concrete).

(pattern-match reactive).

(slot safety (type SYMBOL) (create-accessor read-write)).

(slot slide (type SYMBOL) (create-accessor read-write)).

(slot hammer (type SYMBOL) (create-accessor read-write)).

(slot chamber (type INTEGER) (create-accessor read-write)).

(slot magazine (type SYMBOL) (create-accessor read-write)).

(slot rounds (type INTEGER) (create-accessor read-write)).

).

Перші три слота — системні. Вони потрібні объектно-ориентированной надбудові CLIPS (COOL-CLIPS object-oriented language). Ці слоты COOL сповіщають у тому, що. pistol — це користувальницький клас;. pistol є конкретним класом, тобто. можливе створення примірників цього (альтернативний тип — абстрактний клас, що грає таку ж роль, як і віртуальний клас у З++);. екземпляри класу pistol можна використовувати як об'єкти даних, які можна зіставляти з умовами в правила і залучити до діях, певних правилами.

Наступні п’ять слотів представляють властивості і члени даних класу:. слот safety (запобіжник) може містити символ on чи off;. слот slide (затвор) може містити значення forward чи back, тобто. зберігає інформацію про стан затвора;. слот hammer (курок) містить інформацію про стан курка, back чи down;. слот chamber (патронник) містить значення 1 чи 0, залежно від цього, чи є патрон в патроннику;. слот magazine (обойма) може містити значення in чи out, залежно від цього, вставлена чи обойма;. слот rounds (патрони) містить поточне кількість патронів в обойме.

Щоб матимуть можливість нотувати у слот нового значення чи зчитувати поточне, потрібно дозволити формування відповідних функцій доступу через фацет create-accessor. Тепер сформуємо примірник класу pistol з допомогою наступного выражения:

(definstances pistols.

(PPK of pistol.

(safety on).

(slide forward).

(hammer down).

(chamber 0).

(magazine out).

(rounds 6).

).

).

Цей примірник, PPK, правильно покладено — обойма вийнято з рукоятки, пістолет установлено в запобіжник, затвор в передньому становищі, курок опущений, а патронник порожній. У обоймі є 6 патронов.

Тепер, маючи у своєму програмі визначення класу тут і сформувавши примірник класу, розробимо правил і оброблювачі повідомлень, з допомогою яких можна описати окремі операції роботи з пістолетом і стрільби потім із нього. І тому спочатку розробимо шаблон завдання. Бажано відстежувати дві речі:. чи є патрон в патроннику;. зроблено чи выстрел.

І тому можна використовувати наступний шаблон:

(deftemplate range-test.

(field check (type SYMBOL) (default no)).

(field fired (type SYMBOL) (default no)).

).

Перше правило встановлюватиме в робочу пам’ять програми завдання range-test.

(defrule start.

(initial-fact).

=>

(assert (range-test)).

).

При активізації цього правила в робочу пам’ять буде добавлено.

(range-test (check no) (fired no)).

Три наступні правила перевірятимуть правильно чи споряджений пистолет.

(defrule check.

(object (name [PPK]) (safety on) (magazine out).

?T.

(send [PPK] clear).

(modify ?T (check yes).

).

Правило check у тому, що й пістолет слід за запобіжнику (safety on), обойма вийнято (magazine out) і пістолет ні перевірений, потрібно очистити патронник і перевірити, чи немає у ньому патрона. Оброблювач повідомлень clear для класу pistol виглядатиме наступним образом:

(defmassage-handler pistol clear ().

(dynamic-put chamber 0).

(ppinstance).

).

У першій рядку оголошується, що clear є обрабртчиком повідомлення для класу pistol, причому цей оброблювач не вимагає передачі аргументів. Оператор на другий рядку «очищає» патронник. Присвоєння виконується незалежно від цього, яке поточне значення має тут слот chamber, — 0 чи 1. Оператор у третій рядку вимагає, щоб примірник розпечатав інформацію про поточний стан своїх слотов.

У наступних двох правилах обробляються ситуації, коли пістолет споряджений неправильно, — не установлено в запобіжник чи нього вставлена обойма. Правило correct1 встановлює пістолет на запобіжник, а правило correct2 витягує зі нього обойму.

(defrule correct1.

(object (name [PPK]) (safety off)).

(range-test (check no)).

=>

(send [PPK] safety on).

).

(defrule correct2.

(object (name [PPK]) (safety on) (magazine in)).

(range-test (check no)).

=>

(send [PPK] drop).

).

Як за розробці попереднього правила, нам знадобляться оброблювачі повідомлень safety і drop.

(defmessage-handler pistol safety (?on-off).

(dynamic-put safety? on-off).

(if (eq ?on-off on) then (dynamic-put hammer down).

).

).

Оброблювач повідомлення safety приймає єдиний аргумент, який може мати не лише два символічних значення on чи off. У протилежному разі ми мусили б розробити два оброблювача: один для повідомлення safety-on, а інший — для повідомлення safety-off. Врахуйте, що деякі моделях, наприклад, у Walther PPK, за умови встановлення пістолета на запобіжник патронник очищається автоматически.

Оброблювач повідомлення drop просто дістає обойму з пистолета.

(defmessage-handler pistol drop ().

(dynamic-put magazine out).

).

Тепер, коли забезпечене правильне вихідне спорядження пістолета, можна розпочати стрільбі. Наступне правило забезпечує вставку обойми в пістолет перед стрельбой:

(defrule mag-in.

(object (name [PPK]) (safety on) (magazine out)).

(range-test (fired no) (check yes)).

=>

(send [PPK] seat).

).

Оброблювач повідомлення seat виконує дії, протилежні тим, що виконує оброблювач drop.

(defmessage-handler pistol seat ().

(dynamic-put magazine in).

).

Можна було б, звісно, включити у програмі й таке правило magin:

(defrule mag-in.

?gun.

(modify ?gun (magazine in).

) але ці суперечить одного з принципів объектно-ориентированного програмування, де йдеться, що об'єкт має обробляти що їх містить дані. Наступне правило забезпечує спорядження обойми патронами:

(defrule load.

(object (name [PPK]) (magazine in) (chamber 0)).

=>

(send [PPK] rack).

).

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

(defmessage-handler pistol rack ().

(if (> (dynamic-get rounds) 0) then (dynamic-put chamber 1).

(dynamic-put rounds (- (dynamic-get rounds) 1)).

(dynamic-put slide forward) else (dynamic-put chamber 0).

(dynamic-put slide back).

).

).

У цьому вся обработчике забезпечується досылка патрона в патронник у цьому разі, тоді як обоймі є патрони. Наступне правило підготовляє пістолет до стрільбі, знімаючи його з запобіжника. Зверніть увагу, що він повторно використовується повідомлення safety, але цього разу з аргументом off.

(defrule ready.

(object (name [PPK]) (chamber 1)).

=>

(send [PPK] safety off).

).

Правило fire виконує стрельбу.

(defrule fire.

(object (name [PPK]) (safety off);

?T.

(if (eq (send [PPK] fire) TRUE) then (modify ?T (fired yes))).

).

Зверніть увагу, що в правилі використовується оброблювач повідомлення, що повертає значення. Аналізуючи його, бачимо, зроблено чи постріл, тобто. виконано у дійсності та операція, яка «закріплена» для цього повідомленням. Якщо патроннику був патрон і пістолет зняли з запобіжника, то оброблювач повідомлення поверне значення TRUE (по тому, як виведе на екран BANG!). Інакше він поверне FALSE (по тому, як виведе на екран click).

(defmessage-handler pistol fire ().

(if (and.

(eq (dynamic-get chamber) 1).

(eq (dynamic-get safety) off).

) then (printout t crlf «BANG!» t crlf).

TRUE else (printout t crlf «click» t crlf).

FALSE.

).

).

Нехай вас це не бентежить, що у обработчике повідомлення аналізується умова, що була проаналізоване правилом, отославшим повідомлення (у разі йдеться про умови safety off). Річ у тім, що одне теж повідомлення може відсилатимуться різними правилами немає жодної гарантії, що у кожному з них перевірятися це условие.

Після закінчення стрільби пістолет потрібно знову повернути становище «похідним-похідній-по-похідному». Починається це сіло, що пістолет встановлюється на запобіжник, навіщо використовується раніше розроблений оброблювач повідомлення safety.

(defrule unready.

(object (name [PPK]) (safety off)).

(range-test (fired yes)).

=>

(send [PPK] safety on).

).

Наступна операція — вийняти обойму. Зверніть увагу, що він ми знову звертаємося до оброблювачу повідомлення drop.

(defrule drop.

(object (name [PPK]) (safety on)).

(range-test (fired yes)).

=>

(send [PPK] drop).

).

Останнє правило викидає патрон з патронника, викликаючи оброблювач повідомлення clear.

(defrule unload.

(object (name [PPK]) (safety on) (magazine out)) range-test (fired yes)).

=>

(send [PPK] clear).

).

У цьому вся приемре було продемонстровано, як у межах єдиної CLIPS програми «уживаються» правил і об'єкти. Правила управляють ходом обчислень, та деякі операції об'єкти виконують та самостійно, отримавши «вказівку» (повідомлення) від правил. Об'єкти не являютя резидентами робочої пам’яті, але члени лівої частини правил (умов) може бути порівняно зі змістом їх слотів. Стан об'єктів може змінитися, й внаслідок побічні ефекти активізації правил, але вважаю, краще надати об'єктах можливість самостійно виконувати маніпуляції з хранящимися у яких даними у відповідь які від правил повідомлення. Об'єкти що неспроможні самостійно активізувати правила, та їх оброблювачі повідомлення можуть «повертати» певну інформацію про результати, яка використовується керувати логікою виконання дій у правій частині правил.

А.4. ЗАВДАННЯ «ПРАВДОЛЮБЦІ І ЛЖЕЦЫ».

А, щоб продемонструвати вам можливості мови CLIPS, я вибрав головоломку, а чи не завдання з практики застосування експертних систем. У головоломці вирішується одне з завдань, виникаючих на острові, населеному мешканцями двох категорій: одні завжди кажуть правду (назвемо їх правдолюбцами), інші завжди брешуть (їх, природно, назвемо брехунами). Безліч подібних головоломок ви можете зустріти зі сторінок цікавою книжки Раймонда Смуляна «What is the Name of this Book?». Нижче наведено різні завдання з цього серии.

Р1. Зустрічаються двоє, Проте й У, одна з яких правдолюбець, а інший — брехун. А каже: «Або я брехун, або У правдолюбець». Хто з цих двох правдолюбець, хто ж лжец?

Р2. Зустрічаються троє, А, У і З. Проте й каже: «І ми брехуни», а У відповідає: «Один лише із нас правдолюбець». Хто з цих трьох правдолюбець, хто ж лжец?

Р3. Зустрічаються троє, А, У і З. Четвертий проходячи повз, запитує А: «Скільки правдолюбців серед вас?» А відповідає невизначено, а У відповідає: «А сказав, що з маємо один правдолюбець». Ось у розмова вступає З повагою та додає: «У бреше!» ким по-вашому є У і С?

У конкурсній програмі, вирішальної проблеми такого класу, буде використано широкі можливості коштів програмування правив у мові CLIPS і продемонстровані деякі цікаві прийоми, наприклад використання контекстів й протилежного простежування. Ми також покажемо, як конструювати і тестувати прототипи, які приблизно відтворюють поведінка остаточної програми. Як у основному матеріалі книжки, технологія побудови експертних систем з допомогою прототипів — одна з найпоширеніших на цей время.

А.4.1. Аналіз проблемы.

Першим етапом будь-якого програмного проекту є аналіз розв’язуваної проблеми. Експерт мусить уміти покінчити з проблемою, а інженер за знаннями повинен розібратися, як саме отримали рішення. За позитивного рішення нашої завдання вам доведеться виступити на обох ипостасях.

Запропоновані головоломки можна вирішити, систематично аналізуючи, що станеться, якщо персонаж, вимовляє репліку, є правдолюбцем, а що, коли він — брехун. Означимо через Т (А) факт, що, А каже правду, і отже, є правдолюбцем, а ще через F (А) — факт, що, А бреше і, отже, є лжецом.

Розглянемо спочатку головоломку Р1. Припустимо, що, А каже правду. Тоді з його репліки слід, або, А брехун, або У правдолюбець. Формально це можна зробити явити у наступному виде:

Т (А) =>F (А) v Т (В).

Оскільки, А може і брехуном, і правдолюбцем, то звідси следует.

Т (А) =>Т (В).

Аналогічно можна записати інший варіант. Припустимо, що, А лжет:

F (A)=>-(F (A) v Т (В)).

Спростимо це выражение:

F (A)=>-F (A)^-Т (В) чи F (A)=> Т (А)^F (B).

Порівнюючи обидва варіанти, неважко зробити висновок, що тілки останній правильний, що у перший варіант домовилися висновку, яка суперечить умовам (неможливо знайти правдолюбцами одночасно Проте й В).

Отже, розглянута проблема належить до типу таких, вирішення яких перебуває у результаті аналізу висновків, що із певних припущень, й пошуку у яких протиріч (або відсутність таких). Ми вважаємо, що включає певний персонаж каже правду, а потім дивимося, чи можна у разі так розподілити «ролі» інших персонажів, що ні буде порушено умови, сформульовані репліках. На жаргоні, був прийнятий математичне логіці, припущення щодо правдивості чи брехливість безлічі висловлювань називається інтерпретацією, а варіант несуперечливого присвоєння значень істинності елементам безлічі - моделью.

Проте наші головоломки включають і щось, що виходить далеко за межі типових проблем математичної логіки, оскільки репліки у яких може вимовляти не один персонаж (як і головоломці Р2), але в репліку одного персонажа може наслідувати відповідна репліка іншого (як і головоломці Р3). У вихідної версії програми, що її розглянемо нижче, це ускладнення відсутня, але у остаточної вона має бути враховано. Ми покажемо, що поступове ускладнення програми досить добре цілком узгоджується з використанням правил.

Насправді виявляється, що у першу версію програми найзручніше скористатися «вырожденным» варіантом проблеми, тобто. постаратися вирішити їх у тривіальному вигляді, який, тим щонайменше, містить у собі багато особливості реального випадку. Ось як це буває щодо наших правдолюбців і лжецов.

Р0. А заявляє: «Я брехун». Хто ж у дійсності А — брехун чи правдолюбец?

Ми хіба що фактично процитували добре відомий Парадокс Брехуна. Якщо, А брехун, отже, він бреше, тобто. насправді він правдолюбець. Але тоді ми дійшли протиріччю. Якщо ж, А правдолюбець, тобто. каже правду, то дійсності він брехун, але це знову протиріччя. Отже, у цій головоломці немає несуперечливого варіанта «розподілу ролей», тобто. немає моделі тому, який надається їй у математичної логике.

Є чимало достоїнств у виборі для прототипу програми варіанта головоломки Р0.. У головоломці присутній один персонаж.. Вислів зовсім позбавлений логічних зв’язок, як-от І чи АБО, чи кванторів, на кшталт квантора спільності (все) та інші.. Відсутня відповідна реплика.

У той самий час суттєві риси проблеми, у цьому варіанті присутні. Ми досі повинні спробувати знайти несуперечливу інтерпретацію висловлювання А, тобто. повинні реалізувати два завдання, наявні у будь-яких варіантах як і головоломки:. формувати альтернативні інтерпретації висловлювань;. аналізувати наявність противоречий.

Ви побачите, що з виконання цих двох завдань знадобиться використовувати механізм, дуже близька до тим, які ми розглядали при описі систем обробки правдоподібності в розділах 17 і 19.

А.4.2. Онтологічний аналіз політики та уявлення знаний.

Наступний етап — визначити, з які види даних доведеться мати справу під час вирішення цього головоломок. Які об'єкти представляють інтерес у світі правдолюбців і брехунів і яким атрибутами ці об'єкти характеризуются?

Очевидно, вирішення завдань цього доведеться мати справу з такими об'єктами.. Персонажі, котрі вимовляють репліки. Сказана репліка характеризує або самого персонажа, або інших персонажів, або й тих, та інших. Персонаж може або правдолюбцем, або брехуном.. Твердження, що міститься в репліці. Це твердження може або повністю брехливим, або абсолютно правдивим (истинным).

Трохи поміркувавши, ми то дійдемо висновку, що ще та інші об'єкти, які треба враховувати під час вирішення завдань цього.. існує середовище (світ), що характеризується сукупністю наших припущень. Наприклад, існує світ, у якому припустили, що А.

— правдолюбець, отже, висловлену ним твердження (чи затвердження) істинно. Це тягне у себе різні слідства, що утворюють контекст даного гіпотетичного світу.. Є ще щось, що ми назвемо причинами, чи причинними связями.

(reasons), пов’язуваних висловлення про те чи іншому гіпотетичному світі. Якщо, А стверджує, що «У — брехун», і нам здається, що, А — правдолюбець, це твердження причина (підставою), з якої ми можемо стверджувати, що в гіпотетичному світі У — брехун, отже, усі твердження, які у репліках, виголошуваних У, брехливі. Відстежуючи такі зв’язки між висловлюваннями, можна відновити вихідне стан проблеми, тоді як результаті міркувань ми то дійдемо противоречию.

Природно, що це об'єкти можна представляти у програмі порізного. Онтологічний аналіз практично будь-коли призводить до єдиному способу уявлення. Для першу версію CLIPS-программы я вибрав таке уявлення описаних объектов:

;; Об'єкт statement (висловлювання) пов’язані з определенным.

;; персонажем (полі speaker).

;; Висловлення містить твердження (полі claim).

;; Висловлення має підставу — причину (полі reason),.

;; через яку можна доверять,.

;; і тэг (tag) — це то, можливо произвольный.

;; идентификатор.

(deftemplate statement.

(field speaker (type SYMBOL)).

(multifield claim (type SYMBOL)).

(multifield reason (type INTEGER) (default 0)).

(field tag (type INTEGER) (default 1)).

).

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

(statement (speaker A) (claim F A)).

Цей шаблон можна перекласти «людський» мову наступним образом:

«Існує висловлювання, зроблене персонажем На которм стверджується, що, А брехун і тэг цього висловлювання за умовчанням отримує значення 1». Зверніть увагу, що у полі reason також встановлено значення за умовчанням (це значення одно 0), тобто. ми можемо припустити, що жодних попередніх висловлювань, які б підтвердити дане, у цій завданню не было.

Зверніть увагу, що поля claim і reason мають уточнювач multifield, оскільки можуть утримувати кілька елементів даних (більш докладно звідси розказано в Керівництві пользователя).

Проте недостатньо лише явити у програмі висловлювання персонажів — нам знадобитися також виявити суть які у них тверджень. Далі, прийнявши певне припущення щодо правдивості чи брехливість персонажа, якому належить висловлювання, можна побудувати гіпотезу про істинності чи брехливість цього твердження. Із кожним таким твердженням зв’яжемо унікальний числової идентификатор.

;; Твердження, зміст якої, например,.

;; полягає у следующем,.

;; Т, А. ... означає, що, А правдолюбец;

;; F, А. ... означає, що, А лжец.

;; Твердження може мати під собой.

;; підставу (reason) — зазвичай тэг.

;; висловлювання (об'єкта statement) чи тэг.

;; іншого затвердження (об'єкта claim).

;; Твердження також характеризується ознакою scope,.

;; який може приймати значення «істина» чи «ложь».

(deftemplate claim.

(multifield content (type SYMBOL)).

(multifield reason (type INTEGER) (default 0)).

(field scope (type SYMBOL)).

).

Наприклад, розкривши вміст наведеного вище висловлювання на припущенні, що, А каже правду, одержимо такі твердження (об'єкт claim):

(claim (content F A) (reason 1) (scope truth)).

Отже, об'єкт claim успадковує вміст від об'єкта statement. Останній стає обгрунтуванням (reason) цього твердження. Поле scope об'єкта claim приймає значення припущення правдивості чи брехливість цього высказывания.

Ще нам знадобиться подання до програмі того світу (world), в якому ми час перебуваємо. Об'єкти world народжуються в останній момент, ми формуємо певні припущення. Треба мати можливість розрізняти різні безлічі припущень і ідентифікувати в програмі на той час, коли процес роздумів наводить нас до протиріччю. Наприклад, протиріччя між висловлюваннями Т (А) і F (A) відсутня, якщо вони істинними у різних світах, тобто. в різних припущеннях. Коли ви є сумніви з цього приводу, поверніться знову до прикладів від початку розділу А.4.

Світи представлятимемо у програмі наступним образом:

;; Об'єкт world представляє контекст,.

;; сформований певними предположениями.

;; про правдивості чи брехливість персонажей.

;; Об'єкт має унікальний ідентифікатор на полі tag,.

;; а сенс припущення — істинність чи брехливість -.

;; фіксується на полі scope.

(deftemplate world.

(field tag (type INTEGER) (default 1)).

(field scope (type SYMBOL) (default truth)).

).

Зверніть увагу, що з вказаних у шаблоні значеннях по вмовчанням ми можемо починати кожен процес обчислень з об'єкта world, має на полі значення 1, причому цей «світ» можна заселити висловлюваннями персонажів, що їх може бути вважаємо правдолюбцами. Таким чином можна форматувати базу фактів the-facts для завдання Р0 наступним образом:

;; Твердження, що, А лжец.

(deffacts the-facts.

(world).

(statement (speaker A) (claim F A)).

).

Якщо це оператор deffacts буде той самий файл, як і оголошення шаблонів (і навіть правила, про які йшлося піде нижче), то після завантаження цього файла у середу CLIPS нам знадобиться для запуску програми дати добро тільки команду reset.

А.4.3. Розробка правил.

У розділі ми розглянемо набір правил, який допомагає справитися з вырожденной формулюванням Р0 завдання про брехунах і правдолюбцах. Перші дві правила, unwrap-true і unwrap-false, витягають вміст висловлювання на припущенні, що персонаж, якому належить висловлювання, є відповідно правдолюбцем чи брехуном, на цьому підставі формують об'єкт claim.

;; Вилучення вмісту высказывания.

(defrule unwrap-true.

(world (tag ?N) (scope truth)).

(statement (speaker ?X) (claim $?Y) (tag ?N)).

=>

(assert (claim (content T? X) (reason ?N).

(scope truth))).

(assert (claim (content $?Y) (reason ?M).

(scope truth))).

).

(defrule unwrap-false.

(world (tag ?N) (scope falsity)).

(statement (speaker ?X) (claim $?Y) (tag ?N)).

=>

(assert (claim (content F? X) (reason ?N).

(scope falsity))).

(assert (claim (content NOT $?Y) (reason ?N).

(scope falsity)).

).

У кожному з наведених правил перший оператор в умовної частини робить припущення відповідно про правдивості чи брехливість персонажа, а другий оператор в заключної частини правила поширює припущення на формовані затвердження — об'єкти claim.

Далі нам знадобляться правила, які запровадять заперечення в висловлювання. Оскільки -Т (А) еквівалентно F (A), а -F (A) еквівалентно Т (А), то правила, виконують відповідні перетворення, написати досить просто. Аналіз результатів застосування цих правил значно спростить виявлення протиріч, що із певного предположения.

;; Правила отрицания.

(defrule not1.

?F.

(modify ?F (content F? P)).

).

(defrule not2.

?F.

(modify ?F (content T? P)).

).

;; Виявлення протистояння між припущенням о.

;; правдивості, і які випливають із нього фактами.

(defrule contra-truth.

(declare (salience 10)).

?W f-3 (claim (content F A) (reason 1) (scope truth)).

= => f-4 (claim (content T A) (reason 1) (scope truth)).

FIRE 2 contra-truth: f-1, f-2, f-4, f-3.

Statement is inconsistent if A is a knight. f-7 (claim (content F A) (reason 1) (scope falsity)).

FIRE 4 not2: f-6.

f-8 (claim (content T A) (reason 1) (scope falsity)).

FIRE 5 contra-falsity: f-5, f-2, f-7, f-8.

Statement is inconsistent if A is a knave. f-9 (world (tag 1) (scope contra)).

Вправа 1.

Читачам, бажаючим самостійно проэкспериментировать з цим програмою, я пропоную розглянути інший вырожденный випадок головоломок цього класса.

Припустимо, що персонаж, А стверджує: «Завжди кажу правду». До який категорії слід віднести цей персонаж?

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

Ваше завдання — модифікувати вищеописану програму в такий спосіб, щоб він давала висновок, що обидві контексту несуперечливі. Одне з можливих варіантів модифікації - увести до складу програми правила consisttruth і consist-falsity, розробивши їх за зразком правил contra-truth і contra-falsity. Ці правила мусять дати користувачеві знати, що з даному становищі протиріч нема, причому правила повинні активізуватися у разі, коли немає більше правил, претендують на увагу интерпретатора.

Зверніть увагу, що у завданнях цього недостатньо переконатися, що початкова припущення про істинності деякого висловлювання не призводить до суперечності. Необхідно що й перевірити, спричинить до протиріччю зворотне припущення. Якщо з’ясується, що його також несуперечливо, отже, завдання має єдиного решения.

А.4.4. Розширення набору правил — роботу з складовими высказываниями.

Розширимо тепрь можливості програми в такий спосіб, щоб він могла працювати з іншими складовими висловлюваннями. Це можна буде охопити у ній як вырожденный випадок, розглянутий у минулому розділі, а й складніші. За основу візьмемо таку головоломку.

Р4. Зустрічаються два персонажа, Проте й У, кожен із яких брехун, або прадолюбец. Персонаж, А каже: «Ми обидва брехуни.» До якої категорії слід віднести кожного з них?

У цьому завданню доведеться поводитися з конъюнкцией, оскільки твердження, висловлене персонажем А, моделюється выражением.

F (A) ^ F (B).

Цю конъюнкцию потрібно розділити на выражения-компоненты і проаналізувати їх несуперечність. Вочевидь, що, А то, можливо правдолюбцем, оскільки суперечить утвердженню, що міститься в його репліці. Але до програми повинна самостійно «розпакувати» цю конъюнкцию у тому, щоб дійти токому выводу.

Нам також знадобиться забезпечити програму і коштами обробки диз’юнкції, оскільки, якщо припустити, що, А бреше, потрібно буде оперувати з запереченням цього твердження, яке перетворює выражение.

F (A) ^ F (B) в.

F (A) v F (B).

Отже, у програмі потрібно включити правило виконання заперечення складових висловлювань та правило, яке «розуміло» б, що диз’юнкції на кшталт Т (А) насправді є припущеннями. Складене вираз T (A) v T (B) будемо обробляти, припустивши Т (А), і проаналізуємо, чи немає у ньому протиріччя. Якщо це не виявиться, то можна припустити, що T (A) v T (B) сумісно з твердженням у тому, що, А брехун, тобто. F (A). Але якщо припущення Т (А) призведе до несумісності, потрібно відмовитися його й припустити Т (У). Якщо це припущення призведе до несумісності, це озаначает, що затвердження Т (А) v Т (У) несумісне із припущенням F (A). Інакше Т (У) утворює частина совместимоц інтерпретації вихідного высказывания.

У CLIPS складові висловлювання найпростіше представляти з допомогою так званої «польської» (чи префиксной) нотації операцій. Сутність цього способу уявлення операцій у тому, що символ операції передує символів операндов. Кожен оператор має фіксований кількість операндов, тому завжди є можливість однозначно встановити область дії операцій навіть тоді, якщо операнды є вкладені висловлювання. Отже, вираз, представлене скобочной формою — (F (A)^T (B)), у польській записи буде мати вид.

NOT AND F A T B.

Найлегше відновити вихідний вид висловлювання, поданого до польської нотації, переглядаючи його справа-наліво. У цьому операнды зчитуються до того часу, доки зустрінеться який би їх оператор. Одержаний вираз оказвается операндом наступного оператора. У представленому вище вираженні У є операндом одномісного оператора Т, а пара операндов Т (В) і F (A) об'єднується оператором AND.

Поставивши у такий спосіб уявлення складових висловлювань, сформуємо правило виконання заперечення диз’юнктивної і конъюнктивной форм, у якому використовуватися функція flip, що заміняє «T» на «F» і наоборот.

(defrule not-or.

?F.

(modify ?F (content AND (flip ?P) ?X (flip ?Q) ?Y)).

).

(defrule not-and.

?F.

(modify ?F (content OR (flip ?P) ?X (flip ?Q) ?Y)).

).

Використання функції flip спрощує перетворення і дозволяє вийти з выражения.

NOT AND F A T B.

Прямо к.

OR T A F B,.

Минуя.

OR NOT F A NOT T B.

Функція flip визначено наступним образом:

(deffunction flip (?P).

(if (eq ?P T) then F else T).

).

Для спрощення ми обмежимося твердженнями як простих диз’юнкцій чи конъюнкций вида.

T (A)vT (B).

Или.

F (A)^T (B),.

Та годі використовувати складніші затвердження в форме.

F (B)^(T (A)vT (B)).

Или.

-(F (A)vF (B))^(T (A)vT (B)), оскільки вирішення більшості цікавих головоломок цілком досить простих выражений.

Найбільші складності при модифікації нашої програми пов’язані з обробкою дизъюнктивных висловів, оскільки висновок про наявність протиріччя може бути зроблений тільки після завершення аналізу всіх членів операндов диз’юнкції. Наприклад, немає протистояння між F (A) і T (A)vF (B). Протиріччя, яке виявиться при обробці першого операнда диз’юнкції Т (А) в припущенні F (A), буде локальним у тих Т (А). Але коли ми повернемося до вихідної диз’юнкції і спробуємо проаналізувати контекст F (B), то ніякого протиріччя виявлено нічого очікувати, і, отже, інтерпретація найдена.

Реалізувати такий аналіз локальних і глобальних протиріч можна, впорснувши у шаблон об'єкта claim атрибут contest:

(deftemplate claim.

(multifield content (type SYMBOL)).

(multifield reason (type INTEGER) (default 0)).

(field scope (type SYMBOL)).

(field context (type INTEGER) (default 0)).

).

Значення 0 на полі context означає, що ми маємо справу з глобальним контекстом, значення 1 — з локальним контекстом лівого операнда, а значение2 — з локальним контекстом правого операнда диз’юнкції. Нехай, наприклад, аналізується дизъюнкция.

T (A)vF (B),.

Причому Т (А) буде достеменним у контексті 1, а F (B) — достеменним у контексті 2. І тут все вираз буде істинним глобально, тобто. в контексті 0.

Структуру об'єкта world також потрібно модифікувати — доповнити неї полі context. Це дозволить відстежувати хід обчислень. Нехай, наприклад, об'єкт world має вид.

(world (tag 1) (scope truth) (context 2)).

Це означає, що це «світ» створено наступній парою припущень:. істинно висловлювання, має ідентифікатор (tag), рівний 1, і. правий операнд затвердження, що міститься у тому висловлюванні, має значення «истина».

Новий варіант шаблону об'єкта world наведено ниже.

;; Об'єкт world представляє контекст,.

;; сформований певними предположениями.

;; про правдтвости чи брехливість персонажей.

;; Об'єкт має унікальний ідентифікатор на полі tag,.

;; а сенс припущення — істинність чи брехливість -.

;; фіксується на полі scope.

;; У центрі context зберігається поточний контекст.

;; аналізованого операнда дизъюнкции.

;; 0 означає глобальний контекст дизъюнкции,.

;; 1 означає лівий операнд,.

;; 2 означає правий операнд.

(deftemplate world.

(field tag (type INTEGER) (default 1)).

(field scope (type SYMBOL) (default truth)).

(field context (type INTEGER) (default 0)).

).

Наступний крок — розробка правил, маневрують контекстом. Наведене нижче правило формує контекст для лівого операнда дизъюнкции.

(defrule left-or.

?W.

(modify ?W (context 1)).

(assert (claim.

(content ?P ?X) (reason ?N) (scope ?V).

(context 1))).

).

Це встановлює значення 1 на полі context об'єкта world т формує відповідний об'єкт claim.

У цій тим же принципом розробимо правило на формування контексту правого операнда дизъюнкции.

(defrule right-or.

?W.

(modify ?W (context 2)).

(assert (claim.

(content ?Q ?Y) (reason ?N) (scope ?V).

(context 2)).

).

Вправа 2.

Розробіть самостійно правило, яке оперувало б із об'єктом claim утримуємо твердження в конъюнктивной формі, як показано ниже.

(claim (content AND T A F B) (reason 1) (scope truth)).

Це має розділити таке твердження на два: суть першого — твердження, що, А — правдолюбець, а другого — твердження, що У — брехун. Новяе об'єкти claim має існувати нинішнього року контексті, певному в об'єкті world.

Далі розробимо правила, чутливі до контексту, які виявляти наявність суперечностей у аналізованих утверждениях.

;; Виявлення протистояння між припущенням о.

;; правдивості, і які випливають із нього фактами.

;; у різних контекстах однієї й тієї ж об'єкта world.

(defrule contra-truth-scope.

(declare (salience 10)).

(world (tag ?N) (scope truth) (context ?T)).

(claim.

(content T? X) (reason ?N) (scope truth).

(context ?P.S&: (< ?P.S ?T))).

?Q.

(printout t «Disjunct » ?T.

" is inconsistent with earlier truth context. «.

;; «Дизъюнкт » ?T.

;; «суперечить раніше встановленому контексту правдивості. «crlf).

(retract ?Q).

).

;; Виявлення протистояння між припущенням о.

;; брехливості й які випливають із нього фактами.

;; у різних контекстах однієї й тієї ж об'єкта world.

(defrule contra-falsity-scope.

(declare (salience 10)).

?W f-2 (statement (speaker A) (claim OR F A T B) (reason 0) (tag 1)).

CLIPS> (run).

FIRE 1 unwrap-true: f-1, f-2.

Assumption.

F is a knight, so (OR F A T B) is true.

= => f-3 (claim (content OR F A T B) (reason 1) (scope truth) (context 0)).

= => f-4 (claim (content T A) (reason 1) (scope truth) (context 0)).

FIRE 2 left-or: f-1, f-3.

= => f-5 (claim (content F A) (reason 1) (scope truth) (context 1)) f-6 (world (tag1) (scope truth) (context 1)).

FIRE 3 contra-truth-scope: f-6, f-4, f-5.

Disjunct 1 is inconsistent with earlier truth context. f-7 (claim (content T B) (reason 1) (scope truth) (context 2)) f-8 (world (tag 1) (scope truth) (context 2)).

FIRE 5 consist-truth: f-8, f-2.

Statement is consistent: f-9 (world (tag 1) (scope consist) (context 2)).

FIRE 6 true-knight: f-9, f-7.

B is a knight.

F (A) v F (B).

І проаналізуємо лівий операнд диз’юнкції. Через війну буде сформована коректна несуперечлива інтерпретація: У — правдолюбець, А — лжец.

Отримавши несуперечливу інтерпретацію висловлювання персонажа У, час торкнутися аналізу висловлювання персонажа А:

T (A)=> FALSE.

Оскільки правдивість, А суперечить сформованої раніше інтерпретації висловлювання персонажа У. Припустимо, що, А — брехун. Тогда:

F (A)=> -(T (A) v T (B))=> F (A) ^ F (B)=> FALSE.

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

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

T (B)=> F (A) v F (B).

Не було проаналізовано припущення, що У брехун. До того часу, це буде виконано, ми маємо права робити висновок, що висловлювання на формулюванні завдання суперечать друг другу.

Тому доведеться повернутися у ту точку процесу логічного аналізу, де було зроблено припущення про істинності лівого операнда в диз’юнкції, і проаналізувати замість нього правий операнд F (B). У цьому відразу ж потрапляє буде виявлено протиріччя між істинністю F (B) й раніше висловленим припущенням про правдивості персонажа У, але, не повернувшись тому і виконавши цей аналіз, ми змогли виявити це протиріччя. Тепер залишається проаналізувати слідство з припущення, що У — лжец.

F (B)=> -(F (A) v F (B))=> T (A) ^ T (B)=> FALSE.

Лише тепер з чистою совістю стверджувати, що немає несуперечливої інтерпретації висловлювань, які у умови завдання. Припущення про правдивості персонажа У призводить до конфлікту з виступом персонажа А, а припущення щодо брехливість У суперечить її ж словам.

Щоб на системі, використовує правила як основне програмного компонента, реалізувати відкіт (зворотне простежування), потрібно насамперед матимуть можливість відновити той контекст, який існував в останній момент, коли було сформульовано припущення, що призвело до не задовольняючому нас результату. Як засвідчили у розділі 5, одна з достоїнств продукционных систем, подібних CLIPS, у тому, що вони здатні виконати такий відкіт, не зберігаючи колишнього стану процесу обчислень, що докорінним чином відрізняла їхню відмінність від фундаментально рекурсивних мов програмування, як-от LISP і PROLOG. У разі необхідності виконати відкіт продукционные системи послідовно скасовують у порядку усі фінансові операції, пов’язані з додаванням даних в робочу пам’ять, хто був виконані, починаючи з місця повернення, у якому потрібно повернутися, до поточного етапу обчислень. Але у такий спосіб можна реалізувати повернення, лише припускаючи, що під час виконання операцій, наступних за точкою повернення, із робітничого пам’ять був віддалене нічого істотного, проте дії, модифікують стан робочої пам’яті, носили виключно аддитивный характер.

Приклади, подібні завданню Р6, істотно ускладнюють життя, оскільки їхнього рішення програма виконає деякі додаткові операції, у яких був необхідності під час вирішення завдань із єдиним висловлюваннями. 1) Зберігати інформацію про можливі точках повернення. 2) При виявленні протиріччя приймати рішення, виконувати або виконувати відкіт, і якщо виконувати, то яку саме точку. 3) Скасувати зміни, внесені до стан робочої пам’яті после.

«проходження» обраної точки повернення. 4) Відновити обчислення починаючи з місця возврата.

Розглянемо докладніше кожну з операцій.. Кожен об'єкт world має унікальний числової ідентифікатор, що зберігається у полі tag. Цю інформацію практично використовується під час вирішення завдань із єдиним виступом, оскільки ми завжди маємо працювати з у тому ж об'єктом world, пов’язаних із цим виступом. Але у рішенні завдань, оперують з кількома висловлюваннями, доведеться розрізняти затвердження, які породжені різними висловлюваннями в разных.

«світах». Принаймні того, як ми переходити від аналізу одних висловлювань решти, формуватимуться і призначає нові об'єкти world. Колишні об'єкти world потрібно залишати у стані, щоб за необхідності до них були ще раз повернутися. Це означає, що вектор world, з яким припинені операції (можливо, тимчасово), містив усю інформацію, яка знадобиться програмі поновлення роботи з ним.

У цьому та точка, у якій процес обчислень «переключився» нового об'єкт world, і буде, потенційної точкою повернення. Інформація, сохраняемая в об'єкті, включає знання у тому, яке припущення щодо правдивості чи брехливість персонажа було зроблено на цьому «світі» і які дизъюнкты (операнды складеного диз’юнктивного висловлювання) утвердженню, що міститься в висловлюванні персонажа, вже проаналізовані.. Оскільки кожна об'єкт world має власний унікальний ідентифікатор і кожен твердження (об'єкт claim) индексировано певним об'єктом world, можна досить просто з’ясувати, може бути протиріччя між різними «світами» (тобто. між твердженнями, пов’язані з різними об'єктами world). Залишається єдине питання — чи потрібно повертатися в раніше покинений «світ», тоді як поточному «світі» виявлено в протиріччя з ним. Ми будемо застосовувати стратегію пошуку глибину, що складається у цьому, що відкіт треба виконувати в тому разі, якщо протиріччя зберігається після повного завершення аналізу поточного «світу».. Якщо об'єкти world нумеруються послідовно, в міру їхнього формування, знадобиться розробити правило, яке за повернення покинений раніше «світ» знищить як поточний об'єкт world, і все проміжні об'єкти подібного типу, які за необхідності потім може бути відтворено.. Якщо колишній об'єкт world містить повну інформацію у тому, що не стані був залишать «світ», і затвердження у тому «світі» не суперечать цього стану, то ніщо корисно нам продовжити обчислення з точки возврата.

Почнемо модифікацію нашої програми сіло, що у шаблон об'єкта world ввімкнемо слот, у якому зберігатися ідентифікатор раніше покинутого «світу» (об'єкта), з яким даний об'єкт конфліктує. Це потрібно зробити з двом причин. 1) Нам знадобиться розрізняти випадки, у яких протиріччя творяться у межах й того «світу», від конфліктів між «світами». Якщо поточне висловлювання саме собою суперечливо (тобто. є парадоксом), немає сенсу виконувати відкіт в колишній світ образу і шукати у ньому владнання суперечностей. 2) Наявність такої слота дасть змогу розробити правило, що буде виконувати відкіт просто у цей покинений раніше «мир».

Нижче буде показано, що розв’язання проблеми можна уникнути реалізації правила, згаданого в п. 2., хоча й негаразд легко зробити, але міркування, сказані у п. 1., у разі залишаються у силе.

;; Об'єкт world представляє контекст,.

;; сформований певними предположениями.

;; про правдивості чи брехливість высказывания,.

;; належить деякому персонажу.

;; Об'єкт має унікальний ідентифікатор на полі tag,.

;; а сенс припущення — істинність чи брехливість -.

;; фіксується на полі scope.

;; Поле prior може містити идентификатор

;; об'єкта world, обробленого перед тем,.

;; як було створено даний об'єкт, і з яким данный.

;; об'єкт може потенційно конфликтовать.

;; У центрі context зберігається поточний контекст.

;; аналізованого операнда дизъюнкции.

(deftemplate world.

(field tag (type INTEGER) (default 1)).

(field scope (type SYMBOL) (default truth)).

(field prior (type INTEGER) (default 0)).

(field context (type INTEGER) (default 0).

).

Крім модифікації структури об'єкта, до виконання відкоту знадобиться розробити правила до виконання деяких ключових операцій. Ці операції перераховані нижче разом із ключовими словами, асоційованими з кожною з них.

. CHECK. Ця операція реалізує нормальний режим виконання обчислень під час аналізу припущень про правдивості чи брехливість.. CONTRA. Аналіз виявленого протиріччя. Виникло воно між двома висловлюваннями щодо одного й тому самому «світі»? Виникло чи протиріччя між двома висловлюваннями щодо одного й тому самому «світі», у різних контекстах, наприклад, у різних операндах диз’юнкції? Виникло воно між двома різними «світами», похідними від висловлювань різних персонажів?. CLEAN. Потому, як виявлено характер виниклого протиріччя, і для тим, як виконати відкіт в точку повернення, війни операція видаляє усі твердження, створені нинішнього року «світі».. BACK. Якщо ми маємо справу з протиріччям між поточним «світом» й раніше самотнім, війни операція виконує повернення у раніше покинений «світ», у якому ні цілком завершено аналіз всіх дизъюнктов або було проаналізовано припущення щодо брехливість.. QUIT. Нам знадобиться знайти ситуацію, що у разі, коли проаналізовані всіх можливих інтерпретації безлічі висловлювань, тобто. все диз’юнктивні галузі всі можливі комбінації припущень про правдивості чи брехливість висловлювань. Якщо за виявленні цій ситуації зірвалася знайти несуперечливу інтерпретацію, можна з всієї відповідальністю стверджувати, що умови завдання власними силами несумісні, тобто. немає його розв’язання термінах віднесення кожного з персонажів до визначеної категорії - до брехунам чи правдолюбцам.

Вкотре модифікуємо визначення шаблону об'єкта world — внесемо в нього полі TASK, у якому представлені перелічені завдання. Це полі буде використано правилами, які потрібні ще попереду розробити. Механізм роботи з завданнями подібний до того, використовуваний для маніпулювання лексемами управління (control tokens), описаними в розділах 5 і 14. Цей механізм активізує певні правила. Однак цьому ми думати використовувати стратегію MEA чи спеціальні вектори. Лексеми управління будуть просто зберігатися у певному полі об'єкта world. Але результат буде хоча б — ця лексема буде використано для активізації певного правила.

;; Об'єкт world представляє контекст,.

;; сформований певними предположениями.

;; про правдивості чи брехливість высказывания,.

;; належить деякому персонажу.

;; Об'єкт має унікальний идентификатор

;; на полі tag, який соответствует.

;; тегу высказывания.

;; Сенс припущення — істинність чи брехливість -.

;; фіксується на полі scope.

;; Поле TASK містить одна з перечисленных.

;; нижче значений:

;; CHECK — аналіз припущень о.

;; правдивості чи брехливість высказывания;

;; CONTRA — аналіз виявленого противоречия;

;; CLEAN — видаляє усі твердження, созданные.

;; в суперечливому світі ;

;; BACK — відкіт в точку возврата;

;; QUIT — припинення процесса.

;; Поле prior може містити идентификатор

;; об'єкта world, обробленого перед тем,.

;; як було створено даний об'єкт, і з яким данный.

;; об'єкт може потенційно конфликтовать.

;; У центрі context зберігається поточний контекст.

;; аналізованого операнда дизъюнкции.

(deftemplate world.

(field tag (type INTEGER) (default 1)).

(field scope (type SYMBOL) (default truth)).

(field task (type SYMBOL) (default check)).

(field prior (type INTEGER) (default 0)).

(field context (type INTEGER) (default 0)).

).

Тепер розробимо правила, котрі виконуватимуть перелічені вище операції. З іншого боку, потрібно внести деякі зміни й у Правила, розроблені для колишньої версії программы.

Выявление противоречий.

У процесі вирішення завдань про правдолюбцах і брехунах може бути виявлено логічні протиріччя двох типів:. між висловлюваннями щодо одного й тому самому «світі», але, можливо, у різних контекстах диз’юнктивного затвердження;. між висловлюваннями у різних «мирах».

Для аналізу варіантів виникнення протиріч доцільно розробити чотири правила. Розіб'ємо першу із зазначених ситуацій на два випадку:. можна знайти протиріччя між припущенням і висловлюваннями, що у тому ж самому контексті (наприклад, коли з предположения.

Т (А) безпосередньо слід висновок F (A), як у заяві персонажа.

А: F (A));. можна знайти протиріччя між припущенням одним із дизъюнктов складеного висловлювання, як у заяві персонажа А: T (B) v F (A).

Ситуацію, коли протиріччя між висловлюваннями в різних «світах», теж розділити на два випадку:. поточний «світ» у припущенні, що персонаж каже правду (на полі scope об'єкта world міститься значення truth);. поточний «світ» у припущенні, що персонаж бреше (на полі scope об'єкта world міститься значення falsity).

Якщо, припустивши правдивість персонажа, програма знайде протиріччя, вона повинна переважно проаналізувати та досудове слідство з протилежного припущення — що персонаж брехун. І лише за умови, що обидва варіанти припущення призводять до протиріччю, треба зробити откат.

Аналіз кожного з чотирьох варіантів ситуації виконується окремим правилом, програми яких нижче. Зверніть увагу, що це правила мають досить високий пріоритет (значення параметра salience). Це забезпечує їх першочергову активізацію механізмом дозволу конфліктів між правилами. З іншого боку, правила, що аналізують розбіжність у межах однієї й тієї ж «світу», мають вищий пріоритет, аніж правило, що аналізують протиріччя між різними «світами». Тим самим було забезпечується реалізація стратегії наскільки можна уникати відкотів у процесі рішення проблемы.

;; ЯКЩО можна знайти протиріччя між предположением.

;; і похідними від цього фактами у межах и.

;; тієї самої «світу» й у тому ж контексте,.

;; ТЕ зафіксувати у собі удалить.

;; суперечливі затвердження (об'єкти claim).

;; з убозівської бази фактов.

(defrule contradiction.

(declare (salience 100)).

?W.