Анализ проблемы
Первым этапом любого программного проекта является анализ решаемой проблемы. Эксперт должен уметь решить проблему, а инженер по знаниям должен разобраться, как именно было получено решение. При решении нашей задачи вам придется выступить в обеих ипостасях.
Предложенные головоломки можно решить, систематически анализируя, что случится, если персонаж, произносящий реплику, является правдолюбцем, а что, если он – лжец. Обозначим через Т(А) факт, что А говорит правду и, следовательно, является правдолюбцем, а через F(A) – факт, что А лжет и, следовательно, является лжецом.
Рассмотрим сначала головоломку Р1. Предположим, что А говорит правду. Тогда из его реплики следует, что либо А лжец, либо В правдолюбец. Формально это можно представить в следующем виде:
Т(А) › F(A) v T(B)
Поскольку А не может быть одновременно и лжецом и правдолюбцем, то отсюда следует:
T(A) › Т(В).
Аналогично можно записать и другой вариант. Предположим, что А лжет:
F(A) › -{F(A) v T(B)).
Упростим это выражение:
F(A) › -F(A) ^-T(B) или F(A) › Т(А) ^ F(B).
Сравнивая оба варианта, нетрудно прийти к выводу, что только последний правильный, поскольку в первом варианте мы пришли к выводу, противоречащему условиям (не могут быть правдолюбцами одновременно А и В).
Таким образом, рассматриваемая проблема относится к типу таких, решение которых находится в результате анализа выводов, следующих из определенных предположений, и поиска в них противоречий (или отсутствия таковых). Мы предполагаем, что определенный персонаж говорит правду, а затем смотрим, можно ли в этом случае так распределить "роли" остальных персонажей, что не будут нарушены условия, сформулированные в репликах.
На жаргоне, принятом в математической логике, предположение о правдивости или лживости множества высказываний называется интерпретацией, а вариант непротиворечивого присвоения значений истинности элементам множества – моделью.
Однако наши головоломки включают и нечто, выходящее за рамки типовых проблем математической логики, поскольку реплики в них может произносить не один персонаж (как в головоломке Р2), а на реплику одного персонажа может последовать ответная реплика другого (как в головоломке Р3). В исходной версии программы, которую мы рассмотрим ниже, это усложнение отсутствует, но в окончательной оно должно быть учтено. Мы покажем, что постепенное усложнение программы довольно хорошо согласуется с использованием правил.
На практике оказывается, что в первой версии программы удобнее всего воспользоваться "вырожденным" вариантом проблемы, т.е. постараться решить ее в тривиальном виде, который, тем не менее, несет в себе многие особенности реального случая. Вот как это выглядит в отношении наших правдолюбцев и лжецов.
Р0. А заявляет: "Я лжец". Кто же в действительности А – лжец или правдолюбец?
Мы только что фактически процитировали хорошо известный Парадокс Лгуна. Если А лжец, то, значит, он врет, т.е. в действительности он правдолюбец. Но тогда мы приходим к противоречию. Если же А правдолюбец, т.е. говорит правду, то в действительности он лжец, а это опять противоречие. Таким образом, в этой головоломке не существует непротиворечивого варианта "распределения ролей", т.е. не существует модели в том смысле, который придается ей в математической логике.
Есть много достоинств в выборе для прототипа программы варианта головоломки Р0.
- В головоломке присутствует только один персонаж.
- Выражение не содержит логических связок, таких как И или ИЛИ, или кванторов, вроде квантора общности (все) и прочих.
- Отсутствует ответная реплика.
В то же время существенные черты проблемы в этом варианте присутствуют. Мы по-прежнему должны попытаться отыскать непротиворечивую интерпретацию высказывания А, т.е. должны реализовать две задачи, присутствующие в любых вариантах подобной головоломки:
- формировать альтернативные интерпретации высказываниям;
- анализировать наличие противоречий.
Вы увидите, что для выполнения этих двух задач потребуется использовать механизм, очень близкий к тем, которые мы рассматривали при описании систем обработки правдоподобия в главах 17 и 19.