Обратное прослеживание и множество контекстов
Модифицируем программу таким образом, чтобы она могла справиться и с задачами этого класса в более сложной постановке. Речь идет о задачах, в которых несколько персонажей произносят реплики. Пример такого рода головоломки приведен ниже.
Упражнение 3
Р5. Встречаются два человека, А и В, которые заявляют следующее. А: "Я говорю правду, либо В лжец", В: " А говорит правду, либо я лжец".
К какой категории следует отнести каждый из персонажей? (Решите эту задачу самостоятельно вручную, используя ту же систему обозначений, которая применялась ранее в этом Приложении.)
Задача анализа высказываний нескольких персонажей потребует использования более сложной методики, которая получила наименование "обратное прослеживание на основе анализа зависимостей"(dependency-directed backtracking).
От программы потребуется выполнить обратное прослеживание (откат) в следующих ситуациях:
- когда обнаружится конфликт между текущим "миром" и ранее существовавшим, причем в ранее существовавшем "мире" предполагается истинность высказывания, но не была проанализирована его лживость;
- когда обнаружится конфликт между текущим "миром" и ранее существовавшим, причем в ранее существовавшем "мире" был проанализирован только один операнд в составном дизъюнктивном утверждении.
Чтобы смысл этих формулировок стал более понятным, рассмотрим следующий пример.
Р6. Встречаются два человека, А и В, которые заявляют следующее.
А: "Хотя бы один из нас говорит правду". В: "Хотя бы один из нас лжец". К какой категории следует отнести каждый из персонажей?
Высказывания персонажей представим в следующем виде:
А: Т(А) v Т(В) В: F(A) v F(B)
Начнем с заявления персонажа В:
71(5) › F(A) v F(B)
И проанализируем левый операнд дизъюнкции. В результате будет сформирована корректная непротиворечивая интерпретация: В – правдолюбец, А – лжец.
Получив непротиворечивую интерпретацию высказывания персонажа В, перейдем к анализу высказывания персонажа А:
Т(А) › FALSE,
Поскольку правдивость А противоречит сформированной ранее интерпретации высказывания персонажа В. Предположим, что А – лжец. Тогда:
F(A) › -(T(А) v T(B)) › F(A) ^ F(B) › FALSE.
Таким образом, оказывается, что это предположение также не работает, поскольку противоречит выбранной ранее интерпретации высказывания персонажа В, из которой следует, что В говорит правду.
Но анализ высказывания персонажа В нельзя считать законченным, поскольку не был выполнен анализ правого операнда дизъюнкции:
N(B) › F(A) v F(B)
И не было проанализировано предположение, что В лжец. До тех пор, пока это не будет выполнено, мы не имеем права делать вывод, что высказывания в формулировке задачи противоречат друг другу.