45186 (664345), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

?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.

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

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

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

;; в разных контекстах одного и того же объекта 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. Обратное прослеживание и множество контекстов

Модифицируем программу таким образом, чтобы она могла справиться и с задачами этого класса в более сложной постановке. Речь идет о задачах, в которых несколько персонажей произносят реплики. Пример такого рода головоломки приведен ниже.

Упражнение 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

Только теперь можно с чистой совестью утверждать, что не существует непротиворечивой интерпретации высказываний, приведенных в условии задачи. Предположение о правдивости персонажа В приводит к конфликту с высказыванием персонажа А, а предположение о лживости В противоречит его же словам.

Чтобы в системе, использующей правила в качестве основного программного компонента, реализовать откат (обратное прослеживание), нужно в первую очередь иметь возможность восстановить тот контекст, который существовал в момент, когда было сформулировано предположение, приведшее к не удовлетворяющему нас результату. Как было показано в главе 5, одно из достоинств продукционных систем, подобных CLIPS, состоит в том, что они способны выполнить такой откат, не сохраняя прежнего состояния процесса вычислений, что коренным образом отличает их от фундаментально рекурсивных языков программирования, таких как LISP и PROLOG. При возникновении необходимости выполнить откат продукционные системы последовательно отменяют в обратном порядке все операции, связанные с добавлением данных в рабочую память, которые были выполнены, начиная с точки возврата, в которую нужно вернуться, вплоть до текущего этапа вычислений. Но таким способом можно реализовать возврат, только предполагая, что в ходе выполнения операций, следующих за точкой возврата, из рабочей память не было удалено ничего существенного, а все действия, модифицирующие состояние рабочей памяти, носили исключительно аддитивный характер.

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

1. Сохранять информацию о возможных точках возврата.

2. При обнаружении противоречия принимать решение, выполнять или не выполнять откат, а если выполнять, то в какую именно точку.

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

4. Возобновить вычисления начиная с точки возврата.

Рассмотрим подробнее каждую из этих операций.

• Каждый объект world имеет уникальный числовой идентификатор, который хранится в поле tag. Эта информация практически не используется при решении задач с единственным высказыванием, поскольку мы всегда имеем дело с одним и тем же объектом world, связанным с этим высказыванием. Но при решении задач, оперирующих с несколькими высказываниями, нам придется различать утверждения, которые порождены разными высказываниями в разных «мирах». По мере того, как мы будем переходить от анализа одних высказываний к другим, будут формироваться и новые объекты world. Прежние объекты world нужно оставлять в таком состоянии, чтобы при необходимости к ним можно было еще раз вернуться. Это означает, что вектор world, с которым прекращены операции (возможно, временно), содержал всю информацию, которая потребуется программе для возобновления работы с ним. При этом именно та точка, в которой процесс вычислений «переключился» на новый объект world, и будет, потенциальной точкой возврата. Информация, сохраняемая в объекте, включает знание о том, какое предположение о правдивости или лживости персонажа было сделано в этом «мире» и какие дизъюнкты (операнды составного дизъюнктивного выражения) в утверждении, содержащемся в высказывании персонажа, уже проанализированы.

• Поскольку каждый объект world имеет свой уникальный идентификатор и каждое утверждение (объект claim) индексировано определенным объектом world , можно довольно просто выяснить, существует ли противоречие между разными «мирами» (т.е. между утверждениями, связанными с разными объектами world). Остается единственный вопрос – нужно ли возвращаться в ранее покинутый «мир», если в текущем «мире» обнаружено противоречие с ним. Мы будем применять стратегию поиска в глубину, которая состоит в том, что откат нужно выполнять только в том случае, если противоречие сохраняется после полного завершения анализа текущего «мира».

• Если объекты world нумеруются последовательно, по мере их формирования, то потребуется разработать правило, которое при возвращении в покинутый ранее «мир» уничтожит как текущий объект world, так и все промежуточные объекты такого типа, которые при необходимости затем могут быть воссозданы.

• Если прежний объект world содержит полную информацию о том, в каком состоянии был покинут «мир», и утверждения в этом «мире» не противоречат этому состоянию, то ничто не мешает нам продолжить вычисления из точки возврата.

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

1. Нам потребуется различать случаи, в которых противоречия возникают в пределах одного и того же «мира», от конфликтов между «мирами». Если текущее высказывание само по себе противоречиво (т.е. является парадоксом), нет смысла выполнять откат в прежний мир и искать в нем разрешения противоречия.

2. Наличие такого слота позволит разработать правило, которое будет выполнять откат прямо в этот покинутый ранее «мир».

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

;; Объект world представляет контекст,

;; сформированный определенными предположениями

;; о правдивости или лживости высказывания,

;; принадлежащего некоторому персонажу.

;; Объект имеет уникальный идентификатор в поле tag,

;; а смысл допущения – истинность или лживость –

;; фиксируется в поле scope.

;; Поле prior может содержать идентификатор

;; объекта world, обработанного перед тем,

;; как был создан данный объект, и с которым данный

;; объект может потенциально конфликтовать.

Характеристики

Список файлов реферата