离散数学 计算机系 陈翌佳.

Presentation on theme: "离散数学 计算机系 陈翌佳."— Presentation transcript:

1 离散数学 计算机系 陈翌佳

2 联系方式 陈翌佳： basics.sjtu.edu.cn/~chen

3 教材和辅导书 1、教材： 数理逻辑与集合论（第二版）：石纯一，等 图论与代数结构：戴一奇，等，清华大学出版社。 2、辅导书（数理逻辑部分）：
集论与逻辑：沈恩绍，科学出版社。 A Mathematical Introduction to Logic, H.Enderton, Academic Press Logic for Applications, A. Nerode, Springer Mathematical Logic, H.-D.Ebbinghaus and J. Flum, Springer

4 课程说明 讲授内容： 数理逻辑 集合论 图论

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

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

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

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

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

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

11 数理逻辑奠基时期 逻辑演算的建立和发展——Frege（1848-1925） Peano的符号体系
罗素（B.Russell, ）的逻辑演算和罗素悖论 逻辑主义学派（Russell） 直觉主义学派（Brower） 形式主义学派（Hilbert）

12 数理逻辑发展初期 （20世纪三十年代） Gödel ( ) 完全性定理 不完全性定理 连续统假设的一致性

13 数理逻辑现代发展时期 （20世纪四十年代~） 各种非经典逻辑演算和四论： 集合论（公理集合论） 模型论（形式语言语法与语义间的关系）
递归论（可计算性和可判定性） 证明论（数学本身的无矛盾性）