Самая сложная логическая задача
“Самая сложная логическая задача” в классическом виде формулируется следующим образом:
Есть три бога: \(A\), \(B\) и \(C\), которые являются богами истины, лжи и случая в произвольном порядке. Бог истины всегда говорит правду, бог лжи — всегда обманывает, бог случая может говорить и правду, и ложь в произвольном порядке. Требуется определить богов, задав 3 вопроса, на которые можно ответить «да» или «нет». Нельзя спрашивать несколько богов одновременно. Боги понимают язык, но отвечают на своем языке, в котором есть 2 слова «da» и «ja», причем неизвестно, какое слово обозначает «да», а какое «нет».
Задача впервые предложена общественности в итальянском журнале La Republica американским философом и логиком Джорджем Булосом в 1992 году.
Дополнительные условия задачи (или вернее разъяснения к условиям):
- Можно задавать одному богу более чем один вопрос (поэтому другим богам может быть не задано ни одного вопроса вообще).
- Каков будет следующий вопрос и кому он будет задан, может зависеть от ответа на предыдущий вопрос.
- Бог случая отвечает случайным образом, зависящим от подбрасывания монетки, спрятанной в его голове: если выпадет аверс, то отвечает правдиво, если реверс — то врет.1
- Бог случая отвечает «da» или «ja» на любой вопрос, на который можно ответить «да» либо «нет».
Так же в классическом варианте нельзя задавать богам вопросы, “от которых взрывается голова”2, (т.е. на которые нельзя ответить) и вопросы, на которые нельзя ответить “да” или “нет”.
Для решения задачи сперва проведем логический анализ более простой задачи “о рыцарях и лжецах”. Она формулируется (в одном из наиболее интересных вариантов) следующим образом:
Путешественник вышел на дорогу, соединяющую город лжецов и город рыцарей. Он хочет узнать, в какой стороне находится каждый из городов. Какой вопрос он должен задать прохожему (не зная, рыцарь он или лжец), чтобы определить это?
В условиях задачи считается, что рыцари всегда говорят правду, а лжецы всегда лгут. Классическим решением этой задачи является вопрос “Если я спрошу у Вас, в той ли стороне находится город рыцарей, что Вы мне ответите?”. Это вложенный вопрос (внутренний – “в той ли стороне город рыцарей?”, внешний – “что Вы мне ответите?”), и если он задан рыцарю, тот на оба вопроса ответит правду и в результате получится правда. Если же вопрос задан лжецу, лжец на оба вопроса ответит ложь, и двойное отрицание даст правду.
Теперь проанализируем эту задачу в рамках формальной логики.
Введем предикаты:
- \(T\) – предикат, истинный, если опрашиваемый говорит правду и ложный в обратном случае.
- \(Q\) – непосредственно предикат заданного вопроса.
- \(A\) – полученный ответ
Если \(T\) – истинно, то \(A\) и \(Q\) эквивалентны. Формально, \(T \rightarrow (A \equiv Q)\) (импликация)
Если \(T\) – ложно, то \(A\) эквивалентно \(\overline Q\). Формально, \(\overline T \rightarrow (A\equiv \overline Q)\)
Из законов формальной логики, известно, что \(A\equiv \overline B\) \(\Rightarrow\) \(\overline{A\equiv B}\), и \(A\rightarrow B \Rightarrow \overline B\rightarrow \overline A\).
Тогда \(T\rightarrow (A\equiv Q)\) и \((A\equiv Q)\rightarrow T\), что равносильно \(T\equiv (A\equiv Q)\). В силу коммутативности эквивалентности, так же \(A\equiv (Q\equiv T)\).
Положим \(Q = Q'\equiv T\). Тогда \(A\equiv (Q'\equiv T\equiv T)\), но \(T\equiv T\) – тавтология, и значит \(A\equiv Q'\).
Таким образом, интересующий нас вопрос – \(Q'\), вопрос, который необходимо задать – \(Q=Q'\equiv T\). Операцию эквивалентности можно читать как “тогда и только тогда, когда”. Таким образом, мы приходим к следующей формулировке вопроса:
“В той ли стороне город рыцарей, тогда и только тогда, когда Вы говорите правду?”. Безусловно, формулировка далека от разговорной речи, но ответ получается правильным. Важным следствием является эквивалентность данной формулировки и вложенного вопроса (в котором эквивалентность неявно присутствует во внешнем вопросе).
Возвращаясь к исходной задаче, она оказывается немногим сложнее данной. Введем дополнительный предикат, разрешающий неопределенность языка:
- R – предикат истинный, когда “da” означает истину, а “ja” означает ложь.
Тогда, если \(A\) – ответ на языке бога, то логический ответ \(B\) можно формально записать в виде:
\(B\equiv (A\equiv R)\)
(если \(R\) – истинно, то \(A\) и \(B\) эквивалентны, иначе \(A\) эквивалентно \(\overline B\))
Теперь, объединяя теоремы для \(A\) и \(B\), получаем: \(B \equiv ((Q\equiv T)\equiv R)\)
Пусть \(Q\) теперь имеет вид \(Q=Q'\equiv T\equiv R\). Аналогично предыдущему случаю, получаем:
\(B \equiv Q'\)
Таким образом, вопрос \(Q\) должен иметь вид \(Q = Q'\equiv T\equiv R\).
При таком подходе, мы можем считать предикат \(R\) истинным, и исходя из этого трактовать ответы бога (даже если этот предикат ложен, это учитывается в постановке вопроса)
Очевидно, первый вопрос \(Q'\), который интересует вопрошающего – какой из трех богов является богом случайности. Оригинальный вопрос Джорджа Булоса (популяризатора задачи) выглядит так:
“Означает ли «da» «да», только если ты бог правды, а бог B — бог случая?”
Очевидно, что этот вопрос лексически эквивалентен формальной записи. Однако, можно предложить форму короче (это было сделано Т.С. Робертсом в 2001 году). Давайте посмотрим, как.
В задаче с рыцарями и лжецами, мы уже видели эквивалентность высказывания \(Q'\equiv T\) и вложенного вопроса. Добавим к нему условие \(\ldots\equiv R\):
“Если я спрошу у тебя, является ли бог В богом случая, что ты мне ответишь?” расширяется условием “‘да’ означает истину” очень легко. Достаточно заменить вопрос “что ты мне ответишь?” на дополнительное утверждение \(R\): “ты ответишь ‘da’?”.
Эквивалентная формулировка Робертса (задаваемая богу B) “Если я спрошу у тебя „Бог А — бог случая?“, ты ответишь „ja“?” отличается только выбором предиката \(R\), который может быть выбран с известной долей свободы, и первого вопрошаемого бога.
Ответ на первый вопрос не позволяет определить, является ли бог богом случая, однако позволяет определить, какой бог точно не является богом случая. Введем предикат \(C\), истинный, если вопрошаемый бог – бог случая. Тогда можно записать:
\(B \rightarrow C\vee Q'\) (т.е. если ответ на первый вопрос утвердительный, то или отвечает бог случая, или бог B – бог случая)
\(\overline B \rightarrow C\vee \overline {Q'}\) (т.е. если ответ на вопрос отрицательный, то или отвечает бог случая, или бог B – не бог случая)
Так же известно, что бог случая только один, то есть
\((C\&\overline {Q'}\&\overline D)\vee (\overline C\&{Q'}\&\overline D)\vee (\overline C\&\overline {Q'}\&D)\)
где предикат \(D\) истинный, если третий бог – бог случая.
Если \(B\) истинно, в свою очередь \(C\vee {Q'}\) истинно, тогда \(\overline C \& \overline {Q'}\) ложно.
\((C\&\overline {Q'}\&\overline D)\vee (\overline C\&{Q'}\&\overline D)\)
Используя свойство дистрибутивности:
\(\overline D\&((C\&\overline {Q'})\vee (\overline C\&{Q'}))\)
\(\overline D\&(C\oplus Q')\)
Очевидно, что \(\overline D\) должно быть истинно, то есть третий бог не бог Случая.
Если \(B\) ложно, то \(C\vee \overline {Q'}\), тогда \(\overline C\&{Q'}\) ложно. Тогда теорема об одном случайном боге запишется в виде \((C\oplus D)\&\overline {Q'}\), тогда \(\overline {Q'}\), то есть бог, о котором задан вопрос, не бог Случая.
Теперь, определив бога, не являющегося богом случая, зададим ему вопрос \(Q={Q'}\equiv T\equiv R\) с \({Q'}=\;\)“Бог, которого я спросил первым – бог случая?”. Независимо от ответа, мы однозначно определили бога случая.
Оставшегося бога теперь следует спросить \({Q'}=\;\)“Из трех богов, не ты и не бог случайности, является ли богом Истины?”, либо \({Q'}=\;\)“Являешься ли ты богом Истины?”. Во втором случае, поскольку \(Q'=T\), вопрос \(Q\) тривиализуется до вида \(Q=T\equiv R\) то есть, “Если я спрошу, ты ли бог Истины, ответишь ли ты ‘da’?”
Задача решена.
Пример
Положим, что “da” это “да” (предикат R).
Зададим первому богу вопрос: “Если я спрошу, является ли второй бог богом случайности, ответишь ли ты ‘da’?”
Если ответ “da”, то третий бог определенно не бог случайности.
Тогда зададим ему вопрос “Если я спрошу, является ли первый бог богом случайности, ответишь ли ты `da’?”
Если ответ “da”, то первый бог – бог случайности.
Если ответ “ja”, то второй бог – бог случайности.
Зададим теперь не-богу-случайности вопрос: “Если я спрошу тебя, ты ли бог Истины, ответишь ли ты ‘da’?”.
Если ответ “da”, то перед нами бог истины. Иначе, бог лжи.
Если ответ на первый вопрос “ja”, то второй бог определенно не бог случайности.
Тогда зададим ему вопрос “Если я спрошу, является ли первый бог богом случайности, ответишь ли ты `da’?”
Если ответ “da”, то первый бог – бог случайности.
Если ответ “ja”, то третий бог – бог случайности.
Далее аналогично.
Вообще говоря, в такой формулировке задача решается крайне легко:
Любому богу задается вопрос “Если я спрошу тебя, являешься ли ты богом случайности/правды/лжи, ответишь ли ты ‘da’, пребывая в текущем состоянии ума?” – последняя фраза эффективно сводит на нет “случайность”
Далее рассматривается вариант, если ответы бога случая действительно случайны, то есть “монетка” определяет не правдивость ответа, а сам ответ.↩︎
Кстати, если можно, и у богов действительно “взрывается голова” – ну или они просто молчат, то задача решается в 2 действия.↩︎