1701741294
1701741295
于是，我们尝试另一个假设。假定说话者是说谎话的。于是，“或者说话者是说谎话的，或者2+2=5”这个命题是假的，其中的两个子命题必须都是假的。如果其中有一个子命题是真的，那么由“或者……或者……”构成的整个复合命题就是真的。因此，判定“或者A或者B”为假等于判定“A和B都是假的”。如果说话者是说谎话的，那么“我是说谎话的”和“2+2=5”这两个命题必须都是假的。可是我们又遇到了一个矛盾。如果说话者是说真话的，那么他必须是说谎话的；如果说话者是说谎话的，那么他又必须是说真话的。
1701741296
1701741297
事实上，斯穆里安提出的这个谜题是说谎者悖论的一个巧妙的变种。这个谜题的“答案”是：答案不存在。（或者用斯穆里安的话说，唯一能够得出的结论是：这道题的出题者不是说真话的。）
1701741298
1701741299
有一个方法可以应用于任何“说真话—说假话”问题，即使无解的问题（就像斯穆里安提出的问题那样）也不例外。对于任意一个问题中提到的海岛居民，无非有两种可能：他属于说真话部落或者属于说谎话部落。我们把关于每一个海岛居民的部落归属的一个猜测称为一个“完全假说”（例如，“艾丽斯说真话，本说谎话，查理说真话”是一个完全假说）。对于任意一个问题，关于海岛居民的完全假说的数量是固定的（在古德曼的问题中，其数量是2×2×2=8）。我们需要做的全部工作就是，列出所有这些假说，看看哪个假说与题中的命题相符。
1701741300
1701741301
在验证各个完全假说的过程中，我们的目标是找矛盾，换句话说，我们在使用归谬法。例如，在古德曼的问题中，有一个完全假说是三个人都说真话，这个完全假说导致一个结论：本会说出他不应当说出的话。这是一个矛盾，于是我们可以排除这个完全假说。把全部8个完全假说检验一遍，我们发现只有一种情况不导致矛盾：艾丽斯、本和查理分别说真话、谎话、真话。通过排除法，此题得到解决。
1701741302
1701741303
在《四签名》（The Sign of Four）中，福尔摩斯说道：“我跟你说过多少遍了，在我们排除了所有不可能的情况以后，剩下的情况——无论多么不可思议——一定是真的。”应用排除法可以解决许多类型的问题，但它并非总是切实可行的。
1701741304
1701741305
麻烦在于，排除的过程是缓慢的，这是因为需要检验的完全假说数量经常是无比巨大的。
1701741306
1701741307
一个布尔变量只能是真的或假的。对于一个未知量来说，有两种可能性。每一个未知量使得完全假说的总量倍增。在涉及三个未知的布尔变量的问题中，可能的完全假说的数量是23=8。一般地，当存在n个或真或假的未知量时，有2n个可能的完全假说。如果一个“说真话—说假话”问题牵涉24个海岛居民，完全假说个数将有上百万。
1701741308
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
[
上一页 ]
[ :1.701741294e+09 ]
[
下一页 ]