Hilbert的主要贡献:
(1)对几何基础进一步作了深入的研究，于1899年发 表著名的《几何基础》一书，创立了现代公理方法. 比前人达到更高的抽象，更透彻地揭示出公理系统 内在的联系。明确提出了公理系统的三大基本要求， 即相容性、独立性和完备性。
(2)1917年以后对于数学基础的研究是他关于几何基 础研究的自然延续。他早在1904年的海德堡数学 家大会上就提出了对一般数学基础的研究题。 1917年前后，由于集合论中的悖论以及数学中的 直觉主义的发展越来越危及到古典数学的已有成 就，他被被迫重新回到数学基础的研究，提出了 著名的形式化方法。其方法的要点在对于整个数 学的逻辑系统的相容性的研究，这就是著名的证 明论或者“元数学”的研究，希望一劳永逸地解 决数学基础中的问题(注:数学直觉主义的代表人 物是德国著名数学家L.E.J.Brouwer)。
§1.2联结词
用于将原子命题联结成复合命题的运算符号。 原子命题：不能再分解的命题。 eg. P：雪是白色的。
复合命题：由原子命题符号及联结词组成的 “有意义”的命题表达式。 eg. Q：如果雪是黑色的，那么5>3。
Frege的主要贡献:
(1)开始主要从事纯逻辑研究，其总结性著作为《概 念语言》一书(1879年出版)。在其中他创造了一种 所谓的“纯粹思想的语言”，即表意的语言,使我 们可以完全精确地表达判断的概念内涵。例如：他 严格区别了命题的表达和判断；明确提出了真值蕴 含的思想,并指出了它与日常语言的区别；他还引 进了内容同一的符号；引入了量词的理论等等。 (2)给出了历史上第一个严格的现代逻辑系统。这个 系统实际上包含了作为现代数理逻辑基础的两个演 算系统------命题演算系统和一阶谓词演算系统。
华东理工大学 《离散数学》课程
任课教师：施 劲 松
Email: pineshi@
《离散数学》课程简介
《离散数学》是以研究离散量的结构和相 互间关系为主要内容的一门课程，内容涉及数 理逻辑、集合论、近世代数、图论等数学分支; 与计算机科学中的数据结构，编译原理，操作 系统，形式语言和自动机，逻辑设计，机器定 理证明等课程有密切的联系，故也被称为计算 机数学。
eg3：离散老师会在考试时出什么题目呢？ 解答：不是命题，因为它不是陈述句。 eg4：华理比北大历史悠久。
解答：是命题，真值为F。
eg5：海王星上有生物。
解答：是命题但真假待定。 eg6：我正在说谎。 解答：不是命题，是悖论。
3.命题变元（又称命题变量） 一般用P、Q、R、S、E、M表示。
4.命题指派（赋值） eg. P：雪是白色的。
• 内容很多，范围很广 • “离”：概念很多，之间联系不多 • “散”：各部分思想、方法差异很 大 • 浮于概念，不能深入 • 这么多概念到底有什么用？
各部分内容之间可以不离散 ——用课程目的统一所有内容
• 课程目的：提供计算机科学的数学基础
– 计算机科学需要各部分的内容， – 信息与计算科学的需要
下面来分别介绍上述各位数学家在数理逻 辑等方面的主要贡献。
Leibniz的主要贡献：
(1)发明了微积分;创造了一套微积分的符号系统。 (2)设计、制造了能做加、减、乘、除以及开方运算的计 算机,提出了“使所有推理过程实现机械化”这一宏伟 计划。 (3)发明了二进制系统,并用它对中国古老的八卦方圆图 给出了合理的解释(将中国古老的易图解释成0~64的二进 制数表)。 (4)提出了数理逻辑的基本思想和理论基础(手稿)。
教学资源：相关网站
• 哈佛大学/e-resources/details/d/descmath.html • 普林斯顿大学 /~bsudakov/seminar.html • 伯克利大学/~cs70/ • 肯塔基大学 /~math/Research/Margot/DM/ DiscreteMath.html • 离散数学论坛网址 /discrete • 布朗大学 /courses/cs022/ • 科罗拉多大学/education/DMP/ • 数学世界网址 /topics/DiscreteMathematics.html来自– *是G上的二元运算，也是集合
• 初等数论、组合都是关于自然数的性质
– 自然数也是集合
• 逻辑是集合
– 逻辑是形式系统，形式系统是集合
• 计算理论涉及的自动机、图灵机、文法等都是用集合定义的 • 离散数学为什么不称为集合论？ – 用不同名称强调各特殊离散数学结构的特殊性质 – 集合本身有不严谨地方
(3) 数学形式主义纲领的代表著(与 W.Ackermann以 及 P.Bernays合作): 《数理逻辑基础》(1928年出版) 《数学基础》(1934年出版) (4) 23个数学问题对二十世纪数学发展的巨大贡献。
Russel的主要贡献:
(1)受Peano的影响，深入研究了数理逻辑对数学基 础的重要作用。 (2)给出著名的Russel悖论，并提出了类型论以消除 悖论。对数学基础产生了重大影响，并对数学基 础的研究进一步做出了贡献。 (3)与A.N.Whitehead合著《数学原理》一书(共三 卷，1910 ~1913年间出版)。从较简单的逻辑系 统出发，再加上少量的非逻辑公理，推导出了很 大一部分经典数学，是数学基础研究中的一个重 大成就 (注:非逻辑公 理包括无穷公理、选择公理 和可归化公理)。
Peano的主要贡献:
(1)是符号逻辑的先驱和公理化方法的身体力行推行 人。 (2)对整数作了公理化处理，给出了著名的自然数公 理。见他的名著《算术原理新方法》一书(1889年 出版)。 (3)用公理化方法研究数学，写出了5卷本巨著《数 学公式汇编》(1895~1908年间出版)。 (4)为他的《数学公式》计划花了26年的时间进行研 究，试图从他的逻辑记号的若干基本公理出发来 建立整个的数学体系。对当代数学家以及后来著 名的Bourbaki学派产生了很大的影响。
罗素在《数学原理》中写道：
“数学可以从逻辑的规则中推导出来。”
比罗素年长18岁的法国数学家庞加莱1904年写道： “运用逻辑，我们证明；利用直觉，我们创造。”
后来他声明： “因此，如果没有直觉的浇灌，逻辑还是荒漠一片。”
Gödel的主要贡献:
(1)他是继Aristotle和Leibniz以来世界上最伟大的 数理逻辑学家。Hilbert的形式公理系统的逻辑基 础是谓词演算，当时已证明了谓词演算的可靠性 (即一致性)，然而直到1928年以前还无人能证明 谓词演算是否具有完全性。是 Gödel于1929年证 明了谓词演算也有完全性。这是对Hilbert的形式 化方案的一个有力支持。 (2)1934年他证明了形式算术系统的不完全性这一著 名的定理，从而否定了Hilbert的形式化数学方案。
• • • • • • •
集合：数组，关系数据库 图论：各种数据结构 代数结构：代数编码 组合：算法复杂性分析 逻辑：数字逻辑 初等数论：密码 计算理论：计算机不可解问题
• 图<V，G >也是集合： – 集合有序对<A, B>也是集合 • 群<G, *>也是集合
各部分内容之间可以不离散 ——用集合统一所有内容
Boole的主要贡献:
(1)实现了逻辑的数学化(用符号进行逻辑演算),创造 了逻辑的代数系统。 (2)出版了两部重要的数理逻辑奠基性的著作: 《逻辑的数学分析》(1847) 《思维规律的研究作为逻辑与概率的数学理论的 基础》(1854) 在这两部著作中,他给出了现今称为“Boole代数” 的这一在许多分支中都有重要应用价值的理论的 雏形。
1、什么是离散数学（Discrete Mathematics）？
离散数学是以研究离散量的结构和相互间关 系为主要内容的一门学科。
2、还是没怎么明白，离散数学到底有什么用？
当然，当我还在大学里时，不可能把这些点点滴滴 预先串在一起，但是这在十年后回顾，就显得非常清 楚。 我再说一次，你不能预先把点点滴滴串在一起； 唯有未来回顾时，你才会明白那些点点滴滴是如何串在 一起的。所以你得相信，你现在所体会的东西，将来多 少会连接在一块。你得信任某个东西，直觉也好，命运 也好，生命也好，或者业力。这种作法从来没让我失望， 也让我的人生整个不同起来。
逻辑：以研究人的思维形式及思维规律
为目的的一门学科。 分类 辨证逻辑
形式逻辑（类似于一门语法的工具性学科）
数理逻辑：利用数学符号来协助推理的
一门形式逻辑学。
为之做出奠基性工作的有:
莱布尼兹(Leibniz, 德 国, 1646-1716) 布 尔(Boole, 英 国, 1815-1864) 弗 雷 格(Frege, 法 国, 1848-1925) 皮 亚 诺(Peano, 意大利, 1858-1932) 希尔伯特(Hilbert, 德 国, 1862-1943) 罗 素(Russel, 英 国, 1872-1970) 哥 德 尔(Gödel, 德 国, 1906-1978) 图 灵(Turing, 英 国, 1912-1954 )等
——斯蒂夫·乔布斯 05年斯坦福大学毕业典礼上的演讲
《离散数学》教学内容
1.数理逻辑（ch1.） 2.集合、二元关系与函数 （ch3.+ch4.§1.§2） 3.图论（ch7） 4.代数系统（ch5）
本 讲 内 容
第一章
简介
§1.1 命题及其表示方法 §1.2 联结词
§1.3 命题公式与翻译
第一章：数理逻辑
推荐课外阅读书目：
§1.1 命题及其表示方法
1.命题：具有确定真值的陈述句。 2.真值：每个命题都具有的一个值。要么为真 （T，1），要么为假（F，0）。
判断下列语句是否是命题，如果是，判断真假。
eg1：这是我第一次接触《离散数学》。 解答：是命题，真值为T。
eg2： 1+11=100.
解答：不是命题，因为它的真假随着外部条 件的改变而改变。
哥德尔不完备定理