有史以来最难的逻辑谜题是由逻辑学家 Raymond Smullyan 和 John McCarthy 提出的,此谜题在20世纪90年代就已闻名于世。

想象一下这里有三位信使,分别为True, False,Random。其中True总说真话,False总说假话,Random时真时假。你的任务是通过询问他们是/否的问题来确认三者的身份。但有一个额外的难题:信使们拥有自己神秘的语言,他们的回答会是“DA” / “BAL”,但你并不得知那个代表“YES”,哪个又代表着“NO”。

最简单而又最困难谜题(解决最难逻辑谜题)(1)

令人惊讶,其实我们只需三个问题就足以解开这个谜。在你开始思考之前,你需要事前了解三件事:

如果你此刻绞尽脑汁,请不要绝望,毕竟它可是被誉为有史以来最难的逻辑谜题。解决这个问题通常的思路是:通过询问第一个问题,您需要找出非Random身份的信使 X。接着你再问X两个问题,第二个问题用来确定X是True还是False,第三个问题确定另外两位的身份。

当且仅当

这个方案使用了逻辑中当且仅当的概念:给定两个命题A、B,命题“当且仅当A,B”为真,意思是“A和B都为真或都为假”,否则命题为假。(本文的当且仅当是数学中逻辑关系,可能我们自己理解的因果关系略有偏颇,不过不要担心,请记住这个逻辑门关系来阅读本文),此逻辑举例说明:

当且仅当月亮是奶酪做的时,2 2=4,该命题为假。因为两个命题一个为真,一个为假。

而当且仅当月亮是奶酪做的时,2 2=5,该命题为真。因为这两个命题均为假。

最简单而又最困难谜题(解决最难逻辑谜题)(2)

月亮不是奶酪做的

“当且仅当”是“异或”的否定,你可以在此网址仔细阅读:https://plus.maths.org/content/os/issue36/features/nishiyama/index

从简单开始

现在我们回到最开始的谜题并做一个简化:假设DA代表“YES”,BAL代表“NO”。

首先,假设您已经向某个信使O提出了第一个问题,该信使O已经确定了X不是Random。你能想出一个简单的问题来揭示X是谁吗? 再接着,你能不能再提问X一个简单的问题来揭示另外两位信使的身份?

READING

以下是答案

为了判断X是True还是False,你只需问一个你已经知道答案的问题,例如: 2加2等于4吗?

要找出另外两个的身份,你可以这样问X:这个信使(指着你问的第一个信使O)是Random吗?

因为你已知道X是True或是False,你就可以确定你指着问的第一个信使O是否是Random。通过排除,您也可以识别出第三位的身份。

第一个问题

我们还是假设DA是“YES”,BAL是“NO”(稍后我们再讨论语言问题),我们先关注需要提问的第一个至关重要的问题,也是最困难的问题。随便找一个信使O问:

当且仅当这个信使(你指向一个信使,称之为 P)是Random,你是True吗?

如果您从O得到的答案是“是”且O为True,则P必是Random。因为当且仅当规定只要两部分均为真,或均为假,则为真;如果答案为“是”且O为False,则真实的答案应该为“否”,命题“当且仅当P为Random时O为True”为假。由于第一部分“ O为True”为假,因此第二部分“ P身份为Random”一定为真。

所以无论O是True还是False,答案“是”都告诉我们信使P的身份是Random,这意味着第三个信使,称为Q,不是Random。

如果O是Random,答案“是”告诉我们什么? 它不能确定地告诉我们P是什么,但这无关紧要。在这种情况下,因为O是Random,第三个信使 Q肯定不是Random。

综上所述,如果答案是“是”,那么我们可以肯定地说,无论O是什么,第三个信使Q肯定不是Random。

如果O的回答是“否”呢? 如果O为True,这就意味着P不是Random;如果O为False,那么正确答案应该为“是”,这个命题为真命题。则因为命题的第一部分为假,则命题的第二部分“P是Random”在这种情况下必然为假命题,即“P不是Random”。

所以无论O是True还是False,答案为“否”就告诉我们P不是Random。

如果O是Random,答案“否”会告诉我们什么? 它告诉我们P不是Random,因为O已是Random。

综上所述,答案“否”告诉我们,无论O是什么,P都不是Random。

在这两种情况下,无论O的答案是“是”还是“否”,我们都能确定其中一个信使不是Random的身份。如果O的答案是“是”,那么信使Q不是Random。如果O的答案是“否”,那么信使P就不是Random。这就达到了找出非Random身份的信使X的目的。我们现在可以按照步骤进行另外两个问题,进而解开谜题。下面的图表说明了我们将提问的三个问题以及各种答案。

最简单而又最困难谜题(解决最难逻辑谜题)(3)

该图列举了三个问题的各种答案。其中T代表True,F代表False,R代表Random。

注意,当且仅当的作用是在并不知道O是True/False/Random的情况下,从O的答案中获得确定性信息。

DA 和BAL

让我们来思考最初的谜题-------你并不知道DA和BAL的意思。因此我们需要引入深一层“当且仅当”,即通过在这三个问题的最后加上“当且仅当DA表示‘YES’”,我们可以把答案DA解释为对原问题的肯定答案,把答案BAL解释为对原问题的否定答案。下一节中,我们将举例说明它,现在我们将陈述这个谜题通常的解法。

首先选择一个信使O并问它:“当且仅当P是Random,当且仅当DA表示“YES”,你是True吗?”

当这两个命题“当且仅当P是Random,O是True” 和 “ DA代表‘YES’”同时为真或同时为假时,这个命题为真。

和以前一样,这个问题将识别出非Random身份的信使 X。然后,你再问X:“当且仅当DA代表‘YES’”,2 2=4吗?”

据此你将会判断出X是“True”还是“False”;

最后你再问X:“当且仅当DA代表‘YES’,O是Random吗? ”

和之前一样,因为你已经知道X的身份,所以由此你将会判断出O的身份,谜题解开!

真的吗?

为了证明可行,我们一起看一下最后一个问题。至此,我们已经知道X是True还是False了。

当X身份是True

你问X:“当且仅当DA代表‘YES’,O是Random吗?”

1.如果X回答DA,同时DA代表‘YES’,那么O是Random;如果DA代表‘NO’,那么O也是Random。这是因为:“DA代表‘YES’”是假命题时,那么X回答“DA”,代表在说‘NO’,则命题“O是Random”为真;

2.如果X回答BAL,同时BAL代表‘YES’,那么O不是Random。这是因为:“DA代表YES”是假命题时,既然X回答BAL,那么代表在说“YES”,那么“O是Random”必然是假命题。

正如我们上述所讨论的那样,如果X身份是True,那么X回答“DA”相当于在告诉我们“O的身份是Random”,而回答“BAL”相当于在告诉我们“O的身份不是Random”。

当X身份是False

与上同理,X回答“DA”相当于在告诉我们“O的身份不是Random”,而回答“BAL”相当于在告诉我们“O的身份是Random”。

总结一下,我们可以根据X的答案从而判断出O的身份是否是Random,而并不需要得知DA和BAL谁代表“YES”,谁代表“NO”。

这也就说明了,通过第一个问题的答案可确定一个非Random身份的X,由第二个问题的答案确定X为True 或是False,即使你并不知道DA和BAL 谁是YES谁是NO。谜底揭开~

作者简介

Antonella Perucca是卢森堡大学数论教授。她是数论研究人员,并举办过多场数学展览。想了解更多信息,可以浏览她的网页 http://www.antonellaperucca.net/

Author

最简单而又最困难谜题(解决最难逻辑谜题)(4)

文 / Antonella Perucca

翻译及排版 / Hurricane

校对 / 心月

原标题:True?False?Random?

来源:中科院高能所

编辑:观山不易、yrLewis

,