通往真假和随机之路:如何解决史上最难的逻辑谜题?

  11957年,一个名叫Raymond Smullyan的普林斯顿博士生正在理论计算机科学的一名创始人指引下学习。 Smullyan在这段时间会时常去纽约城。其中一次,他遇见了一个「非常迷人的女音乐家」。在他们的第一次约会中,Smullyan,这位高超的调情家,非常逻辑地——同时也非常狡猾地展开了他的攻势。 「您愿意帮我个忙吗?」他请求道,「我要说出一句话。如果这句话是真的,您愿意给我一个您的签名吗?」 她没有拒绝这个游戏,而是愉快地说:「我看不出有何不可。」 「如果这句话是错的,」他继续道,「您将不必给我您的签名。」 「没问题……」 Smullyan的这句话是:「您不会给我您的签名,也不会给我一个吻。」 尽管有点复杂,但Smullyan的小阴谋里显现的机智还是不证自明。 一个真实的陈述将会使他得到一个签名,正如他们达成的协议一样。但Smullyan的话,假设是真的,就会有矛盾:它使亲笔签名变成了不可能。那会使他的话变成假的。但是如果Smullyan的话是假的,那么这位迷人的女音乐家将会给他一个签名或者一个吻。现在你看到埋在其中的陷阱了:她已经同意了不给假陈述奖励亲笔签名。 利用逻辑,Smullyan将一个假命题变成了一个吻(以及一个浪漫的爱情故事:他们最终结婚了)。 无标题 2这正是Smullyan所钟情的逻辑游戏,并且也让他为大家所爱。他写了一本关于数学与逻辑娱乐的书,标题类似《这本书叫做什么?》和《嘲笑一只知更鸟》,不仅仅鼓励人们追求这些领域的职业生涯,还改变了数学与逻辑的教授方式。在他接近一个世纪的生命里,96岁的Smullyan是一位成功的钢琴家与魔术师,为现代逻辑做出了重要的贡献,并且撰写了许多有关道家哲学与国际象棋的著作。「他是无可争议的逻辑谜题大师。」他的前博士学生Bruce Horowitz如此评价他。 Smullyan留下的诸多遗产之一便是至今仍然在吸引着哲学家与逻辑家的最困难的谜题,也被称为《有史以来最难的逻辑谜题》。这个标题是由麻省理工学院的逻辑哲学家George Boolos所写,他同时也是Smullyan的一位同事,喜欢各种类型的逻辑挑战。曾经通过仅用单音词开设一堂关于哥德尔第二不完备定理——「现代逻辑最重要结果之一」——的讲座来测试自己。 《有史以来最难的逻辑谜题》如下所示:
三个神A、B、C按乱序分别叫做「真实」、「错误」与「随机」。「真实」一直说真话,「错误」一直说假话,但是「随机」说真话或说假话是一件完全随机的事情。你的任务是通过问3个是与非的问题来确认A、B和C的身份,每一个问题智能问一个神。这些神听得懂英语,但会用它们自己的语言作答,「是」和「否」变成了「da」和「ya」,但你不知道哪个对应哪个。
对于挑战我永远都是跃跃欲试。我坐在沙发上,纸和笔在手里,有自信在两小时内就解决这道题。它看起来就是让我一次想出三个问题作为开始,并找出结果。例如,我问A,是否B就是「真实」;问B是否A就是「真实」;并且问C他自己是否是「真实」。几个小时过去,在询问了这些神所有我能想出的是与非的问题后,我意识到这个谜题是如何的名副其实的难。很显然我的问题根本无法让神做出我想要的回答。 大受挫折,我试图找一点启发。这个谜题在1996年被解开,而这位高山之巅的大师正是Boolos。而他解决问题的过程是我所接受过的逻辑与真实最好的一课。如果你想自己去试一试这个谜题,那么你可以在此停止阅读这篇文章,祝你好运!如果你成功了,那么我得给你我的祝贺。但是如果你没有,回来吧,你可以随我一起回顾Boolos的解决方法。 [caption id="attachment_6928" align="aligncenter" width="733"]YE GODS:在有史以来最难的谜题中,你必须去找出这些神与「真实」、「错误」和「随机」所对应的关系。 神啊:在有史以来最难的谜题中,你必须去找出这些神与「真实」、「错误」和「随机」所对应的关系。[/caption] 3Boolos告诉我们的第一件事是你不应该急于在问题上做功夫,就像我一样,希望假设-推理的策略有所效果。反之,你首先该做的是找出一个问题能够确定谁不是「随机」——或者谁只可能是「真实」或「错误」。通过排除法,帮助你来解开「随机」的身份。一旦你确认了「随机」,其他两个迎刃而解。 为了更好地理解这个方法,Boolos指出,我们需要去看一下它如何在三个简单的谜题里解决问题。 第一个简单的谜题实际上是Smullyan经典的骑士与恶棍谜语的迭代,在他的《这本书叫做什么?》中有所介绍。在该谜题里,骑士永远说真话,恶棍永远撒谎,你的任务则是根据他们所说的找出谁是谁。 因此在我们的第一个谜题里,假设你不记得冥王星是否是个矮行星,你需要去问附近的人来确定——但你不知道这个人是骑士还是恶棍。那么能够确定冥王星是否是个矮行星的是与否的问题该是什么呢? 就像Boolos解释的,你想要给骑士或恶棍设置一个陷阱来给出你想要的。你用「当且仅当」来设置这个陷阱——一种叫做「双重条件」的逻辑架构。因此在此情况下你的问题应该是:「当且仅当冥王星是矮行星的时候你是否是一个骑士?」 在你将「当且仅当」插入到「两句或者全部真或者全部假的话之间时,你会得到一句为真的话。但如果你将之插入在一句真话和一句假话之间时,你会得到为假的话。」Boolos写道。它就像一个乘号:就像让两个都是正或都是负的数字相乘,结果总是正的,在两句都是真话或者都是假话的短句中插入「当且仅当」,结果也总是真话。 鉴于你可能正在向一个骑士或恶棍问问题,会有四种可能的回应(假设我们不知道冥王星实际上是一个矮行星):
  1. 如果这个人是骑士并且冥王星是一个矮行星,那么你会得到「是的」,因为两句在「当且仅当」前后的话都是对的,而骑士永远说真话;
  2. 如果这个人是一个骑士,而冥王星不是一个矮行星,你会得到「不是」,因为这个问题包含了一句错误的话;
  3. 如果这个人是一个恶棍,而冥王星是一个矮行星,你会得到「是的」,因为恶棍永远说假话,而正确的回答是「不是」;
  4. 如果这个人是恶棍,而冥王星不是一个矮行星,你会得到「不是」,因为正确的回答是「是的」。
看看我们都做了些什么:通过利用双重条件来提出问题,你会得到你想要的信息——如果冥王星是矮行星你就会得到「是」的反馈,如果它不是,你就会得到「不是」——无论你是否在问一个诚实与否的人。然而,当你在试图解决《有史以来最难的谜题》时要记住——不像上面的例子——骑士与恶棍并不讲英语。 为了给它们制造露出马脚的陷阱,比如是否「da」与「ja」代表着「是的」与「不是」或反之,要看一下Boolos的第二个简单的谜题。 在这个谜题里,你知道你正在询问一个骑士——永远讲真话——但是他只能用「da」与「ja」来回答。那么你该用个什么样的是与非问题来确定冥王星是不是矮行星呢?从上一个谜语中拾得灵感,你会得到这个:问骑士,「『da』是否代表『是的』当且仅当冥王星是个矮行星?」这就对了:如果冥王星是一个矮行星,你会得到一个回答「da」,如果不是,则是一个「ja」,即使我们不知道它们是什么意思。这个结果和上面的一样有用:不知道这个人是否是骑士或恶棍并不能造成阻碍,因此不知道「da」与「ja」的意思也不会有所妨碍。 Boolos告诉我们《有史以来最难的谜题》本质上是前两个简单的谜题加上第三个。在我们解决那个之前,先来看一下前两个谜语是如何结合的:你需要找出冥王星是否是一个矮行星,并且问一个可能是骑士也可能是恶棍的人,他仅能够用「ja」与「da」来回答。那么你会问什么问题?因为这是个复合谜语,如果你想到了用一个复合问题来问,那么你是正确的! 你需要去问:「『da』是否意味着『是的』当且仅当你是一个骑士,并且当且仅当冥王星是一个矮行星?」通过这个问题,如果冥王星是一个矮行星你会得到「da」的回答,不是则会得到「ja」,无论你是在问一个骑士还是恶棍。这个精心谋策的问题将是解开谜题的钥匙。
每句话要么是对的,要么是错的——没有中间地带。
现在这里是第三个谜题。它的规则是这样的:假设我在你面前按一排摆放了三张扑克牌——两张A与一张J——面朝下。你不知道它们的顺序,但是我知道。你需要指着一张牌,问我一个是与非的问题,在必有一张是A的情况下,才可以确认它们是什么。如果你碰巧指到两张A中的一个,我会正确回答问题,像骑士一样;如果你指着J,我会随机回答「是」与「不是」,就像「随机」之神。你会指着哪一张,又会问什么? 这一个看起来有些难,但是它其实不是。指向任何一张牌,并问其他的两张牌其中是否有一个是A。例如,你指着中间的牌,问左边的牌是不是一张A。「无论中间的牌是不是A」Booloa说,「如果你听到我说『是的』,你都能确定左边的牌是一张A,如果你听到『不是』,你会选择右边的牌。」为什么?这样,如果中间的牌是个A,那么当我说「是的」的时候,左边的牌也是一张A;如果我说「不是」,那么右边的牌就是。如果中间的牌是一张J,我随机说的「是」或「不是」是没有关系的:因为中间的牌是J,左边与右边的牌一定都是A。所以,无论你指的是不是一张A,只要这张你在怀疑是不是A的牌不是你正在指的牌,我给予你的回答「是」或「不是」就永远可以定位另一张A。 指向任何一张牌,并问另一张是什么,这是一种在解决《有史以来最难的谜题》你需要用来找到谁肯定是「真实」或「错误」的陷阱策略。是一种你将指向任何一张牌翻译成语句来作为你问题中的一部分的方法,是一种在上述复杂谜题中替代「冥王星是一个矮行星」事实语句来断定「随机」是谁的方法——你会注意到它和指向哪一张牌一样是一个裁决的决定。我们在这个问题里判断「随机」是谁将会取决于我们决定去问谁问题。它并不重要,并且可以是三个神中的任意一个。 让我们把问题给A神,并且断言B就是「随机」:「『da』是否是『是的』的意思当且仅当你是『真实』并且当且仅当B是『随机』?」这就相当于指向B去问A是什么。在扑克牌谜题里,无论我是诚实地还是随机地回答,你可以依据于我的「是」或「不是」来准确找到A,在这里也是同理。「无论A是『真实』、『错误』还是『随机』,」Boolos说,「如果你得到了一个回答『da』,C不是『真实』就是『错误』;如果是『ja』,B不是『真实』就是『错误』。」 让我们假设我们得到「ja」(我们必须的假设得到一个或另一个答案),这意味着B不是「真实」就是「错误」,而这就是我们想要的——我们已经知道如何揭露其他的身份:问B:「『da』是否意味着『是的』当且仅当冥王星是一个矮行星?」鉴于我们知道冥王星是一个矮行星,这里有两种可能:
  1. 如果B是「真实」,那么你就会得到「da」;
  2. 如果B是「错误」,那么你会得到「ja」,因为正确的答案是「da」,并且「错误」永远说假话。
再让我们假设我们得到了「da」,这意味着B是「真实」。现在问「真实」你的第三个也是最后一个问题:「『da』是否意味着『是的』当且仅当A是『随机』?」因为「随机」一定是A或者C,这里只有一种可能的回答:
  1. 因为B是「真实」,你会得到一个「da」,这意味着A是「随机」,因此C就是「错误」;
再次总结:利用Boolos的所有逻辑,这三个问题来决定三个神的身份,如下所示:
  1. 对于神A:「『da』是否意味着『是的』当且仅当你是「真实」和当且仅当B是「随机」?」(我们假设A说:「ja」,意味着B是「真实」或「错误」);
  2. 对于神B:「『da』是否意味着『是的』当且仅当冥王星是一个矮行星?」(我们假设B说:「da」,意味着B是「真实」);
  3. 对于神B「真实」:「『da』是否意味着『是的』当且仅当A是「随机」?」因为B是「真实」,他一定会说「da」,意味着A是「随机」,C是「错误」。
解决了! 4因此《有史以来最难的谜题》到底想要教给我们什么呢?根据Boolos,它展示给我们逻辑的基本法则——排除中间法——是如此的重要。「如果我们否定了排除中间法,」Boolos说,「那么甚至在日常生活中我们分析可替代可能性的能力都会瘫痪。」 排除中间法十分简单:每一句话要么是真的,要么就是假的——没有中间地带。这才是清醒的思考。然而我们只能感谢Smullyan设计出这些恶魔般的谜题们,以此给予我们启蒙般的喜悦与欢乐去进行深切的思考。   来自nautilus,作者BRIAN GALLAGHER,机器之心编译出品。参与成员:Chen Xiaoqing,柒

入门
登录后评论
暂无评论
暂无评论~
返回顶部