1701740073
悖论与可满足性
1701740074
1701740075
在面对一个未知对象时，画出其界限通常比描述它更容易。比如，托马斯·杰斐逊不知道路易斯安那地区具体有什么，只知道它的边界。在描述“理解一段信息”是什么含义时，使用同样的方法也更方便。
1701740076
1701740077
在最低限度上，“理解”必须得保证有能力发现内部矛盾（即悖论）。如果你无法辨别一组命题内部是否自相矛盾，那么你就没有真正理解它们，即你还没有想透。想象一下这个场景：一个挑剔的老师在课堂上陈述了一个矛盾，然后试探一个溜号的学生的反应：
1701740078
1701740079
“不是这样吗，米里亚姆？”
1701740080
1701740081
“嗯……是这样，老师。”
1701740082
1701740083
“我明白了，某人显然对我说的话只字未听。”
1701740084
1701740085
发现矛盾并不意味着理解的全部，“理解”很可能包含更多的内容。然而，发现矛盾一定是一个必要前提。悖论的发明者就是通过揭示一组预设中的内在矛盾来提醒我们，我们并不是像我们以为的那样来理解这些预设。
1701740086
1701740087
在逻辑学中，发现悖论的问题在理论上被称为“可满足性”（SatisfiabiLity，此问题及相关的逻辑问题经常用大写字母表示）。若给定一组前提，可满足性要讨论的是：“这些命题是否必然导致矛盾？”另一种表述是：“是否存在一个可能世界，使得所有这些前提都为真？”
1701740088
1701740089
可满足性讨论的是逻辑领域的抽象概念，不必涉及真实世界中的真理。比如以下两个命题：
1701740090
1701740091
1.所有的牛都是紫色的。
1701740092
1701740093
2.西班牙国王是一头牛。
1701740094
1701740095
我们的自然反应是，这两个命题都是假的。但是，假并不等于悖论。至少我们可以想象有一个世界，在那个世界里，这两个命题都是真的。如果一组命题在某个可能世界中为真，即使这个可能世界不是我们所处的世界，逻辑学家也会称这组命题为可满足的。
1701740096
1701740097
下面的例子则不同：
1701740098
1701740099
1.所有的牛都是紫色的。
1701740100
1701740101
2.西班牙国王是一头牛。
1701740102
1701740103
3.西班牙国王是绿色的。
1701740104
1701740105
没有哪个可能世界可以同时满足这三个命题（假定紫和绿之类的颜色相互排斥）。这里出现了一个悖论，因此，我们称此命题集合为不可满足的。
1701740106
1701740107
需要注意的是，这里的矛盾不是由某一个单独的命题造成的。我们可以在三个命题中去掉任何一个，剩下的命题则是可能同时实现的。悖论是由三个命题相互作用产生的。
1701740108
1701740109
这种奇异之处具有不可思议的重要性。由于悖论不能归结于某个局部问题，所以可满足性问题通常是极其困难的。实际上，此问题以困难著称，甚至被作为困难的典范。其困难之处在于，随着前提数目的增加，为检查前提内部是否包含矛盾所需的时间会以惊人的速度增加。增加的速度如此迅速，以至于许多包含100个（或更多）前提的可满足性问题从实际应用角度看是不可解的。即使把这些问题交给现有的运算速度最快的计算机，从实际角度看，要花费的时间也相当于无限长。
1701740110
1701740111
我们可以把悖论当作一个隐喻，一种揭示理解的限度的方法。科学试图用简单的概括来解释形形色色的事实。面对一组知识或观念时，如果我们甚至无法发现其中包含的尖锐矛盾，那么我们其实根本不能理解它们。可满足性问题的难度是一个粗略的指示，它揭示了把经验信息“压缩”进概括之中是多么困难。可满足性为获取信息并从中推出结论的难度设置了一个大致的限度。
1701740112
1701740114
普遍性问题
1701740115
1701740116
20世纪70年代初，数理逻辑领域诞生了一个非同寻常的发现。计算机科学家斯蒂芬·库克（Stephen Cook）和理查德·卡普（Richard Karp）的两篇开创性论文表明，许多类型各异的抽象的逻辑问题其实是同一个问题伪装成了不同形式。这些问题都等价于可满足性问题，即识别悖论的问题。
1701740117
1701740118
与可满足性问题等价的这一类问题被称为“NP完全问题”（如果读者现在不理解这个名称的含义，先别着急）。NP完全问题的一个惊人之处在于，这些问题表面看来各不相关。理查德·卡普的论文列出了21个NP完全问题，其中包括“旅行推销员”问题（一个古老的数学谜题）、“哈密顿回路”问题（此问题起源于一种流行于19世纪的智力玩具，该玩具可被视为魔方的前身）。若干年来，已知属于NP完全问题家族的问题列表已经膨胀得相当惊人了。
1701740119
1701740120
走迷宫、解密码以及设计填字游戏，这些问题都属于NP完全问题。许多经典的逻辑谜题和智力题都可以概括为NP完全问题。近年来的谜题作家马丁·加德纳（Martin Gardner）和雷蒙德·斯穆里安（Raymond Smullyan），以及更早的萨姆·劳埃德（Sam Lloyd）、刘易斯·卡罗尔（Lewis Carroll）、亨利·欧内斯特·杜登尼（Henry Ernest Dudeney）[6]，还有许多知名或无名的作者，他们的趣味逻辑问题通常都属于此类。这些形态各异的问题在本质上是同一的，这是一个非常令人意外的结论。即使我们把库克和卡普的这个发现与“所有物体均由原子构成”的发现相提并论，也不算夸张得太离谱。世界上有许多智力难题，其意义深远重大，可看起来又比较琐碎，其实这些问题包含相同的内核。NP完全问题是一个宇宙之谜，当我们以有限的心灵面对复杂度成指数增长的辽阔宇宙时，世界的不可思议便通过NP完全问题得到了充分的展示。
1701740121
[
上一页 ]
[ :1.701740072e+09 ]
[
下一页 ]