LinkBack URL
About LinkBacks
Задача о двух дверях
Вы в комнате с двумя дверями: за одной вас ожидает смерть, а за другой свобода. Так же в комнате находится служитель, который знает какая дверь куда ведёт. Известно, что он обязан либо всегда говорить правду, либо всегда лгать. Необходимо задав один вопрос узнать где дверь на свободу.
П.С. Чтобы было интереснее, не говорите сразу правильный ответ, озвучим его через несколько дней.
Правильный ответ: ЬЖсГхюЦЭюЙюаЦН,ПшлЧЯлБ,-ЦИ,ДцчЮЖуЭргД.уПцлОК
Последний раз редактировалось Joremar; 22.02.2011 в 13:02.
То ли я ещё играю роль, то ли роль уже играет мною.
Женя, я тебе указал на ошибку и указал на не состыковки в логике, однако ты видеть их просто не хочешь, уверенный в непогрешимости своего решения.Сообщение от Joremar
Во-первых тыц, во-вторых тыц-тыц, в третьих тыц-тыц-тыц. Нежелание понимать написанного мною - это не ко мне.
И ещё, я ничего не путаю. Небольшой ликбез по логическим операциям, в частности исключающее или (a ≠ b, не равно):прямая импликация (подчинение, ¬a ⋁ b, a ≼ b):
- 0 ⊕ 0 = 0
- 0 ⊕ 1 = 1
- 1 ⊕ 0 = 1
- 1 ⊕ 1 = 0
обратная импликация (a ⋁ ¬b, a ≽ b):
- 0 → 0 = 1 (¬0 ⋁ 0)
- 0 → 1 = 1 (¬0 ⋁ 1)
- 1 → 0 = 0 (¬1 ⋁ 0)
- 1 → 1 = 1 (¬1 ⋁ 1)
отрицание:
- 0 ← 0 = 1 ( 0 ⋁ ¬0)
- 0 ← 1 = 0 ( 0 ⋁ ¬1)
- 1 ← 0 = 1 ( 1 ⋁ ¬0)
- 1 ← 1 = 1 ( 1 ⋁ ¬1)
двойное отрицание:
- ¬ 0 = 1
- ¬ 1 = 0
конъюнкция (логическое и):
- ¬ (¬ 0) = 0
- ¬ (¬ 1) = 1
дизъюнкция (логическое или):
- 0 ⋀ 0 = 0
- 0 ⋀ 1 = 0
- 1 ⋀ 0 = 0
- 1 ⋀ 1 = 1
Так вот, Женя, в твоей задаче между двумя логическими частями предложения, даже в твоём ответе, явно идёт не двойное отрицание, просто часть речи "что" в вопросе "можешь ли ты утверждать, что это дверь в рай?" однозначно не выражает нужную логическую операцию.
- 0 ⋁ 0 = 0
- 0 ⋁ 1 = 1
- 1 ⋁ 0 = 1
- 1 ⋁ 1 = 1
Смотри, распишем приведённое тобою решение с точки зрения алгебры логики: «можешь ли ты утверждать, что это дверь в рай?»:Допустим следующие определения:
Распишем твоё решение.
- Правдолюб - истина, true, т.е. 1.
- Лжец - ложь, false, т.е. 0.
- Ответ да - истина, true, т.е. 1.
- Ответ нет - ложь, false, т.е. 0.
Сведём итоговую таблицу, причём первую часть выражения (стоящую до искомой операции) менять нельзя (правдолюб, лжец), хотя можно попробовать отрицать её, а вот часть между искомой операцией и равенством менять можно (т.е. комбинировать разные вопросы):
- Дверь в рай:
- 1 ? 1 = 1
- 0 ? 1 = 1
- Дверь в ад:
- 1 ? 0 = 0
- 0 ? 0 = 0
Вот теперь можно пробовать искать логическую операцию, которая объединит левую и правую часть выражения.
- 0 ? 0 = 0
- 0 ? 1 = 1
- 1 ? 0 = 0
- 1 ? 1 = 1
Видим, что решения «в лоб», одной логической операцией, не получается.
- 0 ⊕ a = 0 (допустимо a = 0, т.к. 0 ⊕ 0 = 0)
- 0 ⊕ a = 1 (допустимо a = 1, т.к. 0 ⊕ 1 = 1)
- 1 ⊕ a = 0 (допустимо a = 1, т.к. 1 ⊕ 1 = 0)
- 1 ⊕ a = 1 (допустимо a = 0, т.к. 1 ⊕ 0 = 1)
Зато теперь можно нарисовать следующую табличку (0 - лжец, 1 - правдолюб; 0 - дверь в ад, 1 - дверь в рай), собственно решение:
Т.е. в итоговом ответе должен присутствовать ещё один вопрос, на который и лжец и правдолюб всегда и однозначно должны ответить нет, либо это должен быть не вопрос, а просто утверждение которое всегда возвратит ложь. Увы, я не литератор, поэтому перевести два исключающих или на литературный русский язык не могу, я лишь привёл логику итогового ответа, с точки зрения дискретной математики. Заодно, кстати, доказав отсутствие полноты в приведённом тобою ответе, а следовательно и ошибочность ответа в том виде в котором ты его представил ;)
- 0 ⊕ (0 ⊕ 0) = 0 ⊕ 0 = 0
- 0 ⊕ (0 ⊕ 1) = 0 ⊕ 1 = 1
- 1 ⊕ (0 ⊕ 1) = 1 ⊕ 1 = 0
- 1 ⊕ (0 ⊕ 0) = 1 ⊕ 0 = 1
ps: Да, кстати, искренне надеюсь, что всё выше написанное не покажется тебе абракадаброй и абстрактными фразами.
пс: jennydr, всё ещё хочу книжку Виктора Егоровича «Дискретная математика» ;)
---------- Сообщение добавлено в 12:22 ---------- Предыдущее сообщение было в 12:18 ----------
А зачем?
Ты лучше докажи что-либо не написав рекурсивную функцию (что уже само по себе не предусматривает простого ответа в удобочитаемой форме), а с точки зрения математического аппарата алгебры логики (читай с точки зрения дискретной математики). Кстати, можешь попробовать решить задачу при помощи алгебры множеств - тоже вариант ;)
Последний раз редактировалось oldengremlin; 27.02.2011 в 15:13.
«Когда у общества нет цветовой дифференциации штанов — то нет цели!»
http://oldengremlin.blogspot.com/
Fire (27.02.2011), lucky (27.02.2011), the_aLeXiS (27.02.2011)
пока не планирую=)
Адрес : шоссе Красных Фонарей, XII
Ну наконец-то! Не логическая операция, тогда что? Обратимся к словарю:
"Что - союз. Присоединяет придаточное предложение к главному"
То есть, "что" - это никакое не ИЛИ, а... скобка!
Олден, можешь ли ты заранее согласиться или не согласиться с тем, что (я_скажу_позже)? Если да, то дальше можешь не читать - сделай это, а я потом подберу какое-нибудь весёленькое утверждение.
Если ты читаешь это, значит согласен, что "что" в логике - это скобка, а исходный вопрос выглядит так:
"Можешь ли ты утверждать что (за дверью рай)?".
Учитывая, что правдивец не может утверждать ложного выражения, а лжец - истинного, получаем следующую таблицу:
Ответчик___(за дверью Рай)___Можешь ли ты утверждать___Ответ
Честный______true__________________true______________________ true
Лжец_________true__________________false______________________ not(false)=true
Честный______false__________________false______________________false
Лжец_________false__________________true______________________ not(true)=false
То ли я ещё играю роль, то ли роль уже играет мною.
Я могу согласиться, что без поллитры я этого вопроса не пойму, так как скобка, Женя, в алгебре логики не является операцией, обратись к раздел логики высказываний. Равно как и часть речи (союз) "что" выражает отношение, но не логическую операцию.
Ты просто сейчас пытаешься подменять понятия и свойства алгебры логики, и это говорит лишь о том, что фундаментальных знаний по предмету у тебя нет, но интуитивно ты что-то такое чувствуешь. :(
Хочешь я покажу тебе уличную магию?
Любую логическую операцию можно выразить через дизъюнкцию, конъюнкцию и отрицание. Т.о. исключающее или (да, да, почему-то тебе эта операция жутко не нравится) можно выразить таким образом: a ⊕ b = (a ⋁ b) ⋀ (¬a ⋁ ¬b) = (a ⋀ ¬b) ⋁ (¬a ⋀ b)
Простая сводная таблица:0 0 (0⋁0)⋀(1⋁1)=0 (0⋀0)⋁(1⋀0)=0Ничего не напоминает?
0 1 (0⋁1)⋀(1⋁0)=1 (0⋀0)⋁(1⋀1)=1
1 0 (1⋁0)⋀(0⋁1)=1 (1⋀1)⋁(0⋀0)=1
1 1 (1⋁1)⋀(0⋁0)=0 (1⋀0)⋁(0⋀1)=0
А теперь смотри, есть такое свойство операции исключающего или: a ⊕ 1 = ¬a, что собственно и можно считать одним из определений не (not).
Ну и опять, даже исходя из предложенной тобою таблицы:
Расписано, разжёвано…
Отобразим функцию трёх переменных:
Попытаемся найти первую операцию воспользовавшись коммутативностью ⊕ и вычленим из f(x,y,z) функцию двух переменных f(x,y):
- x y z f(x,y,z)
- (0?0)⊕1=0
- (0?1)⊕0=1
- (1?0)⊕0=0
- (1?1)⊕1=1
получили f(x,y) = (¬x ⋀ ¬y) ⋁ (¬x ⋀ y) [вроде бы не ошибся? ;)]; исключающее или ⊕, в свою очередь, тоже можно разложить: ⊕(a,b) = a ⊕ b = (a ⋁ b) ⋀ (¬a ⋁ ¬b) = (a ⋀ ¬b) ⋁ (¬a ⋀ b)
- x y f(x,y)
- 0?0=1
- 0?1=1
- 1?0=0
- 1?1=0
Пока имеем:
f(x,y,z) = (¬x ⋀ ¬y) ⋁ (¬x ⋀ y) ⊕ z;
…но заниматься дальнейшими упрощениями просто лениво, да и домой пора… уже 5 минут как закончилось дежурство;)… так что пусть это будет заданием для самостоятельной работы :)
Ежели чего не понятно - прямая дорога в В.Е.Ходакову на его лекции по "Дискретной математике".
Надеюсь, что даже невооружённым взглядом видно, что нет тут места простому отрицанию или даже двойному отрицанию ;)
ps: На 100% правильность последних выкладок не претендую, так как очень хочется спать (всё-таки после поезда и сразу на работу). Если кому не будет лениво - проверьте меня ;)
«Когда у общества нет цветовой дифференциации штанов — то нет цели!»
http://oldengremlin.blogspot.com/
the_aLeXiS (27.02.2011)
Далее не читаю, так как:
---------- Сообщение добавлено в 07:58 ---------- Предыдущее сообщение было в 07:49 ----------
"І знов двійка, Носенко"(с). До вычисления х - у не определён, а до вычисления у - не определён z. Правильная функция - z(y(x)).Отобразим функцию трёх переменных:
x y z f(x,y,z)
То ли я ещё играю роль, то ли роль уже играет мною.
У меня появилась идея как однозначно определить чей метод решения является правильным. Выложим блок-схемы своих алгоритмов решения.
Уточню задачу: определить ответ на вопрос "Можешь ли ты утверждать, что за дверью рай?", с учётом того что за дверью и кем является ответчик: честным(может говорить только правду) или лжецом ( может говорить только неправду).
То ли я ещё играю роль, то ли роль уже играет мною.
Собственно, вот:
То ли я ещё играю роль, то ли роль уже играет мною.
Евгений, для того чтобы решить эту задачу в твоём духе достаточно из таблицы составить ДНФ или КНФ и блок-схема тут и даром не нужна.
Что такое ДНФ и КНФ тебе, надеюсь, известно?
---------- Сообщение добавлено в 11:38 ---------- Предыдущее сообщение было в 11:26 ----------
Таблицу истинности привёл не ты?
Блок-схема, в таком виде, Евгений, как привёл её ты, содержит пять блоков с условиями, что уже не является одним вопросом из условия задачи.
Так что на счёт двойки ты прав, только ставить её ты, увы, должен сейчас себе.
Ещё раз - один вопрос! В условии задачи должен быть один вопрос, т.е. одно логическое выражение, а не пять!
По приведённой тобою таблице можно составить и КНФ и ДНФ, т.к. есть и входные параметры и результат который должны получить.
А спор можно решить просто. Ты только скажи, не отказываешься от составленной тобою таблицы истинности? /да, нет/
---------- Сообщение добавлено в 11:52 ---------- Предыдущее сообщение было в 11:38 ----------
Давай пошагово.
Эта таблица истинности верна?
Ну так как отступать тебе не куда, так как эта таблица приведена именно тобою то посмею предположить, что твой ответ будет "да".
Принимаем следующие сокращения
a - "Ответчик"
b - "за дверью Рай"
c - "Можешь ли ты утверждать"
f - "Ответ"
Теперь смотри на полную таблицу соответствий итоговой фкнкции:
a b c | f
0 0 0 | 0
0 0 1 | 0
0 1 0 | 1
0 1 1 | 0
1 0 0 | 0
1 0 1 | 0
1 1 0 | 0
1 1 1 | 1
Заметь, ещё ни одной логической операции я не ввёл, так как на данном этапе они попросту не нужны.
Сможешь исходя из этой таблицы соответствий составить ДНФ или КНФ?
---------- Сообщение добавлено в 11:57 ---------- Предыдущее сообщение было в 11:52 ----------
А где тут один вопрос? Женя, в условиях задачи требуется один вопрос, т.е. один условный блок, т.е. один ромбик!
«Когда у общества нет цветовой дифференциации штанов — то нет цели!»
http://oldengremlin.blogspot.com/
the_aLeXiS (01.03.2011)
он просто каждое условие (типа "это рай?" и "служитель честный?") зачем-то по два раза в каждой ветви проверял, чем сильно запутал блок-схему.
В той схеме был учтен тип ответчика. Чтож, если это для тебя слишком сложно, держи две схемы - отдельно для честного и для лжеца - с одним условием в решении.А где тут один вопрос? Женя, в условиях задачи требуется один вопрос, т.е. один условный блок, т.е. один ромбик!
a b c | fТеперь смотри на полную таблицу соответствий итоговой фкнкции:
0 0 0 | 0 - OK
0 0 1 | 0 - Fail
0 1 0 | 1 - OK
0 1 1 | 0 - Fail
1 0 0 | 0 - OK
1 0 1 | 0 - Fail
1 1 0 | 0 - Fail
1 1 1 | 1 - OK
fail - функция не имет значения, так как нарушается условие задачи (честный может говорить только правду, а лжец - только лгать).
Учитывая ошибочность таблицы, а так же то, что <oldengremlin:"что" выражает отношение, но не логическую операцию>, составление ДНФ или КНФ не имеет смысла.Сможешь исходя из этой таблицы соответствий составить ДНФ или КНФ?
Итак, я продолжаю настаивать на том, что твой метод решения ошибочен. Опровергнуть это может только предоставление блок-схемы рабочего(!) алгоритма решения по твоему методу.
То ли я ещё играю роль, то ли роль уже играет мною.
Ваши права 
