打字猴:1.701741309e+09
1701741309 推理的迷宫:悖论、谜题及知识的脆弱性 [:1701739689]
1701741310 可满足性
1701741311
1701741312 现在我们已经触及演绎推理的核心。逻辑问题的花哨背景(关于此问题看起来在讨论什么东西)与问题的解决无关。撇开这些花哨的虚饰之后,还剩下什么?
1701741313
1701741314 剩下的是“可满足性”。对于复杂性理论来说,可满足性是最基本的、不可还原的逻辑内核。每一个演绎推理问题的内部,都以可满足性为骨骼。
1701741315
1701741316 459个苹果加上273个苹果是多少、459个橘子加上273个橘子是多少、459根棒球棍加上273根棒球棍是多少,在我们看来,所有这些问题在本质上都是一个问题。算术的基础就在于意识到所有这类问题就其基础而言是一样的。
1701741317
1701741318 复杂性理论得以建立的基础,在于意识到许多更复杂的问题实际上是同一个问题。算术发源于古代人计数的问题。人们意识到,对小麦的蒲式耳数[2]进行加减,与对骡子和金币的数量进行加减没什么两样。在20世纪60年代和70年代,计算机程序员面临一些问题,这些问题导致了复杂性理论的诞生。这些程序员发现,许多看起来不同的问题是相互等价的。
1701741319
1701741320 习惯上,可满足性可以表达为一个用“是—否”来回答的问题:给定一组前提,它们是否相互一致?或者说:它们是否描述了一个可能的世界?或者说:它们是否包含不可解的悖论?
1701741321
1701741322 一个完整的可满足性问题包括一组布尔变量(即最初真假未定的基本命题)和一组关于这些布尔变量的逻辑命题,这些命题可以包含“或者”“并且”“并非”“如果……那么……”之类的标准的逻辑连接词。
1701741323
1701741324 通常,每个命题描述一个单独的、不明确的观察结果。以古德曼的“说真话—说假话”问题为例,以三个人的名字为符号表示三个布尔变量。这个问题实际上就是:
1701741325
1701741326 布尔变量:
1701741327
1701741328 艾丽斯(表示艾丽斯是说真话的)
1701741329
1701741330 本(表示本是说真话的)
1701741331
1701741332 查理(表示查理是说真话的)
1701741333
1701741334 命题:
1701741335
1701741336 1.如果(艾丽斯并且本)那么并非艾丽斯
1701741337
1701741338 2.如果本那么并非查理
1701741339
1701741340 3.如果查理那么艾丽斯
1701741341
1701741342 第一个命题是最难处理的,它对应着本断言艾丽斯称自己是说谎的。如果本和艾丽斯都是说真话的,那么这个命题就是可信的,而在此情况下,艾丽斯就不是说真话的。[3]
1701741343
1701741344 推理的迷宫:悖论、谜题及知识的脆弱性 [:1701739690]
1701741345 猪排问题
1701741346
1701741347 可满足性问题可能非常难。刘易斯·卡罗尔设计过一些极其枯燥的逻辑谜题,这些题要求解题者借助十几个(甚至更多)无意义的前提推出一个单独的有效结论。有几道题收在他未完成的教科书《符号逻辑》中,这些问题是对科学推理或数学推理的拙劣模仿,但是却出人意料地困难。一些更难的问题已超出了大多数人的耐心的极限(虽然这些问题已经被计算机解决)。最困难的一个问题是在他的笔记中发现的,直到1977年才发表,这个问题包含50个前提。
1701741348
1701741349 卡罗尔设计过一个被人脑和计算机广泛分析过的问题,即大名鼎鼎的“猪排问题”。这个谜题要求推出“完全结论”,即一个既与所有其他命题相一致又被所有其他命题所要求的假说。
1701741350
1701741351 猪排问题
1701741352
1701741353 (1)一个晚餐吃猪排的逻辑学家很可能丢钱;
1701741354
1701741355 (2)一个食欲旺盛的赌徒很可能丢钱;
1701741356
1701741357 (3)一个已经丢了钱的,并且可能丢更多钱的、郁闷的人,总是在凌晨5点起床;
1701741358
[ 上一页 ]  [ :1.701741309e+09 ]  [ 下一页 ]