Алиса в стране смекалки - Смаллиан Р.М.
Скачать (прямая ссылка):
Из условия Н Крэг вывел заключение относительно того, гёделев ли тот остров, на котором он находился. К какому заключению пришел инспектор Крэг?
Решение. Остров гёделев. Выберем любой клуб С. Пусть D -клуб, заданный условием Н. Клуб D носит имя какого-нибудь островитянина, например островитянина по имени Джон. Сам Джон либо состоит, либо не состоит членом клуба D. Предположим, что Джон состоит членом клуба D. Тогда у него есть друг (назовем его Джек) в клубе С, который подтверждает, что Джон номинабелен. Поскольку Джон состоит членом клуба D, то Джон действительно номинабелен. Значит, Джек рыцарь. Следовательно, Джек рыцарь и состоит членом клуба С, поэтому Джек утверждает, что состоит членом клуба С.
Предположим, что Джон не состоит членом клуба D. Тогда у Джона есть друг (назовем его Джим), не состоящий членом клуба С и подтверждающий, что Джон номинабелен. Поскольку Джон не состоит членом клуба D, то Джон в действительности неноминабелен. Значит, Джим лжец. Итак, Джим лжец и не состоит членом клуба С, поэтому Джим солгал бы и утверждал бы, что состоит членом клуба С.
Следовательно, независимо от того, состоит или не состоит Джон членом клуба D, существует островитянин, утверждающий, что он состоит членом клуба С.
Ше:Шу4 _Ьиблиотека_КОЛХОЗ/коІхо3^І5с05/М_МАТНЕМ/МРОР_РОР/16.5ІіїтІМт (5оБ 19)19.01.2004 16:56:35
"Как же называется эта книга?" - 16
Примечание. Объединяя решения задач 264 и 265, можно утверждать, что на любом острове, удовлетворяющем условиям Е1, Е2, С и Н, заведомо найдется непризнанный рыцарь и неотъявленный лжец. Этот результат в действительности представляет собой "замаскированную" форму знаменитой теоремы Гёделя о неполноте, к которой мы еще вернемся в разделе В этой главы.
Если вы хотите предложить одному из ваших друзей действительно трудную задачу, задайте ему задачу 264 для острова, удовлетворяющего условиям Е1, Е2, С и Н, (об условии G пока умолчите). Выведет ли ваш приятель самостоятельно условие G?
Б. - Дважды гёделевые острова.
Задачи этого раздела представляют более специальный интерес, и ознакомление с ними можно отложить до прочтения раздела В.
Под дважды гёделевыми островами мы будем понимать острова рыцарей и лжецов, объединенные в клубы, удовлетворяющие условию CG.
CG: для любых двух клубов С1, С2 найдутся островитяне А, В, о которых известно следующее: А утверждает, что В состоит членом клуба С1, а В утверждает, что А состоит членом клуба С2.
Насколько мне известно, из условия CG не следует условие G, а из условия G не следует условие CG. Оба условия выглядят совершенно независимыми, поэтому (насколько мне известно) дважды гёделевы острова не обязательно должны быть гёделевыми островами.
Изучение дважды гёделевых островов - мой "конек".
Задачи, связанные с ними, имеют такое же отношение к парадоксу Журдэна с двусторонней карточкой (см. задачу 254 в предыдущей главе), какое задачи о гёделевых островах имеют к парадоксу лжецов.
Ше:Шу4 _Ьиблиотека_КОЛХОЗШхо3ЛІ5с05/М_МАТНЕМ/МРОР_РОР/16.5ІіїтІМт (6о? 19)19.01.2004 16:56:35
"Как же называется эта книга?" - 16
266. Дважды гёделев остров S.
Однажды мне посчастливилось открыть дважды гёделев остров S, для которого выполняются условия Е1, Е2 и С острова G.
а) Можно ли определить, найдется ли на острове S хоть один непризнанный рыцарь? Что можно сказать о неотъявленном лжеце?
б) Можно ли установить, состоят ли рыцари острова 8 членами одного клуба? А лжецы?
Решение. Начнем со второй части задачи. Если все рыцари острова состоят членами одного клуба, то (по условию С) все лжецы также состоят членами одного клуба, а если все лжецы острова 8 состоят членами одного клуба, то (в силу того же условия С) рыцари также состоят членами одного клуба. Следовательно, если представители одной из двух групп населения острова (либо рыцари, либо лжецы) состоят членами одного клуба, то представители каждой из двух групп состоят членами одного клуба. Итак, предположим, что все рыцари состоят членами одного клуба и что все лжецы состоят членами одного клуба. Тогда по условию CG должны найтись островитяне А, В, высказывающие следующие утверждения:
А: В - лжец.
В: А - рыцарь.
Как показано в решении задачи 259 в предыдущей главе, это невозможно. Следовательно, все рыцари не могут состоять членами одного клуба, и все лжецы не могут состоять членами одного клуба.
Что касается первой половины задачи, то ее можно решить двумя способами. Первый из них проще того способа, которым мы только что решили вторую часть задачи, зато второй способ более поучительный.
Первый способ. Так как все рыцари не состоят членами одного клуба, а все признанные рыцари состоят членами одного клуба, то множество всех рыцарей не совпадает с
Ше:Шу4 _Ьиблиотека_КОЛХОЗ/коІхо3^І5с05/М_МАТНЕМ/МРОР_РОР/16.5ІіїтІМт (7о? 19)19.01.2004 16:56:35
"Как же называется эта книга?" - 16
множеством всех признанных рыцарей. Следовательно, не все рыцари признанные. Аналогично не все лжецы отъявленные.
Второй способ. Так как все признанные рыцари состоят членами одного клуба, то все островитяне, не принадлежащие к числу признанных рыцарей, также состоят членами одного; клуба. Если эти клубы выбрать в качестве клубов С1, С2, то (по условию CG) найдутся островитяне А, В, высказывающие следующие утверждения:
