上海交通大学：《离散数学》课程教学资源（PPT课件）Introduction（主讲：陈玉泉）

离散数学 计算机系 陈玉泉

离散数学 计算机系 陈玉泉

教材和辅导书 1、 教材： 数理逻辑与集合论（第二版）：石纯一，清华大学出版社。 图论与代数结构：戴一奇，清华大学出版社。 2、辅导书（数理逻辑部分）： 数理逻辑：莫绍揆，科学文献出版社。 数理逻辑教程：莫绍揆，华中工学院出版社。 集论与逻辑：沈恩绍，科学出版社。 A Mathematical Introduction to Logic,2nd.Ed, H.Enderton,Academic Press Logic for Applications,2nd ed.,A.Nerode,Springer 离散数学（第4版），Richard Johnsonbaugh,电子工业出版 社

教材和辅导书 1、教材： 数理逻辑与集合论（第二版）：石纯一，清华大学出版社。 图论与代数结构：戴一奇，清华大学出版社。 2、辅导书（数理逻辑部分）： 数理逻辑：莫绍揆，科学文献出版社。 数理逻辑教程：莫绍揆，华中工学院出版社。 集论与逻辑：沈恩绍，科学出版社。 A Mathematical Introduction to Logic, 2nd. Ed, H.Enderton, Academic Press Logic for Applications, 2nd ed., A. Nerode, Springer 离散数学（第4版），Richard Johnsonbaugh，电子工业出版 社

课程说明 讲授内容： ·数理逻辑 ·集合论 ·图论 ■作业： ·每周二交作业 4

4 课程说明 n 讲授内容： n 数理逻辑 n 集合论 n 图论 n 作业： n 每周二交作业

数理逻辑与计算机科学 1946年，德国数学家Von Neumann提 出计算机模型 ■计算机模型根植于数理逻辑、图林机与 布尔代数。 ■Turing机：数字电子计算机的抽象雏形 布尔代数：设计数字电子计算机的数学 工具 5

5 数理逻辑与计算机科学 n 1946年，德国数学家Von Neumann提 出计算机模型 n 计算机模型根植于数理逻辑、图林机与 布尔代数。 n Turing机：数字电子计算机的抽象雏形 n 布尔代数：设计数字电子计算机的数学 工具

数理逻辑与计算机科学 计算机科学的核心算法 ■程序设计语言 ■程序设计方法学 ■计算复杂性理论 均涉及到数理逻辑的知识和理论 6

6 数理逻辑与计算机科学 n 计算机科学的核心算法 n 程序设计语言 n 程序设计方法学 n 计算复杂性理论 均涉及到数理逻辑的知识和理论

E.W.Di jkstra 我现在年纪大了，搞了这么多年软件， 错误不知犯了多少，现在觉悟了。我想， 假如我早年在数理逻辑上好好下点功夫 的话，我就不会犯这么多的错误，不少 东西逻辑学家早就说了，可我不知道 要是我能年轻二十岁的话，就要回去学 逻辑。 7

7 E. W. Dijkstra n 我现在年纪大了，搞了这么多年软件， 错误不知犯了多少，现在觉悟了。我想， 假如我早年在数理逻辑上好好下点功夫 的话，我就不会犯这么多的错误，不少 东西逻辑学家早就说了，可我不知道。 要是我能年轻二十岁的话，就要回去学 逻辑

什么是数理逻辑？ 逻辑：是对人类推理过程的研究。 数理逻辑：是用数学的方法对人类推理 过程作研究。 ■数学研究方法：使用符号 8

8 什么是数理逻辑？ n 逻辑：是对人类推理过程的研究。 n 数理逻辑：是用数学的方法对人类推理 过程作研究。 n 数学研究方法：使用符号

数理逻辑史 数理逻辑前史时期一古典形式逻辑时 期 ■数理逻辑初创时期一 逻辑代数时期 ■数理逻辑奠基时期 ■数理逻辑发展初期 数理逻辑现代发展时期 9

9 数理逻辑史 n 数理逻辑前史时期——古典形式逻辑时 期 n 数理逻辑初创时期——逻辑代数时期 n 数理逻辑奠基时期 n 数理逻辑发展初期 n 数理逻辑现代发展时期

古典形式逻辑时期 亚里士多德三段论 ■斯多阿学派的命题逻辑 ■中世纪的形式逻辑 10

10 古典形式逻辑时期 n 亚里士多德 三段论 n 斯多阿学派的命题逻辑 n 中世纪的形式逻辑

逻辑代数时期 数理逻辑产生的时代背景 ■笛卡尔 ■霍布斯 数理逻辑创始人一莱布尼兹(Leibniz,1646- 1716,德) ■莱布尼兹的数理逻辑思想 理性演算 ·普遍语言 ■逻辑代数一布尔 11

11 逻辑代数时期 n 数理逻辑产生的时代背景 n 笛卡尔 n 霍布斯 n 数理逻辑创始人——莱布尼兹(Leibniz,1646- 1716,德) n 莱布尼兹的数理逻辑思想 n 理性演算 n 普遍语言 n 逻辑代数——布尔