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
1701741345
猪排问题
1701741346
1701741347
可满足性问题可能非常难。刘易斯·卡罗尔设计过一些极其枯燥的逻辑谜题，这些题要求解题者借助十几个（甚至更多）无意义的前提推出一个单独的有效结论。有几道题收在他未完成的教科书《符号逻辑》中，这些问题是对科学推理或数学推理的拙劣模仿，但是却出人意料地困难。一些更难的问题已超出了大多数人的耐心的极限（虽然这些问题已经被计算机解决）。最困难的一个问题是在他的笔记中发现的，直到1977年才发表，这个问题包含50个前提。
1701741348
1701741349
卡罗尔设计过一个被人脑和计算机广泛分析过的问题，即大名鼎鼎的“猪排问题”。这个谜题要求推出“完全结论”，即一个既与所有其他命题相一致又被所有其他命题所要求的假说。
1701741350
1701741351
猪排问题
1701741352
1701741353
（1）一个晚餐吃猪排的逻辑学家很可能丢钱；
1701741354
1701741355
（2）一个食欲旺盛的赌徒很可能丢钱；
1701741356
1701741357
（3）一个已经丢了钱的，并且可能丢更多钱的、郁闷的人，总是在凌晨5点起床；
1701741358
[
上一页 ]
[ :1.701741309e+09 ]
[
下一页 ]