Самая сложная логическая задача

[hitthelimit]

 

Есть логическая головоломка, называемая «Самая сложная логическая задача» (рекомендую предварительно ознакомиться).(L'indovinello più difficile del mondo) — название логической задачи, предложенной американским философом и логиком Джорджем Булосом  )
Я обнаружил, что все статьи в русскоязычном интернете на эту тему являются перепечаткой одного исходника, и не способны полностью удовлетворить интерес к этой действительно необычной головоломке. Я обнаружил дополнительную информацию по этому вопросу, с который и знакомлю всех интересующихся на этой странице.

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

Простое решение самой сложной логической головоломки. (Брайан и Лэндон Раберн)
Мы представляем самое простое решение “самой сложной логической головоломки". Затем мы изменяем головоломку, чтобы сделать ее еще сложнее и приводим простое решение модифицированной головоломки. В заключительных разделах исследуется вариант “взрыва головы Бога» с решением исходной головоломки в два вопроса.

1. Самое простое решение «трудной» головоломки

Головоломка. Три бога A, B, и C называются в некотором порядке 'Правда', 'Ложь', и 'Случай'. Правда всегда говорит правду, Ложь всегда говорит ложь, но говорит ли Случай правду или ложно является совершенно случайным делом. Ваша задача заключается в определении личности A, B, и C с помощью трех “да-нет” вопросов, каждый вопрос должен быть задан одному богу. Боги понимают по-английски, но ответят на все вопросы на своем родном языке, в котором словами для "да" и "нет" являются "DA" и "JA", в некотором порядке. Вы не знаете, что означает каждое слово.

Boolos в 1996 предложил следующие основные принципы:

(В1) Одному богу может быть задано больше одного вопроса (и, следовательно, некоторым богам вопрос задан не будет).
(В2) Второй вопрос, и бог, которому он задается, может зависеть от ответа на первый вопрос. (То же самое с третьим вопросом).
(B3) Говорит ли Случай правду или нет должно рассматриваться как зависимость от броска монеты, скрытой в его мозгу: если монета выпадет решкой, он говорит правду, а если орлом - ложь.
(B4) Случай ответит "DA» или «JA» на любой вопрос «да-нет” .

Прежде, чем продолжить чтение этой статьи, читатель может сделать паузу и попытаться решить головоломку.

Для решения этой головоломки введем функцию от вопросов к вопросам и докажем лемму, которая делает головоломку тривиальной задачей.

Пусть Е - функция, приводящая вопрос q к вопросу «Если я задам тебе вопрос q в твоем текущем умственном состоянии, ты ответишь «JA”?

Лемма, встроенная в вопрос. Когда любому богу задается вопрос E(q), ответ «JA” указывает, что правильный ответ на q положительный, а ответ «DA” указывает, что правильный ответ на q — отрицательный.

Доказательство. Если бог Правда или Ложь, следует результат, поскольку и двойное утверждение, и двойное отрицание дают позитивное утверждение. Таким образом, мы можем полагать, что бог — Случай. В соответствии с (В3), когда мы задаем Е(q) Случаю, в его мозгу подбрасывается монета. Если монета выпадет решкой, умственное состояние Случая таково, что он говорит правду, а если орлом - ложь. В любом случае, мы снова имеем результат, так как и двойное утверждение, и двойное отрицание дают позитивное утверждение.
С леммой, включенной в вопрос, «трудная» головоломка становится не сложнее следующей тривиальной задачи.

Тривиальная головоломка. Три бога А, В и С в некотором порядке называются Zephyr, Eurus и Aeolus. Боги всегда говорят правду. Ваша задача — установить личности А, В и С, задав три «да-нет» вопроса; один вопрос должен быть задан только одному богу. Боги понимают английский и ответят по-английски.

2. Проблемы со Случайным и модификация Случайного.

Одним из достоинств логической аргументации является то, что нет ни разрыва между тем, что говорится и тем, что подразумевается, и между тем, что подразумевается и говорится. Загадка была представлена ​​именно так, как выше, и мы предложили самое простое решение для головоломки в таком изложении. Тем не менее, оригинальный дух Smullyan-головоломки, безусловно, был потерян. Большинство комментаторов головоломки предположили, что ответы Случая – случайные, и поэтому ничто не может быть почерпнуть из его ответов, но Случай работает не так. Обратите внимание, что произойдет, если мы просим Случая: “Собираетесь ли вы ответить на этот вопрос ложью?" Если его монета в мозгу выпадет решкой, он должен ответить отрицательно (так как это не правда, что он будет лгать), а если его монета выпадет орлом, он также должен ответить отрицательно (потому как верно, что его ответ является ложью, и он лжет, чтобы не ответить утвердительно). В каком смысле это случайность? Он всегда отвечает на этот вопрос отрицательно!

Эта предсказуемость, которая был встроена в Случай (видимо, непреднамеренно) — это именно то, что мы использовали, чтобы сделать задачу тривиальной. Чтобы сделать Случай действительно случайным, мы заменяем (B3) следующим (и вносим необходимые изменения в исходную головоломку):

( В3 * ) Отвечает Случая "JA" или "DA" следует рассматривать как зависимость от броска монеты, скрытой в его мозгу: если выпадает решка, он отвечает "JA" , если орел , он отвечает “Da”.

3 . Самое простое решение модифицированной головоломки

Модифицированная головоломка.
Три бога A, B и C называются в некотором порядке “Правда”, “Ложь» и “Случай». Правда всегда говорит правду, Ложь всегда лжет, но отвечает ли Случай "JA " или "DA" является совершенно случайным дело. Ваша задача заключается в определении личности A, B, и C тремя “да-нет” вопросами, каждый вопрос должен быть задан только одному богу . Боги понимают по-английски, но будут отвечать на все вопросы на своем родном языке, в котором слова для "да" и "нет" являются "DA" и "JA ", в некотором порядке . Вы не знаете, какое слово что означает.

Для решения модифицированной головоломки мы вводим другую функцию от вопросов к вопросам и доказываем две леммы. Пусть Е* будет функцией, переводящей вопрос q в вопрос «Если я спрошу тебя «q”, ты ответишь «JA”?”

Встроенная в вопрос лемма*. Если Правде или Лжи задается вопрос Е*(q), ответ «JA” указывает, что правильный ответ на q положительный, а ответ «DA» указывает, что правильный ответ на q — отрицательный.

Доказательство. Двойное утверждение и двойное отрицание дают положительное утверждение.

Лемма идентификации. Если было установлено, что данный бог не является Случай, и остается два вопроса, то личности двух оставшихся богов могу быть установлены.

Доказательство. Без потери всеобщности, предположим, что было установлено — А не является Случаем. Зададим А следующие два вопроса:

1. Е* (Является ли А Правдой?)


2. Е* (Является ли В Случаем?)

Согласно включенной в вопрос лемме*, ответ А на вопрос (1) установит его личность, а его ответ на вопрос (2) установит личности В и С.

С использованием этих лемм головоломка решается легко. Задаем В вопрос Е* (Является ли А Случаем?). Если В отвечает (JA), тогда или В — Случай, или А - Случай (согласно встроенной в вопрос лемме*). Тогда С — не Случай. Если В отвечает «DA», тогда или В - Случай, или А — не Случай (согласно встроенной в вопрос лемме*). Следовательно, А — не Случай. Таким образом, ответ В на наш первый вопрос устанавливает, что определенный бог — не Случай. Теперь лемма идентификации завершает дело.

4. Взрывающиеся головы богов.

Поскольку головоломка не содержит ограничений на типы «да-нет» вопросов, на которые бог гарантированно дает ответ, мы испытываем побуждение попытаться проделать следующее. Боги сидят перед нами и мы спрашиваем их:

Вы ответите «JA” на этот вопрос?

Если «JA” означает «нет», то Правда будет не в состоянии ответить правдой. Если «JA” означает «да», то Ложь будет не в состоянии ответить ложью. Но они — непогрешимые боги! У них только один выход — их головы взрываются.
Такой вопрос, похоже, не помогает нам найти решение головоломки, поскольку личность бога зависит от значения слов «JA” и «DA”. Но несколько подправив наши вопросы, мы можем добыть больше информации. Подумайте над вопросом: «Ответите ли вы на этот вопрос словом, означающим «нет» в вашем языке?». Если постановкой этого вопроса мы взрываем голову бога, тогда мы знаем, что бог старался сказать правду. (В оригинальной трактовке Boolos предполагалось, что это бог Случай, монета которого выпала решкой. В этой секции мы сконцентрируемся на модифицированной головоломке.)

Лемма взрывающейся личности. Идентичность любого бога может быть установлена максимум двумя вопросами.

Доказательство. Без потери всеобщности предположим, что мы адресуемся богу А. Мы спрашиваем: «Ответите ли вы на этот вопрос словом, означающим «нет» в вашем языке?» Если его голова взрывается, тогда мы знаем, что это Правда, и работа закончена. Также мы можем предположить, что его голова не взорвалась. Мы спрашиваем: «Ответите ли вы на этот вопрос словом, означающим «да» в вашем языке?». Если его голова взрывается, тогда мы знаем, что это — Ложь. Если его голова не взрывается, тогда это — Случай.
Теперь мы можем иметь другое простое решение модифицированной головоломки, используя эту лемму; а именно: сначала устанавливаем личность А с использованием леммы взрывающейся личности, затем, в зависимости от личности А, спрашиваем В либо: ««Ответите ли вы на этот вопрос словом, означающим «нет» в вашем языке?», либо «Ответите ли вы на этот вопрос словом, означающим «да» в вашем языке?».

5. Оригинальная головоломка Boolos за два вопроса?

Прежде всего, кажется, мы можем доказать, что потребуется по меньшей мере три вопроса для установления личности всех богов. Существует 6 способов организации богов, и каждый «да-нет» вопрос устанавливает максимум две возможности, таким образом, нам потребуется log2(6), т.е. 3 вопроса для установления их личностей. Тем не менее, предположение, что каждый «да-нет» вопрос устанавливает максимум две возможности — ошибка. Возможно установить три возможности одним вопросом, если мы задаем вопрос, способный взорвать голову бога. Для иллюстрации мы решим тривиальную головоломку за два вопроса.

Тривиальная головоломка. Три бога А, В и С в некотором порядке называются , Eurus и Aeolus. Боги всегда говорят правду. Ваша задача — установить личности А, В и С, задав три «да-нет» вопроса; один вопрос должен быть задан только одному богу. Боги понимают английский и ответят по-английски.

Лемма закоренелого лжеца. Если мы задаем А вопрос: «Так ли это, что ((вы собираетесь ответить «нет» на этот вопрос) И (В является Zephyr)) ИЛИ (В - Eurus)»?, ответ «да» указывает, что В - Eurus, ответ «нет» - что В - Aeolus, а взорвавшаяся голова — что В - Zephyr. Таким образом, мы можем установить личность В одним вопросом.

Доказательство. Допустим, А ответил «да», и В — не Eurus. Тогда А ответил «да» на вопрос «Так ли это, что вы собираетесь ответить «нет» на этот вопрос?». Это невозможно, так как А говорит правду.
Предположим, А ответил «нет», и В - не Aeolus. Тогда А ответил «нет» на оба вопроса: «Так ли это, что: вы собираетесь ответить «нет» на этот вопрос И В является Zephyr» и вопрос «В - В - Eurus?» Отрицание последнего указывает, что В — не Eurus, а значит - Zephyr. Отрицание предыдущего указывает, что либо А не сказал «нет», либо В — не Zephyr. Противоречие.
Предположим, голова А взорвалась, и В — не Zephyr. Тогда В также и не Eurus, иначе А ответил бы «да». Таким образом, поскольку В не Zephyr и не Eurus, А будет отрицать обе части дизъюнкции, следовательно, на весь вопрос он ответит «нет». Это последнее противоречие завершает доказательство.
Теперь, для решения тривиальной головоломки за два вопроса, просто используйте лемму закоренелого лжеца для установления личности В одним вопросом, а затем, относительно бога, которым В не является, спросите В, является ли С этим богом.
Как было замечено в первой секции этой статьи, встроенная в вопрос лемма сводит поиск решения оригинальной головоломки Boolos тремя вопросами к нахождению решения тремя вопросами тривиальной головоломки. Кажется резонным, что похожее соотношение сохранится также и для решения двумя вопросами. И это так, тем не менее, необходимо соблюдать осторожность при встраивании вопросов, содержащих индексность или указательность (indexicals or demonstratives), т.е. сложное указание «этот вопрос», относящееся к самому глубокому цитатному блоку, в котором он содержится. Нам требуется термин, относящийся к самому внешнему цитатному блоку (т.е. вопросу внешнего типа), в котором он содержится. Для этого можно вести имя. Пусть следующий вопрос будет называться «Запрос-1»:

Е(«Так ли это, что: ((в твоем текущем состоянии сознания ты всегда будешь отвечать «DA”на «Запрос-1») И (В — Правда)) ИЛИ (В — Ложь)?»

Лемма закоренелого лжеца*. Если мы спросим А «Запрос-1», ответ «JA” означает, что В — Ложь, а ответ «DA” означает, что В — Случай, а взорвавшаяся голова — что В — Правда. Таким образом, мы можем установить личность В одним вопросом.

Доказательство. Предположим, А ответил «JA» и В не Ложь. Тогда, в соответствии со встроенной леммой, правильный ответ на вопрос «Так ли это, что: ((в твоем текущем состоянии сознания ты всегда будешь отвечать «DA”на «Запрос-1») И (В — Правда)) ИЛИ (В — Ложь)?» утвердительный. Так как В не Ложь, правильный ответ на «Так ли это, что: в твоем текущем состоянии сознания ты всегда будешь отвечать «DA”на «Запрос-1»?, но А ответил «JA” на «Запрос-1». Противоречие.
Предположим, А ответил «DA” и В — не Случай. Тогда, в соответствии со встроенной леммой, правильный ответ на вопрос «Так ли это, что: в твоем текущем состоянии сознания ты всегда будешь отвечать «DA”на «Запрос-1» И В — Правда?» и вопрос «Так ли это, что В — Ложь?» отрицательный. Отрицание последнего означает, что В — не Ложь, а значит, Правда. Отрицание предыдущего означает, что либо А не ответил «DA”, или что В — не Правда. Противоречие.
Предположим, голова А взорвалась, и В — не Правда. Тогда В и не Ложь, иначе А ответил бы «JA”. Тогда, раз В не Правда и не Ложь, А будет отрицать обе стороны дизъюнкции, следовательно, ответит «DA” на весь вопрос. Последнее противоречие завершает доказательство.

Теперь, для решения оригинальной головоломки Boolos за два вопроса просто используйте лемму закоренелого лжеца для установления личности В за один вопрос, затем для какого-то бога, кем В не является, спросите В является ли С этим богом.

(Перевод — hitthelimit, при копировании ссылка обязательна).

Мой вариант решения.

По условиям задачи не следует, что должны быть запрещены вопросы, которые могут быть как вопросами типа «да-нет», так и не являться ими. Если классификация вопроса не является возможной для спрашивающего, значит, такие вопросы допустимы — это просто не наша проблема. Далее, я исходил из того, что в случае, если для данного бога вопрос не является вопросом типа «да-нет», у него голова не взрывается, а он просто зависает, что имеет больший логический смысл, так как указывает на не распознавание вопроса как вопроса типа «да-нет». В таком случае вопрос не снимается, и спрашивающий может его переформулировать. Это дает преимущество, делая задачу более чем тривиальной.
Решение.
Расположим богов треугольником, и будем адресоваться к ним последовательно по часовой стрелке или против.
Для наших вопросов совершенно не важна поправка на тип случайности в ответах Случая, которая упоминается в статье, таким образом, мы будем решать оригинальную версию головоломки.
В качестве вопросов нам необходимы всего два простых вопроса (могут быть модифицированы), типа:
1. Этот бог ответит мне правду?
2. Ты меня видишь?

Они задаются последовательно. Существует немного вариантов развития событий.

Пусть бог А — Правда, В — Ложь, С — Случай.

Вариант 1. Задаем А вопрос номер 1 относительно бога В. Ответ: «JA» или «DA». Задаем этот же вопрос богу В относительно С. В ответ — молчание. Вывод — С — Случай. «JA» или «DA» (в зависимости от того, что именно прозвучало) означает «нет». Задаем вопрос номер 2 богу А или В, устанавливаем личности А и В. (Замена местами А и В ничего не меняет).

Вариант 2. Задаем первый вопрос богу С. В ответ — либо «JA», либо «DA». Задаем первый вопрос богу А, в ответ - либо «JA», либо «DA». Задаем первый вопрос богу В, в ответ — молчание. Идентифицируем бога С. Переформулируем вопрос богу В на вопрос номер два, зная, что ответ бога А означает «нет». Устанавливаем личности А и В.

Можно попытаться усмотреть жульничество с моей стороны, но я думаю, что я всего лишь вернул условию задачи логическую чистоту. В противном случае в условии следует избирательно (и волюнтаристски) запретить специфический класс вопросов.