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