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

Таким образом, у нас имеются два утверждения X и Y, причем X утверждает, что Y допускает распечатку, а Y утверждает, что X не допускает распечатки.

Предположим теперь, что X допускает распечатку. Тогда утверждение X окажется истинным, а это будет означать, что утверждение Y допускает распечатку. Но тогда Y окажется истинным, откуда будет следовать, что X распечатки не допускает. Тем самым мы приходим к противоречию, поскольку в данном случае X оказывается одновременно и допускающим, и не допускающим распечатку; следовательно, утверждение X не может быть напечатано. Далее, раз X не допускает распечатки, а Y как раз это и утверждает, то, стало быть, утверждение Y является истинным. Таким образом, мы имеем:

(1) X не допускает распечатки;

(2) Y истинно.

Наконец, утверждение X может быть либо истинным, либо ложным. Если X истинно, тогда, согласно (1), X истинно, но не допускает распечатки. Если же X ложно, тогда Y не допускает распечатки, поскольку само X говорит нам о том, что Y допускает распечатку. Значит, в данном случае Y истинно — согласно (2) — и не допускает распечатки. Итак, либо X, либо Y истинно и не допускает распечатки — однако определить, какое именно из этих двух выражений истинно и не допускает распечатки, оказывается невозможно.

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

Подобная ситуация рассматривается в последней главе моей книги «Как же называется эта книга?» в разделе «Дважды гёделевы острова», к которому мы и отсылаем читателя.

3. Положим Z = PA-P-NP-РА.

Далее, положим Y = NP-Z (то есть Y = NP-РА-Р-NP-РА).

Положим, наконец, Х = Р-Y (то есть Х = Р-NP-PA-P-NP-PA).

Из этих выражений сразу ясно: X утверждает, что Y допускает распечатку, а Y говорит нам о том, что Z не допускает распечатки. Что же касается Z, то оно утверждает, что допускает распечатку ассоциат утверждения Р-NP-РА; но ассоциат Р-NP-РА есть утверждение Р-NP-РА-Р-NP-РА, которое в свою очередь и есть X! Итак, Z утверждает, что X допускает распечатку.

Таким образом, X утверждает, что Y допускает распечатку, Y утверждает, что Z не допускает распечатки, a Z утверждает, что распечатку допускает X. Посмотрим теперь, что же из этого следует.

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

(1) Z не допускает распечатки;

(2) Y истинно.

Далее, X может быть либо истинным, либо ложным. Предположим, что X истинно. Если Z ложно, то тогда X не допускает распечатки, а это означает, что X истинно, но не допускает распечатки. Если же Z истинно, то тогда, поскольку, согласно (1), оно не допускает распечатки, Z истинно, но не допускает распечатки. Итак, если X истинно, то либо X, либо Z истинно, но не допускает распечатки. Если же X ложно, тогда Y не допускает распечатки и, следовательно, Y истинно — согласно (2) — и не допускает распечатки.

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

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

5. а) Выберем в качестве X утверждение Р-RA-Р-RA, а в качестве Y — утверждение RA-Р-RA. Ясно, что X утверждает доказуемость Y, а Y утверждает опровержимость ассоциата выражения Р-RA (ассоциат Р-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-Р-R-R-NPA.

Х = Р-Y. откуда Х = Р-R-R-NPA-Р-R-R-NPA.

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

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