【离散数学】逻辑世界探幽——读《逻辑的引擎》有感

【离散数学】逻辑世界探幽——读《逻辑的引擎》有感

摘  要：逻辑理论的发展凝聚了一代代学者的智慧。莱布尼兹首先认识到推理演算和逻辑代数的重要性；布尔在其著作中首次介绍了逻辑代数；弗雷格定义了逻辑演算以支持他在数学基础上的研究；康托尔为集合论做出了突出贡献；希尔伯特站在前人的肩膀上，丰富并发展了逻辑理论；图灵提出图灵机模型，为现代计算机的逻辑工作方式奠定了基础……直至今日，逻辑和计算机科学之间仍在发生广泛而持续的相互作用，人们对逻辑世界的探索仍在进行中。

关键词：布尔代数，数理逻辑，集合论，图灵机，计算机科学

1 把逻辑变为代数

莱布尼茨十岁时便接触到了亚里士多德提出的逻辑系统。他为此着迷，并想要寻求这样一张特殊的字母表，其元素表示的不是声音而是概念，有了这样一个逻辑系统，我们就可以发展出一种语言，仅凭符号演算就可以确定用这种语言写成的句子是真还是假，以及他们之间存在的逻辑关系。在一封写给数学家洛必达的信中，莱布尼茨声称算数和代数表明了一个恰当的符号系统的重要性：首先要创造一套覆盖人类全部知识范围的“百科全书”，完成这一步之后，对其背后的关键观念进行选择并为其中的每一个赋以合适的符号就是可以实现的了。最后，演绎规则可以还原成对这些符号的操作，也即莱布尼茨所说的“推理演算”。英国数学家布尔的逻辑体系不仅包含了亚里士多德的逻辑，而且还远远超过它。布尔把逻辑简化为一种仅有0和1两个数字的代数运算，后世称之为布尔代数。从布尔开始，数理逻辑就一直处于不断的发展中。

2 概念文字与语言哲学

弗雷格的概念文字与康托尔对于无穷的探索都在当时时代的相应研究大环境中开辟了一个特殊的舞台，即针对现实意义的形式化表示和无穷意义的存在与否与何以正确的表达其意义。弗雷格在布尔逻辑的基础上更进一步，创造出一个精密的可以囊括数学中常用的推理，但在罗素致其的一封信中，其原本预想中的将数学完全囊括至逻辑的体系中破灭，其前提有缺，并不能完全的诠释数学，但可以指出的是其创造的形式语言仍在如今的众领域研究中发挥着作用，而更进一步的在哲学层次上，弗雷格建立了属于他的语言哲学，其强调以意义为核心的区分，而其形成为计算机科学领域的某些重要概念奠定了基础。康托尔则是在无穷数的探索中不断行进，其针对无穷的意义给出了自己的体系，但却无法进行严谨的数学推导，但在其研究过程中，集合论的建立延续至今，而超穷数理论的创造激发出了关于无穷意义的争变，斗争的副产物却出乎意料的发挥了至今重大的作用--即图灵机数学模型。二者坚定的学术坚持让其直面困难，，为逻辑体系与无穷体系的发展作出了重要的贡献，弗雷格语言哲学的应用，让现实世界的事件以命组合的形式和意义的核心标准能够实现转换，为以图灵机模型为架构基础的计算机提供了面向现实的基础，弗雷格或许没曾想到其研究的理论会以这种形式发挥着如此重大的作用，或许这就是学术研究的魅力吧，个人研究探究真理的极限，不立一时之誉，而成万世之功。而康托尔的集合论无论在计算机科学领域还是数学领域都发挥着不可忽视的重要作用，其为分类的处理以及元素的处理都提供了一个合理且好用的形式，而其对于无穷数的研究虽然陷入困境却也以别开生面的理解为后人的研究提供一个有用的方向。

3 希尔伯特和哥德尔的探索

希尔伯特对历史上几个疑难证明问题进行逻辑推导，并在逻辑证明中，总结出自己的一套逻辑证明方法，也就是希尔伯特纲领，并创造性地提出元数学这一概念。在当时，数学界受康托尔等人的影响，无穷集与超穷数等概念深入到每位数学家内心，而希尔伯特并没有被这些概念辖制头脑。在解决果尔丹问题时，（一个特定代数表达式中所有不变量总会有几个主要不变量，通过它们可以用一个公式将其他不变量表示出来），他为了证明这几个主要不变量存在，先假设这些对象存在并且不导致原命题矛盾，通过有限次的逻辑过程证明，赋予一个概念的性质不会导致矛盾，那么这些对象的存在性就被证明了。1900年，希尔伯特参加了第一届巴黎国际数学大会，在会上阐述了23个问题，这23个问题成为了至今仍在数学界争论不休的数学问题。他的这些问题显示出强烈的形式主义，它分为两个方面，一个是对于无穷数学进行严格的公理化，只是把它们看作是形式系统的对一些句子的推演，通过公理引入新的推理方式。另一部分就是有穷数学，是关于有穷、具体的理论。基于此，希尔伯特创立了自己的纲领，逻辑证明方法要严格限于有限性的无可争议的方法，只允许有限性的推理，要证明某个系统的无矛盾性就要用到有限性方法。当然，提出这样的纲领少不了质疑声，其中布劳威尔是反应最为强烈的，布劳威尔对于康托尔、希尔伯特等人的工作认为是荒谬的，他反对将排中律运用于无限集（认定任何命题或者为为真，或者为假，不存在亦真亦假的情况），而希尔伯特在解决果尔丹问题时运用排中律，所以布劳威尔对于证明不满意，对希尔伯特提出的纲领持反对意见。后来，希尔伯特发展了他的逻辑纲领，使它的某些方面符合布劳威尔的看法，布劳威尔也无法彻底推翻他的理论。

哥德尔的理论对计算机程序语言做出了巨大贡献。起初，哥德尔支持希尔伯特的理论体系，并在很多逻辑证明中运用了希尔伯特的有限性方法，他希望用有限性方法把可以包含实数算术的更强的系统的一致性还原为一般的算术一致性，以此来完成希尔伯特的一致性问题并发展其理论。谁知，在他运用符号串编码方法将命题化为一个个数字时，问题出现了，根据康托尔的对角线法则，这样编码的命题会有无穷个，这与希尔伯特的有穷性不符。就这样，哥德尔的证明葬送了希尔伯特纲领。在这之后，哥德尔得出并发展自己的理论---哥德尔不完全性定理，任何一个初等数论的形式系统，都存在一个命题，他在这个系统中既不能被证明为真，也不能被证明为假。该定理是对希尔伯特纲领的否定，即使形式系统内部所有的数学方法也无法证明该形式系统的一致性，更不用说希尔伯特纲领那样用有限的子集、有限性方法来证明一致性。另外，不完全性第二定理提出，如果系统中含有初等数论，当该系统无矛盾时，他的无矛盾性不可能在其内证明。假定一无穷命题集PM，其中有一个命题U，它是真的，但在命题集中不可证，如果U为假，那该命题就是可证的，那就可以证明它为真，那就与假设矛盾，所以U一定为真，U不可证。在计算机领域，虽然哥德尔得出不完全性定理时计算机没有出现，但他的命题编码化对日后计算机程序语言开发有着启发开导的作用，从复杂的高级程序语言转化到汇编语言，符合机器逻辑判断。另外，基于当今计算机仍然是冯诺依曼体系的，处理数据仍然递归的判断某些编码命题的真伪，哥德尔的不完全性定理指出其缺陷，至少存在一个命题使得计算机无法判断其真伪，计算机就卡壳了。综上，哥德尔通过其创造思想，极大地推动计算机的出现与发展。

4 图灵与冯诺依曼的伟大构想

图灵在14岁时发现了数学的美妙，转而全身心的投入到了数学的研究，他甚至还自己研究起来了爱因斯坦的相对论。再后来，图灵利用他所掌握的全新的数学证明了他自己的才能，最终发表了一篇论文，这篇论文中，他对冯诺依曼所证明的一条定理进行了改进，它属于一个极其专业的领域，殆周期函数论。图灵后来进行了对计算过程的分析，计算的过程就是注视着一个数并对它加以规则的约束，使其成为之后数的数，使用了乘法进行举例，将数字都放在无限长的纸带上，进行一个数对应一个数的运算，再将纸带进行推进，这样即可得到最终想要的结果。如果要将其变为运转的机器的话，就得加上许多的判定条件，这里使用各类符号进行判断，再加上逻辑的规则，即可完成纸带进入机器到出来机器得出正确的结果，再后来，图灵参与了密码的破译工作，这也是他将自己的理论应用于实践的一次尝试，尽管刚开始失败了很多次，但他坚信自己的理论是正确的并最终制造出了这台近乎全自动的破解迷式密码的机器。

在战后，图灵学习掌握了晶体管的相关知识，开始着手制造通用计算机。没有人可以说是自己一手制造出了第一台通用计算机，这是许许多多科学家共同努力的结果，他们每个人对于通用计算机都有自己独到的见解，这些见解合在一块才组成了通用计算机的全貌，EDVAC（电子离散变量自动计算机）在这之后计算机具备了良好的存储能力，还包含一个实现逻辑控制的器件，它把需要执行的指令（每次执行一条）从存储器转移到算术器件。计算机的这种组织方式后来被称为“冯诺依曼结构”。

冯诺依曼还强调一台计算机的逻辑控制对于它的尽可能接近通用是至关重要的。战后的计算机与战前的计算机有着本质性的区别，主要是战后的机器都被设计成了通用的普遍装置，只要过程中的步骤被明确指定了，它们就可以执行任何符号过程。在这同时期，图灵也完成了他的ACE自动计算机的报告。ACE与EDVAC之间的一个不同之处是，后者是一份尚未完成的草案，但ACE的报告却是一次完整的描述，一直到逻辑电路图。

引用时代杂志对冯诺依曼的评价：事实上，从耗资1000万美元的超级计算机到今天的无线电话和菲比玩具上所使用的微小芯片，所有计算机都有一个共同点：它们都是“冯诺依曼机”，都是冯诺依曼基于图灵在20 世纪 40年代的工作所提出的计算机的基本结构的变种。

5 结语

逻辑与计算密不可分，从亚里士多德开始，人们便为把逻辑推理归结为形式规则而努力。莱布尼茨梦想寻找一种普遍的计算语言，图灵说明了任何计算都能在他的通用机上进行，他们的学说和成就都间或由亚里士多德的工作作为基础与支撑。直至今日，逻辑和计算机科学之间仍在发生着广泛而持续的相互作用，在分布式计算、人工智能、数据库系统等领域，逻辑为计算机科学提供了一种统一的基础架构和建立模型的工具，值得我们深入学习与探索。