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
1701740122
当逻辑学家说所有的NP完全问题本质上是一个问题时，他们的意思是说，如果找到了可解决任一NP完全问题的有效通解，则对此通解进行某种方式的变换就可以解决所有其他问题。面对整个NP完全问题家族，一旦解决了其中一个，所有的问题都会迎刃而解。
1701740123
1701740124
我们似乎发现，世界上所有著名的宝库均可用同一把钥匙打开——如果有这样一把万能钥匙的话。是否存在某些（或全部）NP完全问题的有效解？今天这仍是数理逻辑中最深奥的未解之谜之一。
1701740125
1701740126
悖论的深刻性和普遍性超出了前人的想象。悖论不是一个怪胎，而是科学哲学的一根支柱。悖论问题既引人入胜，又令人魂牵梦绕。眼见逻辑推理像纸壳搭的房子一样崩塌，会令人有一种颠覆的快感。从某种意义上说，所有证实理论和认识论领域内的著名悖论都是智力游戏的产物。在其他领域，非专业的爱好者几乎不可能获得品味和把玩其中真义的机会。我们如何知道归纳和演绎、模糊性和确定性之间的交互作用？这是后文将介绍的悖论的主题。
1701740127
1701740128
[1]塞缪尔·泰勒·柯尔律治（Samuel taylor Coleridge）的杰作《忽必烈汗》是在梦中诞生的。柯尔律治在研读忽必烈大帝的历史时睡着了，做了一个梦。令人震惊的是，梦境异常清晰：他梦到了一首300行的诗。醒来后，柯尔律治爬起来，想趁着还有印象时，把诗记录下来。他记下了大约50行——这就是我们所知的《忽必烈汗》，可是他被一个来访者打断了。以后，其余的250行他只能记起只言片语。然而，柯尔律治在现实生活里就是一个诗人。我向大家推荐的这种鉴定方法只适用于那些没有做过打油诗的人。此外，柯尔律治的故事也许不足为例，因为此人曾服用鸦片当安眠药。
1701740129
1701740130
[2]这是一首典型的打油诗。作者把它放在这儿，意思是说：如果你想确证自己是清醒的，这首诗就足够了。这首诗你写不出来，所以它一定是外部世界的一部分，而非梦境的一部分。——译者注
1701740131
1701740132
[3]此处不甚准确，柏拉图著作中的某些言论确实出自苏格拉底本人。——译者注
1701740133
1701740134
[4]原名为Tlon, Uqbar, Orbis Tertius，前两个词是虚构的地名，音译为“特兰”和“乌克巴”，后两个词是拉丁语。这是一个精妙的短篇故事，介绍了特兰——一个虚构世界——中的思想状态。特兰人视唯物主义为荒诞的异端邪说，而一个天才的邪教领袖发明了“九枚铜币”悖论论证物质的存在，下面的引文介绍这个悖论以及正统的特兰理论家对悖论的反驳。——译者注
1701740135
1701740136
[5]疯马酋长（Chief Crazy Horse）是印第安人部落中的著名勇士、部落领袖和英雄，美国儿童喜爱的电动转马也以疯马命名。——译者注
1701740137
1701740138
[6]此处列举的几个人物均为著名的畅销书作家，以善于设计奇诡、精妙而和谐的智力趣题著称。他们的许多佳作已有汉译本。——译者注
1701740139
1701740140
1701740141
1701740142
1701740144
推理的迷宫：悖论、谜题及知识的脆弱性 第2章 归纳：亨佩尔的乌鸦
1701740145
1701740146
与证实有关的最著名的现代悖论是由德裔美国哲学家卡尔·G·亨佩尔（Carl G. Hempel）1946年提出的“乌鸦悖论”。这一悖论指向归纳法，即体现的是一个进行概括的过程。对于那些相信科学可以分解为按部就班的科学方法的人来说，乌鸦悖论是一个坏消息。
1701740147
1701740148
亨佩尔设想有一位鸟类观察者试图检验一个假说：“所有乌鸦都是黑色的”。[1]检验这个假说的传统方法是搜寻乌鸦并检查其颜色。每发现一只黑乌鸦都是对假说的证实[2]（提供证据）。相反，只要发现一只其他颜色的乌鸦就立刻驳倒假说。只要找到一只红乌鸦，你就不用再费事了：假说已经被推翻了。
1701740149
1701740150
对以上说法我们全无异议。亨佩尔悖论这样开始，原来的假说可以换一种表述方式，“所有非黑的东西都并非乌鸦”。根据逻辑原则，这两种表述方式是完全等价的。如果所有的乌鸦都是黑色的，那么任何颜色非黑的东西当然不可能是乌鸦。这两个语句之间的变换被称为“换质位法”，即一个命题经过换质位得到的新命题与原命题在意义上等价。
1701740151
1701740152
与原命题相比，“所有非黑的东西都是非乌鸦”要容易验证得多。每当你见到一件颜色不是黑色的东西，而且证实此物不是乌鸦，这个命题就得到了一次证实。我们不必在人迹罕至的潮湿荒原上守候乌鸦，只要找一些非黑并且不是乌鸦的东西就行了。
1701740153
1701740154
如果我们见到一只蓝松鸦，它不是黑色的，也不是乌鸦，这就证实了原假说换质位之后的等价性；同样，一只红鹤、一只紫燕、一只绿孔雀都可以作为证据。当然，我们甚至不必要求作为证据的非黑的东西必须是鸟，一条红鲱鱼、一枚金戒指、一条蓝草虫，甚至本书的这一页白纸，都能提供证实。这位鸟类观察者没有必要告别他的安乐椅，出去搜集证据证明所有的乌鸦都是黑色的，此刻你的视野中已充满了证明这个假说的证据。
1701740155
1701740156
显然这是荒唐的，但是更荒唐的还在后面。为了深入讨论，假设我们用如下策略消解亨佩尔悖论：蓝松鸦、红鲱鱼等确实证实了原假说，虽然只是在一个无穷小的程度上提供了证实。如果你能招来一个具有魔力的精灵，这个精灵可以在一眨眼之间检验世界上所有非黑色的东西，并且发现这些非黑色的东西中没有一样是乌鸦，这无疑证明了不存在非黑色的乌鸦，即所有的乌鸦都是黑色的。这样看来，也许用一条红鲱鱼证实所有的乌鸦都是黑色的并不荒唐。
1701740157
1701740158
先别急着为如上回答得意。很明显，同样是这条红鲱鱼，它也能证实“所有的乌鸦都是白色的”。这个命题换质位之后得到“所有非白色的东西是非乌鸦”，这条红鲱鱼是非白色的东西，证实了换质位之后的命题。一个观察结论不可能同时证实两个相互排斥的假说。[3]一旦你接受了这个显而易见的矛盾，那么就没有什么是不可“证明”的了。例如，这条红鲱鱼证实所有乌鸦的颜色都是黑色的，同时也证实所有乌鸦的颜色都是白色，因此，黑就是白。从合理的前提出发推出了一个明显的矛盾。
1701740159
1701740160
对于科学家来说，亨佩尔悖论不仅是一个谜题。任何假说都有一个换质位的形式，而证实这个换质位形式的例证通常极容易发现。这里显然出了错误，可是错误在哪儿呢？
1701740161
1701740162
亨佩尔的乌鸦精妙地展示了证实问题中的危险和困惑。在我们将要讨论的所有主要悖论中，这个悖论是最接近得到解决的悖论之一。在研究如何解决之前，有必要做一点引申，讨论一下这个悖论的背景。
[
上一页 ]
[ :1.701740113e+09 ]
[
下一页 ]