Алиса в стране смекалки - Смаллиан Р.М.
Скачать (прямая ссылка):
А: В - признанный рыцарь.
В: А - не признанный рыцарь.
Предоставляем читателю самостоятельно убедиться в том, что по крайней мере один из островитян А, В должен быть признанным рыцарем (точнее говоря, требуется доказать, что если А - рыцарь, то он не признанный рыцарь, а если А -лжец, то В должен быть не признанным рыцарем. Установить, кто из островитян А, В не признанный рыцарь, мы не можем, хотя и знаем, что кто-то из них не признанный рыцарь. [С точно такой же ситуацией мы уже сталкивались в задаче 134 (о паре шкатулок, изготовленных Беллини и Челлини): одна
из шкатулок заведомо должна быть работы Беллини, но
установить, какую из двух шкатулок изготовил Беллини, невозможно.]
Аналогичным образом, так как все отъявленные лжецы состоят членами одного клуба, то все островитяне, не принадлежащие множеству отъявленных лжецов, также состоят членами одного клуба. Следовательно (по условию CG), непременно найдутся островитяне А, В, высказывающие следующие утверждения:
А: В - отъявленный лжец,
В: А - не отъявленный лжец.
Отсюда мы заключаем, что если В - лжец, то он не отъявленный лжец, а если В - рыцарь, то А - не отъявленный лжец (доказательство этого утверждения мы также предоставляем читателю). Итак, в любом случае либо А, либо
Ше:Шу4 _Ьиблиотека_КОЛХОЗ/коІхо3ЛІ5с05/М_МАТНЕМ/МРОР_РОР/16.5ІіїтІМт (8о? 19)19.01.2004 16:56:35
"Как же называется эта книга?" - 16
В - не отъявленный лжец, но мы не знаем, кто именно. (По существу эта задача ничем не отличается от задачи 135 о двух шкатулках, изготовленных Беллини и Челлини.)
267. Остров S1.
Однажды мне удалось открыть еще один дважды гёделев остров S1, который показался мне еще более интересным, чем остров S. Для острова S1 выполнены оба условия Е1, Е2, но не известно, выполняется ли условие С. (Напомним, что, согласно этому условию, все островитяне, не состоящие членами клуба С, состоят членами одного клуба.) По-видимому, невозможно доказать, что на острове S1 непременно есть не признанный рыцарь или что на том же острове есть не отъявленный лжец. Невозможно, по-видимому, доказать также, что все рыцари не состоят членами одного клуба или что все лжецы не состоят членами одного клуба.
Но следующие утверждения доказать можно:
а) На острове S1 найдется либо не признанный рыцарь, либо не отъявленный лжец.
б) Не может быть, чтобы все рыцари состояли членами одного клуба и все лжецы состояли членами одного клуба.
Решение. Докажем сначала утверждение (б). Предположим, что все рыцари состоят членами одного клуба и все лжецы состоят членами одного клуба. Тогда найдутся островитяне А, В, о которых известно следующее: А утверждает, что В -лжец, а В утверждает, что А - рыцарь. Но это, как мы уже знаем, невозможно (см. предыдущую задачу или задачу 259 в предыдущей главе). Итак, невозможно, чтобы все рыцари состояли членами одного клуба и все лжецы также состояли членами одного клуба. Значит, либо все рыцари не состоят членами одного клуба, либо все лжецы не состоят членами одного клуба. Если все рыцари не состоят членами одного клуба, то непременно найдется по крайней мере один не признанный рыцарь (поскольку все признанные рыцари состоят членами одного клуба). Если все лжецы не состоят членами одного клуба, то непременно найдется по крайней мере один не отъявленный лжец. Но какой именно случай представится на острове, мы не знаем. Итак, утверждение (а) доказано.
Ше:Шу4 _Ьиблиотека_КОЛХОЗ/коІхо3ЛІ5с05/М_МАТНЕМ/МРОР_РОР/16.5ІіїтІМт (9оґ 19)19.01.2004 16:56:35
"Как же называется эта книга?" - 16
Альтернативное (и более интересное) доказательство того, что непременно найдется не признанный рыцарь или не отъявленный лжец, состоит в следующем. Так как признанные рыцари состоят в одном клубе и отъявленные лжецы состоят в одном клубе, то найдутся островитяне А, В, высказывающие следующие утверждения:
А: В - отъявленный лжец.
В: А - признанный рыцарь.
Предположим, что А - рыцарь. Тогда его утверждение истинно. Значит, В - отъявленный лжец, поэтому его утверждение ложно. Следовательно, А - не признанный рыцарь. Значит, А - не признанный рыцарь. Если же А -лжец, то высказанное В утверждение ложно, поэтому В -лжец. Высказанное А утверждение также ложно, поэтому В -не отъявленный лжец. Следовательно, В - не отъявленный лжец.
Итак, либо А - не признанный рыцарь, либо В - не отъявленный лжец (но мы опять не знаем, какая из двух альтернатив истинна).
Эта задача очень напоминает одну из задач о парах шкатулок (задачу 136 из гл. 9), в которой одна из двух шкатулок (какая именно - неизвестно) изготовлена либо Беллини, либо Челлини (но кем именно - опять-таки неизвестно).
268. Несколько нерешенных задач.
Я придумал несколько задач о гёделевых и дважды гёделевых островах, но решить их так и не собрался. Думаю, что читателю будет приятно испробовать свои силы на работе, сулящей неожиданности и, быть может, даже открытия.
2 68 а.
Я уже говорил о том, что, насколько мне известно, ни
одно из условий G, CG не следует из другого. Удастся ли вам доказать (или опровергнуть, что я считаю маловероятным) мою гипотезу? Для этого вам необходимо "построить" остров, для которого выполняется условие G, но
