Логическая задача

Dmitry67 · Post by **Dmitry67** » 03 Nov 2001 05:15

В одной стране был король который никогда не лгал (Клинтон [img:a91b5ee7a2]images/smiles/icon_smile.gif[/img:a91b5ee7a2] )
Он сказал осужденному на казнь
1) тебе отрубят голову в один из дней на рассвете, на следующей неделе (с понедельника по воскресенье, для определенности
2) но так, что это будет абсолютно неожиданно для тебя, то есть заранее знать в какой день тебя казнять ты не будешь

Вечером осужденного навестил адвокат
- Что ты расстраиваешься ? Спросил он. Представь что ты дожил до дня субботы. Значит, для казни осталось одно утро - воскресенье. Но тогда ты знаешь заранее когда тебя казнят ! Поэтому, в воскресенье тебя казнить не могут !

Идем дальше. Воскресенье отпадает. Предположим ты дожил до пятницы. Отсается один день - суббота. Но ты тогда опять знаешь когда тебя казнят ! Суббота тоже отпадает

Так вычеркиваем все дни. Значит ни в один день тебя казнить не могут. Значит, тебя не казнят. Спи спокойно

Обрадованный осужденный так и радовался жизни, пока в четверг утром за ним неожиданно не явились и не казнили с полным соблюдением всех условий

Вопрос: в каком именно месте в рассуждениях адвоката ошибка ?

P.S. Попробуйте рассмотреть задачу с разным числом дней: год (N=365), меньшее количество дней, произвольное N..

P.P.S Задачу встречал в литературе, но ни разу не видел чтобы было приведено правильное решение

dimach · Post by **dimach** » 03 Nov 2001 12:43

<BLOCKQUOTE>quote:<HR>Originally posted by Dmitry67:
Вопрос: в каком именно месте в рассуждениях адвоката ошибка ?
<HR></BLOCKQUOTE>
"Представь что ты дожил до дня субботы"

Melkor · Post by **Melkor** » 03 Nov 2001 15:44

<BLOCKQUOTE>quote:<HR>Originally posted by dimach:

"Представь что ты дожил до дня субботы"<HR></BLOCKQUOTE>

Ну, это можно сформулировать иначе: "если ты дожил до дня субботы". При этом, если осужденный не дожил до дня субботы, то его все равно не могут казнить в воскресенье.

Мне кажется, что проблема в том, что предикат "знать, в какой день казнят" на ранних шагах индукции зависит от более поздних, создавая бесконечный цикл, и, в результате, определенного значения он имеет.

-ЭР- · Post by **-ЭР-** » 03 Nov 2001 19:43

<BLOCKQUOTE>quote:<HR>Originally posted by Dmitry67:
Вопрос: в каком именно месте в рассуждениях адвоката ошибка ?
<HR></BLOCKQUOTE>

Ошибка адвоката заключается в том, что он убедил заключенного в том, что его не могут казнить. Так как заключенный после этих слов адвоката уверен, что его не казнят, то и казнь является для него полной неожиданностью. Кстати, любой день а не только четверг может быть днем казни.

Вот здесь можно почитать поподробнее

Там есть очень интересный пример из статьи Майкла Скривена, который дает довольно простое объяснение парадокса. Процитирую:

Муж говорит своей жене: "Я сделаю тебе ко дню рождения сюрприз. Ты ни за что не догадаешься, какой подарок тебя ожидает. Это тот самый золотой браслет, который ты видела на прошлой неделе в витрине ювелирного магазина". С одной стороны, жена знает, что муж никогда не лжет и всегда выполняет свои обещания. Однако если он все же подарит ей золотой браслет, то это уже не будет сюрпризом и тогда обещание окажется невыполненным, то есть муж сказал ей неправду. А если это так, то к каким выводам может она прийти, рассуждая логически? Не исключено, что муж сдержит слово и подарит ей браслет, нарушив обещание удивить ее неожиданным подарком. С другой стороны, он может сдержать свое слово, что подарок будет неожиданным, но нарушить второе обещание и вместо золотого браслета подарит ей, например, новый пылесос. Поскольку муж своим утверждением сам себе противоречит, у нее нет никаких разумных оснований предпочесть одну из этих возможностей другой, следовательно, у нее нет оснований надеяться на золотой браслет. Нетрудно догадаться, что будет дальше: когда. в день рождения муж преподнесет ей браслет, подарок мужа окажется для нее приятным сюрпризом, поскольку его нельзя предсказать заранее никакими логическими рассуждениями. Муж все время знал, что может сдержать слово и сдержит его. Жена же этого не знала до тех пор, пока обещанное событие не произошло. Утверждение мужа, которое еще вчера казалось ей чепухой и ввергло ее в запутаннейший клубок логических противоречий, сегодня вдруг стало абсолютно правильным и непротиворечивым благодаря появлению долгожданного золотого браслета.

Dmitry67 · Post by **Dmitry67** » 04 Nov 2001 00:00

По этой ссылке находится одна лирика

Вот отгадка
Первая часть рассуждений правильная
Не правилен момент: значит тебя не могут казнить ни в один дней. Значит, тебя не казнят вообще

Правильным продолжением является: Но король сказал, что тебя казнят. Значит, это противоречивая аксиоматическая система. Из противоречивой системы следует ВСЕ ЧТО УГОДНО. (В том числе и что казнят в четверг)

Парадокс в человеческом восприятии
Человек: из противоречия нечего не следует, так как непонятно
Формальная логика: из противоречия следует ВСЕ ЧТО УГОДНО

-ЭР- · Post by **-ЭР-** » 04 Nov 2001 00:37

<BLOCKQUOTE>quote:<HR>Originally posted by Dmitry67:
По этой ссылке находится одна лирика

Вот отгадка
из противоречия следует ВСЕ ЧТО УГОДНО
<HR></BLOCKQUOTE>

Дмитрий,

Честно говоря я не очень понял, чем "лирика" по ссылке отличается от ваших доводов. А пример с браслетом - это именно то, что вы говорили, про противоречивую систему.

С одной только оговоркой. Я бы уточнил ваше утверждение "Из противоречивой системы следует ВСЕ ЧТО УГОДНО.". Наверное правильней было бы сказать, что "для системы, содержащей противоречивые утерждения нельзя утверждать, что любое из этих утверждений истинно или ложно". Здесь есть два момента:

1) Например в задачке, которую вы задали, из противоречивости системы не следует, что адвокату дадут медаль "Мать героиня". А по вашему утверждению, должно следовать ВСЕ ЧТО УГОДНО, в частности то что дадут медаль.

2) В системе может быть 3 утверждения, два из которых противоречивы, а третье ничему не противоречит. Например, к двум противоречивым утверждениям из задачки добавим, что адвокату таки дадут медаль "Мать героиня" в воскресенье. Система при этом остается противоречивой, но из нее следует, что адвокату будет чем похвастаться пред друзьями в понедельник, т.е. можно говорить, что третье утверждение истинно.

[ 03-11-2001: Message edited by: -ЭР- ]

Dmitry67 · Post by **Dmitry67** » 04 Nov 2001 02:55

<BLOCKQUOTE>quote:<HR>Originally posted by -ЭР-:
С одной только оговоркой. Я бы уточнил ваше утверждение "Из противоречивой системы следует ВСЕ ЧТО УГОДНО.". Наверное правильней было бы сказать, что "для системы, содержащей противоречивые утерждения нельзя утверждать, что любое из этих утверждений истинно или ложно". Здесь есть два момента:
<HR></BLOCKQUOTE>

Мы сейчас уйдем в дебри
Давайте отделим мухи от котлет

Есть два понятия: ВИВОДИМО (ДОКАЗУЕМО). Оно совершенно формально. Если система противоречива, то в ней выводимо все что угодно. Потому что FALSE=>TRUE, и FALSE=>FALSE

Есть понятие ИСТИННО и ЛОЖНО. Это более глубокие понятия. Но они определены всегда с опорой на "здравый смысл".

Например, в теореме Геделя конструктивно построенное недоказуемое утверждение "Я недоказуемо" является истинным.

В Соседнем топике про парадокс Банаха с двумя сферами - утверждение о том, что такое разбиение на конечное число частей существует ВЫВОДИМО (в ZF+AC - Цермело Френкеля с Аксиомой Выбора), а ИСТИННО ли оно ? Думаю, для множеств мощностью более счетного понятие ИСТИННО начинает терять смысл...

Melkor · Post by **Melkor** » 04 Nov 2001 14:15

Но ведь парадокс задачи как раз в том, что утверждение короля [i:a88a4487ac]не[/i:a88a4487ac] противоречиво, как мы смогли убедиться. А происходит это потому, что в него входит предикат, описавыющий результат логических умозаключений осужденного, в которые этот самый предикат входит и как аргумент, т.е. он как бы с обратной связью. Предикат будет иметь определенное значение даже если логический вывод пришел к противоречию, это как бы мета-предикат.

-ЭР- · Post by **-ЭР-** » 05 Nov 2001 00:00

<BLOCKQUOTE>quote:<HR>Originally posted by Dmitry67:

Мы сейчас уйдем в дебри
Давайте отделим мухи от котлет
<HR></BLOCKQUOTE>
Ну это вы круто завернули. Мне очень понравилось. Поэт Рождественский написал бы: «Так з-заложит, а-аж небо дрожит» [img:459cece781]images/smiles/icon_smile.gif[/img:459cece781] Вообщем я с вами согласен за исключением все той же выводимости ЧЕГО УГОДНО.

Насколько я помню, теорема Геделя звучит приблизительно так (наверное я немного упрощаю). Для любой достаточно «сложной» аксиоматической системы можно придумать утверждение, такое что внутри этой системы:

1) нельзя будет ни доказать ни опровергнуть это утверждение
2) можно будет доказать, что оно одновременно и истинно и ложно.

Я хотел бы подчеркнуть: “можно придумать”, а не “любое”. Т.е. существуют и утверждения, про которые можно сказать истинны они или ложны.

Что касается «сложности» системы аксиом, то если мне не изменяет память, для теорема Геделя небходимо, чтобы с помощью этой системы можно было описать свойства натуральных чисел.

В вашем примере с истинностью утверждением "Я недоказуемо”, по-моему, не хватает добавления о том, что это утверждение сделано внутри аксиоматической системы и истинно (и ложно) оно, или в случае противоречивости этой системы, или истинность эта не может быть доказана внутри этой системы.

Возможно я что-то упустил в этих высоких [img:459cece781]images/smiles/icon_smile.gif[/img:459cece781] рассуждениях, поэтому предлагаю простой пример. Вот моя система из трех аксиом:

1. Любой осужденный всегда мертв к Воскресенью
2. Любой осужденный всегда жив к Воскресенью
3. Любой адвокат всегда получает медаль в Воскресенье

Эта система противоречива. Следуя, вашему утверждению о том, что из противоречивой системы можно вывести все что угодно, из этой системы можно вывести, что адвокат будет мертв к мометну награждения его медалью. Как формально это вывести?

P.S. В философском плане не могу не согласиться с вашим тезисом о том, что для множеств мощностью более счетного понятие ИСТИННО начинает терять смысл...

[ 04-11-2001: Message edited by: -ЭР- ]

Dmitry67 · Post by **Dmitry67** » 05 Nov 2001 03:01

<BLOCKQUOTE>quote:<HR>Originally posted by Melkor:
Но ведь парадокс задачи как раз в том, что утверждение короля [i:f58a2f3011]не[/i:f58a2f3011] противоречиво, как мы смогли убедиться.<HR></BLOCKQUOTE>

На самом деле в задаче есть более глубокий замкнутый цикл. Ключ - в слове "заранее не сможешь узнать".

В зависимости как мы формально интерпретируем эти слова задача меняется. Например, "не выводимо" или "не выводимо или выводимо, но в противоречивой системе"
Вы правильно подметили слово "мета" - парадокс связывает уровень простой логики (казнят в день X), да/нет и МЕТА уровень - выводимо/невыводимо

Dmitry67 · Post by **Dmitry67** » 05 Nov 2001 03:17

<BLOCKQUOTE>quote:<HR>Originally posted by -ЭР-:
Насколько я помню, теорема Геделя звучит приблизительно так (наверное я немного упрощаю). Для любой достаточно «сложной» аксиоматической системы можно придумать утверждение, такое что внутри этой системы:

1) нельзя будет ни доказать ни опровергнуть это утверждение
2) можно будет доказать, что оно одновременно и истинно и ложно.

Я хотел бы подчеркнуть: “можно придумать”, а не “любое”. Т.е. существуют и утверждения, про которые можно сказать истинны они или ложны.
<HR></BLOCKQUOTE>

Не совсем так. Первая теорема Геделя говорит что в формальной арифметике (и любом ее непротиворечивом расширении) существует высказывание истинное, и недоказуемое, и ложное, но неопровергаемое

Первая теорема Геделя [b:19e71b71d1]конструктивна[/b:19e71b71d1], то есть она говорит не о том что "можно построить", она его ЯВНО СТРОИТ. Если не лень, то это высказывание можно будет написать на бумаге (получится, правда, несколько страниц с кванторами).

Итак, пусть мы сканируем все высказывание формальной арифметики по возрастанию их длины. Упс - натолкнулись на первое недоказуемое высказывание. Мы можем принять его как аксиому, а можем - его отрицание. Так как оно недоказуемо, то в любом случае система останется непротиворечива.

Итак у нас появились ДВЕ разные арифметики. Идем до следующего недоказуемого высказывание. Снова развилка. Итд. Итак, мы имеем бесконечно много разных арифметик, противоречащих друг другу.

Но не все так плохо ! Оказывается, первая развилка неравноценна - одна теория будет Омега-непротиворечива, вторая - Омега-противоречива. Омега непротиворечиваось это более слабое требование чем противоречивость.

Оно говорит вот о чем. Пусть мы можем доказать A(0), A(1), A(2)... A(n).
Вообще, для любого N мы можем доказать A(N)
Очевидно ожидать что можно доказать утверждение: (A перевернутое)N A(N) - Для любого N A(N).
Но это не всегда так.
Может оказаться что это утверждение недоказуемо. Тогда мы его примем в качестве аксиомы.
Если мы примем в качестве аксиомы ее отрицание, то система будет Омега-противоречивой
Таким образом Омега-непротиворечивость является естественной для человека, и как бы путеводной звездой по развилкам - на каждой развилке мы будем идти по Омега-непротиворечивому пути.
Таким образом, хоть существует бесконечно много разных арифметик, только одна из них "хорошая".

К сожалению, все это уже не работает в теории множеств. Судя по всему все теории множеств (их уже черезчур много, и они РАЗНЫЕ) Омега-противоречивы, и неизвестно, может быть они вообще противоречивы (изза второй Теоремы Геделя, вообще непонятно, как доказать их непротиворечивость)

Dmitry67 · Post by **Dmitry67** » 05 Nov 2001 03:29

<BLOCKQUOTE>quote:<HR>Originally posted by -ЭР-:
Что касается «сложности» системы аксиом, то если мне не изменяет память, для теорема Геделя небходимо, чтобы с помощью этой системы можно было описать свойства натуральных чисел.<HR></BLOCKQUOTE>

Да.
Есть еще одно требование, о рекурсивности (алгоритмической разрешимости) правил вывода, но аксиоматика Пеано этому требованию удовлетворяет

<BLOCKQUOTE>quote:<HR>
Возможно я что-то упустил в этих высоких [img:c2d69e75f1]images/smiles/icon_smile.gif[/img:c2d69e75f1] рассуждениях, поэтому предлагаю простой пример. Вот моя система из трех аксиом:

1. Любой осужденный всегда мертв к Воскресенью
2. Любой осужденный всегда жив к Воскресенью
3. Любой адвокат всегда получает медаль в Воскресенье

Эта система противоречива.
<HR></BLOCKQUOTE>

Нет [img:c2d69e75f1]images/smiles/icon_smile.gif[/img:c2d69e75f1].
В ней не заданы правила вывода, поэтому к противоречию в ней придти нельзя - есть три аксиомы, и все, дальше ни на шаг не продвинуться [img:c2d69e75f1]images/smiles/icon_smile.gif[/img:c2d69e75f1]

<BLOCKQUOTE>quote:<HR>
P.S. В философском плане не могу не согласиться с вашим тезисом о том, что для множеств мощностью более счетного понятие ИСТИННО начинает терять смысл...
<HR></BLOCKQUOTE>

Тогда ответьте на вопрос, истинно ли высказывание "существует разрезание шара на конечное количество частей так что из них можно слощить два шара того же диаметра"

P.S. В свое время я очень активно интересовался мат логикой. Меня на это подтолкнул друг. Както пия чай с конфетами в Питере (я был на первом курсе) он задал мне вопрос:
"имеют ли натуральные числа 1,2,3... некое существование безотностительно человеческого разума, или являются лишь способом мышления homo sapiens ?". Сколько я прочел и думал после этого...

P.P.S. А сейчас думаю - лучше бы я в институте с девушками больше развлекался чем о мат логике думал... [img:c2d69e75f1]images/smiles/icon_smile.gif[/img:c2d69e75f1]

-ЭР- · Post by **-ЭР-** » 05 Nov 2001 06:34

<BLOCKQUOTE>quote:<HR>Originally posted by Dmitry67:

В ней не заданы правила вывода
<HR></BLOCKQUOTE>

Тогда я по другому попробую. Скажу сразу, что в мат. логикику я не влезал глубоко (конечно занимался я мат логикой но без точки после первого слова [img:678f4305f3]images/smiles/icon_smile.gif[/img:678f4305f3], поэтому с моей стороны – чистая любительщина [img:678f4305f3]images/smiles/icon_smile.gif[/img:678f4305f3]. Но несмотря на это. Меняю систему аксиом на следующую.

1. Любому осужденному стражник говорит во вторник, что к воскресенью его казнят.
2. Любому осужденному стражник говорит во вторник, что к воскресенью он будет жив.
3. Любому адвокату стражник говорит во вторник, что он (адвокат) получит медаль в воскресенье
4. С любым человеком происходит именно то, что ему говорят.

Номер 4 – есть правило вывода, т.е. можно вывести и то, что осужденный будет казнен и то, что он казнен не будет. Как вывести, что адвоката казнят?

<BLOCKQUOTE>quote:<HR>Originally posted by Dmitry67:

Тогда ответьте на вопрос, истинно ли высказывание "существует разрезание шара на конечное количество частей ...<HR></BLOCKQUOTE>

Я написал "Не могу не согласиться", т.е. согласен я. А про шар - не знаю.

И с вашим P.P.S. я тоже полностью согласен, но с оговоркой [img:678f4305f3]images/smiles/icon_smile.gif[/img:678f4305f3] В отношении девушек очень часто возникают вопросы такие же, что и в отношении 1, 2, 3 [img:678f4305f3]images/smiles/icon_smile.gif[/img:678f4305f3]

Online · Post by **Online** » 12 Nov 2001 01:58

<blockquote>quote:<hr>Originally posted by Dmitry67:
 Идем дальше. Воскресенье отпадает. Предположим ты дожил до пятницы. Отсается один день - суббота. <hr></blockquote>
А другой адвокат говорит так:
"Воскресенье отпадает, если ты дожил до субботы.
Усли ты дожил до пятницы, то казнить тебя могут как в субботу, так и в воскресенье. Так что остаются щесть дней, в которые тебя, засранца, казнят, конечно... С другой стороны, король сказал, что ты не будешь знать "заранее".
А знать, что казнят на этой неделе - это совершенно определенно знать, что тебя казнят на этой неделе, то есть знать заранее. Так что давай-ка мы засудим короля.