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

то нужно отказаться от него и предположить Т (В). Если и это предположение

приведет к несовместимости, то это озаначает, что утверждение

Т (А) 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, 5, 6, 7, 8