史上最难的逻辑谜题、其形式化和无解问题 王海若 逻辑11硕 2013.03.20.

Presentation on theme: "史上最难的逻辑谜题、其形式化和无解问题 王海若 逻辑11硕 2013.03.20."— Presentation transcript:

1 史上最难的逻辑谜题、其形式化和无解问题 王海若 逻辑11硕

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

3 Boolos 史上最难逻辑谜题（HLPE）由美国哲学与逻辑学家 George Boolos于1996年在其论文The hardest puzzle ever 中提出，问题本身则改编自美国逻辑学家 Raymond Smullyan在其1978年的著作What is the name of this book中提出的谜题。 在该篇文章中间，Boolos首先对该谜题进行了下述四点澄清： 1、你可以问一位神祇多于一条问题，也可以完全不问祂问题。 2、你可以根据之前其他问题的答案，来决定下一条问题的内容。 3、任性之神如何作答，可以想像为祂会在脑中掷铜板，若掷得正面，则回答真话；反面，则答假话。 4、对于只有“是”或“否”两种答案的问题，任性之神只会回答 da 或 ja。 接着Boolos先解决了三个较小的逻辑谜题，然后将其解决方式应用到HLPE中。Boolos解决谜题的核心思想是利用当且仅当句式，例如：“‘da’的意思是‘是’ 当且仅当 Dushanbe在Tajikistan吗？” 这种问句消除了被提问者的类型不同导致的回答差异。在文章的末尾，Boolos肯定了排中律在人们进行可能性推理和日常推理中的必不可少的地位。

4 Robert 在Boolos发表了这篇论文之后，Tim S. Robert、Brain Rabern、Gabriel Uzquiano、Gregory Wheeler以及刘奋荣等相继对HLPE提出不同的解决方式或变体。 Robert在some thoughts about the hardest logic puzzle ever中对HLPE做出了四个评述并随后给出了一套更为简单和自然的解决方法，这里列出他的四个评述： 1、HLPE相较于其他大多数相似谜题的难点在于：引入了一个任意作答的神祗，以及用“da”和“ja”来表示“是”和“否”，却不给出哪个回答表示哪个意思。 2、因为第一个问题的提问对象可能是任性之神，所以第一次提问似乎永远都不能得到任何有效的信息。 3、共有12种不同的可能性，而3次回答最多只能区分8种情况（2乘2乘2），所以，任何使我们知道三个神祗的身份的解决方法都不能解释“da”和“ja”分别表示什么意思。 4、Boolos的解决方法太过复杂，当且仅当句式很不自然 Robert采用的问句形式是“如果我问你Q，你会回答‘da’吗？”。只要回答者不是任性之神，则回答“da”意味着Q是真的，回答“ja”意味着Q 是假的。这种问句形式在以后的相关论文中被广泛采用，并且被命名为嵌入问题定理。在论文的最后，Robert给读者列出了两个谜题变体，但似乎没有后续研究对此进行讨论。

5 Rabern&Rabern Brain Rabern和Landon Rabern在2008年发表了一篇论文名为A simple solution to the hardest logic puzzle ever. 这篇论文的最大贡献是阐明了嵌入问题引理，并且修正了Boolos的谜题。 在Boolos的谜题中，任性之神回答问题是根据在脑中掷铜板，正面则说真话，反面则说假话。“然而，”该论文中写道：“这种做法完全丢失了原始Smullyan谜题的精神。”因为无论是掷到铜板的正面或反面，任性之神都必须说真话或假话。按照嵌入问题引理，让其回答诸如“如果我问你北京是不是在中国，你会回答‘ja’吗？”时，任性之神永远只能回答“ja”。 基于此，论文给出了HLPE的修正版：有代号 A, B, C 的三位神祇，只知它们名为“真实、虚谎、任性”，但不知哪个代号属哪个名字。真实之神只说真话，虚谎之神只说假话，而任性之神会随意说“da”和“ja”。你的任务是利用三条是非题，找出 A, B, C 的身份，但每次只能向一位神祇发问。神祇们都懂得你的语言，但只会用它们的语言回答 “da” 或 “ja”。这两种回答，一个解“是”，一个解“否”，但你不知道哪个回答是哪个意思。

6 Rabern&Rabern 同时boolos对谜题提出的四点澄清中德第三条也得到相应修正：任性之神如何作答，可以想像为它会在脑中掷铜板，若掷得正面，则回答“ja”；反面，则答“da”。 在我们前面介绍的两篇论文中，作者都只给出了三个提问的解决方法。而且根据Robert的分析，六种可能性不可能通过两个是否问题来确定。然而，在本文中，Brain Rabern和Landon Rabern给出了一个对原始HLPE谜题两个提问的解决方法。首先由于嵌入问题引理和任性之神的定义漏洞，原始问题可被简化成一个对三个说真话的未知身份的神祗提出是否问题以确定他们身份的谜题。解决方法简化的关键在于，三个神祗除了对问题给出是或否的回答之外，还可能因无法做出回答而导致头部爆炸。考虑以下问题：

7 Rabern&Rabern “以下情况是否真实：你会对这个问题回答“否”并且B是真实之神或者B是虚谎之神吗？”
此时回答“是”则B是虚谎之神，回答“否”则B是任性之神，头部爆炸则B是真实之神。 以上问题属于自我指涉问题，这种问题有可能导致有理性并依照理性说话的个体无法做出回答。但是该种方法是否能应用于修正后的谜题中呢？Gabriel Uzquiano对此给出了肯定的回答。

8 Uzquiano Uzquiano在其2010年的论文How to solve the hardest logic puzzle ever in two questions中对修正后的HLPE给出了两个问题之内的解决方法。他在文中写道： “…there are both self-referential questions that no truth-teller can answer and self-referential questions that no liar can answer.” “The key to two-question solutions to the puzzle is to learn how to glean information from certain god’s inability to answer a question.”

9 Uzquiano 考虑以下问题： Q1. 你会用你的语言中表达“是”的词来回答是否Q吗？ Q2. 你会对Q1回答“ja”吗？
解码引理：真实之神和虚谎之神用“ja”和“da”来回答Q2的方式完全按照它们对Q表达肯定和否定的方式。

10 Uzquiano 由此，Uzquiano将谜题简化成每个神都用“是”和“否”来回答问题。（但是文中神祗并没有因为无法回答问题而头部爆炸，它们只是会保持沉默。)问题Q的形式是：“你和X对北京在中国的回答会是一样吗？”。 但之后， Uzquiano考虑了真实之神和虚谎之神都能够预测任性之神的回答的情况，并利用自我指涉问句给出了新的解决方法。其问题的形式如下： 1 你会用“ja”回答是否： a X不是任性之神并且你是虚谎之神， b X是任性之神并且你会对1回答“da”； 以上两个命题至少有一个为真吗？

11 Uzquiano 在论文的最后，Uzquiano给出了一个更难的HLPE版本：任性之神的回答方式被修改得更为随机——它可能回答“da”、“ja”或根本不回答，而且它如何回答完全取决于脑中一个匀称的三面骰子的投掷结果，每一面各代表一个不同的反应。 这个新的版本消除了任性之神和其他两个神祗的“particular asymmetry”。此时，任性之神可以完美地模仿其他任何一个神祗。Uzquiano声称他不知道如何在两个提问之内解决这个谜题。而Gregory Wheeler和Pedro Barahona随后证明，这个新的HLPE不能在两个提问之内得到解决。

12 Wheeler&Barahona Gregory Wheeler和Pedro Barahona在Why the hardest puzzle can not be solved in less than three questions中先给出了针对Uzquiano的改进版的解决方法，和Uzquiano的解决方法几乎一样，只是由于谜题难度的增加，问题的个数变成了三个。 随后他们论述了为何不可能在两个提问之内解决HLPE。

13 Wheeler&Barahona 回应1 回应2 回应3 RTL RLT LTR LRT TLR TRL
QL引理：如果一个问题有N个可能回答，那么这N个回答最多区分N种不同的可能性。 现在我们已知共有三种不同的回应：“ja”、“da”和不回答。而只考虑3个神祗的类型则有6种不同情况，假使神祗类型能在2个提问之内得到确定，则在第一个提问之后每一个回答之后的可能情况最多只能有3种。现假设对A提出第一个问题，由于任何回应都无法排除被提问者是任性之神的情况，那么只有剩下4种情况可以被区分，那么一定有一个回应保留3种以上可能情况。 回应1 回应2 回应3 RTL RLT LTR LRT TLR TRL

14 Wheeler&Barahona 依照惯例， Gregory Wheeler和Pedro Barahona给出了一个更难的HLPE版本：
有代号 A, B, C 的三位神祇，只知它们名为“真实、狡诈、任性”，但不知哪个代号属哪个名字。真实之神只说真话，任性之神会随意说“da”、“ja”或不回答。狡诈之神在它确定自己所说的是谎言的情况下会说谎，当它不确定的时候它会表现得和任性之神一样。你的任务是利用三条是非题，找出 A, B, C 的身份，但每次只能向一位神祇发问。神祇们都懂得你的语言，但只会用它们的语言回答 “da” 或 “ja”。这两种回答，一个解“是”，一个解“否”，但你不知道哪个回答是哪个意思。

15 Wheeler&Barahona 这个谜题其实很好解决，将问题Q放在“你确定Q吗？”之中既可以将谜题回归到之前的版本。 然而，文中继续写到：
“However, here is the catch. Our solution hinges on the gods, unlike us, being aware of who their neighbors are, but like us in not having the oracular ability to predict with certainty what Random or Devious will say… ” 论文最后对这些新的修改也给出了比较可靠的讨论，利用“在未来某一个时间你会和X的回答一样吗？”的问题形式似乎就可以解决以上问题。

16 Gregory Wheeler和Pedro Barahona以及前面提到的几个作者在改进HLPE时倾向于让三个神祗的回应方式更加符合人类对神的直观：任性之神应该能够对任何问题进行随机的回答；神祗应该是全知全能，所以它们应该能够预测随机的回答；虚谎之神应该是怀着邪恶的目的阻挠人类，所以在不确定的情况下应该像任性之神一样行事；神祗不应该向人类直接揭示自己的身份，因此它们不会对直接涉及身份的提问给出回应。然而，刘奋荣和王彦晶通过一个相反方向的努力使得HLPE的某些变体无解同时对HLPE给出了形式化的定义。

17 Liu&Wang 刘奋荣和王彦晶在Reasoning about agent types中对HLPE给出的形式化定义。该文所采用的形式化语言是在多主体公开宣告逻辑语言的基础上添加提问算子、类型变元、发音变元以及将宣告算子变更为回答算子和任意回答算子。 在HLPE中出现了不同的类型：真实、虚谎和任性。为了对其进行形式化，文中首先对类型做出了精确定义并将其作为语言的核心要素。 除此之外，在解决谜题的过程中会涉及到提问、回答、根据回答提问、再回答…直到三个神祗的类型被确定。因此需要对这种一环扣一环的提问过程给出形式化的定义。文中将这种解决方法形式化为提问策略，策略的每一次执行表示一次提问过程，只有当一个策略的所有执行过程都能使三个个体的类型被D（提问者）确定时，这个提问策略才有效。

18 Liu&Wang

19 Liu&Wang

20 Liu&Wang

21 Liu&Wang 具体的语义定义在ppt最后列出，以下是文中的直观说明： 1.初始状态没有任何问题被提出；
2.当提问者提出一个问题时，这个问题和它的回答者会被记录下来，并取代之前没被回答的问题； 3.只有当问题被提出后，回答者才能够作出相应回答； 4.当回答着作出回答后，记录被清空到初始状态#； 5.提问者可以对任何个体提出任何问题。

22 Liu&Wang

23 Liu&Wang 第二个定义保证一个提问策略的每一次执行过程中，其中任何一个提问状态的问题都必须是可回答的。

24 Liu&Wang 构造模型如下：

25 Liu&Wang Rabern&Rabern的解决方法即可形式化如下， 由定义可证

26 Liu&Wang 之前我们已经提到，到现在为止，所有的HLPE都有解决方法并且更新的趋势是使得谜题中神祗的性质更加符合我们对神的直观。然而该论文中给出了一个新的HLPE，他们试图将神祗还原为普通人类。新谜题如下： 一个（主观）说谎者、一个（主观）说真话者和一个（主观）吹牛者一起住在岛上。他们知道自己的类型但不知道其他两个人的。除此之外，在这三个人之中，每个人的类型都不同于其他两个是常识。他们听得懂英语但是只会以自己的语言回答“da” 或 “ja”。这两种回答，一个解“是”，一个解“否”，但你不知道哪个回答是哪个意思。现在，你能够通过向他们提出可以用“da”或“ja”回答的问题来确定这三个人的类型吗？

27 Liu&Wang

28 Liu&Wang 之后这个新的HLPE被形式化证明无解。我们在这里仅阐述其主要思想。首先利用嵌入问题引理可以形式化证明该谜题有解当且仅当以下谜题有解： 一个（主观）说谎者、一个（主观）说真话者和一个（主观）吹牛者一起住在岛上。他们知道自己的类型但不知道其他两个人的。除此之外，在这三个人之中，每个人的类型都不同于其他两个是常识。他们听得懂英语并且用“是”或”否”来回答问题。现在，你能够通过向他们提出可以回答的是否问题来确定这三个人的类型吗？

29 Liu&Wang

30 Liu&Wang

31 无解问题 现在我们已经简要介绍了对史上最难逻辑谜题的代表性研究。在最后的论文中，作者给出一个新的HLPE并且形式证明了其无解。现在我们想要在该证明基础之上对类似的HLPE给出一个比较随意的无解证明。 首先我们指出，在上述提到的无解版本的HLPE中，模型最后总会缩小至到如下形式的子模型：

32 无解问题 由命题9可知，现在无法对A, B, C中任何一个个体提出有效问题，所以该子模型不可能再缩小。我们在这个观察的基础上提出假设：

33 无解问题

34 无解问题 Liu&Wang对命题9的证明在此模型中同样成立。假设子模型的所有可能世界中A或为STT或为LT，现分三种情况考虑：
子模型中A全为STT，由模型的性质这些可能世界同时不可被A和D（提问者）区分，x只能回答他所知道的东西，那么他的答案必定在每个可能世界上为真，因此D也知道答案。 A全为LT，LT类型个体无法提供任何有效信息，因为他们的回答前提是重言式。 A至少在一个可能世界上为STT，在一个可能世界上为LT

35 无解问题 若该提问有效，那么ja和da都会排除至少一个A为STT的世界，即在其上A不知道问题的答案。显然所有A为STT的世界对A而言都是不可区分的，所以不可能出现以上情况，因此也不会有有效提问。

36 无解问题

37 无解问题 综合以上两个性质我们知道，每个个体被有效提问后就排除了某个非LT情况，此时根据命题9，提问者无法再对该个体提出任何有效问题。因此每个个体最多可以被提一次有效问题。现在，因为我们考虑的是无解问题，所以可将类型LT看作捣乱者，即他总是会设法阻止提问者知道答案。在我们的模型中可假设LT总会模仿t中的自己的回答。因此，现对G中个体按任意顺序逐一提问，若个体为类型为非LT，我们已知t中该个体类型要么为LT要么和真实世界一致，因此任何回答都无法排除t；若个体类型为LT，因为LT会模仿那个可能世界中个体的回答，所以同样也无法排除t。而当所有个体被问完之后，我们无法再提出任何有效提问，因此t永远无法被排除，所以我们无法确定所有个体的类型。

38 完 谢谢

39 Liu&Wang

40 Liu&Wang

41 Liu&Wang 在形式化HLPE之前还需对谜题的隐含假设给予进一步澄清和形式化。本文在Rarbern&Rabern的四点澄清的基础上添加了六个必要假设和两个非必要假设。这里只列出非形式化的假设： 1.ABC的类型为STT，SLL或LT，并且这是常识。 2.ABC拥有不同的类型，并且这是常识。 3.ABC知道其他人的类型，并且这是常识。 4.ABC知道“da”和“ja”的意思，并且这是常识。 5.D不知道ABC的类型并且这是常识。 6.D不知道“ja”和“da”的意思但是他知道一个表示“是”，一个表示“否”，并且这是常识。 B1. 所有的提问和回答公开进行。 B2. D不会再提问中提到自己。

42 Liu&Wang 同样，在形式化前他们先提出了几个新的假设： 1a. A、B和C的类型都在T={STT,SLL,LT}中，并且这是常识。
4~6, B1和B2和之前一样。