史上最难的逻辑题

转自：http://jandan.net/2012/12/30/hardest-logic-problem.html




现在马上就要到新年了，蛋友们是在上班呢还是在打发无聊的周末呢？无聊的话，试试下面这道逻辑题吧。在理想情况下，你差不多得把一上午花在这道题上。


题目在此：

现在有三位神祗，名字分别“真实”、“虚伪”、和“任意”，但是你并不知道哪位神祗名字是什么。“真实”永远说真话，“虚伪”永远说假话，而“任意”所说的话是真是假则完全是随机的。现在，你需要辨识出这三位神祗的真实名字，只能问3次答案是“是”/“否”的问题，每个问题只能针对一个神祗（但你可以问多个神祗同样的问题）。神祗能听懂你说的话，但是祂们只会用自己的语言回答你的问题。在他们的语言中是否分别为da, ja，但是你也不知道哪个是“是”，哪个是“否”。

在1996年，美国逻辑学家George Boolos最早给出问题的解答（很不幸，他给出解答的不久之后就去世了。）这个问题的难点在于它将“语言不通”、“真实与虚伪”和“随机性”三者融入到一起。哲学家声称，破解难题的勇士们将能透彻地理解逻辑学的本质。

















It's that strange time of year, the lull between Christmas and New Year, when you're notreallycelebrating but notreallyworking either. So, how about you wrap your brain around the world's hardest logic puzzle to keep yourself amused? Y'know, just for fun.


New Scientist has a lovely feature(which is available to read if you sign up for a free account) in its Christmas issue about the world's most difficult logic problem. If you're wondering what could possibly be so tough, check it out:

"Three gods A, B, and C are called, in some order, True, False, and Random. True always speaks truly, False always speaks falsely, but whether Random speaks truly or falsely is a completely random matter. Your task is to determine the identities of A, B, and C by asking three yes-no questions; each question must be put to exactly one god. The gods understand English, but will answer all questions in their own language in which the words for 'yes' and 'no' are 'da' and 'ja', in some order. You do not know which word means which."

It was dreamt up—and solved—by US logician George Boolos shortly before his death in 1996. What makes it so difficult is it's incredible amount of problems, all squeezed into one puzzle: language barriers, untruthfulness, and randomness, too. Philosophers claims that cracking the puzzle reveals the true nature of logic itself to those willing to toil with the problem—but if you can't be bothered, you can find a (relatively) simple solutionhere.



但是，一个上午废了N张草稿纸也解不出来是么？不用着急，我们有答案。（痛戳答案）
答案打不开？打开之后全是看不懂的鸟语花香？别急，这是中文版答案。

马克一下

“在1996年，美国逻辑学家George Boolos最早给出问题的解答”

那么在他给出解答之前，人们是如何知道这道题可解的呢？

可能科学家证明了2不可解，并且找到了4个问题的解，所以三个问题就变成了一个猜想直到1996年

身边没纸笔，胡乱说几句。
题目中最麻烦的是随机回答者，嵌套问题中如果出现一次随机神，那就没意义。所以至少要有一个问题没有随机神。由于我们不知道谁是随机神，所以有两条路:1 通过问题获知谁是随机；2 构造3个类似问题各缺少一个神，分析出谁是随机神。我倾向于后者

已短路！

答案看不懂

答案同样看不懂路过一下。。智商太低

打发时间的好东西，留着慢慢想。

可以轻松通过设置悖论的方法一个问题就辨识出虚伪,但随机无法仅通过一个问题辨识出吧

想了三分钟，如果能问6个问题的话那就很容易，三个问题这也太少了

mark

美国可以合法拥有枪支，用枪抵着脑门问吧:"别TM给我废话什么da啊ja，你是谁？否则把你打成爆米花！" :-)

那个逻辑学家肯定也是想太猛了脑子血管爆裂而死的吧。。。

有个类似的题，比这简单点，谎话村和实话村，两村交叉路口上各站一个村民，你要到实话村，只能问一个问题

本帖最后由 山寨饭 于 2013-1-2 16:04 通过手机版编辑

答案的第二种，看明白了。但第一种的第一个问题看不懂，求解。

我来解释一下第二种答案吧：
首先，对任何问题 Q，都可以定义如下的内嵌问题 ：E(Q)=ja么？ 即 若用你此刻的心态（E）来回答 Q 这条问题，你会回答 "ja" 吗？
无论向哪一位神祇发问E(Q)=ja么？，若祂回答 ja，则表示 Q 的真正答案必为“是”；若答 da，则 Q 的真正答案必为“否”。
这是答案2的核心，我来重点说一下：

1.假设E是真的，那么有两种情况
1.1Q为真的情况下：ja假定为真，则问题就是以你的心态这个为真的问题是真的么？回答：真=ja；如果ja假定为非，则问题就是以你的心态这个为真的问题是假的么？回答：非=ja。即E是真实的情况下，Q为真的情况下，回答必为ja。
1.2Q为假的情况下：ja假定为真，则问题就是以你的心态这个为非的问题是真的么？回答：非=da；如果ja假定为非，则问题就是以你的心态这个为非的问题是假的么？回答：是=da。即E是真实的情况下，Q为非的情况下，回答必为da

2.假设E是非的，那么对于问题Q，不论Q的真假，E（Q）的真实答案=非（Q），而因为E为非，所以在回答的时候会否认真实答案，所以回答=非（真实答案）=非[非（Q）]=真（q）
真（q）的情况在1中论述过了

所以综合1+2，得出结论：无论向哪一位神祇发问E(Q)=ja么？，若祂回答 ja，则表示 Q 的真正答案必为“是”；若答 da，则 Q 的真正答案必为“否”。


剩下的就简单了，直接贴维基上的答案了
Q1: 你是任性之神吗？
Q2: 你是真实之神吗？
Q3: 你是任性之神吗？

E（Q1）=ja么？问A，回答ja，则A是任性，然后用E（Q2）=ja么？问剩下两个任何一个，就行了。
E（Q1）=ja么？问A，回答da，则确定A不是任性；然后E（Q2）=ja么？，确定A是真实还是谎言，最后用E（Q3）=ja么？问剩下两个任意一个，得解。

第二个答案解释完了，希望大家指正。谁知道的一种解法是怎么回事的，给说说呗。

[本帖最后由 魂影 于 2013-1-2 17:02 编辑]

前面这个引理就有问题，对于随机神来说，问题是什么根本是无所谓的，所以要借随机神的回答来分析信息简直不可能。所以“无论向哪一位神祇发问E(Q)=ja么？，若祂回答 ja，则表 ... ”这个部分，对诚实和虚伪都是成立的，但对随机不成立。

对于随机神也是成立的，你仔细看我的回答，随机神就是自我意志为 是或者非，根据问题的证明，是或非的结论是一致的。是就是1，非就是2。

[本帖最后由 魂影 于 2013-1-2 17:41 编辑]

注意看原题：任性之神会随意说真话或假话，而不是随意说ja或da，这意思是不一样的！

but whether Random speaks truly or falsely is a completely random matter
这样子这题目的叙述就太脑残了
本来就不简单，为什么还要在叙述上设陷阱，故意误导人


换一种说法：三个诚实的神，两种语言。第一个和第二个的语言对ja和da的定义相反，而第三个神会随机选用一种语言

speaks truly or falsely不是speaks ja or da，原文很清楚啊！

题目在此：



现在有三位神祗，名字分别“真实”、“虚伪”、和“任意”，但是你并不知道哪位神祗名字是什么。“真实”永远说真话，“虚伪”永远说假话，而“任意”所说的话是真是假则完全是随机的。现在，你需要辨识出这三位神祗的真实名字，只能问3次答案是“是”/“否”的问题，每个问题只能针对一个神祗（但你可以问多个神祗同样的问题）。神祗能听懂你说的话，但是祂们只会用自己的语言回答你的问题。在他们的语言中是否分别为da, ja，但是你也不知道哪个是“是”，哪个是“否”。

问题具象化，把问题Q代入为“1+1是否等于2”则相当于问：

针对1+1是否等于2这个问题，依照你的心态你会回答“ja”吗？

随机精神病的回答肯定是可能ja也可能da啊，这根问题根本就无关啊。

真的说的很清楚么？
我就理解错了。LS某位也理解错了

他加一句说明，很多人就不会把时间浪费在没意义的方向上

真假之外，还有不真不假的悖论
这个就是给回答者设置悖论

这样子的话，就没多难了
就是把那个诚实岛与谎言岛的故事稍微复杂化

我已经说过了，用悖论轻松就可以析出说假话的，很简单，但是遇上随机的根本没办法

他根本就不是真正的随机

but whether Random speaks truly or falsely is a completely random matter.

那你要给他改成怎么随机？

答案或对或错，但不能无法判断对错
这就限制了他的答案，所以不是完全随机

我知道你的意思，随机真假的前提是起码你要知道孰真孰假，但在二至逻辑以外的领域还存在真假未知这个第三值，所以随机是不能确保做到的。
严格说所有这类问题在题目本身上就存在逻辑缺陷，一定说假话的人和一定随机真假的人，设定这个条件在逻辑上就是错的，因为二值逻辑不适用于所有情形，但题目又不能做严格限定，所以解答方式本身也可以钻这个空子。但你要较真这个的话就没法解析了

这题可以列入我国小学生暑假作业了

注意是所说的话是真是假是完全随机的，不是说ja或da是随机的！注意看题

这题的原意肯定是不讨论悖论的问题的，非要用悖论来说，我觉得就是抬杠了

受不了了，随机说真话或说假话，在回答一个是否问题的情形下，必然表现为随机答ja 或 da，这难道还需要争么………………

悖论不是你想不讨论就可以不讨论的，一个设置上存在逻辑上的缺陷的问题遇上悖论那叫天经地义明白么？说真话砍头说假话绞死那个故事就是典型的题目设置有逻辑缺陷被人用悖论攻破的例子。

这个不是缺陷，你理解不对，这个随机指的是，先判定真或假，然后用随机所得的真或假来做题目得出答案，即结果的真假和前面进行判断的真假是相一致的。而你说的随机是说的结果的随机与前面是否判断无关，如果按你的说法，题目自然就应该是说ja和da。

当然不一样，请看我上面的证明，如果按照真话假话判断，发问E(Q)=ja？那无论真话假话，结果都是一定的！！！

这道题的解法思路就是运用一个问题，能够让真假话都获得一致的答案。
在E(Q)=ja这个问题中，真假话不会对结果有任何影响，结果是ja还是da只与Q的真假有关，Q为真则答案是ja，Q为假则答案是da！！！！

[本帖最后由 魂影 于 2013-1-2 18:58 编辑]

你别怪我说话直，你根本没理解为什么这种题目必然导致悖论，也无法解决悖论。

这么说吧，假设你就是说一定假话的神，下面这个问题你该怎么回答：

对“你是假话神吗？”这个问题，你的答案是“是”还是“否”？


你仔细想一下就明白了，面对这种问题，“一定说假话”的这个前提设置根本就是不可能的，或者说是错的。

代入具体值验算一遍吧。
设ja等于“是”，设Q等于“1+1等于2吗？”这个问题。
你遇上随机神，
问：“1+1等于2吗？”这个问题依照你的心态，你会回答“是”吗？
随机神对问题Q的心态如果是说真话，那么第一步答案应当是“是”，但是由于对这个嵌套了问题的大问题他的心态还是随机说真假话，所以他可能答“是”也可能答“否”，也就是说及可能答ja也可能答da，这还能判断个毛啊…………

这个我说了属于悖论，类似的还有这世界有没有永恒不变的真理，如果你非要这么说我认为是抬杠了，因为那不是题目的本意。
只要你肯承认题目说的是真假随机，不是ja da随机 就行了，钻牛角尖就没意思了，你说是不？

题目有缺陷导致了悖论，结果说指出这个问题的人抬杠钻牛角尖………………这这这………………

你的题目就错了，应该是问：“1+1等于2吗？”这个问题依照你的心态，你会回答“ja”吗？这个ja可以为”是“也可以为”假“，无论随机神的心态是真是假，他都会回答ja！！！！

[本帖最后由 魂影 于 2013-1-2 19:07 编辑]

可能是因为我没有加黑，放大字体，没变变红色，所以你没有看见“代入具体值”几个字………………
无非就是真和假两个值么，我以为可以举一反三，所以没必要穷举，看来是我偷懒了
问题Q有真假两个值，ja有指真或假两种可能，组合一共四种，但不管哪一种情形，随机神都有两个选择……这没必要穷举吧…………

不好意思，是没看到带入具体值。
带入具体职业没变化啊，你红字部分之矛盾的，按题目你现在的心态，即对Q心态是真话，那么一直就是真话状态解答，如果是假话就是一直佳话状态解答，判断一次不是两次！

问的问题是：若用你此刻的心态……，是一个给定的值，而不是随时变化的。

出去吃了点东西这题让你改成这样了………………

让我们先回顾一下题目设置的前提，需要指出的是如果这个前提我们可以篡改，我想就没有任何再讨论研究的必要了。
题目原文摘要：
中文：
现在有三位神祗，名字分别“真实”、“虚伪”、和“任意”，但是你并不知道哪位神祗名字是什么。“真实”永远说真话，“虚伪”永远说假话，而“任意”所说的话是真是假则完全是随机的。

英文：
Three gods A, B, and C are called, in some order, True, False, and Random. True always speaks truly, False always speaks falsely, but whether Random speaks truly or falsely is a completely random matter.

好，再强调一次：
随机神（经病）和前两者一样，也是永远，always随机真假不定的，他说真假话完全是completely random 。

记住了这个前提再回看你们的演绎：
你从维基百科复制过来的解答原文是：
无论向哪一位神祇发问E(Q)=ja么？，若祂回答 ja，则表示 Q 的真正答案必为“是”；若答 da，则 Q 的真正答案必为“否”。
换言之：
如果你的问题Q的真正答案是“是”，则随机神经病肯定是回答“ja”这一个答案，而不会随机，
ok，现在已经与前提冲突了，所以你们的解答本身篡改了前提，已经错误了。
如果这个你接受不了，我们带入我刚才提的具体值再演绎一次：
设问题Q指的是“1+1是否等于2”，“ja”的值无所谓，真假皆可，
现在问随机神：
对“1+1是否等于2”这个问题，依照你的心态，你会回答“ja”吗？
根据你们的“解答”，随机神对这个问题的答案一直是“ja”，
但是，如果随机神对问题Q“1+1是否等于2”的心态是（偶然地）说真话回答是，那么对嵌套了Q的这个大问题，他如果也一致地说是；如果随机神对问题Q“1+1是否等于2”的心态是（偶然地）说假话回答否，那么对嵌套了Q的这个大问题，他如果也一致地说否；请注意，这里是重点，在这种情况下，对于嵌套了问题Q的大问题，随机神的回答不再是随机真或假的了，而是一定真。明白吗？他的心态对问题Q随机是什么状态，他在大问题里就会真实地回答这个状态，也就是说，对大问题，他保持说真话。

而这，已经和前提冲突。

所以你们的解答是建立在更改题目前提的基础上，说错误都不够，已经没有意义了。

这里与你的观点我觉主要分歧就是判定真假一次还是2次，甚至n次。

从原文but whether Random speaks truly or falsely is a completely random matter.可见 completely random 是对truly or falsely说的，而不是ja或da说的。结合维基给出问题的条件：mental state即是他此刻究竟想回答真话抑或假话。注意此刻，所以必定是一次判定。

至于你说的“在这种情况下，对于嵌套了问题Q的大问题，随机神的回答不再是随机真或假的了，而是一定真。明白吗？他的心态对问题Q随机是什么状态，他在大问题里就会真实地回答这个状态，也就是说，对大问题，他保持说真话。”这是不对的，假如他此刻说假话那么E(Q)就是对问题Q的真实答案说假话，这就是假话下他对大问题的真实回答，又因为他要说假话，所以他要说大问题的真实回答的假话，也就是Q的真实答案的假话的假话。



[本帖最后由 魂影 于 2013-1-2 21:57 编辑]