数理逻辑回顾

计算机科学MOOC课程群

数理逻辑，或符号逻辑，也称为现代形式逻辑，采用一套符号体系及其组合的语句、公式等描述结构，加上一套演绎系统，完全取代经典形式逻辑的语言化的描述和推理方式。

数理逻辑是研究推理逻辑规律的一个数学分支，它采用数学符号化的方法（符号、公式、公理化），给出逻辑规则，建立推理体系，进而讨论推理体系的一致性、可靠性和完备性等。其研究对象是对证明和计算这两个直观概念进行符号化以后的形式系统。

莱布尼兹：代数演绎的思想

» 莱布尼茨曾经设想过能不能创造一种¡°通用的科学语言¡±，可以把推理过程象数学一样利用公式来进行计算，从而得出正确的结论。

布尔代数

» 布尔在1847年出版的《逻辑的数学分析，论演绎推理的演算法》一书中建立了完整的逻辑代数体系，即布尔代数。

弗雷格的《表意符号》

» 弗雷格在1879年的《表意符号》和1884年的《数论的基础》中引入量词符号和变元约束，使得数理逻辑的符号系统更加完备。

罗素悖论

» 集合论在19世纪末由康托建立后，集合概念成为最基本、应用最广的一个概念，人们曾经相信，全部数学的基础理论可用集合概念统一起来。

1903年英国唯心主义哲学家、逻辑学家、数学家罗素对集合论提出了以他名字命名的“罗素悖论”，几乎动摇了整个数学基础，引起了所谓第三次数学危机。

罗素悖论

» 集合可以划分为两类。第一类集合是：集合本身又是该集合中的元素，例如人们经常说的¡°所有集合所成的集合¡±；第二类集合是：集合本身不

是该集合的元素，例如直线上点的集合，或所有人的集合。一个集合必须是且只能是这两类集合中的一类。

罗素悖论

» 现在定义 R 是由所有第二类集合所构成的集合。那么，R 是两类集合中的哪一类呢？ 

– 如果 R 是它本身的成员，则 R 是第一类集合而不是第二类集合，由 R 的定义 R 不

是它本身的成员。另一方面，如果 R 不是它本身的成员，则 R 是第二类集合而不是

第一类集合，由 R 的定义 R 是它本身的成员。 

悖论在于：无论哪种情况，都将导致矛盾。

罗素悖论 - 理发师困境  

» 罗素悖论的通俗形式是所谓“理发师困境”。某村理发师宣布：他给所有不给自己刮脸的人刮脸，并且只给村子里这样的人刮脸。那么“理发师是否自己给自己刮脸？”如果他给自己刮脸。那么他就不符合他的原则；如果他不给自己刮脸，那么他按原则就该为自己刮脸。 

莱布尼兹的逻辑主义思想萌芽

» 逻辑学先于一切科学

莱布尼兹时代，他把逻辑学想象成一种普遍的科学， 这种科学包括构成其它所有科学的基础的一些原则。这种逻辑学先于一切科学的观点，是逻辑主义思想原则的萌芽。

罗素的《数学原理》  

» 罗素与怀特海于1913年完成了逻辑主义的经典巨著《数学原理》。

作者企图在这3卷本的数学巨著中向人们说明：全部数学可以从一个逻辑公理系统严格推导出来，也就是说可以从逻辑概念出发，用明显的定义得出数学概念；由逻辑命题开始用纯逻辑的演绎推得数学定理。从而，全部数学都可以从基本的逻辑概念和逻辑规则推导出来。

这样，就可以把数学看成是逻辑学的延伸或分支。所以，罗素说：“逻辑学是数学的青年时代，而数学是逻辑学的壮年时代。”、“数学即逻辑。”数学化归于逻辑是罗素的基本观点，但实际上并不成功。

《数学原理》以严格的形式化的符号语言来陈述作者建立的逻辑体系、定义和定理，标志着符号逻辑方法的成功，并显示了数学的逻辑基础研究的意义，进一步显示了现代逻辑的科学意义。

希尔伯特

» 希尔伯特(德,1862-1943)于1900年8月8日在巴黎第二届国际数学家大会

上，提出了新世纪数学家应当努力解决的23个数学问题，被认为是20世纪

数学的至高点，对这些问题的研究有力推动了20世纪数学的发展，在世界上产生了深远的影响。

形式主义理论体系是在非欧几何产生之后，在数学和数学哲学研究中弥漫的“重建数学基础”的气氛中形成的。当非欧几何得到人们的承认，亦即当得出互相矛盾的定理的两种几何都证明了不自相矛盾的时候，人们便要问：数学的真理体现在那里？ 试想一下，一种几何说，过直线外一点只能作一条直线不与原有的直线相交；另一种几何说，过直线外一点至少可作两条直线不与原有的直线相交；还有一种几何说：过直线外一点不可以做任何直线于原有的直线不相交。

希尔伯特认为，为了避免在数学中出现悖论，就要设法绝对的证明数学的无矛盾性，使数学奠定在严格的公理化的基础上。数学的公理和逻辑推理就像天文学家手中的望远镜那样重要，是不能丢弃的。为了实现这一目的，在1922 年提出了希尔伯特计划。

希尔伯特计划

» 希尔伯特指出: 奠定一门数学的基础，应该严格的、数学的证明这门数学的协调性（即无矛盾性或一致性、相容性）。数学建立在集合论和数理逻辑两块基石上。

希尔伯特的《数学基础》

» 希尔伯特的《数学基础》是希尔伯特计划的代表作。

希尔伯特的《数学基础》是希尔伯特计划的代表作。它计划将各门数学形式化，构成形式系统，然后用一种初等方法证明各个形式系统的相容性，即无矛盾性，从而导出全部数学的无矛盾性。

希尔伯特纲领

» 希尔伯特纲领是以证明论为核心的关于数学基础的所谓形式主义纲领。数学被形式化为一个系统，这个形式系统的对象包含了数学的与逻辑的两个方面，人们必须通过符号逻辑的方法来进行数学语句的公式表述，并用形式的程序表示推理。

哥德尔定理

» 1931年哥德尔指出，没有一种公理系统可以导出数论中所有的真实命题，除非这种系统本身就有悖论。或：任何一个足以包含实数算术的形式系统，必定存在一个不可判定的命题 S (即 S 与~S 皆成立)。

形式主义和逻辑主义都从公理系统出发，不同的是：

» 逻辑主义者要求逻辑公理系统具有内容， 而且想方设法探求逻辑规律的真理性究竟体现在什么地方

» 形式主义者认为数学的公理系统或逻辑的公理系统，其中的基本概念都是没有意义的，其公理也只是一行行的符号，无所谓真假，只要能够证明该公理系统是相容的，不互相矛盾

的，该公理系统便得到承认，它便代表某一方面的真理。

直觉主义数学观

» 存在即是被构造。人们对数学的认识不是依赖于逻辑和语言经验，而是原始直觉（即人皆有的一种能力），纯粹数学是心智的数学构造自身、是反身的构造，它开始于自然数，而不是集合论。

直觉主义数学观

» 逻辑不是发现真理的绝对可靠的工具，并认为在真正的数学证明中不能使用排中律，因为排中律和其他经典逻辑规律是从有穷集抽象出来的规律，因此不能无限制的使用到无穷集上去。同样不能使用反证法。

20世纪30年代以后，由于哥德尔的工作，许多数学家开始重视直觉主义。数学家们纷纷尝试用构造法建立实数理论、数学分析以至全部数学，得出不少重要结果。构造性数学已经成为数学科学中一个重要的数学学科群体，与计算机科学密切相关。

1936年图灵发表了一篇著名的论文《论数字计算在判决难题中的应用》。他提出了一种十分简单但运算能力极强的理想计算装置，用于计算所有能想象得到的可计算函数。

图灵机

» 图灵机由一个控制器和一根假设两端无界的工作带组成。工作带起着存储器的作用，它被划分为大小相同的方格，每一格上可书写一个给定字母表上的符号。控制器可以在带上左右移动，控制带有一个读写头，读写头可以读出控制器访问的格子上的符号，也能改写和抹去这一符号。

图灵机是一种理想的计算模型，或者说是一种理想中的计算机。图灵的这一思想实际上奠定了现代计算机的基础。图灵和冯·诺依曼在普林斯顿曾有沟通，后者一再强调，他的“存储程序”的思想主要来自图灵。

图灵给“可计算性”下了一个严格的数学定义， 这个已经超出本课程的讨论范围。数理逻辑的递归论研究解决问题的可行的计算方法和计算的复杂程度 ，图灵可计算的函数与递归函数等价。图灵-丘奇论题指出：递归函数是可计算函数的精确的数学描述。

早期的布尔逻辑属于代数，而数理逻辑已成为独立的边缘学科类型。从广义上理解，它包括了逻辑演算、证明论、公理集合论、递归论和模型论（研究形式系统和数学模型之间的关系）五个部分。逻辑演算属于逻辑学范畴，主要指一阶逻辑演算（包括命题逻辑和一阶谓词逻辑），构成数理逻辑的基础内容，而后四论属于数学范畴。

从狭义上理解，数理逻辑就是逻辑演算，其中一阶逻辑演算也称为经典逻辑或

标准逻辑。对经典逻辑的扩充或修改构成了非经典逻辑或非标逻辑。

本课程的数理逻辑部分将主要讨论最基本的内容，包括命题逻辑的概念、等值演算、推理演算以及谓词逻辑的概念、等值演算、推理演算。对其他部分内容有所涉猎。

　 下一单元内容提示

命题的概念 

命题连接词