|
|
马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
您需要 登录 才可以下载或查看，没有账号？注册
x
本帖最后由 genghis 于 2009-11-6 19:53 编辑
背景 ：
逻辑学家和难题大师 Raymond Smullyan 制作了一道逻辑题，在很长的一段时间内无人能够解答，被称为迄今世界上最难的逻辑题。后来计算机科学家John McCathy 对题目进行了修改，使题目变得更难。麻省理工学院哲学教授，Provability 逻辑领域的创始人 George Boolos 首先成功解答了这个逻辑题，并且发表了论文《 The Hardest Logic Puzzle Ever 》。这篇论文收录在 George Boolos 的著作《Logic , Logic , and Logic》( 1998年 哈佛大学出版社 )里。
Raymond Smullyan 制作的原题 ：
Three gods A , B , and C are called , in some order , True , False , and Random . True always speaks truly , False always speaks falsely , but whether Random speaks truly or falsely is a completely random matter . Your task is to determine the identities of A , B , and C by asking three yes-no questions ; each question must be put to exactly one god .
John McCathy 修改后的题目 ：
Three gods A , B , and C are called , in some order , True , False , and Random . True always speaks truly , False always speaks falsely , but whether Random speaks truly or falsely is a completely random matter . Your task is to determine the identities of A , B , and C by asking three yes-no questions ; each question must be put to exactly one god . The gods understand English , but will answer all questions in their own language , in which the words for " yes " and " no " are " da " and " ja " in some order . You do not know which word means which .
John McCathy 修改后的题目 ：
有甲、乙、丙三个精灵，其中一个只说真话，另外一个只说假话。还有一个随机地决定何时说真话，何时说假话。你可以向这三个精灵发问三条是非题，而你的任务是从他们的答案找出谁说真话，谁说假话，谁是随机答话。这个难题困难的地方是这些精灵会以“Da”或“Ja”回答，但你并不知道它们的意思，只知道其中一个字代表“对”，另外一个字代表“错”。你应该问那三条问题呢？
解题思路 ：
第一个问题 : 确定一个非 Random 精灵 。
第二个问题 ：确定非 Random 精灵的身份 。
第三个问题 ：确定其它精灵的身份 。
解题过程 ：
问 A 第一个问题 ：你对 “ da 表示是吗 ？ ” 和 “ 你对 ‘ 你是 Ture 吗 ？’ 和 ‘ B 是 Random 吗 ？’ 这两个问题的回答相同吗 ？” 这两个问题的回答相同吗 ？
如果 A 是 Random ，那么 B 和 C 都不是 Random 。
如果 A 不是 Random ，那么 A 对第二个是非问句的回答为
A B “ 你是 True 吗 ？” “ B 是 Random 吗 ？” 回答
True Random 是 是 是
True False 是 否 否
False Random 是 否 是
False True 是 是 否
可以得出 :
如果 A 对第二个是非问句的回答为是 ，那么 B 是 Random , C 不是 Random 。
如果 A 对第二个是非问句的回答为否 ，那么 B 不是 Random 。
A 对第一个问题的回答为
A da “ da 表示是吗 ？” 第二个是非问句 回答
True 是 是 是 da
False 是 否 是 da
True 否 否 是 da
False 否 是 是 da
True 是 是 否 ja
False 是 否 否 ja
True 否 否 否 ja
False 否 是 否 ja
可以得出 :
如果 A 对第一个问题的回答为 da , 那么 A 对第二个是非问句的回答为是 。
如果 A 对第一个问题的回答为 ja , 那么 A 对第二个是非问句的回答为否 。
因此得出：
如果 A 对第一个问题的回答为 da , 那么C 不是 Random 。
如果 A 对第一个问题的回答为 ja , 那么 B 不是 Random 。
当 B 不是 Random 时（ 当 C 不是 Random 时 ，同理分析 ） , 问 B 第二个问题 ：你对 “ da 表示是吗 ？” 和 “ 你是 Random 吗 ？” 这两个问题的回答相同吗 ？
B 对第二个问题的回答为
B da “ da 表示是吗 ？” “ 你是 Random 吗 ？” 回答
True 是 是 否 ja
True 否 否 否 ja
False 是 否 是 da
False 否 是 是 da
可以得出：
如果 B 对第二个问题的回答为 da , 那么 B 是 False 。
如果 B 对第二个问题的回答为 ja , 那么 B 是 Ture 。
问 B 第三个问题 ：你对 “ da 表示是吗 ？” 和 “ A 是 Random 吗 ？” 这两个问题的回答相同吗 ？
当 B 为 True 时（当 B 为 False 时 ，同理分析） ，B 对第三个问题的回答为
A da “ da 表示是吗 ？” “ A 是 Random 吗 ？” 回答
Random 是 是 是 da
Random 否 否 是 da
False 是 是 否 ja
False 否 否 否 ja
可以得出 ：
如果 B 对第三个问题的回答为 da , 那么A 是 Random 。因此三个精灵身份全部确定 。
如果 B 对第三个问题的回答为 ja , 那么 A 是 False 。因此三个精灵身份全部确定 。
|
|
/1 
eetop公众号
创芯大讲堂
创芯人才网
发表于 2007-12-30 11:25:53
