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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

Булос також роз'яснює деякі моменти завдання:

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

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

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

Історія[ред.ред. код]

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

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

Рішення задачі[ред.ред. код]

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

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

Рішення завдання може бути спрощене, якщо використовувати умовні висловлювання, що суперечать фактам (контрфакти[en])[4][5]. Ідея цього рішення полягає в тому, що на будь-яке питання 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», що означає «ні».

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

  • Запитаємо бога 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 // Harvard Review of Philosophy. — 1996. — Vol. 6. — P. 62-65.
  2. Raymond Smullyan. What is the Name of This Book? pp. 149–156
  3. http://www.astrolog.org/labyrnth/captions.txt
  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).

Посилання[ред.ред. код]