史上最难逻辑谜题

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

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

Boolos 于文中另有数点澄清：

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

历史

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

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

Boolos 的解答

此谜题有多个解答。Boolos 在原文中提出了其中之一（下一节将介绍另一个由 Rabern and Rabern (2008)设计，相当简洁易明的解答）。他的解答之中，第一条问题的目的，在于找出一位并非任性的神。这是最关键的一步。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) 发现，只要利用一种特殊的复合问题，就可以将所谓“史上最难逻辑谜题”转化为一道极为显浅的谜题。

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

E(Q): 若用你此刻的心态 (mental state)来回答 Q 这条问题，你会回答 "ja" 吗？

Rabern and Rabern 证明了以下引理。

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

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

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

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

• Q₁: 你是 Zephyr 吗？
• Q₂: 你是 Eurus 吗？
• Q₃: 你是 Zephyr 吗？

那么 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=虚谎（实际上如何标签三位神祇，并不重要），于是 Q₁, Q₂, Q₃ 变成

• Q₁: 你是任性之神吗？
• Q₂: 你是真实之神吗？
• Q₃: 你是任性之神吗？

然后，从简化版谜题的发问流程中，将“是”换成 "ja"，“否”换作 "da" ，并将每项问题 Q_i 置换成内嵌问题 E(Q_i)，即可得出 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 给出了一个只需要问两个问题就能识别所有神的方案。