跳转到内容

史上最難邏輯謎題

维基百科,自由的百科全书

史上最難邏輯謎題意大利文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.