Рефераты

Программирование на языке CLIPS

. Выражение не содержит логических связок, таких как И или ИЛИ, или

кванторов, вроде квантора общности (все) и прочих.

. Отсутствует ответная реплика.

В то же время существенные черты проблемы в этом варианте

присутствуют. Мы по-прежнему должны попытаться отыскать непротиворечивую

интерпретацию высказывания А, т.е. должны реализовать две задачи,

присутствующие в любых вариантах подобной головоломки:

. формировать альтернативные интерпретации высказываниям;

. анализировать наличие противоречий.

Вы увидите, что для выполнения этих двух задач потребуется

использовать механизм, очень близкий к тем, которые мы рассматривали при

описании систем обработки правдоподобия в главах 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

(printout t crlf

“Statement is inconsistent if “ ?Y “ is a knight.”

;; “Высказывание противоречиво, если “ ?Y “ правдолюбец.”

t crlf)

(retract ?Q)

(retract ?P)

(modify ?W (scope falsity))

)

Если предположить, что исходное высказывание было правдивым, то в

дальнейшем обнаруживается противоречивая пара утверждений, которые затем

удаляются из рабочей памяти, а значение «правдивости» предположения в

объекте world изменяется на falsity (лживость). Если же после этого также

будет обнаружено противоречие, то мы приходим к выводу о глобальной

несовместимости условий задачи, т.е. в данной постановке мы имеем дело с

логическим парадоксом.

;; Выявление противоречия между предположениями о

;; лживости и следующими из него фактами.

(defrule contra-falsity

(declare (salience 10))

?W

(printout t crlf

“Statement is inconsistent if “ ?Y “ is a knave.”

;; “Высказывание противоречиво, если “ ?Y “ лжец.”

t crlf)

(modify ?W (scope contra))

)

Правило sweep обеспечивает проверку, все ли следствия из неверного

предположения удалены из памяти.

;; Удалить из базы фактов все утверждения,

;; которые следуют из предположения о правдивости.

(defrule sweep

(declare (salience 20))

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

?F

(retract ?F)

)

Обратите внимание на то, что правила contra-truth, contra-falsity и

sweep имеют более высокий приоритет (значение параметра salience), чем

другие правила. Этим обеспечивается как можно более ранее обнаружение

противоречия, а следовательно, и удаление из базы фактов утверждений,

сделанных на основе предположения, приведшего к противоречию.

Если теперь запустить на выполнение программу, представив ей

исходный набор фактов, соответствующих условию задачи Р0, то программа

обнаружит, что оба контекста противоречивы. Другими словами, независимо от

того, предполагаем ли мы, что А говорит правду или лжет, программа

обнаружит противоречие в контексте world. Трассировка программы в этом

случае представлена в листинге А.1. Строки, выведенные курсивом, -

сообщения основной программы, а прочие – сообщения программы трассировки.

Для удобства строки, указывающие на активизацию правил, представлены

полужирным шрифтом.

Листинг А.1. Трассировка решения задачи Р0

CLIPS> (reset)

= => f-0 (initial-fact)

= => f-1 (world (tag 1) (scope truth))

= => f-2 (statement (speaker A) (claim F A) (reason 0) (tag 1))

CLIPS> (run)

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

Assumption:

A is a knight, so (T A) is true.

= => 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-5 (world (tag 1) (scope falsity))

FIRE 3 unwrap-false: f-5, f-2

Assumption

A is a knave, so (T A) is false.

= => f-6 (claim (content NOT F A) (reason 1) (scope falsity))

= => 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

(printout t “Disjunct “ ?T

“ is inconsistent with earlier falsity context. “

;; “Дизъюнкт” ?T

;; “ противоречит ранее установленному контексту лживости. “

crlf)

retract ?Q)

)

Нам потребуется модифицировать и прежний вариант правила contra-

truth.

;; Выявление противоречия между предположением о

;; правдивости и следующими из него фактами

;; в одном и том же контексте оджного и того же объекта world.

(defrule contra-truth

(declare (salience 10))

?W

(printout t

“Statement is inconsistent if “?X “ is a knight”

;; “Высказывание противоречиво, если “? X

;; “ правдолюбец.”

crlf)

(retract ?Q)

(retract ?P)

(modify ?W (scope falsity) (context 0)

)

;; Выявление противоречия между предположением о

;; лживости и следующими из него фактами

;; в одном и том же контексте одного и того же объекта world.

(defrule contra-falsity

(declare (salience 10))

?W

(printout t

“Statement is inconsistent whether “ ?X

“ is a knight or knave.”

;; “Высказывание противоречиво, независимо от того,”

;; “является ли “ ?X “ прадолюбцем или лжецом.”

crlf)

(modify ?W (scope contra)

)

Поскольку теперь постановка задачи усложнилась по сравнению с

вырожденным случаем, имеет смысл включить в программу распечатку

предположений о характеристиках персонажей, упомянутых в высказываниях.

(defrule consist-truth

(declare (salience -10))

?W

(printout t

“Statement is consistent:”

;; “Высказывание непротиворечиво:”

crlf)

(modify ?W (scope consist)

)

(defrule consist-falsity

(declare (salience -10))

?W

(printout t

“Statement is consistent:”

;; “Высказывание непротиворечиво:”

crlf)

(modify ?W (scope consist)

)

(defrule true-knight

(world (tag ?N) (scope consist))

?C

(printout t

?X “is a knight”

;; ?X “ – правдолюбец”

crlf)

(retract ?C)

)

(defrule false-knave

(world (tag ?M) (scope consist))

?C

(printout t

?X “ is a knave”

;; ?X “ – лжец”

crlf)

(retract ?C)

)

Ниже приведенное правило разделения операции конюънкции, которое

ранее мы предлагали вам разработать самостоятельно. Обратите внимание на

то, что в нем также отслеживается контекст, хотя в данном случае без этого

можно было бы и обойтись.

(defrule conj

(world (tag ?N) (context ?S))

(claim (content AND ?P ?X ?Q ?Y) (reason ?N)

(scope ?V))

=>

(assert (claim

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

(context ?S)))

(assert (claim

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

(context ?S)))

)

Прежде чем запустить программу на выполнение, сформируем исходные

факты в соответствии с условиями задачи Р4:

(deffacts the-facts

(world)

(statement (speaker A) (claim AND F A F B ) (tag 1))

)

После запуска программы в режиме трассировки интерпретатор

сформирует распечатку процесса ее выполнения, приведенную в листинге А.2.

Листинг А.2. Трассировка решения задачи Р4

CLIPS> (reset)

= => f-0 (initial-fact)

= => f-1 (world (tag 1) (scope truth) (context 0))

= => 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

А.5. Обратное прослеживание и множество контекстов

Модифицируем программу таким образом, чтобы она могла справиться и с

задачами этого класса в более сложной постановке. Речь идет о задачах, в

которых несколько персонажей произносят реплики. Пример такого рода

головоломки приведен ниже.

Упражнение 3

Р5. Встречаются два человека, А и В, которые заявляют следующее.

А: «Я говорю правду, либо В лжец».

В: «А говорит правду, либо я лжец».

К какой категории следует отнести каждый из персонажей? (Решите эту

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

применялась ранее в этом Приложении.)

Задача анализа высказываний нескольких персонажей потребует

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

«обратное прослеживание на основе анализа зависимостей» (dependency-

directed backtracking).

От программы потребуется выполнить обратное прослеживание (откат) в

следующих ситуациях:

. когда обнаружится конфликт между текущим «миром» и ранее существовавшим,

причем в ранее существовавшем «мире» предполагается истинность

высказывания, но не была проанализирована его лживость;

. когда обнаружится конфликт между текущим «миром» и ранее существовавшим,

причем в ранее существовавшем «мире» был проанализирован только один

операнд в составном дизъюнктивном утверждении.

Чтобы смысл этих формулировок стал более понятным, рассмотрим

следующий пример.

Р6. Встречаются два человека, А и В, которые заявляют следующее.

А: «Хотя бы один из нас говорит правду».

В: «Хотя бы один из нас лжец».

К какой категории следует отнести каждый из персонажей?

Высказывания персонажей представим в следующем виде:

А: T(A) v T(B)

B: F(A) v F(B)

Начнем с заявления персонажа В

T(B)=>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

Только теперь можно с чистой совестью утверждать, что не существует

непротиворечивой интерпретации высказываний, приведенных в условии задачи.

Предположение о правдивости персонажа В приводит к конфликту с

высказыванием персонажа А, а предположение о лживости В противоречит его же

словам.

Чтобы в системе, использующей правила в качестве основного

программного компонента, реализовать откат (обратное прослеживание), нужно

в первую очередь иметь возможность восстановить тот контекст, который

Страницы: 1, 2, 3, 4


© 2010 БИБЛИОТЕКА РЕФЕРАТЫ