史上最难逻辑谜题

史上最难逻辑谜题意大利文L'indovinello più difficile del mondo英文The Hardest Logic Puzzle Ever)乃美国哲学与逻辑学家 George Boolos英语George Boolos 一篇文章的标题及其所载谜题的名称。该文章于1992年先刊登在意大利《共和报》上[1],到了1996年再在《哈佛哲学评论》刊登英语版[2]。谜题乃改编自美国逻辑学家雷德蒙·斯穆里安的创作,其内容如下:

有代号 A, B, C 的三位神祇,只知祂们名为“真实、虚谎、任性”,但不知哪个代号属哪个名字。真实之神只说真话,虚谎之神只说假话,而任性之神会随意说真话或假话。你的任务是利用三条是非题,找出 A, B, C 的身份,但每次只能向一位神祇发问。神祇们都懂得你的语言[注 1],但只会用祂们的语言回答 "da" 或 "ja"。这两种回答,一个解“是”,一个解“否”,但你不知道哪个回答是哪个意思。[注 2]

Boolos 于文中另有数点澄清:

  1. 你可以问一位神祇多于一条问题,也可以完全不问祂问题。
  2. 你可以根据之前其他问题的答案,来决定下一条问题的内容。
  3. 任性之神如何作答,可以想像为祂会在脑中掷铜板,若掷得正面,则回答真话;反面,则答假话。[注 3]
  4. 对于只有“是”或“否”两种答案的问题,任性之神只会回答 da 或 ja。

历史

Boolos 将发明此谜题的功劳归于雷德蒙·斯穆里安,而“不知 da, ja 为何义”的变奏则归功于编程语言 Lisp 的发明者及图灵奖得主约翰·麦卡锡。斯穆里安创作过许多著名的“武士与无赖谜题”(Knights and Knaves puzzles),譬如在一个虚构的岛上,岛民若非只说真话的武士,就是只说谎的无赖,而谜题的主旨,就是问访客如何靠询问一些只有“是/否”两种答案的问题,来获取所需情报。1986年电影《魔幻迷宫》(Labyrinth[3])也有此等情节:有两道门,各由一名门卫把守。一道门通向城堡,进入另一道则肯定引致死亡。门卫之中,一个说真话,一个只说谎。主角要靠问一条问题来找出通往城堡之路。最后主角问的是:“他(即另一名门卫)会否说这道门通往城堡?”

广义来说,“史上最难逻辑谜题”可视为这类“武士与无赖谜题”的伸延。从斯穆里安的著作中,亦可找到类似的谜题。例如在《What is the Name of This Book》第149-156页,他就描写一个海地岛屿,当中一半住民为只说谎话的丧尸,另一半住民为只说真话的人类。尽管全体居民都谙英语,但古老的禁忌禁止他们用土话以外的语言交流。若问他们一条只有“是/否”答案的问题时,他们会回答 Bal 或 Da — 其中有一个解“是”,另一个解“否”,但岛外人事前不知哪个才是“是”,哪个才是“否”。另一著作《The Riddle of Sheherazade》亦有其他相关谜题。

Boolos 的解答

此谜题有多个解答。Boolos 在原文中提出了其中之一(下一节将介绍另一个由 Rabern and Rabern (2008)[4]设计,相当简洁易明的解答)。他的解答之中,第一条问题的目的,在于找出一位并非任性的神。这是最关键的一步。Boolos 在原文中详述了这步是如何设计出来,但此处不赘。他的问题,是问 A:

1)(Da 的意思是“是”)当且仅当((你是真实)当且仅当(B 是任性))吗?

上述问题用了逻辑学的术语“当且仅当”,一般人可能难于理解。然而,运用真值表计算,可以证明以上问题等价于以下者:

1) “Da 的意思是‘是’”、“你是真实”、“B 是任性”三项命题之中,是否有单数的命题为真?

之后两条问题的发问对象,取决于第一条问题的答案。若 A 回答 da,余下两条问题将向 C 发问;若 A 回答 ja,余下两条问题将向 B 发问。可以证明,以此计策选出来的发问对象,必然是真实之神或虚谎之神两者之一,而绝非任性之神。

第二条问题的目的,是在不明 da 及 ja 语义的情况之下,确认发问对象(已知为真实或虚谎两者之一)的身份。问题内容是:

2)(Da 的意思是“是”)当且仅当罗马位于意大利)吗?

或者等价而简单地问:

2) Da 的意思是“是”吗?

可以证明,不管 da, ja 两者哪个指“是”,哪个指“否”,只要对方回答 da,就表示祂是真实之神;若回答 ja,则为虚谎之神。

由于第二条问题的发问对象(视乎情况,是 B 或 C)的身份已经锁定,只要 A 的身份也能确知,余下一神的身份亦可推得。因此,此时我们所关心的命题为

X: A 是任性。

暂且不理 X 的内涵,先视它为一般命题。第三条问题的重点,是面对真实(或虚谎)之神,如何在 da, ja 语义不明的情况之下,针对任意的命题 X,设计出一条可以套出 X 真伪的复合问题 Q(X)。Boolos 所用的,是如下的复合问题——

Q(X):(Da 的意思是“是”)当且仅当 X 吗?

换成一般人也能理解的问法,就是:

Q(X): “Da 的意思是‘是’”与 X 两个命题,是否全对或全错?

那么:

  • 若发问对象为真实之神,而祂回答 da,则 X 为真;若回答 ja,则 X 为伪。
  • 若发问对象为虚谎之神,而祂回答 da,则 X 为伪;若回答 ja,则 X 为真。

将 X 换回具体内容“A 是任性”,第三条问题就是:

3)(Da 的意思是“是”)当且仅当(A 是任性)吗?

或者等价地:

3) “Da 的意思是‘是’”与“A 是任性”两个命题,是否全对或全错?

因此:

  • 若发问对象为真实之神,而祂回答 da,则 A 是任性之神,否则 A 为虚谎之神。
  • 若发问对象为虚谎之神,而祂回答 da,则 A 乃真实之神,否则 A 为任性之神。

既知第二、三两条问题的发问对象(视乎情况,是 B 或 C)与 A 的身份,余下一神的身份可用消去法得知。留意谜题并无要求找出 da 及 ja 的语义,而 Boolos 提供的解答亦不能保证可解释两者的意思。

Rabern and Rabern 的解答

Rabern and Rabern (2008)[4] 发现,只要利用一种特殊的复合问题,就可以将所谓“史上最难逻辑谜题”转化为一道极为显浅的谜题。

首先,对任何问题 Q,都可以定义如下的内嵌问题 (embedded question):

E(Q): 若用你此刻的心态 (mental state)[注 4]来回答 Q 这条问题,你会回答 "ja" 吗?

Rabern and Rabern 证明了以下引理。

内嵌问题引理 (Embedded Question Lemma): 无论向哪一位神祇发问 E(Q),若祂回答 ja,则表示 Q 的真正答案必为“是”;若答 da,则 Q 的真正答案必为“否”。[注 5]

利用此引理,原来的谜题可以转化成以下的简单谜题:

有代号 A, B, C 的三位神祇,只知祂们名为 "Zephyr, Eurus, Aeolus"[注 6],但不知哪个代号属哪个名字。三位神祇均只说真话。你的任务是利用三条是非题,找出 A, B, C 的身份,但每次只能向一位神祇发问。神祇们都懂得你的语言,并会用你的语言作答。

这个简化版的谜题很容易解决。譬如设定三条问题如下——

  • Q1: 你是 Zephyr 吗?
  • Q2: 你是 Eurus 吗?
  • Q3: 你是 Zephyr 吗?[注 7]

那么 A, B, C 的身份可以轻易用以下策略套出:

A答Q1
B答Q2 A答Q2
A=Zephyr
B=Eurus
C=Aeolus
A=Zephyr
B=Aeolus
C=Eurus
B答Q3 B答Q3
A=Eurus
B=Zephyr
C=Aeolus
A=Eurus
B=Aeolus
C=Zephyr
A=Aeolus
B=Zephyr
C=Eurus
A=Aeolus
B=Eurus
C=Zephyr


现在要将以上策略转化回解决 Boolos 谜题的方案。首先,将“真实、虚谎、任性”三神随意标签为 Zephyr, Eurus, Aeolus 三者,例如 Zephyr=任性、 Eurus=真实、Aeolus=虚谎(实际上如何标签三位神祇,并不重要),于是 Q1, Q2, Q3 变成

  • Q1: 你是任性之神吗?
  • Q2: 你是真实之神吗?
  • Q3: 你是任性之神吗?[注 8]

然后,从简化版谜题的发问流程中,将“是”换成 "ja",“否”换作 "da" [注 9] ,并将每项问题 Qi 置换成内嵌问题 E(Qi),即可得出 Boolos 谜题的解:

A答E(Q1)
ja da
B答E(Q2) A答E(Q2)
ja da ja da
A=任性
B=真实
C=虚谎
A=任性
B=虚谎
C=真实
B答E(Q3) B答E(Q3)
ja da ja da
A=真实
B=任性
C=虚谎
A=真实
B=虚谎
C=任性
A=虚谎
B=任性
C=真实
A=虚谎
B=真实
C=任性


简化版谜题的任何其他解答,均可以如法炮制成解决 Boolos 谜题的方案。

无法解答的问题和神祇爆掉的脑袋

Rabern and Rabern 的解答中进一步设计了悖论式的问题,如,你会对这个问题用“否”在你的语言中对应的词来回答吗?

对于真实之神,这个问题是无法回答的,因为怎么回答都会造成矛盾。于是 Rabern and Rabern 说明了问一个神问题,实际上有三种可能性:回答 ja,回答 da,或者脑袋爆掉。在这样的设计下,Rabern and Rabern 给出了一个只需要问两个问题就能识别所有神的方案[4]

附注

  1. ^ 《哈佛哲学评论》原文指神祇们都懂得英语。
  2. ^ "Da" 与 "ja" 其实都是斯洛文尼亚语之中“是”的意思(而“否”为 "ne"),Boolos 只不过借用了这两个词语来作其他设定。
  3. ^ Boolos 所述的任性之神,乃任性地选择回答真话或假话,切勿与随意回答“是”或“否”混淆。举例说,解答某些逻辑谜题的常用伎俩,是设计一条(可能是复合)的问题,迫使诚实者说谎者都回答“是”。面对如此问题,无论“任性地选择回答真话或假话的神”作何选择,祂仍被迫(用祂自己的语言)回答“是”。然而,对“随意回答是或否的神”来说,“是”或“否”都是可能的答案。
  4. ^ 即是祂此刻究竟想回答真话抑或假话。
  5. ^ 留意,这并不是说 da 代表“是”或 ja 代表“否”。无论 da 与 ja 之中哪一个代表“是”,此引理依然正确。
  6. ^ Zephyr 实乃古希腊神话的风神之首,而 Eurus 与 Aeolus 为祂座下四风神之二。
  7. ^ 此处并非笔误,第三题的内容与第一题相同,只是询问对象有别。
  8. ^ 由于 Boolos 版的问题乃从简化版转化而来,此处第三题的内容亦与第一题相同。
  9. ^ 此置换乃根据内嵌问题的定义和内嵌问题引理而作出,而不是说 ja 的意思为“是”或 da 的意思为“否”。倘若将 E(Q) 重新定义为“若用你此刻的精神状况来回答 Q 这条问题,你会回答 "da" 吗?”那么在引理之中,da 及 ja 的角色将掉转,而将简化版谜题的发问流程转化时,就变成将“是”换作 "da",“否”换作 "ja"。

参考文献

  1. ^ L'indovinello più difficile del monde, La Repubblica, 16 April 1992.
  2. ^ George Boolos, The hardest logic puzzle ever页面存档备份,存于互联网档案馆, The Harvard Review of Philosophy, 6:62–65, 1996.
  3. ^ Labyrinth (1986)页面存档备份,存于互联网档案馆), IMDb.
  4. ^ 4.0 4.1 4.2 Brian Rabern and Landon Rabern, A simple solution to the hardest logic puzzle ever, Analysis, 68(2):105-112, 2008.