Рэймонд Смаллиан - Принцесса или тигр?

Итак: если X истинно, то по крайней мере одно из двух утверждений X и Z является истинным, но не допускающим распечатки. Если же X ложно, то истинным, но не допускающим распечатки, оказывается утверждение Y.

4. Пусть S есть утверждение вида RA‒RA. Оно говорит нам о том, что ассоциат выражения RA (а ассоциат RA есть само S !) является опровержимым; следовательно, S истинно в том и только том случае, когда S опровержимо. Поскольку S не может быть одновременно и истинным и опровержимым, значит оно ложно, но неопровержимо.

5. а) Выберем в качестве X утверждение P‒RA‒P‒RA, а в качестве Y — утверждение RA‒P‒RA. Ясно, что X утверждает доказуемость Y, а Y утверждает опровержимость ассоциата выражения P‒RA (ассоциат P‒RA есть в данном случае просто само X ). Итак, X утверждает, что Y доказуемо, а Y утверждает, что X опровержимо. (Другой вариант решения — принять за X утверждение РА‒R‒РА, а за Y — утверждение R‒РА‒R‒РА. )

Далее, если Y доказуемо, то Y истинно, откуда следует, что X опровержимо и, следовательно, ложно, что в свою очередь означает, что Y недоказуемо. Таким образом, допущение о доказуемости Y приводит нас к противоречию; стало быть, оно неверно, и Y недоказуемо. Если же Y недоказуемо, то X ложно. Итак, мы имеем:

(1) X ложно;

(2) Y недоказуемо.

Теперь если Y истинно, то Y истинно и недоказуемо. Если же Y ложно, то X неопровержимо (поскольку Y утверждает опровержимость X), и поэтому в данном случае X ложно, но неопровержимо. Следовательно, либо Y истинно, но недоказуемо, либо X ложно, но неопровержимо.

б) Возьмем в качестве X утверждение NP‒NRA‒NP‒NRA, а в качестве Y — утверждение NRA‒NP‒NRA (или же за X можно принять NPA‒NR‒NPA, а за Y — NR‒NPA‒NR‒NPA ). Тогда, как читатель может убедиться сам, X утверждает недоказуемость Y, а Y утверждает неопровержимость X. Если X опровержимо, то X ложно; тогда Y доказуемо и, значит, Y истинно, откуда следует, что X неопровержимо. Следовательно, X неопровержимо и, кроме того, Y истинно. Если же X ложно, то X ложно и неопровержимо. Если, наконец, X истинно, то Y недоказуемо; поэтому в данном случае Y будет истинным и недоказуемым.

Обсуждение. По аналогии предположим, что на нашем острове, где живут рыцари и плуты, имеются еще два обитателя X и Y, причем X заявляет, будто Y — признанный рыцарь, а Y утверждает, что X — отъявленный плут. Единственный вывод, который можно сделать, — это что один из них (мы не знаем, кто именно) должен оказаться либо непризнанным рыцарем, либо неотъявленным плутом. Точно такая же ситуация будет иметь место, если X станет утверждать, что Y непризнанный рыцарь, а Y заявит, что X — неотъявленный плут.

6. Положим

W = NPA‒P‒R‒R‒NPA,

Z = R‒W, откуда Z = R‒NPA‒P‒R‒R‒NPA,

Y = R‒Z, откуда Y = R‒R‒NPA‒P‒R‒R‒NPA,

X = P‒Y, откуда X = P‒R‒R‒NPA‒P‒R‒R‒NPA.

Тогда X утверждает доказуемость Y, Y утверждает опровержимость Z, Z утверждает опровержимость W, a W утверждает недоказуемость X (действительно, W утверждает недоказуемость ассоциата выражения P‒R‒R‒NPA, которым является само высказывание X).

Если W опровержимо, то W ложно; поэтому X доказуемо и, значит, истинно; следовательно, Y доказуемо, а значит, истинно; стало быть, Z опровержимо, а потому ложно. Отсюда сразу следует, что W неопровержимо. Итак, W не может быть опровержимым; значит, W является неопровержимым, и, следовательно, Z будет ложным.

Далее, если W ложно, то W ложно, но неопровержимо. Предположим, что W истинно; тогда X недоказуемо. Если X истинно, то X истинно и недоказуемо. Предположим теперь, что X ложно; тогда Y недоказуемо. Если Y истинно, то Y истинно, но недоказуемо. Предположим, наконец, что Y ложно; тогда Z неопровержимо. Итак, в данном случае Z ложно, но неопровержимо.

Приведенное рассуждение показывает, что либо W ложно и неопровержимо, либо X истинно и недоказуемо, либо Y истинно и недоказуемо, либо Z ложно и неопровержимо.

7. Эта задача фактически представляет собой просто записанный в других обозначениях вариант задачи 1 данной главы!

Мы знаем, что число 32983 в первой машине Мак-Каллоха порождает число 9832983. Следовательно, по условию Мс 1утверждение 832983 истинно в том и только том случае, если утверждение 9832983 доказуемо. Кроме того, по условию Мс 2; утверждение 9832983 истинно в том и только том случае, если утверждение 832983 не является истинным. Итак, сопоставляя эти два факта, мы получаем, что утверждение 9832983 истинно в том и только том случае, если оно недоказуемо. Значит, решением является число 9832983.

Если мы сравним эту задачу с задачей 1, то увидим, что цифра 9 играет здесь роль N , цифра 8 соответствует символу P, цифра 3 соответствует А, а цифра 2 играет роль тире. В самом деле, если мы заменим символы P, N, А, — соответствующими цифрами 8, 9, 3, 2, то утверждение NPA‒NPA (которое является решением задачи 1) трансформируется в число 9832983 (то есть в решение данной задачи!)

8. Прежде всего отметим, что третья машина Мак-Каллоха также подчиняется закону Мак-Каллоха, который гласит, что для любого числа А всегда найдется некое число X, которое порождает число АХ. Доказывается это следующим образом. Из гл. 13 мы знаем, что существует число Н, а имении число 5464, такое что для любого X число Н 2 Н 2 порождает число Х 2 X 2. (Вспомним также, что число Н 2 Н 2 в данной ситуации порождает само себя; впрочем, к нашей задаче это никакого отношения не имеет.) И теперь произвольное число А и положим X = Н 2 АН 2), Тогда число X порождает число АН 2 АН 2, которое и есть АХ. Таким образом, X порождает АХ. Итак, для любого числа А число X, порождающее число АХ, — это есть число 54642 A 54642.

Пусть нам требуется найти такое X, которое порождало бы 98 X . Предположим, что это X действительно порождает число 98 X . Тогда утверждение 8 X истинно в том и только том случае, если утверждение 98 X доказуемо (согласно условию Мс 1); поэтому утверждение 98 X истинно в том и только том случае, если утверждение 98 X недоказуемо (согласно условию Мс 2). Значит, утверждение 98 X является истинным, но недоказуемым в данной системе (поскольку система правильна).