离散数学 计算机系 陈翌佳
联系方式 陈翌佳： yijia.chen@cs.sjtu.edu.cn basics.sjtu.edu.cn/~chen
教材和辅导书 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
课程说明 讲授内容： 数理逻辑 集合论 图论
数理逻辑与计算机科学 1946年，德国数学家Von Neumann提出计算机模型 计算机模型根植于数理逻辑、图林机与布尔代数。 图灵机：数字电子计算机的抽象雏形 布尔代数：设计数字电子计算机的数学工具
数理逻辑与计算机科学 计算机科学的核心算法 程序设计语言 程序设计方法学 计算复杂性理论 均涉及到数理逻辑的知识和理论
什么是数理逻辑？ 逻辑：是对人类推理过程的研究。 数理逻辑：是用数学的方法对人类推理过程作研究。 数学研究方法：使用符号
数理逻辑史 数理逻辑前史时期—古典形式逻辑时期 数理逻辑初创时期—逻辑代数时期 数理逻辑奠基时期 数理逻辑发展初期 数理逻辑现代发展时期
古典形式逻辑时期 亚里士多德 三段论 斯多阿学派的命题逻辑 中世纪的形式逻辑
逻辑代数时期 数理逻辑产生的时代背景 数理逻辑创始人—莱布尼兹(Leibniz,1646-1716) 莱布尼兹的数理逻辑思想 逻辑代数—布尔 笛卡尔 霍布斯 数理逻辑创始人—莱布尼兹(Leibniz,1646-1716) 莱布尼兹的数理逻辑思想 理性演算 普遍语言 逻辑代数—布尔
数理逻辑奠基时期 逻辑演算的建立和发展——Frege（1848-1925） Peano的符号体系 罗素（B.Russell, 1872-1970）的逻辑演算和罗素悖论 逻辑主义学派（Russell） 直觉主义学派（Brower） 形式主义学派（Hilbert）
数理逻辑发展初期 （20世纪三十年代） Gödel (1906-1978) 完全性定理 不完全性定理 连续统假设的一致性
数理逻辑现代发展时期 （20世纪四十年代~） 各种非经典逻辑演算和四论： 集合论（公理集合论） 模型论（形式语言语法与语义间的关系） 递归论（可计算性和可判定性） 证明论（数学本身的无矛盾性）