|
Реферат: Программирование на языке CLIPS (Компьютеры)
Министерство общего и профессионального образования
Российской Федерации
Кубанский Государственный Технологический Университет
Курсовая работа на тему:
ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ CLIPS
Работу выполнил
студент группы 01-
КТ-22 факультета
КТАС Мариненко А.
А.
Краснодар 2001
СОДЕРАЖНИЕ
. А.1. Краткая история CLIPS 3
. А.2. Правила и функции в CLIPS
3
. А.3. Обектно-ориентированные средства в CLIPS
10
. А.4. Задача «Правдолюбцы и лжецы» 15
. А.5 Стиль программирования на языке CLIPS 66
А.1. КРАТКАЯ ИСТОРИЯ CLIPS
Название языка CLIPS – аббревиатура от C Language Integrated
Production System. Язык был разработан в центре космических исследований
NASA
{NASA’s Johnson Space Center} в середине 1980-х годов и во многом
сходен с языками , созданными на базе LIPS, в частности OPS5 и ART.
Использование C в качестве языка реализации объясняется тем, что компилятор
LISP не поддерживается частью распространенных платформ, а также сложностью
интеграции LISP-кода в приложения, которые используют отличный от LIPS язык
программирования. Хотя в то время на рынке уже появились программные
средства для задач искусственного интеллекта, разработанные на языке C ,
специалисты из NASA решили создать такой продукт самостоятельно.
Разработанная ими система в настоящее время доступна во всем мире, и нужно
сказать, что по своим возможностям она не уступает множеству гораздо более
дорогих коммерческих продуктов.
Первая версия представляет собой, по сути, интерпретатор порождающих
правил. Процедурный язык и объективно-ориентированное расширение CLIPS
Object-Oriented Language {COOL} были включены в этот программный продукт
только в 1990-х годах. Существующая в настоящее время версия может
эксплуатироваться на платформах UNIX, DOS, Windows и Macintosh. Она
является хорошо документированным общедоступным программным продуктом и
доступна по сети FTR с множества университетских сайтов. Исходный код
программного пакета CLIPS распространяется совершенно свободно и его можно
установить на любой платформе, поддерживающей стандартный компилятор языка
C. Однако я бы рекомендовал пользоваться официальной версией для
определенной платформы, поскольку такие версии оснащены пользовательским
интерфейсом, включающим меню команд и встроенный редактор.
Это Приложение организовано следующим образом. В разделе А.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
< необязательный комментарий >
< необязательное объявление >
< предпосылка_1 >
……………….
< предпосылка_m >
=>
< действие_1 >
………………..
< предпосылка_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 может
быть присвоено любое целочисленное значение в диапазоне [-10000, 10000].
Если параметр 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 не имеют ничего общего с шаблонами C++.) Шаблон выглядит примерно
так:
(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 является конкретным классом, т.е. возможно создание экземпляров
этого класса (альтернативный тип – абстрактный класс, который играет ту
же роль, что и виртуальный класс в C++);
. экземпляры класса 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)
)
Можно было бы, конечно, включить в программу и следующее правило mag-
in:
(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
Читателям, желающим самостоятельно проэкспериментировать с этой
программой, я предлагаю рассмотреть другой вырожденный случай головоломок
этого класса.
Предположим, что персонаж А утверждает : «Я всегда говорю правду». К
какой категории следует отнести этот персонаж?
В такой постановке задача имеет неоднозначное решение.
Предположение, что А правдолюбец, не приводит нас к противоречию. Но точно
так же не приводит к противоречию и предположение, что А – лжец.
Ваша задача – модифицировать описанную выше программу таким образом,
чтобы она давала заключение, что оба контекста непротиворечивы. Один из
возможных вариантов модификации – ввести в состав программы правила consist-
truth и 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 ?S&: (< ?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) При обнаружении противоречия принимать решение, выполнять или не
выполнят | |
