;; Выявление противоречия между предположением о
;; правдивости и следующими из него фактами
;; в разных контекстах одного и того же объекта 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 <- (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 T ?X) (reason ?N)
(scope falsity) (context ?T))
=>
(printout t “Disjunct “ ?T
“ is inconsistent with earlier falsity context. “
;; “Дизъюнкт” ?T
;; “ противоречит ранее установленному контексту лживости. “
crlf)
retract ?Q)
)
Нам потребуется модифицировать и прежний вариант правила contra-truth.
;; Выявление противоречия между предположением о
;; правдивости и следующими из него фактами
;; в одном и том же контексте оджного и того же объекта world.
(defrule contra-truth
(declare (salience 10))
?W <- (world (tag ?N) (scope truth))
?P <- (claim (content T ?X) (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 T ?X) (reason ?N) (context ?S)
(scope falsity))
=>
(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 <- (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-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-1 (world (tag 1) (scope truth) (context 0))
= => 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-5 (claim (content F A) (reason 1) (scope truth) (context 1))
FIRE 4 right-or: f-6, f-3
= => f-7 (claim (content T B) (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
B is a knight
<= = f-7 (claim (content T B) (reason 1) (scope truth) (context 2))
FIRE 7 true-knight: f-9, f-4
A is a knight
<= = f-4 (claim (content T A) (reason 1) (scope truth) (context 0))
CLIPS>
А.5. Обратное прослеживание и множество контекстов
Модифицируем программу таким образом, чтобы она могла справиться и с задачами этого класса в более сложной постановке. Речь идет о задачах, в которых несколько персонажей произносят реплики. Пример такого рода головоломки приведен ниже.
Р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
Только теперь можно с чистой совестью утверждать, что не существует непротиворечивой интерпретации высказываний, приведенных в условии задачи. Предположение о правдивости персонажа В приводит к конфликту с высказыванием персонажа А, а предположение о лживости В противоречит его же словам.
Чтобы в системе, использующей правила в качестве основного программного компонента, реализовать откат (обратное прослеживание), нужно в первую очередь иметь возможность восстановить тот контекст, который существовал в момент, когда было сформулировано предположение, приведшее к не удовлетворяющему нас результату. Как было показано в главе 5, одно из достоинств продукционных систем, подобных CLIPS, состоит в том, что они способны выполнить такой откат, не сохраняя прежнего состояния процесса вычислений, что коренным образом отличает их от фундаментально рекурсивных языков программирования, таких как LISP и PROLOG. При возникновении необходимости выполнить откат продукционные системы последовательно отменяют в обратном порядке все операции, связанные с добавлением данных в рабочую память, которые были выполнены, начиная с точки возврата, в которую нужно вернуться, вплоть до текущего этапа вычислений. Но таким способом можно реализовать возврат, только предполагая, что в ходе выполнения операций, следующих за точкой возврата, из рабочей память не было удалено ничего существенного, а все действия, модифицирующие состояние рабочей памяти, носили исключительно аддитивный характер.
Примеры, подобные задаче Р6, существенно усложняют жизнь, поскольку для их решения программа должна выполнять некоторые дополнительные операции, в которых не было необходимости при решении задач с единственным высказыванием.
(1) Сохранять информацию о возможных точках возврата.