↖  电脑前传(3)：逻辑..

摘要：2019年第1期《电脑前传(2)：计算》回顾：图灵1936年的论文划定了计算的理论边界：计算是机械地执行长度有限的算法的过程，都可以由图灵机完成；所有算法都可以编码成为一个整数，因此是可数的；尽管如此，并不存在枚举出所有算法的算法。在此基础上，图灵对判定问题给出了否定回答。事实上，图灵的这个伟大贡献受到了五年之前另一个伟大贡献的启发，这就是本期要介绍的哥德尔不完备定理。

关键词：布尔代数逻辑主义希尔伯特纲领哥德尔定理

古典逻辑

逻辑学的目的是为人类理智建立一个坚实的基础，轴心时代，三大文明分别萌芽出墨辩（古中国）、因明学（古印度）和逻辑学（古希腊）。

我国春秋时期百家争鸣，注重辩论，墨子尤其注重辩论本身的合理性，提出了辩、类、故等逻辑概念，建立了类比、假言、直言、选言、演绎、归纳等一系列的思维方法，建立了中国第一个逻辑体系。

因明学以立宗、因、喻三支作法而为言论之法，印度各种宗派常用因明学互相辩论，耆那教、印度教与佛教都继承了这个传统。

古希腊哲人辈出，逻辑学至亚里士多德而确立下来，并作为哲学的一部分，主导西方思想近两千年。如今亚里士多德逻辑被称为词项逻辑，其最基本的概念是项和命题。

项是表达某个事物的词类，是命题的基本构件，分为单称项和全称项，两者的区别是亚里士多德“形而上学” 的基础：全称项是亚里士多德逻辑的基本素材，而包含单称项的命题根本就不构成它的一部分。

三段论是解释那些真前提的组合产生真结论的形式理论，即一个命题（结论）的必然性从另两个命题（前提）得出的一种推理。

命题由主词和谓词两项组成，主词可以是全称（例如“所有人”）或特称（例如“有些人”），谓词可以是“确认”或“否认”，这样就构成了四种命题，亚里士多德用逻辑方阵总结了四种命题之间的联系，但存在缺陷，与现代谓词演算并不兼容。

1656年，戈特弗里德·威廉·莱布尼茨(Gottfried Wilhelm Leibniz, 1646—1716)十岁，他的老师把亚里士多德的逻辑系统介绍给他，唤起了他的数学才能与持续一生的梦想：寻求一个符号系统，每个元素是一个概念，发展一种语言，仅凭符号演算，根据它们之间存在的关系，就可以确定用这种语言写成的句子哪些为真。

这里的符号不仅包括算术和代数符号，还包括他所发明的微分和积分，以及化学和天文学使用的符号，每个符号都以一种自然而恰当的方式表示某个确定的概念。莱布尼茨认为，我们需要的是一种普遍文字，即一个不仅真实，而且包含了人类全部思想领域的符号系统。

要实现这个梦想，莱布尼茨认为需要三步[1]：首先创造一套涵盖人类知识全部范围的纲要或百科全书，然后对其背后的观念进行选择，并为每一个观念提供合适的符号，最后是逻辑推演，即采用演绎规则对这些符号进行的操作。

莱布尼茨相信纷繁复杂的宇宙可以还原成这样的符号演算，正如他说过的：严肃的具有善良意志的人们围坐在桌子旁解决某个棘手问题，用普遍文字写出这个问题后，人们就可以说：“让我们算一下。”于是人们拿出笔得到一个解答，其对错必然可以为所有人接受。

莱布尼茨在创造普遍文字方面并无具体贡献，但在逻辑代数方面的思想却领先了一个多世纪。就像普通代数规定了数字的操作规则一样，逻辑代数清楚地规定了逻辑概念的操作规则，他一生都沉湎于此，被称为“十七世纪的亚里士多德”。

布尔逻辑

在并不了解莱布尼茨逻辑代数思想的情况下，乔治·布尔(George Boole, 1815—1864)独自一人提出了一种符号逻辑，把逻辑变成了代数。

布尔少而家贫，无钱求学，这位补鞋匠之子自学四门外语，16岁谋得小学教师职务。因收入微薄，买书只选数学书，因为“数学书看的时间可以更长一些”，没机会接触更多类型的论著反倒使他潜心数学，并在此期间产生了布尔代数的基本思想。因为做礼拜时还沉湎于数学，18岁的布尔被其所在的循道宗小学解雇了。

布尔19岁开办了自己的寄宿学校并担任校长，讲了无数的课，但也没耽误阅读当时最重要的数学文献，并在《剑桥数学期刊》发表了不少文章。

32岁出版《逻辑的数学分析》，39岁出版《思维的法则》，创立布尔逻辑。42岁当选英国皇家学会院士。

布尔的后代名人辈出，代代出院士，人工智能复兴的标志性人物杰弗里·辛顿就是布尔的曾曾外孙。

布尔是怎么想到把逻辑和代数关联到一起呢？布尔回忆说做小学教师时曾灵光乍现[2]。

那个时代的人们逐渐认识到代数的力量来自一个事实，即代表着量和运算的符号服从为数不多的几条基本规则或定律。

布尔早期曾把代数方法应用于被称为“算子”的对象上，例如把代数方法应用于微分算子，就可以解某些微分方程，这使布尔意识到亚里士多德的逻辑可用代数来表达。

布尔用字母代表一类事物，对应词项逻辑的项。

如果x和y分别表示两类事物，那么xy（类似乘法）就表示既属于x又属于y的事物。

布尔举例说，如果x代表“白的事物”，y代表“绵羊”，那么xy表示“白绵羊”。

布尔马上想到：xx表示什么意思呢？它表示既是白的，又是白的，因此还是……白的，所以xx=x。

事实上，布尔整个逻辑体系就建立在这样一个基础上：当x表示一个类时，方程xx=x总为真。

现在到了关键点：回到代数视角，方程xx=x在什么情况下总为真？布尔的回答是：当x=0或1的时候。那么在逻辑体系中，0和1应该表示什么呢？0表示不包含任何事物的类，1表示包含全部事物的类。

乘法有了逻辑对应物，接着看加法和减法。很自然，x+y表示并集， x-y表示在x中但不在y中的事物的集合，1-x表示不在x中的事物的集合。

回到代数视角，xx=x这个方程可以转换成x(1-x)=0，换成逻辑语言就是：没有任何事物既属于给定的类x，同时又不属于类x。这是令布尔最兴奋的一个结果，因为这就是亚里士多德《形而上学》中的矛盾律：

“同一性质既属于又不属于同一个东西，这是不可能的……这是一切原理中最确定无疑的……因此，那些做论证的人把这当成一条最终的意见。因为它依其本性就是其他一切公理的来源。”

x(1-x)=0或xx=x这个代数方程描述的正是作为一切公理之源的基本公理。布尔逻辑就此建立。不难理解布尔为什么把自己的著作题为《作为逻辑和概率的数学理论基础的思维规律研究》[3]。

布尔证明了逻辑演绎可以成为数学的一个分支。正如罗素在《数学原理》中认为的：“纯数学是布尔在一部他称之为《思维规律》的著作中发现的。”

逻辑学在徘徊2000多年之后，就此走上了数理逻辑的康庄大道。

本页Url