Иллюстрированный самоучитель по введению в экспертные системы

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


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

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

Р4. Встречаются два персонажа, А и В, каждый из которых либо лжец, либо правдолюбец. Персонаж А говорит: "Мы оба лжецы". К какой категории следует отнести каждого из них?

В этой задаче нам придется иметь дело с конъюнкцией, поскольку утверждение, высказанное персонажем А, моделируется выражением

Эту конъюнкцию нужно разделить на выражения-компоненты и проанализировать их непротиворечивость. Очевидно, что А не может быть правдолюбцем, поскольку это противоречит утверждению, которое содержится в его реплике. Но программа должна самостоятельно "распаковать" эту конъюнкция для того, чтобы прийти к такому выводу.

Нам также понадобится снабдить программу и средствами обработки дизъюнкции, поскольку, если предположить, что А лжет, нужно будет оперировать с отрицанием этого утверждения, которое преобразует выражение

Т(А) v Т(B).

Таким образом, в программу нужно включить правило выполнения отрицания составных высказываний и правило, которое "понимало" бы, что дизъюнкты вроде Т(А) в действительности являются предположениями. Составное выражение Т(А) v T(B) будем обрабатывать, предположив Т(А), и проанализируем, нет ли в нем противоречия. Если таковое не обнаружится, то можно предположить, что Т(А) v Т(B) совместимо с утверждением о том, что А лгун, т.е. F(A). Но если предположение Т(А) приведет к несовместимости, то нужно отказаться от него и предположить Т(Е). Если и это предположение приведет к несовместимости, то это означает, что утверждение Т(А) v T(B) несовместимо с предположением F(A). В противном случае Т(В) образует часть совместимой интерпретации исходного высказывания.

В CLIPS составные высказывания проще всего представлять с помощью так называемой "польской" (или префиксной) нотации операций.
Суть этого способа представления операций состоит в том, что символ операции предшествует символам операндов. Каждый оператор имеет фиксированное количество операндов, а потому всегда существует возможность однозначно установить область действия операции даже в случае, если операнды представляют собой вложенные выражения. Таким образом, выражение, представленное скобочной формой —(F(/4) ^ Т(В)), в польской записи будет иметь вид

NOT AND F А Т В.

Легче всего восстановить исходный вид выражения, представленного в польской нотации, просматривая его справа налево. При этом операнды считываются до тех пор, пока не встретится объединяющий их оператор. Полученное выражение оказывается операндом следующего оператора. В представленном выше выражении В является операндом одноместного оператора Т, а пара операндов Т(В) и F(A) объединяется оператором AND.



Задавшись таким способом представления составных высказываний, сформируем правило выполнения отрицания дизъюнктивной и конъюнктивной форм, в котором будет использоваться функция flip, заменяющая "Т" на "F" и наоборот.

(defrule not-or

?F <- (claim (content NOT OR ?P ?X ?Q ?Y)) =>

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

(defrule not-and

?F <- (claim (content NOT AND ?P ?X ?Q ?Y)) =>

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

Использование функции flip упрощает преобразование и позволяет перейти от выражения

NOT AND F А Т В

прямо к

OR Т A F В,

минуя

OR NOT F A NOT Т В.

Функция flip определена следующим образом:

(def function flip (?P)

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

Для упрощения мы ограничимся утверждениями в виде простых дизъюнкций или конъюнкций вида

Т(А) v Т(В)

или

F(A) ^ T(B),

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

F(B) ^ (T(А) v T)B))

или

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

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


Например, нет противоречия между F(A) и Т(А) v F(B). Противоречие, которое обнаружится при обработке первого операнда дизъюнкции ДЛ) в предположении F(A), будет локальным в контексте Т(А). Но если мы вернемся к исходной дизъюнкции и попробуем проанализировать контекст F(B), то никакого противоречия обнаружено не будет, и, следовательно, интерпретация найдена.

Реализовать такой анализ локальных и глобальных противоречий можно, добавив в шаблон объекта claim атрибут context:

(def template 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) v F(B)

причем Т(А) будет истинным в контексте 1, a 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 <- (world (tag ?N) (context 0))

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

    (scope ?V)) =>

    (modify ?W (context 1)) (assert (claim

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

    (context 1))) )

    Это правило устанавливает значение 1 в поле context объекта world и формирует соответствующий объект claim.

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

    (defrule right-or

    ?W <- (world (tag ?N) (context 1))

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

    (scope ?V)) =>

    (modify ?W (context 2)) (assert (claim

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

    )

    Упражнение 2

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

    (claim (content AND Т A F В) (reason 1) (scope truth))

    Это правило должно разделить такое утверждение на два: суть первого — утверждение, что А — правдолюбец, а второго — утверждение, что В — лжец. Новые объекты claim должны существовать в текущем контексте, определенном в объекте world.

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

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

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

    ;; в разных контекстах одного и того же объекта world,

    (defrule contra-truth-scope

    (declare (salience 10)) (world (tag ?N)

    (scope truth) (context ?T)) (claim

    (content Т ?Х) (reason ?N) (scope truth)

    (context ?S&:(< ?S ?T))) ?Q <- (claim

    (content P ?x) (reason ?N)

    (scope truth) (context ?T)) =>

    (printout t "Disjunct " ?T

    " is inconsistent with earlier truth context. "



    ;; "Дизъюнкт " ?T

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

    " crlf)

    (retract ?Q)

    )

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

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

    ;; в разных контекстах одного и того же объекта world.

    (defrule contra-falsity-scope (declare (salience 10))

    ?W <- (world (tag ?N) (scope falsity)

    (context ?T» (claim

    (content F ?X) (reason ?N) (scope falsity)

    (context ?S&:(< ?S ?T))) ?Q <- (claim (content Т ?Х)

    (reason ?N)

    (scope falsity) (context ?T)) =>

    (printout t "Disjunct " ?T

    " is inconsistent with earlier falsity context."

    ;; "Дизъюнкт " ?T

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

    crlf)

    (retract ?Q) )

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

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

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

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

    (defrule contra-truth

    (declare (salience 10))

    ?W <- (world (tag ?N) (scope truth))

    ?P <- (claim (content Т ?Х) (reason ?N)

    (context ?S)

    (scope truth) ) ?Q <- (claim (content F ?X)

    (reason ?N) (context ?S)

    (scope truth) ) =>

    (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 <- (world (tag ?N) (scope falsity))

    ?P <- (claim (content F ?X) (reason ?N)

    (context ?S) (scope falsity))

    ?Q <- (claim (content Т ?Х) (reason ?N)

    (context ?S)(scope falsity)) =>

    (printout t

    "Statement is inconsistent whether " ?X

    " is knight or knave."



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

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

    crlf)

    (modify ?W (scope contra) )

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

    (defrule consist-truth

    (declare (salience -10))

    ?W <- (world (tag ?N) (scope truth))

    (statement (speaker ?Y) (tag ?N)) =>

    (printout t

    "Statement is consistent:"

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

    crlf)

    (modify ?W (scope consist)

    )

    (defrule consist-falsity

    (declare (salience -10)) ?W <- (world (tag ?N)

    (scope falsity)) (statement (speaker ?Y) (tag ?N)) =>

    (printout t

    "Statement is consistent:"

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

    crlf) (modify ?W (scope consist)

    )

    (defrule true-knight

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

    ?C <- (claim (content T ?X) (reason ?N) =>

    (printout t

    ?X "is a knight" ;; ?X "- правдолюбец"

    crlf) (retract ?C)

    )

    (defrule false-knave

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

    ?C <- (claim (content F ?X) (reason ?N))

    (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-trues f-1,f-2

    Assumption

    A 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-1 (world (tag 1) (scope truth) (context 0))

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

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

    Disjunct 1 is inconsistent with earlier truth context.

    <== f-5 (claim (content F A) (reason 1)

    (scope truth) (context 1)) FIRE 4 right-or: f-6,f-3 .

    ==> f-7 (claim (content Т В) (reason 1)

    (scope truth) (context 2))

    <== f-6 (world (tag 1) (scope truth)

    (context 1))

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

    (context 2))

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

    Statement is consistent:

    <== f-8 (world (tag 1) (scope truth) (context 2))

    ==> f-9 (world (tag 1) (scope consist) (context 2))

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

    В is a knight

    <== f-7 (claim (content Т В) (reason 1)

    (scope truth) (context 2))

    FIRE 7 true-knight: f-9,f-4

    A is a knight

    <== f-4 (claim (content Т A) (reason 1)

    (scope truth) (context 0))

    CLIPS>


    Содержание раздела