Математическая логика

[cati]

неoбычная задачка: Нeктo нaхoдится в oднoм из гoрoдoв А или В, надo придумaть вoпрoс для пеpвого встречнoгo, пpичeм нектo нe знaет лoжeн oтвeт нa eгo вoпpoc или иcтинeн, нo пo oтвeту надo тoчнo oпрeдeлить, в кaком из гoрoдoв oн нaхoдитcя.

Совсем голову сломала... :)
помогите с чего начать

[arseniiv]

(Оффтоп)

Если правильно нашёл, то «О прохожий, я нахожусь в городе A, и ты говоришь правду?»

Начнём с того, что найдём зависимость того, находимся ли мы в городе A ($A$) от того, что нам ответили ($S$) и говорит ли прохожий правду ($T$). Затем нам надо будет найти зависимость $S(A,T)$. Если её нет, значит, искомого вопроса не существует!

[ShMaxG]

arseniiv

(Оффтоп)

Ответ в виде "Да, вы в городе А и я не вру" может дать как правдивец, так и лжец. Т.е. это может быть как правдой, так и не правдой.

[arseniiv]

Вот тут имелось ввиду, что сначала он внутри говорит правду, а потом произносит её в зависимости от правдивости. Тогда бы подошло. А иначе как-то сложно выходит. Значит, нужен немного другой подход, но не знаю, какой.

[cati]

(Оффтоп)

а если предположить такой вопрос: ecли я ваc cпрошу, в гoрoдe A ли мы нaходимcя, вы oтвeтитe "дa"?

как будет выглядеть на такой вопрос сама "формула " выражения и соответствующая таблица истинности ?

[ShMaxG]

(Моя попытка)

У меня получилось, что можно задать такой вопрос: "Я нахожусь в А и вру?"

[Alfucio]

ShMaxG в сообщении #403528 писал(а):

(Моя попытка)

У меня получилось, что можно задать такой вопрос: "Я нахожусь в А и вру?"

(Оффтоп)

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

Мне кажется, что «исключающее или» подходит. Вроде бы по таблице истинности и с последующей инверсией ложных ответов получается :).

[Maslov]

Если эти города населяют только лжецы и правдецы, то работает вопрос типа
"Что ответит на вопрос о моём местонахождении человек, чья правдивость совпадает с твоей?"

[ShMaxG]

Alfucio
Хм, а у меня почему-то получаются все 4 разных Ладно тогда...

[Andrei666]

Цитата:

"Что ответит на вопрос о моём местонахождении человек, чья правдивость совпадает с твоей?"

не катит

[Maslov]

Andrei666 в сообщении #403600 писал(а):

Цитата:

"Что ответит на вопрос о моём местонахождении человек, чья правдивость совпадает с твоей?"

не катит

В каком случае "не катит"?

[Alfucio]

ShMaxG в сообщении #403598 писал(а):

Alfucio
Хм, а у меня почему-то получаются все 4 разных Ладно тогда...

Я пытаюсь следующим образом проверить через таблицу:
В «А» ли мы сейчас? / Вру ли я (относится к отвечающему)? / Ответ на вопрос (честный)? / Ответ от данного человека (обратный, если врет).
$\begin{array}{*{20}{c}} {{\rm{AreWeInA?}}}&{{\rm{AmILying?}}}&{{\rm{TruthfulAnswer}}}&{{\rm{RealAnswer}}}\\ 0&0&0&0\\ 0&1&0&1\\ 1&0&0&0\\ 1&1&1&0 \end{array}$

Как мне кажется, если будет XOR, то получится.

Возможно, мы по-разному поняли условия, или я где-то ошибаюсь...

(Про оформление таблицы)

Извините, что так оформляю «таблицу», подскажите, пожалуйста, более удачный способ.

[Andrei666]

Цитата:

не катит

В каком случае "не катит"?[/quote][/quote] да во всех!

[Alfucio]

Maslov в сообщении #403591 писал(а):

Если эти города населяют только лжецы и правдецы, то работает вопрос типа
"Что ответит на вопрос о моём местонахождении человек, чья правдивость совпадает с твоей?"

Сейчас заметил, как мне кажется, что Ваш ответ можно распространить до общего решения задачи:
«Скажите, пожалуйста, что ответит человек на вопрос „В пункте А ли я“, если он будет отвечать также, как Вы сейчас (то есть будет или не будет врать)?»

[Shtirlic]

Maslov в сообщении #403591 писал(а):

Если эти города населяют только лжецы и правдецы, то работает вопрос типа
"Что ответит на вопрос о моём местонахождении человек, чья правдивость совпадает с твоей?"

Если один город населен только лжецами (скажем А), а другой правдивцами (скажем В). То подойдет вопрос: "вы в этом городе живете?". Лжец в городе "А" скажет нет, правдивец в городе "А" скажет нет. Лжец в городе "В" скажет да, правдивец в городе "В" скажет да.

-- Пн янв 24, 2011 19:40:10 --

Alfucio в сообщении #403672 писал(а):

Maslov в сообщении #403591 писал(а):

Если эти города населяют только лжецы и правдецы, то работает вопрос типа
"Что ответит на вопрос о моём местонахождении человек, чья правдивость совпадает с твоей?"

Сейчас заметил, как мне кажется, что Ваш ответ можно распространить до общего решения задачи:
«Скажите, пожалуйста, что ответит человек на вопрос „В пункте А ли я“, если он будет отвечать также, как Вы сейчас (то есть будет или не будет врать)?»

Да, это правильно. Либо два раза обман (правда), либо ни одного обмана (правда).
Есть похожая задача. Заключенный, две двери. В одной свобода, другая к виселице. Два охранника, один всегда лжет, другой говорит правду. Можно задать один вопрос и выбрать одну дверь. Какой вопрос нужно задать?
Ответ: "Что скажет твой коллега, если я спрошу его за какой дверью свобода". В любом случае пройдет один раз обман (на одном из двух стражей), значит надо выбрать другую дверь. Сюда тоже подходит.