Задача о стражнике и дверях (именно об одном стражнике и двух дверях)

[Olden Gremlin]

Недавно на одном из форумов у меня с товарищем возникла небольшая дискуссия, относительно решения одной задачи. Суть самой задачи сводится вот к чему:

Я путник, зашёл в комнату в которой есть две двери. Одна дверь ведёт к жизни (в рай), другая к смерти (в ад). При этом в комнате есть один(!) стражник. Причём равновероятно он может быть либо лжецом, либо правдолюбом, т.е. он может либо постоянно лгать на любой заданные ему вопрос, либо отвечать правду. Задача в том, чтобы составить запрос (как бы дико он не звучал на человеческом языке), который однозначно указывал бы нам в какую дверь можно идти (т.е. дверь в рай), а в какую нет (дверь в ад).

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

Spoiler

Итоговые рассуждения из дискуссии со своим оппонентом.

Справедливости ради начну с доводов своего оппонента.
Вот его первый ответ, звучащий человеческим языком: "можешь ли ты утверждать, что это дверь в рай" и рассуждение:

Рассмотрим все варианты:
Дверь в рай
---Правдолюб может так сказать, и он ответит да.
---Лжец так сказать не может, потому что это было бы правдой, но он соврёт и так же скажет "ДА"
Дверь в ад
---Правдолюб не может так сказать, и он ответит "нет"
---Лжец был бы обязан так сказать, но он врёт и отвечает "нет".

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

Ну наконец-то! Не логическая операция, тогда что? Обратимся к словарю:
"Что - союз. Присоединяет придаточное предложение к главному"
То есть, "что" - это никакое не ИЛИ, а... скобка!
Олден, можешь ли ты заранее согласиться или не согласиться с тем, что (я_скажу_позже)? Если да, то дальше можешь не читать - сделай это, а я потом подберу какое-нибудь весёленькое утверждение.

Если ты читаешь это, значит согласен, что "что" в логике - это скобка, а исходный вопрос выглядит так:
"Можешь ли ты утверждать что (за дверью рай)?".
Учитывая, что правдивец не может утверждать ложного выражения, а лжец - истинного, получаем следующую таблицу:

Ответчик___(за дверью Рай)___Можешь ли ты утверждать___Ответ
Честный______true__________________true______________________ true
Лжец_________true__________________false______________________ not(false)=true
Честный______false__________________false______________________false
Лжец_________false__________________true______________________ not(true)=false

Другими словами, сокращённо:

a b c | f
0 0 1 | 0
0 1 0 | 1
1 0 0 | 0
1 1 1 | 1

где:

• a - ответчик
• b - нужная дверь
• c - ответ стражника
• f - идём или не идём

Собственно решение которое по концовке выдал пой оппонент и на котором продолжает настаивать: (b and c) or ( b and not c)

Теперь то, что в конце-концов получилось у меня:

a b c | f | описание
0 0 0 | 0 - /лжец отвечает нет напротив ненужной двери/
_____________лжец ответил правду - это невозможно, т.е. f=0!
0 0 1 | 0 - /лжец отвечает да напротив ненужной двери/
_____________лжец соврал: "это дверь в рай?", ответил "да", но нам не нужна дверь в ад (f=0)
0 1 0 | 1 - /лжец отвечает нет напротив нужной двери/
_____________лжец соврал: "это дверь в рай?", ответил "нет", но эта дверь в рай нам нужна (f=1)
0 1 1 | 0 - /лжец отвечает да напротив нужной двери/
_____________лжец ответил правду - это невозможно, т.е. f=0
1 0 0 | 0 - /правдолюб отвечает нет напротив ненужной двери/
_____________правдолюб: "это дверь в рай?", ответил "нет", но нам не нужна дверь в ад (f=0)
1 0 1 | 0 - /правдолюб отвечает да напротив ненужной двери/
_____________правдолюб солгал - это невозможно, т.е. f=0
1 1 0 | 0 - /правдолюб отвечает нет напротив нужной двери/
_____________правдолюб солгал - это невозможно, т.е. f=0
1 1 1 | 1 - /правдолюб отвечает да напротив нужной двери/
_____________правдолюб: "это дверь в рай?", ответил "да", эта дверь в рай нам нужна (f=1)

т.е. таблица строится из заведомо известных трёх предпосылок:

• a - перед нами либо лжец(0), либо правдолюб(1), но кто именно мы не знаем;
• b - перед нами дверь либо в рай(1), либо в ад(0), но какая именно мы не знаем;
• c - если мы зададим вопрос «в лоб» то лжец солжёт, а правдолюб ответит правду;

и должна нас вести к результату:

• f - нас интересует только тот ответ стражников который приведёт в рай, но не в ад.

Т.е. f(a,b,c) = (¬a⋀b⋀¬c)⋁(a⋀b⋀c) = b⋀((¬a⋀¬c)⋁(a⋀c)) = b⋀(¬(a⋁c)⋁(a⋀c))

Концептуально спор сейчас сводится к следующему:

Во-первых, для частного случая т.№1:

a b c | f
0 0 1 | 0
0 1 0 | 1
1 0 0 | 0
1 1 1 | 1

Обе формулы:

• f(a,b,c) = (b⋀c)⋁( b⋀¬c)
• f(a,b,c) = (¬a⋀b⋀¬c)⋁(a⋀b⋀c) = b⋀((¬a⋀¬c)⋁(a⋀c)) = b⋀(¬(a⋁c)⋁(a⋀c))

вроде бы как верны, но… если рассматривать итоговую таблицу для ф.№1 то получаем т.№2:

a b c | f
0 0 0 | 0
0 0 1 | 0
0 1 0 | 1
0 1 1 | 1
1 0 0 | 0
1 0 1 | 0
1 1 0 | 1
1 1 1 | 1

а для ф.№2, т.№3:

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

то мой оппонент так и не смог дать обоснования решению для комбинаций f(0,1,1) и f(1,1,0), кроме как то, что для т.№1 эти решения являются несущественными, т.е. их можно игнорировать.

Во-вторых, мой оппонент продолжает настаивать лишь на истинности его решения (ф.№1 & т.№2), считая моё (ф.№2 & т.№3) абсолютно неверным.
В-третьих, как будет звучать вопрос в переводе на литературный русский язык?

Собственно слово тем кто хочет присоединится к дискуссии Меня интересуют мнения независимых экспертов … в большей степени мнения по "во-вторых" и "во-первых".

[apprentice]

Можно задать только один вопрос, и получить только один ответ?

[Olden Gremlin]

Можно задать только один вопрос, и получить только один ответ?

Да, только один вопрос и получить только один ответ - либо правдивый, либо лживый. Но вот кто перед вами, лжец или правдолюб - изначально неизвестно.

[Ленивая Бестолочь]

в xkcd было:
2 двери и 3 стражника - один всегда врёт, другой всегда говорит правду, а третий убивает тех, кто задаёт скользкие вопросы :)

[apprentice]

Как вам такой вопрос:

"Если ты честен - покажи где рай, если обманщик - покажи где ад."

[eddy]

"Если ты честен - покажи где рай, если обманщик - покажи где ад."

Честный покажет на рай, лгун - тоже
Хороший вопрос.

[BURF]

"Если ты честен - покажи где рай, если обманщик - покажи где ад."

Честный покажет на рай, лгун - тоже

А ответ лгуна: я честен, рай там -> (показывает на ад) не сработает?

[/dev/random]

Как вам такой вопрос:

"Если ты честен - покажи где рай, если обманщик - покажи где ад."

Или можно перефразировать так, чтобы это всё-таки было _вопросом_, а не просьбой:
"Если рай - для честных, а ад - для лгунов, то за какой дверью место для таких, как ты?"

[eddy]

А ответ лгуна: я честен, рай там -> (показывает на ад) не сработает?

Тогда он признается, что лгун, в общем, не сработает.

[apprentice]

ответ лгуна: я честен

А его не спрашивают честен он он или нет

По условиям задачи он должен всегда отвечать ложь, если он укажет на ад то это не будет ложью.

На самом деле тут имеет значение только одно - признает ли автор загатки данный ответ правильным, или существуют другое, более интересное решение.

"Если рай - для честных, а ад - для лгунов, то за какой дверью место для таких, как ты?"

Это звучит красивее, но требует дополнительного условия.

[SLEDopit]

Если ты скажешь, что за этой дверью рай, ты мне солжешь?

[/dev/random]

Если ты скажешь, что за этой дверью рай, ты мне солжешь?

Не подходит. Если за ней рай, то честный скажет "нет", а лжец - "да".

[Olden Gremlin]

"Если ты честен - покажи где рай, если обманщик - покажи где ад."

Честный покажет на рай, лгун - тоже
Хороший вопрос.

Честный покажет на рай, а лгун на то и лгун, о соврёт, что он лгун и покажет на ад.
Вопрос хороший, но не лишён не однозначностей. Не катит

[/dev/random]

Не катит

А мой?

[Olden Gremlin]

На самом деле тут имеет значение только одно - признает ли автор загатки данный ответ правильным, или существуют другое, более интересное решение.

Автор загадки настаивал на том, что правильным ответом является: "можешь ли ты утверждать, что это дверь в рай?". Но с такой трактовкой ответа я был не согласен, потому и началась дискуссия с поиском ответа, о чём сокращённо нарисовано под спойлером в ТС.

Дико звучащие вопросы:

• "ты лжец и перед нами дверь в рай и ты не можешь этого утверждать или ты честный и перед нами дверь в рай и ты можешь это утверждать?", т.е. простая "в лоб" интерпретация f(a,b,c) = (¬a⋀b⋀¬c)⋁(a⋀b⋀c);
• "перед нами дверь в рай и, ты лжец и не можешь этого утверждать или ты честный и ты можешь это утверждать?", т.е. попытка интерпретации f(a,b,c) = b⋀((¬a⋀¬c)⋁(a⋀c)).

Уж не уверен в том, что вопрос благозвучен с точки зрения литературного языка, но во всяком случае по данным формулам приводит к однозначному указанию на то какая дверь ведёт в рай Или нет?

[Olden Gremlin]

Или можно перефразировать так, чтобы это всё-таки было _вопросом_, а не просьбой:
"Если рай - для честных, а ад - для лгунов, то за какой дверью место для таких, как ты?"

Интересно составленный вопрос.
Но вопрос в том, где лгун может соврать: в том, что он лгун или в том где его место, или и там и там сразу? Неоднозначность

[Olden Gremlin]

Если ты скажешь, что за этой дверью рай, ты мне солжешь?

Ух ты. Неожиданно.

• Ставлю себя на место правдолюба:
  • ты указываешь на дверь ведущую в рай: "нет";
  • ты указываешь на дверь ведущую в ад: "да".
• Ставлю себя на место лжеца:
  • ты указываешь на дверь ведущую в рай: "да";
  • ты указываешь на дверь ведущую в ад: "нет".

Пояснения требуют, наверное, лишь ответы лжеца:

• я лжец, путник указывает на дверь ведущую в рай и задаёт свой вопрос: за дверью действительно рай, но могу ли я об этом сказать - не могу, ведь я лгун, т.е. за дверью ад; солгу ли я если отвечу, что за дверью рай - нет, но я лгун - поэтому отвечу да;
• я лжец, путник указывает на дверь ведущую в ад и задаёт свой вопрос: за дверью действительно ад, но могу ли я об этом сказать - не могу, ведь я лгун, т.е. за дверью рай; солгу ли я если отвечу, что за дверью рай - да, но я лгун - поэтому отвечу нет.

Т.е. видим противоречие в ответах лжеца и правдолюба, но мы не знаем кто перед нами…

[apprentice]

соврёт, что он лгун и покажет на ад.

я уже говорил, его не спрашивают о том кто он, его спрашивают где ад, и он должен ответить не правду.


В общем это логическая задача в два действия, если мы будем знать кто перед нами то мы сможем правильно интерпретировать ответ на главный вопрос, но промежуточная информация о том кем является стражник нас не интересует, поэтому первый ответ (кто ты) можно сократить.

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

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

[alv]

Да, только один вопрос и получить только один ответ - либо правдивый, либо лживый.

Если следовать формулировке буквально, задача не решаема. Потому что любой вопрос типа

Если ты честен - покажи где рай, если обманщик - покажи где ад.

на самом деле содержит два вопроса: стражника спрашивают не только про дверь, но и в неявном виде - про него самого.

[aiming]

А если поставить вопрос ребром?
показать на любую дверь и сказать - "если там рай - зайди туда".

[Olden Gremlin]

В общем мой вердикт - задача тривиальная

Так и хочется сказать - спасибо Кеп. Всегда нравились безапелляционные товарищи… А провести мало-мальский анализ своего единственно правильного ответа, религия мешает? Ну ладно…

Я стражник, ты задаёшь мне свой вопрос: "Если рай - для честных, а ад - для лгунов, то за какой дверью место для таких, как ты?":

• Я - честный: я честный? да. показываю на дверь в рай;
• Я - лжец: я лгун? да, но если я так отвечу то я скажу правду, а я должен соврать, поэтому считаю, что я честный. где место для честных? в раю, но если я покажу на дверь в рай то я скажу правду, поэтому я должен солгать и я лгу - вот она дверь в твой "рай", и ты идёшь прямо в ад.

Что не так?

А если поставить вопрос ребром?
показать на любую дверь и сказать - "если там рай - зайди туда".

Увы, он страж - он никуда не идёт, он лишь отвечает на вопрос.

[apprentice]

Если следовать формулировке буквально, задача не решаема. Потому что любой вопрос тип

на самом деле содержит два вопроса: стражника спрашивают не только про дверь, но и в неявном виде - про него самого.

Ага, а если еще допустить что стражник-лжец будет думать (как тут некоторые предлагали), то на любой самый заковыристый вопрос он ответит так что бы ввести в заблуждение спрашивающего.

[t.t]

"Если рай - для честных, а ад - для лгунов, то за какой дверью место для таких, как ты?"

Отлично! Не только с точки зрения логики, но с точки зрения смысла. (:

Или можно перефразировать так, чтобы это всё-таки было _вопросом_, а не просьбой:
"Если рай - для честных, а ад - для лгунов, то за какой дверью место для таких, как ты?"

Интересно составленный вопрос.
Но вопрос в том, где лгун может соврать: в том, что он лгун или в том где его место, или и там и там сразу? Неоднозначность

Неоднозначности нет: его не спрашивают, лгун ли он; его спрашивают, где его место.

Чтобы уже точно без неоднозначности, нужно не «для таких, как ты», а «для тебя».

[t.t]

Да, только один вопрос и получить только один ответ - либо правдивый, либо лживый.

Если следовать формулировке буквально, задача не решаема. Потому что любой вопрос типа

Если ты честен - покажи где рай, если обманщик - покажи где ад.

на самом деле содержит два вопроса: стражника спрашивают не только про дверь, но и в неявном виде - про него самого.

Почему же? По-моему, Олег уже продемонстрировал, как два вопроса превратить в один. Для полной точности — с моей поправкой: «Если рай для честных, а ад для лгунов, то за какой из дверей место для тебя?»

[apprentice]

«Если рай для честных, а ад для лгунов, то за какой из дверей место для тебя?»

это как раз очень важная поправка, т.к. одной честности для попадания в рай недостаточно, этот стражник, возможно, режет невинных людей десятками... но все это домыслы, т.к. в даже в такой формулировке неявный вопрос "то ты такой" присутствует.

[t.t]

даже в такой формулировке неявный вопрос "то ты такой" присутствует.

Ну, если так рассуждать, то в классической задаче с _двумя_ стражниками тоже присутствует неявный вопрос «кто _он_ такой».

[zhekas]

Вопрос:"Если бы я тебя спросил где рай, то на какую дверь ты бы указал?"

[apprentice]

Ну, если так рассуждать, то в классической задаче с _двумя_ стражниками тоже присутствует неявный вопрос «кто _он_ такой».

А разве я утверждал обратное?

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

"Если бы я тебя спросил где рай, то на какую дверь ты бы указал?"

честный покажет на рай, обманщик на ад и все.

[zhekas]

"Если бы я тебя спросил где рай, то на какую дверь ты бы указал?"

честный покажет на рай, обманщик на ад и все.

тогда он скажет правду.

[/dev/random]

честный покажет на рай, обманщик на ад и все.

Нет. Это _классический_ ответ. ЕМНИП, автор задачи предлагал именно его.
"Если бы я тебя спросил где рай, что бы ты мне ответил?"
Если бы он спросил обманщика, где рай, обманщик бы показал на дверь ада. Значит, чтобы солгать в ответ на полный вопрос, обманщик должен показать на дверь рая.