Найскладніша логічна задача

Найскладніша логічна головоломка (італ. L'indovinello più difficile del mondo) — назва логічної задачі, запропонованої американським філософом і логіком ^[en] в італійській газеті «la Repubblica» в 1992 році:

Є три знайомих один одному боги: A, B і C, які є богами правди, брехні і випадку в довільному порядку. Бог правди завжди каже правду, бог брехні — завжди обманює, бог випадку може говорити і правду, і брехню в довільному порядку. Потрібно визначити богів, поставивши 3 питання, на які можна відповісти «так» чи «ні». Кожне запитання ставиться тільки одному богу. Боги розуміють мову, але відповідають своєю мовою, в якій є 2 слова «da» і «ja», причому невідомо, яке слово означає «так», а яке «ні».

Булос також пояснює деякі подробиці задачі:

• Можна ставити одному богу більш ніж одне питання (тому іншим богам може бути не поставлено жодного питання).
• Яке буде наступне питання і кому воно буде задане, може залежати від відповіді на попереднє питання.
• Бог випадку відповідає випадковим чином, залежним від підкидань монетки, захованої в його голові: якщо випаде аверс — то відповідає правдиво, якщо реверс — то бреше.
• Бог випадку відповідає «da» або «ja» на будь-яке питання, на яке можна відповісти «так» або «ні».

Інші коментарі:

• Не можна ставити питання-«парадокси», на які можна відповісти і «da», і «ja» або не можна відповісти ніяк. Приміром, «Ти зараз відповіси „da“?».

Історія

Булос вказує на логіка Реймонда Смалліана, як автора задачі і на Джона Маккарті, який ускладнив задачу, додавши невизначеність трактувань «da» і «ja». Подібні задачі є в книгах Реймонда Смалліана, наприклад, він описує острів, де половина жителів зомбі (вони постійно брешуть), а інша половина — люди (вони постійно кажуть правду). Ситуацію ускладнює факт, що жителі острова чудово нас розуміють, але давнє табу забороняє їм використовувати нерідні слова. Тому вони використовують відповіді «bal» або «da», які означають «так» і «ні», причому неясно, яке з них що означає. Є ще ряд подібних головоломок у книзі «The Riddle of Scheherazade». Все це різновиди широко відомих задач про лицарів і шахраїв Смалліана.

Одну з таких задач висвітлено у фільмі «Лабіринт»: є 2 дверей і 2 вартових, один завжди каже правду, другий завжди бреше. Одні двері ведуть до замку, другі — до загибелі. Сенс головоломки полягає в тому, щоб дізнатися, які двері ведуть до замку, поставивши одне питання одному вартовому. У фільмі Сара запитувала: «Чи скаже він [другий стражник] мені, що ці двері ведуть до замку?».

Розв'язок задачі

Булус запропонував розв'язок задачі у тій же статті, де він опублікував саму задачу. Він заявив, що першим питанням ми повинні виявити бога, який не є богом випадку, тобто є або богом правди, або богом брехні. Є безліч питань, які можна задати для цього. Одна зі стратегій — використання складних логічних зв'язків у самому питанні.

Питання Булоса: "Чи означає «da» «так», тільки якщо ти бог правди, а бог B — бог випадку?". Інший варіант питання: «Чи є непарним числом кількість правдивих тверджень в такому списку: ти — бог брехні, „ja“ позначає „так“, B — бог випадку?»

Розв'язання завдання можна спростити, якщо використовувати умовні висловлювання, що суперечать фактам (^[en]). Ідея цього розв'язку полягає в тому, що на будь-яке питання Q, що вимагає відповіді «так» або «ні», поставлене богу правди чи богу брехні:

• Якщо я запитаю тебе Q, ти відповіси «ja»?

результатом буде «ja», якщо правильна відповідь на питання Q це «так», і «da», якщо правильна відповідь «ні». Для доведення цього можна розглянути вісім можливих варіантів, запропонованих самим Булосом:

• Припустимо, що «ja» позначає «так», а «da» позначає «ні»:
  • Ми запитували бога правди, і він відповів «ja». Оскільки він каже правду і правильна відповідь на питання Q — «ja», вона означає «так».
  • Ми запитували бога правди, і він відповів «da». Оскільки він каже правду і правильна відповідь на питання Q — «da», вона означає «ні».
  • Ми запитували бога брехні, і він відповів «ja». Оскільки він завжди бреше, то на питання Q він відповість «da». Тобто правильну відповідь на питання «ja», яка означає «так».
  • Ми запитували бога брехні, і він відповів «da». Оскільки він завжди бреше, то на питання Q він відповість «ja». Тобто правильну відповідь на питання «da», яка означає «ні».
• Припустимо, що «ja» означає «ні», а «da» означає «так»:
  • Ми запитували бога правди, і він відповів «ja». Оскільки він каже правду і правильна відповідь на питання Q — «da», вона означає «так».
  • Ми запитували бога правди, і він відповів «da». Оскільки він каже правду і правильна відповідь на питання Q — «ja», вона означає «ні».
  • Ми запитували бога брехні, і він відповів «ja». Оскільки він завжди бреше, то на питання Q він відповідає «ja». Але, оскільки він бреше, правильна відповідь на питання Q — «da», що означає «так».
  • Ми запитували бога брехні, і він відповів «da». Оскільки він завжди бреше, то на питання Q він відповідає «da». Але, оскільки він бреше, правильна відповідь на питання Q — «ja», що означає «ні».

Використовуючи цей факт, можна ставити питання:

• Запитаємо бога B: «Якщо я запитаю тебе „Бог А — бог випадку?“, ти відповіси „ja“?». Якщо бог B відповідає «ja», значить, або він бог випадку (і відповідає випадковим чином), або він не бог випадку, а насправді бог A — бог випадку. У будь-якому варіанті, бог C — це не бог випадку. Якщо ж B відповідає «da», то або він бог випадку (і відповідає випадковим чином), або B не Бог випадку, що означає, що бог А — теж не бог випадку. У будь-якому варіанті, бог A — це не бог випадку.

• Запитаємо бога, який не є богом випадку (за результатами попереднього питання, або A, або C): «Якщо я запитаю тебе: „Ти бог брехні?“, ти відповіси „ja“?». Оскільки він не бог випадку, відповідь «da» означає, що він бог правди, а відповідь «ja» означає, що він бог брехні.

• Запитаємо цього ж бога «Якщо я тебе запитаю: „Бог B — бог випадку?“, ти відповіси „ja“?». Якщо відповідь «ja» — бог B є богом випадку, якщо відповідь «da», то бог, з яким ще не говорили, є богом випадку.

Бог, який залишився, визначається виключенням.

Примітки

1. George Boolos. The Hardest Logic Puzzle Ever : [ 12 грудня 2013] // . — 1996. — Vol. 6. — P. 62-65.
2. Raymond Smullyan. What is the Name of This Book? pp. 149—156
3. . Архів оригіналу за 23 вересня 2015. Процитовано 13 червня 2014.{{}}: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title ()
4. Brian Rabern and Landon Rabern, A simple solution to the hardest logic puzzle ever, (Analysis 68 (298), 105—112, April 2008).
5. T.S. Roberts, Some thoughts about the hardest logic puzzle ever (Journal of Philosophical Logic 30:609-612(4), December 2001).

Література

• T.S. Roberts, Some thoughts about the hardest logic puzzle ever (Journal of Philosophical Logic 30:609-612(4), December 2001).
• Brian Rabern and Landon Rabern, A simple solution to the hardest logic puzzle ever (Analysis 68 (298), 105—112, April 2008).
• Raymond Smullyan, What is the Name of This Book? (Prentice Hall, Englewood Cliffs, NJ, 1978).
• Raymond Smullyan, The Riddle of Sheherazade (A. A. Knopf, Inc., New York, 1997).

Посилання

• T.S. Roberts. Some thoughts about the hardest logic puzzle ever. Journal of Philosophical Logic, 30:609-612(4), December 2001.^{[недоступне посилання з листопадаа 2019]}
• Brian Rabern and Landon Rabern. A simple solution to the hardest logic puzzle ever. Analysis 68 (298), 105—112, April 2008.^{[недоступне посилання з квітня 2019]}