数理逻辑发展简史课件.ppt

1、数理逻辑发展简史马殿富马殿富北航计算机学院北航计算机学院2002009-99-9计算机学院2计算机学院什么是逻辑？什么是逻辑？逻辑示例逻辑示例 有有2 2个红色帽子，个红色帽子，3 3个黑色个黑色帽子。帽子。三个人站成一纵队，各戴三个人站成一纵队，各戴一顶帽子，每人仅能看到一顶帽子，每人仅能看到前面人帽子颜色。前面人帽子颜色。问？问？第三个人帽子颜色？第三个人帽子颜色？回答：不知道！回答：不知道！第二个人帽子颜色？第二个人帽子颜色？回答：不知道！回答：不知道！第一个人帽子颜色？第一个人帽子颜色？回答：知道！回答：知道！第一个人帽子颜色是什么第一个人帽子颜色是什么？为什么？为什么？第一个人推理：

2、第一个人推理：如果第一人和第二人都是红色如果第一人和第二人都是红色帽子，则第三人知道自己帽子帽子，则第三人知道自己帽子颜色为黑色。颜色为黑色。因为第三人不知道自己帽子颜因为第三人不知道自己帽子颜色为黑色，所以，第一人和第色为黑色，所以，第一人和第二人不都是红色帽子。二人不都是红色帽子。如果第一是红色帽子，则第二如果第一是红色帽子，则第二人知道自己帽子颜色为黑色。人知道自己帽子颜色为黑色。因为第二人不知道自己帽子颜因为第二人不知道自己帽子颜色为黑色，所以，第一不是红色为黑色，所以，第一不是红色帽子。色帽子。第一是黑色帽子。第一是黑色帽子。计算机学院3计算机学院什么是逻辑？什么是逻辑？思维形式思维

3、形式 概念概念反映事物本质属性。反映事物本质属性。判断判断由概念组成的一种思维形式叫判断。由概念组成的一种思维形式叫判断。推理推理由几个相关联的判断所构成的思维形式叫推理。由几个相关联的判断所构成的思维形式叫推理。逻辑逻辑 从结构方面研究正确思维形式及其规律的科学。从结构方面研究正确思维形式及其规律的科学。计算机学院4计算机学院数理逻辑是什么？数理逻辑是什么？狭义数理逻辑狭义数理逻辑 用数学方法研究数学中演绎思维和数学基础的学科。用数学方法研究数学中演绎思维和数学基础的学科。广义数理逻辑广义数理逻辑 用特制符号和数学方法来研究处理演绎方法的理论。用特制符号和数学方法来研究处理演绎方法的理论。狭

4、义数理逻辑包括五个部分狭义数理逻辑包括五个部分 逻辑演算逻辑演算 模型论模型论 集合论集合论 递归论递归论 证明论证明论计算机学院5计算机学院数理逻辑发展数理逻辑发展2 2种主要途径种主要途径 借助数学的方法改进传统逻辑不足；借助数学的方法改进传统逻辑不足；对数学基础的研究，产生了大量与逻辑对数学基础的研究，产生了大量与逻辑有关的问题。有关的问题。计算机学院6计算机学院数理逻辑发展简介数理逻辑发展简介史前时期史前时期 亚里土多德的三段论，斯多阿学派的命题逻辑和中世纪形式逻辑。亚里土多德的三段论，斯多阿学派的命题逻辑和中世纪形式逻辑。初创时期初创时期 莱布尼茨的数理逻辑思想莱布尼茨的数理逻辑思想

5、 逻辑代数和关系逻辑逻辑代数和关系逻辑奠基时期奠基时期 从弗雷格的从弗雷格的概念文字概念文字到希尔伯特的元数学纲领到希尔伯特的元数学纲领 逻辑演算的建立，素朴集合论、公理集合论逻辑演算的建立，素朴集合论、公理集合论 逻辑类理论，直觉主义数学基础和逻辑，形式公理学和证明论。逻辑类理论，直觉主义数学基础和逻辑，形式公理学和证明论。发展初期发展初期 哥德尔的几项重大结果哥德尔的几项重大结果完全性定理、不完全性定理和连续统假设的一致性等完全性定理、不完全性定理和连续统假设的一致性等 形式语言中真值概念的定义形式语言中真值概念的定义 一般递归函数和图灵机理论，判定问题的重要成果等。一般递归函数和图灵机理

6、论，判定问题的重要成果等。现代时期现代时期 各种非经典逻辑演算各种非经典逻辑演算 模型论、集合论、递归论和证明论。模型论、集合论、递归论和证明论。计算机学院7计算机学院史前时期史前时期 古代希腊最伟大的哲学家，古典形式古代希腊最伟大的哲学家，古典形式逻辑的创始人；逻辑的创始人；在命题中引进了主谓项的变元，建立在命题中引进了主谓项的变元，建立了三段论的理论；了三段论的理论；在逻辑史上第一次应用了形式化、公在逻辑史上第一次应用了形式化、公理化的的演绎系统，开创了逻辑的形理化的的演绎系统，开创了逻辑的形式化研究；式化研究；构造了模态三段论系统，开创了模态构造了模态三段论系统，开创了模态逻辑的研究；逻

7、辑的研究；在在工具论工具论中，总结了正确的推理中，总结了正确的推理方法，建立了形式逻辑；在方法，建立了形式逻辑；在分析篇分析篇提出公理学理论的基础。提出公理学理论的基础。亚里土多德亚里土多德(Aristotle，公元前，公元前384322)计算机学院8计算机学院史前时期史前时期 斯多阿学派的命题逻辑斯多阿学派的命题逻辑 古希腊的一个哲学学派古希腊的一个哲学学派 创造了命题逻辑，用形式化和公理化的方法第一次构造创造了命题逻辑，用形式化和公理化的方法第一次构造了一个命题逻辑系统，给出了一个命题逻辑系统，给出5 5种公理化基本推理图式。种公理化基本推理图式。斐洛斐洛 (Philo)(Philo)第一

8、个提出了相当于现代命题演算中实质蕴第一个提出了相当于现代命题演算中实质蕴涵的真值表。涵的真值表。欧布理得发现了说谎者悖论：欧布理得发现了说谎者悖论：一个说谎的人说一个说谎的人说“我正在说谎我正在说谎”；他是在说谎，还是说真话他是在说谎，还是说真话?这一悖论现在归属于语义悖论。这一悖论现在归属于语义悖论。中世纪的形式逻辑中世纪的形式逻辑 中世纪逻辑学家总共陈述了中世纪逻辑学家总共陈述了6060多条推论原理多条推论原理计算机学院9计算机学院传统逻辑传统逻辑 传统逻辑主要是指亚里士多德逻辑传统逻辑主要是指亚里士多德逻辑 经过中世纪的演变一直沿用到十九世纪经过中世纪的演变一直沿用到十九世纪;在中世纪被

9、认为金科玉律、完美元缺在中世纪被认为金科玉律、完美元缺;到了十九世纪，它的缺点突出，急需改革。到了十九世纪，它的缺点突出，急需改革。传统逻辑主要缺点：传统逻辑主要缺点：传统逻辑所讨论的子句仅限于主宾式语句，分成四种：传统逻辑所讨论的子句仅限于主宾式语句，分成四种：全称肯定全称肯定A A：AspAsp，凡，凡s s均为均为p p；全称否定全称否定E E，EspEsp，凡，凡s s均非均非p p；特称肯定特称肯定I I，IspIsp，有的，有的s s为为p p；特称否定特称否定O O，OspOsp；有的；有的s s非非p p。限于三段论。限于三段论。没有关于量词的研究，没有没有关于量词的研究，没有

10、“变元变元”的概念。的概念。计算机学院10计算机学院初创时期初创时期 德国哲学家和数学家，德国哲学家和数学家，1717世纪末创建世纪末创建了数理逻辑。了数理逻辑。建立一种理想的建立一种理想的“通用语言通用语言”进行推进行推理。理。他曾经给一位友人的信上写道：他曾经给一位友人的信上写道：“要是我少受搅扰，或者要是我更年青些要是我少受搅扰，或者要是我更年青些，或有一些年青人来帮助我，我将作出一，或有一些年青人来帮助我，我将作出一种种 “通用代数通用代数”(在其中，一切推理的正在其中，一切推理的正确性将化归于计算它同时又将是通用语确性将化归于计算它同时又将是通用语言，但却和目前现有的一切语言完全不同

11、言，但却和目前现有的一切语言完全不同；其中的字母和字将由推理来确定，除却；其中的字母和字将由推理来确定，除却事实的错误以外；所有的错误将只由于计事实的错误以外；所有的错误将只由于计算失误而来。要创作或发明这种语言或字算失误而来。要创作或发明这种语言或字母将是困难的，但要学习它，即使不用字母将是困难的，但要学习它，即使不用字典，也是很容易的。典，也是很容易的。”莱布尼茨(Leibniz，16461716)计算机学院11计算机学院初创时期初创时期 莱布尼茨预创造两种工具，莱布尼茨预创造两种工具，其一是通用语言其一是通用语言使用简单明了的符号；使用简单明了的符号；合理的语言规则；合理的语言规则；便于

12、逻辑分析和综合。便于逻辑分析和综合。另一种是推理演算另一种是推理演算它将处理通用语言；它将处理通用语言；规定符号的演变规则、运算规则；规定符号的演变规则、运算规则；使得逻辑的演算进行机械式计算。使得逻辑的演算进行机械式计算。莱布尼茨的思想是用代数方法处理古典形式逻辑莱布尼茨的思想是用代数方法处理古典形式逻辑的推理，延续了大约二百年。的推理，延续了大约二百年。计算机学院12计算机学院初创时期初创时期 德德.摩根摩根关系逻辑关系逻辑 1919世纪英国数学家和逻辑学家世纪英国数学家和逻辑学家，生于印度；，生于印度；18381838年提出年提出“数学归纳法数学归纳法”的的概念；概念；首先提出首先提出“

13、论域论域”的概念，第的概念，第一次明确用公式表达合取和析一次明确用公式表达合取和析取的关系，称为德取的关系，称为德 摩根律；摩根律；主张判断扩充为一般的关系语主张判断扩充为一般的关系语句，明确主张发展关系逻辑，句，明确主张发展关系逻辑，逻辑代数的创始人之一。逻辑代数的创始人之一。DeMorgan 1806-1871计算机学院13计算机学院初创时期初创时期 布尔布尔英国数学家英国数学家 18471847年，发表了年，发表了逻辑的数学分逻辑的数学分析，论演绎推理演算析，论演绎推理演算，18541854年年出版了出版了思维法则的探讨，作为思维法则的探讨，作为逻辑与概率的数学理论的基础逻辑与概率的数学

14、理论的基础 建立了建立了“布尔代数布尔代数”，并创造一，并创造一套符号系统，利用符号来表示逻套符号系统，利用符号来表示逻辑中的各种概念，这是一种新的辑中的各种概念，这是一种新的逻辑。逻辑。建立了一系列的运算法则，利用建立了一系列的运算法则，利用代数的方法研究逻辑问题，初步代数的方法研究逻辑问题，初步奠定了数理逻辑的基础。奠定了数理逻辑的基础。George Boole 1815-1864计算机学院14计算机学院初创时期初创时期 耶芳斯耶芳斯 使用相等记号来表示命题中的系词使用相等记号来表示命题中的系词 布尔代数引入相容的或运算。布尔代数引入相容的或运算。文恩（英国逻辑学家）文恩（英国逻辑学家）用

15、图解法表示布尔代数用图解法表示布尔代数 18811881年提出符号逻辑年提出符号逻辑 麦柯尔麦柯尔(H(HMcColl)McColl)用字母及字母的组合表示整个命题；用字母及字母的组合表示整个命题；沿用流行的符号把沿用流行的符号把“A A或或B B”，“A A且且B B“非非A A”表为表为A+BA+B，ABAB，A A；引入了引入了A A蕴涵蕴涵B B的概念，表示为的概念，表示为A:BA:B。Stanley Jevons1835-1882John Venn1834-1923计算机学院15计算机学院初创时期初创时期Charles S.Peirce（1839-1914）皮尔斯C.S.Peirce

16、 1885年独立地引进了量词这个名称，以及存在量词x 和全称量词x两个符号。命题代数或命题演算“既非，又非”作为逻辑作为初始运算。在逻辑史上第一次全面、系统地建立了关系演算。皮尔斯和弗雷格都明确指出命题只有真假二值，命题的研究实质上是真假值的研究。计算机学院16计算机学院奠基时期奠基时期 德国人，数学家，逻辑学家，哲学家德国人，数学家，逻辑学家，哲学家 18791879年的年的表意符号表意符号引入和使用量词与约引入和使用量词与约束变元。束变元。18791879年出版著作年出版著作概念文字：一种模仿算术概念文字：一种模仿算术语言构造的纯思维的形式语言语言构造的纯思维的形式语言；第一次把谓词演算形

17、式化第一次把谓词演算形式化,完备地发展了命题完备地发展了命题演算和谓词演算；演算和谓词演算；历史上第一个严格的关于逻辑规律的公理系历史上第一个严格的关于逻辑规律的公理系统；这个系统共有三个基本概念：蕴涵、否统；这个系统共有三个基本概念：蕴涵、否定和全称量词，共有九条公理。定和全称量词，共有九条公理。第一个引入了符号第一个引入了符号；接近于完成数理逻辑整个基础，标志着数理接近于完成数理逻辑整个基础，标志着数理逻辑的发展由创建时期进入奠基时期。逻辑的发展由创建时期进入奠基时期。弗雷格 Gottlob Frege 1848-1925计算机学院17计算机学院奠基时期奠基时期 18991899年意大利数

18、理逻辑学家；年意大利数理逻辑学家；提出了自然数算术的一个公理提出了自然数算术的一个公理系统系统 18941894年出版数学公式，年出版数学公式，逻辑逻辑符号体系沿用至今；符号体系沿用至今；用逻辑演算表述数学、推导用逻辑演算表述数学、推导数学数学；区分集合论中的区分集合论中的“属于属于”关关系和包含关系系和包含关系；关于自然数论的五个公理一关于自然数论的五个公理一直沿用到现在，成为自然数直沿用到现在，成为自然数论的出发点。论的出发点。皮亚诺Giuseppe Peano 1858-1932计算机学院18计算机学院奠基时期奠基时期 罗素罗素(B.Russell)(B.Russell)，英国逻辑学，英

19、国逻辑学家，哲学家；家，哲学家；继承皮亚诺的研究，完备了命继承皮亚诺的研究，完备了命题演算和谓词演算的成果；题演算和谓词演算的成果；以集合论为基础，给出了自然以集合论为基础，给出了自然数定义，证明了自然数满足皮数定义，证明了自然数满足皮亚诺的五个公理；亚诺的五个公理；罗素总结了数理逻辑的成果，罗素总结了数理逻辑的成果，和怀特海合著了和怀特海合著了数学原理数学原理，他的成果汇集成为一本巨著，他的成果汇集成为一本巨著，奠定了数理逻辑的基础。，奠定了数理逻辑的基础。Bertrand Russell 1872-1970计算机学院19计算机学院数学三次大危机数学三次大危机 数学曾发生三次大危机，它使数学

20、基础问题数学曾发生三次大危机，它使数学基础问题发生三次大争论。发生三次大争论。第一次是古希腊时代无理数的发现第一次是古希腊时代无理数的发现 毕达格拉斯学派以毕达格拉斯学派以 “只有可通约量只有可通约量”为信念为信念。为了解释无理数的存在，处理无理数，古。为了解释无理数的存在，处理无理数，古希腊人发展了比例论，从而建立几何公理系希腊人发展了比例论，从而建立几何公理系统。统。第二次是十七、八世纪关于微积分基础的争第二次是十七、八世纪关于微积分基础的争论，即关于无穷小的争论，它一直延续到十论，即关于无穷小的争论，它一直延续到十九世纪，结果得出了极限论以及无理数的算九世纪，结果得出了极限论以及无理数的

21、算术理论。术理论。第三次是集合论悖论的出现，从而导致数理第三次是集合论悖论的出现，从而导致数理逻辑的蓬勃发展。逻辑的蓬勃发展。Pythagoras,572BC497BC),古希腊计算机学院20计算机学院第一次数学危机第一次数学危机 欧几里德，古希腊数学家；欧几里德，古希腊数学家；几何原本几何原本是一个实质公理系统，是一个实质公理系统，把点、线、面、角等分为原始定义概把点、线、面、角等分为原始定义概念（念（2323）和可定义概念，把命题分为）和可定义概念，把命题分为公设（公设（5 5）、公理（）、公理（5 5）和可由公理公）和可由公理公设出发加以证明的定理（设出发加以证明的定理（467467）。

22、从）。从简单到复杂，证明相当严格。从而建简单到复杂，证明相当严格。从而建立了欧几里得几何学的第一个公理化立了欧几里得几何学的第一个公理化数学体系。数学体系。在在几何原本几何原本所给的公理公设中，所给的公理公设中，第五公设是关于平行线的，通常叫做第五公设是关于平行线的，通常叫做平行公理。平行公理。5 5(平行公设平行公设)若一直线与两直线相交若一直线与两直线相交，且若同侧所交两内角之和小于两直，且若同侧所交两内角之和小于两直角，则两直线无限延长后必相交于该角，则两直线无限延长后必相交于该侧的一点。侧的一点。Euclid of Alexandria 325 BC-265 BC 计算机学院21计算机

23、学院无穷的大小无穷的大小 16381638年伽利略年伽利略(Galileo)(Galileo)11，2 2，3 3，4 4，.1,4,9,16,1,4,9,16,伽利略(1564-1642)计算机学院22计算机学院第二次数学危机第二次数学危机 牛顿和莱布尼茨提出微积分，计牛顿和莱布尼茨提出微积分，计算非等速运动、不均匀密度的物算非等速运动、不均匀密度的物体等物理现象引发微积分的基础体等物理现象引发微积分的基础问题争论达一百多年。问题争论达一百多年。极限论的说法中，有一条性质，极限论的说法中，有一条性质，即即“有界单调的数列必有极限有界单调的数列必有极限”，是一切其它性质的基础，别的，是一切其它

24、性质的基础，别的性质都可由它推出。但这条性质性质都可由它推出。但这条性质又从何推出呢又从何推出呢?长期以来，人们以为可以由几何长期以来，人们以为可以由几何性质推出但几何公理中，根本性质推出但几何公理中，根本末讨论到连续的性质，更未讨论末讨论到连续的性质，更未讨论到极限。到极限。Isaac Newton 1643-1727计算机学院23计算机学院 Augustin-Louis CauchyAugustin-Louis Cauchy（1789 1789 1857 1857）柯西用柯西用“-”的数学形式的数学形式对极限、收敛给出了严格对极限、收敛给出了严格的定义。的定义。计算机学院24计算机学院 魏

25、尔斯特拉斯魏尔斯特拉斯 Karl Theodor Wilhelm Karl Theodor Wilhelm Weierstrass Weierstrass（1815 1815 18971897）1919世纪下半叶，维尔世纪下半叶，维尔斯特拉斯、戴德金、斯特拉斯、戴德金、康托尔等数学家分别康托尔等数学家分别给实数作出了算术形给实数作出了算术形式定义之后，实数理式定义之后，实数理论建立在集合论基础论建立在集合论基础之上。之上。计算机学院25计算机学院非欧几何非欧几何 1818世纪初意大利数学家萨克利，用反证世纪初意大利数学家萨克利，用反证法，假设欧氏几何五公设的否定命题，法，假设欧氏几何五公设的否

26、定命题，结果推出了一系列命题，始终没有得到结果推出了一系列命题，始终没有得到矛盾。矛盾。俄国数学家罗巴切夫斯基发现了锐角非俄国数学家罗巴切夫斯基发现了锐角非欧几何。欧几何。从直线外一点，至少可以做两条直从直线外一点，至少可以做两条直线和这条直线平行。线和这条直线平行。18541854年黎曼发现了钝角非欧几何。年黎曼发现了钝角非欧几何。在同一平面内任何两条直线都有交在同一平面内任何两条直线都有交点。点。计算机学院26计算机学院非欧几何非欧几何 15701570年，德国数学家克莱因用微分几何年，德国数学家克莱因用微分几何和射影几何的研究成果，使非欧几何在和射影几何的研究成果，使非欧几何在欧氏几何中

27、得到解释。欧氏几何中得到解释。1919世纪末，希尔伯特给出了简单而完全世纪末，希尔伯特给出了简单而完全的由二十条公理组成的公理系统几何基的由二十条公理组成的公理系统几何基础，并在实数算术理论中为欧氏几何建础，并在实数算术理论中为欧氏几何建立了一个模型。立了一个模型。计算机学院27计算机学院几何相容性几何相容性 非欧几何相容性证明非欧几何相容性证明 只能证明其相对相容性只能证明其相对相容性相对于欧氏几何的相容性，相对于欧氏几何的相容性，并不能证明非欧几何的并不能证明非欧几何的(绝对绝对)相容性相容性(即不矛盾性即不矛盾性)；如果欧氏几何没有矛盾，那末非欧几何亦没有矛盾。如果欧氏几何没有矛盾，那末

28、非欧几何亦没有矛盾。欧氏几何相容性证明欧氏几何相容性证明 借助于解析几何，一切几何命题都可以表示为代数借助于解析几何，一切几何命题都可以表示为代数(实实数论上的）命题。数论上的）命题。如果欧氏几何出现矛盾，那末表述为代数命题以后，也如果欧氏几何出现矛盾，那末表述为代数命题以后，也将得出两条互相矛盾的（实数的将得出两条互相矛盾的（实数的)代数定理，即实数的代数定理，即实数的代数也就出现矛盾了。代数也就出现矛盾了。欧氏几何相对于欧氏几何相对于(实数实数)代数的相容性。代数的相容性。计算机学院28计算机学院集合论创立集合论创立康托尔创立了一门崭新的学科康托尔创立了一门崭新的学科集合论，亦称集合论，亦

29、称为古典集合论或素扑集合论。为古典集合论或素扑集合论。外延原则与概括原则外延原则与概括原则外延原则：一个集合由它的元素唯一地确定。外延原则：一个集合由它的元素唯一地确定。概括原则：每一性质概括原则：每一性质(或谓词或谓词)产生一个集合。产生一个集合。康托尔第一次科学地应用了康托尔第一次科学地应用了“一一对应一一对应”的概的概念来把握无穷集合的本质。念来把握无穷集合的本质。康托尔用康托尔用“一一对应一一对应”的概念解决了伽利略的的概念解决了伽利略的“部分等于全体部分等于全体”的怪论，揭示了无穷集合的的怪论，揭示了无穷集合的本质以及无穷与有穷的本质差别。康托尔的成本质以及无穷与有穷的本质差别。康托

30、尔的成果是人们对无穷集合认识道路上的第一块里程果是人们对无穷集合认识道路上的第一块里程碑。碑。具有伟大历史意义的证明：具有伟大历史意义的证明：关于有理数集可数性的证明关于有理数集可数性的证明关于代数数可数的证明关于代数数可数的证明关于实数集不可数的证明关于实数集不可数的证明康托尔创立的集合论是数学和数理逻辑发展史康托尔创立的集合论是数学和数理逻辑发展史上的惊天动地的伟业，开辟了崭新的数学领域上的惊天动地的伟业，开辟了崭新的数学领域，为数学奠定了初步基础。，为数学奠定了初步基础。Georg Cantor 1845-1918计算机学院29计算机学院相容性相容性实数、自然数、集合论实数、自然数、集合

31、论 狄德金狄德金(R.Dedekind)(R.Dedekind)把实数定义为有理数把实数定义为有理数的分划，实质上是有理数的的分划，实质上是有理数的(无穷无穷)集合，集合，也是自然数的也是自然数的(无穷无穷)集合。集合。康托康托(G.CantorG.Cantor)则把实数定义为正规有理则把实数定义为正规有理数无穷数列，实质上仍可以化归于自然数无穷数列，实质上仍可以化归于自然数的数的(无穷无穷)集合。集合。实数论上的命题既可表示成自然数的集实数论上的命题既可表示成自然数的集合的命题，如果实数论出现矛盾，势必合的命题，如果实数论出现矛盾，势必在自然数论和集合论上出现矛盾。实数在自然数论和集合论上出

32、现矛盾。实数论的相对相容性论的相对相容性相对于自然数论。相对于自然数论。弗雷格和狄德金等利用集合的概念而定弗雷格和狄德金等利用集合的概念而定义自然数，自然数论的相对相容性义自然数，自然数论的相对相容性相相对于集合论的相容性便得到了证明。对于集合论的相容性便得到了证明。集合论的相容性又占着中心的、关键性集合论的相容性又占着中心的、关键性的位置，是整个数学相容性的支柱。的位置，是整个数学相容性的支柱。Richard Dedekind 1831-1916计算机学院30计算机学院彭加勒宣言彭加勒宣言数学成就数学成就 19001900年在巴黎召开的数年在巴黎召开的数学大会上，大数学家彭学大会上，大数学家

33、彭加勒加勒(H.Poincare)(H.Poincare)宣称宣称“现在我们可以说，数现在我们可以说，数学完全的严格性已经达学完全的严格性已经达到了。到了。”Henri Poincar1854-1912计算机学院31计算机学院罗素悖论罗素悖论 集合论既占这么重要的位置，那么集合论具有集合论既占这么重要的位置，那么集合论具有相容性吗？相容性吗？集合悖论：集合论是自相矛盾的，没有相容性集合悖论：集合论是自相矛盾的，没有相容性的！的！罗素悖论罗素悖论(1902)(1902)“理发师悖论理发师悖论”某乡村有一位理发师，有一天他宣布：只给不某乡村有一位理发师，有一天他宣布：只给不自己刮胡子的人刮胡子。那

34、么就产生了一个问自己刮胡子的人刮胡子。那么就产生了一个问题：理发师究竟给不给自己刮胡子？题：理发师究竟给不给自己刮胡子？如果他给自己刮胡子，他就是自己刮胡子的人如果他给自己刮胡子，他就是自己刮胡子的人，按照他的原则，他又不该给自己刮胡子；如，按照他的原则，他又不该给自己刮胡子；如果他不给自己刮胡子，那么他就是不自己刮胡果他不给自己刮胡子，那么他就是不自己刮胡子的人，按照他的原则，他又应该给自己刮胡子的人，按照他的原则，他又应该给自己刮胡子。这就产生了矛盾。子。这就产生了矛盾。罗素悖论概念简单，无法质疑罗素悖论概念简单，无法质疑计算机学院32计算机学院集合论的悖论集合论的悖论 经典悖论经典悖论

35、布拉里布拉里福蒂悖论（福蒂悖论（Borali-Forti1897Borali-Forti1897）:最大序数最大序数的悖论的悖论 康托尔悖论：最大基数的悖论（康托尔悖论：最大基数的悖论（18991899）、）、罗素悖论（罗素悖论（19031903）关系悖论关系悖论 语义悖论语义悖论 古希腊古希腊-欧布理得的说谎者悖论欧布理得的说谎者悖论 罗素把各种悖论加以分析归纳以后，认为罗素把各种悖论加以分析归纳以后，认为“一切一切悖论悖论都有一个公共特征，即自己引证自己，都有一个公共特征，即自己引证自己，或自反性或自反性”计算机学院33计算机学院公理集合论的建立公理集合论的建立 在在19081908年，策

36、梅罗发表论文年，策梅罗发表论文集合论基础研究集合论基础研究，这标志，这标志着公理集合论的建立。着公理集合论的建立。外延性公理、初等集合公理、分离公理、幂集公理、并集公理、选外延性公理、初等集合公理、分离公理、幂集公理、并集公理、选择公理择公理 l922l922年年8 8月，著名的挪威数学家斯科伦月，著名的挪威数学家斯科伦(T.Skolem(T.Skolem）在第五届）在第五届斯堪的纳维亚数学家大会上发表了斯堪的纳维亚数学家大会上发表了对公理集合论的一些对公理集合论的一些评论评论的讲演。他首先提到数理逻辑的五种运算的讲演。他首先提到数理逻辑的五种运算(采用了施采用了施罗德的记法罗德的记法)合取、

37、析取、否定、全称量词、存在量词合取、析取、否定、全称量词、存在量词 策梅罗一弗兰克尔系统记为策梅罗一弗兰克尔系统记为ZFZF系统系统 外延性公理、无序对公理、空集公理、替换公理模式、分离公理模外延性公理、无序对公理、空集公理、替换公理模式、分离公理模式、幂集公理、并集公理、无穷公理、正则公理式、幂集公理、并集公理、无穷公理、正则公理 ZFCZFC系统系统 ZFZF系统系统+选择公理。选择公理。计算机学院34计算机学院集合公理系统集合公理系统 弗兰克尔弗兰克尔 Adolf Abraham Halevi Adolf Abraham Halevi FraenkelFraenkel 1891 1965

38、1891 1965 策梅罗策梅罗 Ernst Friedrich Ferdinand Ernst Friedrich Ferdinand ZermeloZermelo 1871-19531871-1953计算机学院35计算机学院公理集合论的建立公理集合论的建立 在在1923-19291923-1929年间，冯年间，冯诺诺意曼连续发表了意曼连续发表了6 6篇集合篇集合论论文。论论文。这些论文在公理集合论的这些论文在公理集合论的发展史上具有重要意义。发展史上具有重要意义。提出了一种新的序数理论提出了一种新的序数理论 论证了超穷归纳法的定义论证了超穷归纳法的定义 推广了策梅罗和弗兰克尔推广了策梅罗和

39、弗兰克尔的集合论，构造了一个新的集合论，构造了一个新的公理集合论系统，并讨的公理集合论系统，并讨论了相对一致性的问题。论了相对一致性的问题。John von Neumann 1903-1957计算机学院36计算机学院代数学公理化代数学公理化 1919世纪世纪3030年代，伽罗瓦给出了群的概念。年代，伽罗瓦给出了群的概念。群是满足几条运算规律的一个抽象系统，它群是满足几条运算规律的一个抽象系统，它概括了向量、矩阵、变换等研究对象。概括了向量、矩阵、变换等研究对象。群的研究来源于高次方程求解的问题，但群群的研究来源于高次方程求解的问题，但群的出现，导致了现代群论，环论，域论，交的出现，导致了现代群

40、论，环论，域论，交换代数，李代数以致同调代数，代数几何等换代数，李代数以致同调代数，代数几何等等公理化代数系统的惊人发展，在理论和实等公理化代数系统的惊人发展，在理论和实践两方面部取得了极丰富的成果。践两方面部取得了极丰富的成果。计算机学院37计算机学院数理逻辑的三大流派数理逻辑的三大流派 以罗素为代表的逻辑主义派以罗素为代表的逻辑主义派 数学即逻辑，两者之间没有分界线。数学即逻辑，两者之间没有分界线。数学原理数学原理罗素推演，以表明怎样一步一步地从逻辑而过渡到数学；罗素推演，以表明怎样一步一步地从逻辑而过渡到数学；缺乏二公理：无穷公理和选择公理。缺乏二公理：无穷公理和选择公理。从逻辑过渡到数

41、学时，必须发展集合论。从逻辑过渡到数学时，必须发展集合论。以希尔柏特为代表的形式主义派以希尔柏特为代表的形式主义派 数学的真理性体现在什么地方数学的真理性体现在什么地方?逻辑规律的真理性逻辑规律的真理性 以布鲁维以布鲁维(L.E.J.Brouwer)(L.E.J.Brouwer)为代表的直觉主义派为代表的直觉主义派 强调能行性，因而对任何无穷集合都不认为是构造完成的，而是在构造强调能行性，因而对任何无穷集合都不认为是构造完成的，而是在构造中的。中的。讨论范围限于数学命题：一命题真是指已证明其真，一命题假是指证明讨论范围限于数学命题：一命题真是指已证明其真，一命题假是指证明它为假，亦即当假设它为

42、真时可导致矛盾，因此反证法是可以用的，但它为假，亦即当假设它为真时可导致矛盾，因此反证法是可以用的，但只限于用以证明否定命题。只限于用以证明否定命题。排中律断定每个命题或真或假，两者必居其一直觉主义不承认排中律排中律断定每个命题或真或假，两者必居其一直觉主义不承认排中律计算机学院38计算机学院形式公理与证明论形式公理与证明论希尔柏特（希尔柏特（D.HilbertD.Hilbert）规划）规划 直接证明数学理论的相容性直接证明数学理论的相容性 数学理论彻底公理化数学理论彻底公理化一一规定数学基本概念一一规定数学基本概念一一列出基本概念的基本性质一一列出基本概念的基本性质(作为公理作为公理)，一一

43、列出逻辑概念一一列出逻辑概念(如命题联结词和量词等如命题联结词和量词等)一一列出逻辑概念的基本性质一一列出逻辑概念的基本性质(所谓逻辑法则所谓逻辑法则)数学上的推导数学上的推导不但不必再依靠空间关系、不必再依靠直觉，而不但不必再依靠空间关系、不必再依靠直觉，而且不必再依靠逻辑法则，可以纯粹机械地推演。且不必再依靠逻辑法则，可以纯粹机械地推演。每步推演表现为由某个逻辑式子变成另一个逻辑每步推演表现为由某个逻辑式子变成另一个逻辑式子，逐步演算，便能够由公理出发，最后达到式子，逐步演算，便能够由公理出发，最后达到定理即数学的推演表现为一系列逻辑式子的演定理即数学的推演表现为一系列逻辑式子的演变。变。

44、证明论的数学基础是形式公理学证明论的数学基础是形式公理学证明数学理论的相容性，那便等于要求证明，在数学证明数学理论的相容性，那便等于要求证明，在数学的推导中，只要从公理出发，绝不可能导出两个互相的推导中，只要从公理出发，绝不可能导出两个互相反对的矛盾命题。反对的矛盾命题。希尔伯特希尔伯特l899l899年的年的几何基础几何基础是形式公理学的奠基是形式公理学的奠基著作，它不但给出了欧氏几何的一个形式公理系统，著作，它不但给出了欧氏几何的一个形式公理系统，而丛具体地解决了公理方法的一些逻辑理论问题。而丛具体地解决了公理方法的一些逻辑理论问题。David Hilbert 1826-1943计算机学院

45、39计算机学院直觉主义逻辑直觉主义逻辑 Luitzen Egbertus Jan BrouwerLuitzen Egbertus Jan Brouwer 1881 1881 1966 1966 布鲁维布鲁维计算机学院40计算机学院塔尔斯基的语义学塔尔斯基的语义学 在在19311931年，塔斯基年，塔斯基(ATarski)(ATarski)发表发表了论文了论文形式语言中真概念形式语言中真概念,提提出了形式系统真理论，开拓了逻出了形式系统真理论，开拓了逻辑语义学这一重要领域；辑语义学这一重要领域；塔尔斯基以现代逻辑为手段，用塔尔斯基以现代逻辑为手段，用逻辑分析和语义分析的方法，给逻辑分析和语义分析

46、的方法，给出了出了“真真”概念实质上适当、形概念实质上适当、形式上正确的定义；式上正确的定义；提出了著名的语言层次论，创建提出了著名的语言层次论，创建了现代意义上的系统的语义学；了现代意义上的系统的语义学；19541954年，塔斯基建立了模型论；年，塔斯基建立了模型论；塔尔斯基证明不可判定性的一般塔尔斯基证明不可判定性的一般方法。方法。Alfred Tarski 1902-1983计算机学院41计算机学院哥德尔哥德尔 19311931年发表了一篇论文年发表了一篇论文关于数学原理关于数学原理一书，证一书，证明数理逻辑的不完全定理明数理逻辑的不完全定理。在数理逻辑发展史上具。在数理逻辑发展史上具有

47、划时代意义。有划时代意义。哥德尔完全性定理哥德尔完全性定理 哥德尔不完全性定理哥德尔不完全性定理Kurt Gdels 1906-1978计算机学院42计算机学院哥德尔定理哥德尔定理 哥德尔利用一种所谓原始递归函数的工具哥德尔利用一种所谓原始递归函数的工具 所使用的符号与式子对应于自然数；所使用的符号与式子对应于自然数；推理过程，即式子到式子的变换，则对应于原推理过程，即式子到式子的变换，则对应于原始递归函数始递归函数(它是数到数的变换）；它是数到数的变换）；性质能够在自然数中反映出来，元定理也都可性质能够在自然数中反映出来，元定理也都可以表示为自然数论的定理。以表示为自然数论的定理。哥德尔不完

48、全性定理哥德尔不完全性定理 如果公理包括有自然数理论为其一部分，那末如果公理包括有自然数理论为其一部分，那末可以找到一个式子可以找到一个式子A A，使将只要该理论是不矛，使将只要该理论是不矛盾的，那末这个式子盾的，那末这个式子A A及其否定及其否定(非非A)A)都不能在都不能在该理论中推出。这个该理论中推出。这个A A便是所谓形式不可判定便是所谓形式不可判定的语句。的语句。上述表明希尔伯特规划不可能实现。上述表明希尔伯特规划不可能实现。计算机学院43计算机学院 Stephen Cole KleeneStephen Cole Kleene 1909-19941909-1994 哥德尔哥德尔-克林

49、尼提出一克林尼提出一般递归函数般递归函数计算机学院44计算机学院能行可计算性理论能行可计算性理论 一般递归函数一般递归函数 艾尔伯朗艾尔伯朗哥德尔哥德尔克林克林 哥德尔大量使用了原始递归函数。哥德尔大量使用了原始递归函数。原始巡归函数是能行可计算的原始巡归函数是能行可计算的 证明论证明论 19361936，坚钦，坚钦(G.Gentzen)(G.Gentzen)引用了一种超穷归引用了一种超穷归纳法而证明了不加限制的自然数论的相纳法而证明了不加限制的自然数论的相容性。容性。把整个理论、整个系统作为研究对象。把整个理论、整个系统作为研究对象。模型论模型论 主要是对各种数学理论系统建立模型，主要是对各

50、种数学理论系统建立模型，研究各模型之间的关系、模型与数学系研究各模型之间的关系、模型与数学系统之间的关系等等。统之间的关系等等。Gerhard.Gentzen1909-1945计算机学院45计算机学院能行可计算的函数能行可计算的函数 一般递归函数一般递归函数 作出一个形式系统，在其中作出一个形式系统，在其中利用代入及替换两个极有力利用代入及替换两个极有力的运算而能够计算该函数的的运算而能够计算该函数的值的，这个函数便叫做一船值的，这个函数便叫做一船递归函数递归函数 图灵机（图灵机（A.M.Turing）演算（演算（A.Church）函数、自变量、替换规则函数、自变量、替换规则 Church理论