Листинг А.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)
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))
Statement is inconsistent if A is a knight.
<= = f-3 (claim (content F A) (reason 1) (scope truth))
<= = f-4 (claim (content T A) (reason 1) (scope truth))
<= = f-1 (world (tag 1) (scope truth))
= => f-5 (world (tag 1) (scope falsity))
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))
<= = f-6 (claim (content NOT F A) (reason 1) (scope falsity))
= => f-8 (claim (content T A) (reason 1) (scope falsity))
Statement is inconsistent if A is a knave.
<= = f-5 (world (tag 1) (scope falsity))
= => f-9 (world (tag 1) (scope contra))
Читателям, желающим самостоятельно проэкспериментировать с этой программой, я предлагаю рассмотреть другой вырожденный случай головоломок этого класса.
Предположим, что персонаж А утверждает : «Я всегда говорю правду». К какой категории следует отнести этот персонаж?
В такой постановке задача имеет неоднозначное решение. Предположение, что А правдолюбец, не приводит нас к противоречию. Но точно так же не приводит к противоречию и предположение, что А – лжец.
Ваша задача – модифицировать описанную выше программу таким образом, чтобы она давала заключение, что оба контекста непротиворечивы. Один из возможных вариантов модификации – ввести в состав программы правила 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 <- (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 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 <- (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 T A F B ) (reason 1) (scope truth))
Это правило должно разделить такое утверждение на два: суть первого – утверждение, что А – правдолюбец, а второго – утверждение, что В – лжец. Новяе объекты claim должны существовать в текущем контексте, определенном в объекте world.
Далее разработаем правила, чувствительные к контексту, которые будут выявлять наличие противоречий в анализируемых утверждениях.