Казнить нельзя помиловать
Давеча опять всплыл в локальной области ЖЖ известный парадокс приговоренного. Дабы наконец его похоронить (для себя, по крайней мере), даю правильное и окончательное решение. Обжаловать можно.
Собственно парадокс в формулировке Мартина Гарднера (я только привёл к более привычному нам порядку дней недели):
Осужденного бросили в тюрьму в воскресенье .
- Тебя повесят в полдень, - сказал ему судья,- в один из семи дней на следующей неделе. Но в какой именно день это должно произойти, ты узнаешь лишь утром в день казни.
Судья славился тем, что всегда держал свое слово. Осужденный вернулся в камеру в сопровождении адвоката. Как только их оставили вдвоем, защитник удовлетворенно ухмыльнулся.
- Неужели не понятно? - воскликнул он.- Ведь приговор судьи нельзя привести в исполнение!
- Как? Ничего не понимаю,- пробормотал узник.
- Сейчас объясню. Очевидно, что в следующее воскресенье тебя не могут повесить: воскресенье - последний день недели, и в субботу днем ты бы уже знал наверняка, что тебя повесят в воскресенье. Таким образом, о дне казни тебе бы стало известно до официального уведомления в воскресенье утром, следовательно, приказ судьи был бы нарушен.
- Верно, - согласился заключенный.
- Итак, воскресенье, безусловно, отпадает,- продолжал адвокат,- поэтому суббота остается последним днем, когда тебя могут повесить. Однако и в субботу повесить тебя нельзя, ибо после пятницы осталось бы всего два дня - суббота и воскресенье. Поскольку воскресенье не может быть днем казни, повесить тебя должны в субботу. Но раз тебе об этом станет известно еще в пятницу, то приказ судьи опять будет нарушен. Следовательно, суббота тоже отпадает. Итак, последний день, когда тебя еще могли бы казнить, это пятница. Однако пятница тоже не годится, потому что оставшись в четверг живым, ты сразу поймешь, что казнь должна состояться в пятницу.
- Все понятно! - воскликнул заключенный, воспрянув духом.- Точно так же я могу исключить четверг, среду и вторник. Остается только завтрашний день. Но завтра меня наверняка не повесят, потому что я знаю об этом уже сегодня!
На первый взгляд рассуждение адвоката выглядит необоснованными, ведь очевидно, что палач может неожиданно заявиться в любой день (ну, кроме разве воскресенья, ну, может еще субботы :), но в среду, скажем, - уж точно может). С другой стороны, не видно, где в этом рассуждении ошибка.
Таким образом, решение парадокса подразумевает обоснование одного из вариантов:
1) рассуждение адвоката правильно и казнить узника нельзя,
2) адвокат не прав и казнить можно,
3) приговор противоречив, и опять же казнить нельзя, по крайней мере по этому приговору. Ибо, с логической точки зрения, из противоречия следует всё что угодно, невозможно определить - правильно рассуждение или ложно.
Обсуждение самим Гарднером этого парадокса само является образцом парадоксальности :) Он считает, что рассуждение адвоката неверно, ибо приговор противоречив! При этом он приводит еще две формы этого парадокса (как он думает), которые «на самом деле» про другое. В общем-то у него там даже по-больше получается, поскольку он эти задачи по разному интерпретирует, и решения «на самом деле» всё время разные :)
Наша задача исключть все эмоциональные переживания и словесную эквилибристику, переведя тем самым парадокс в чисто логическую форму. Понятно, что при этом всё же не избежать интерпретации собственно приговора, ведь нам надо перевести размытые и многозначные слова в строгие логические определения. И, как оказывается, здесь зарыта одна из собак, в большой степени этот парадокс имеет не логическую, а семантическую природу.
Ну так, начнем. Ясно, что в первую очередь надо внимательно присмотреться к этому таинственному «знанию» узника.
Во-первых, что может знать узник, а чего - не может? На мой взгляд, очевидно, что он не может знать будущего, над ним мы не властны. То есть он не может знать тот день, в который его казнят. Его просто не станет, и знать будет некому. Но узник может (в принципе) знать день, на который назначена казнь (когда его должны казнить). Это вот такое первое и важное различение - «назначение казни» и «исполнение казни».
Во-вторых, нам необходимо как-то формализовать само понятие «знания». Что это значит вообще, что узник знает день назначения казни? Вот, скажем, сообщают ему, что казнь сегодня, а он в ответ - а я уже знаю. Но это же явное безобразие - он должен как-то объективно обосновать свое знание.
Казалось бы, можно потребовать от узника заранее (прямо после оглашения приговора) написать на бумажке день казни. Но, во-первых, это будет чистое угадывание, а не знание, а во-вторых, что еще важнее, это слишком сильное требование, нарушающее приговор, -ведь ему достаточно иметь «знание» непосредственно перед утренним уведомлением о предстоящей казни.
И здесь очень красивая и продуктивная идея, которую выдвинул timur0 (что и подтолкнула меня разобраться до конца, так что timur0 полноценный соавтор этого текста, да и ещё имеющий то преимущество, что за этот текст не отвечает :) ), - узник должен предъявить пришедшему глашатаю казни (отождествим его дальше для упрощения с палачём) формальный логический вывод, доказывающий, что казнь назначена именно на сегодня, - это и будет его знание. А приговор, естественно, задает логическую модель (аксиомы) для этого вывода.
И теперь решение парадокса раскладывается на следующие этапы:
1) формализация приговора (построение аксиоматики),
2) формализация в этой аксиоматике рассуждения адвоката, которое мы оформляем как «знание» узника,
3) доказательство - либо истинности «знания» для любого дня недели, либо его ложности для какого-то дня, либо противоречивости самой аксиоматики (приговора).
Логическая модель приговора:
Прежде всего опеределим термы (логические факты).
Определение 1:
k(i) - казнь назначена на день i (где i пробегает значения от 1 до 7),
d(i) - казнь состоялась в день i
Аксиомы казни (-> - импликация, логическое следование; ~ - отрицание, логическое НЕ):
А1а ≡ d(i) -> k(i) (чтобы казнь состоялась, она должна быть назначена)
А1б ≡ ~ k(i) -> ~ d(i) (если казнь не назначена, она не может состояться).
Аксиома неизбежности назначения казни.
Казнь непременно назначена и только в один из семи дней (ну, то, что она не может быть назначена дважды, - это понятно: либо она сразу состоится, либо узник сможет избежать назначенной казни через своё «знание», тогда его казнить уже нельзя, приговор нарушен. Если же казнь вообще не назначать, то она не состоится, как следует из А1, и будет нарушено незыблимое слово судьи, чего мы допустить не можем).
Формально это будет выглядеть так:
А2 ≡ k(1) & ~k(2) &…~k(7) ˅ ~k(1) & k(2) &…~k(7) ˅ … ˅ ~k(1) & …& ~k(2) & k(7)
где & - коньюнкция (логическое И ), ˅ - дизьюнкция (логическое ИЛИ), ~ - отрицание
(логическое НЕ).
Пора нам определить (функциональный) предикат «знания», который и будет обозначать ту логическую формулу, которую предъявляет узник палачу (о его структуре чуть позже).
Определение 2 (предикат знания казни) - ЗК(i)
Этот предикат должен давать истинное значение, если в него подставить k(i) = истина, и ложное, если для любого j <> i k(j) = истина. Т.е. я (узник) знаю, что казнь назначена на день i и не назначена на какой-либо другой день.
Теперь мы можем сформулировать еще одну аксиому из приговора:
Аксиома отмены казни.
Если узник «узнал» назначенный день казни, то она не может состоятся:
А3 ≡ ЗК(i) -> ~ d(i)
Вот и всё с аксиомами. Переходим теперь к конкретизации предиката ЗК(i). Ясно, что мы должны исключить возможность назначения казни в любой другой день (не в день i), тогда по аксиоме А2 мы сможем утверждать, что назначенный день казни будет i. Запишем это так:
ЗК(i) ≡ А2 & ИКВ(i)
где ИКВ(i) - предикат исключения всех дней казни, кроме i. Понятно, что все дни, предшествующие i, можно исключить автоматически, а все последующие дни (после i) только на основании рассуждения. Итак, мы можем записать:
ИКВ(i) ≡ ~ k(1) & … ~ k(i -1) & ИК(i + 1) & … & ИК(7)
где ИК(i) - предикат исключения казни в день i. То есть он должен обрашаться в истину, если k(i) есть ложь (казнь не назначена на день i) , и наоборот - быть ложным, когда k(i) есть истина.
Но что мы можем использовать в ИК(i) - по существу, только аксиому A3 (что и делает адвокат):
ИК(i) ≡ ЗК(i) -> ~ d(i)
Таким образом мы формализовали «знание» узника (соответствующее рассуждению адвоката), оформив его как логическое высказывание. Рассмотрим теперь, как оно работает:
Воскресенье
Для последнего дня получить ЗК(7) очень просто:
ЗК(7) ≡ А2 & ~ k(1) & … ~ k(6)
Очевидно, что это истина, если k(7) есть истина, и только в этом случае. То есть, действительно, в воскресенье казнить узника не могут (у него есть «знание», если он пережил субботу).
Пошли дальше.
Суббота
ИКВ(6) ≡ ~ k(1) & … ~ k(5) & ИК(7)
Подставим сюда k(7) = ложь, тогда:
ИК(7) ≡ ЗК(7) -> ~ d(7);
ЗК(7) = ложь;
Из лжи следует всё, что угодно, следовательно ИК(7) = истина. Вроде бы исключили воскресенье.
Но если k(7) = истина, ЗК(7) = истина и опять же ИК(7) = истина, в том случае, если d(7) есть ложь (казнь назначена, но не состоялась).
Таким образом ИК(7) не может служить оператором исключения казни. В субботу у заключеного «знания» нет. Рассуждение адвоката ошибочно.
По простому говоря, в субботу узник «знает», что казнь не состоится в воскресенье, но он не может знать, что она на воскресенье не назначена. Ведь отсутствие казни в последний день может иметь две причины - либо она не назначена на этот день, либо назначена, но отменена из-за «воскресного знания» узника. И у заключенного нет оснований для выбора одного из этих вариантов.
Так что узника можно казнить (в рамках нашей формальной интерпретации приговора) в любой день, кроме воскресенья.
Здесь важно отметить, что в число аксиом приговора у нас не включена аксиома незбежности казни для d(i), аналогичная аксиоме А2. Т.е. мы допускаем в принципе, что казнь вообще может не состояться. Что же произойдет, если всключить такую аксиому (А4) ? Вот тогда, как легко убедиться, узник может построить «знание» для любого дня, ибо в этом случае из аксиом A1, А2 и А4 следует k(i) ≡ d(i) и ИК(7) обращаются в ложь при k(7) = истина (что верно и для и всех ИК(i)) . Как бы :)
Но при этом сама система аксиом становится противоречивой - раз узник всегда «знает» день казни, то казнить его нельзя, что противоречит аксиоме о неизбежности казни. И это понятно, аксиомы А1, А2 и А4 говорят, что из назначения казни всегда следует её исполнение, а А3 указывает, что возможен такой случай, что казнь назначена, а исполнение невозможно - это и есть заложенное в логическую модель противоречие.
Вот такой забавный вывод, если отказаться от формальной неизбежности казни (но не её назначения), то узника можно казнить по искомому приговору, и судья сдержит своё слово (даже при самй «либеральной» трактовке «знания»). Т.е. казнь тогда неизбежна.
А вот если фактическую неизбежность казни трактовать как формальную неизбежность (как условие приговора) - тогда казнить нельзя, ибо приговор становится противоречивым.