离散数学01课件.pptVIP

离 散 数 学 离散数学 教材与参考书 屈婉玲，耿素云，张立昂，离散数学及其应用，高等教育出版社，2011 屈婉玲，耿素云，张立昂，离散数学，高等教育出版社，2008 耿素云，屈婉玲，王捍贫，离散数学教程，北京大学出版社，2002 屈婉玲，耿素云，张立昂，离散数学学习指导与习题解析，高等教育出版社，2008 耿素云，屈婉玲，王捍贫，刘田，离散数学习题解析，北京大学出版社，2008 要求 不得旷课、迟到和早退 按时做、交作业。不准抄袭，不要突击 课前预习，课后复习与总结 成绩评定： 平时：20%（作业、出勤） 期末：80% 现代数学的特点 现代数学的特点(续) 注重公理化体系的建立和结构分析 公理化体系: 欧几里得的平面几何公理 集合论的公理化体系 结构分析: 集合 + 对应规则 + 公理 = 结构 实例: 序结构(偏序集) 代数结构(群, 环, 域, 格, 线性空间) 拓扑结构 测度结构 上述结构的复合结构(有序距离线性空间)等 现代数学的特点(续) 学科的交叉和领域的交叉 数学学科的内部 泛函分析, 代数图论 确定性和非确定性的交叉 随机微分方程 和其他的应用领域交叉 模糊数学, 运筹学 ACM CC2004的核心课程 离散数学的主要内容 研究对象：离散个体及其结构 研究思想：以集合和映射为工具、体现公理化和结构的思想 研究内容：包含不同数学分支，模块化结构 数理逻辑：推理、形式化方法 集合论：离散结构的表示、描述工具 代数结构：离散结构的代数模型 图论：离散结构的关系模型 组合数学：离散结构存在性、计数、枚举、优化、设计 CC-CS2005离散结构的主要模块 离散数学与计算机科学的关系 数理逻辑 人工智能、程序正确性证明及验证 集合论 关系数据库模型 图论 数据结构、数据库模型、网络模型等 代数结构 软件规约、形式语义、编译系统 编码理论、密码学、数据仓库 组合数学 算法设计与分析、编码理论、容错 算法的效率分析 例 Hanoi塔问题 移动n个盘子的总次数为T(n). 因此得到递推方程 T(n) = 2T(n?1) +1. 初值是 T(1)=1 可证明解是 T(n)=2n?1 数据仓库中的视图格 视图的格结构 进程的资源共享模型 学习离散数学的目的 掌握离散结构的描述语言和分析方法 为其它专业课程的学习打基础 为掌握软硬件模型的建模与分析方法准备必要的数学工具 学习现代数学的思想 培养分析问题解决问题的能力 第一部分 数理逻辑 什么是数理逻辑 字面含义：数学理论的逻辑。逻辑是研究演绎（推理）规律的学科。 广义理解：用数学方法研究演绎规律的学科。 狭义理解：用数学方法研究数学中演绎规律和数学基础的学科。 研究对象：推理过程的正确性标准。是数学的一个分支。又称符号逻辑等。 简单历史——三个阶段（一） 1. 初始阶段：1660年代—19世纪末 将数学应用于逻辑 ?? Aristotle(前384-前322)：形式逻辑(主词和谓词逻辑)。 ?? Leibniz(1646-1716)：建立直观而又精确的思维演算。 遇有争论，双方可以拿起笔来说：让我们来算一下。 ?? George Boole(1815-1864): 逻辑代数。 ?? De Morgan(1806-1871): 关系逻辑。 [1] 王宪钧，数理逻辑引论，北京大学出版社，1982。 简单历史——三个阶段（二） 2. 过度阶段：19世纪末— 1940前后 逻辑应用于数学 ?? 非欧几何与公理化方法。 ?? 微积分与实数理论，Piano算术。 ?? 集合论与数学基础(1900年世界数学家大会) ?? 悖论与第三次数学危机，Hilbert计划(1922)。 （第一次：勾股定理，无理数的发现） （第二次：穷小量是不是零？） 简单历史——三个阶段（三） 成熟阶段：1930s — 1970年 成为数学的独立分支 G?del完全性定理和不完全性定理(1931)。 四个分支： 公理集合论：大基数，连续统问题 递归论（可计算性理论）：Turing机，不可解性 模型论：实数的非标准模型 证明论：超穷归纳法, Gentzen的数论和谐性证明 特点与方法 ?? 公理化与形式化方法. ?? 特制的符号语言. 与计算机科学的联系 计算理论：可计算性，Turing机，形式语言，自动机，计算复杂性。 程序语义与验证技术. Intel bug: 5亿美元。 程序的自动生成与转换。 布尔电路：香农Shannon是第一人。 SQL: 本质上等价于一阶逻辑。 Prolog语言——以逻辑演算为基础 LISP语言——以λ演算为基础 人工智能：非单调推理，缺省推理。 信息安全等 …… Dijkstra的话 我现在年纪大了，搞