离散数学 董笑菊 BASICS计算机科学与工程系 上海交通大学 xudong@sjtu.edu.cn电院3-327 TeB34205060EXT602 http://basics.sjtu.educn/nxiaoju/Dm
离散数学 董笑菊 BASICS,计算机科学与工程系 上海交通大学 xjdong@sjtu.edu.cn 电院3-327 Tel:34205060 EXT 602 http://basics.sjtu.edu.cn/~xiaoju/dm
离散数学 离散数学是 现代数学的一个重要分支 计算机科学与技术的理论基础 是计算机应用必不可少的工具,所以又称为计 算机数学
2 离散数学 ➢ 离散数学是： ➢ 现代数学的一个重要分支 ➢ 计算机科学与技术的理论基础 ➢ 是计算机应用必不可少的工具，所以又称为计 算机数学
数理逻辑 电灯开关 两个开关A、B同时控制一盏灯C (1)只要有一个开关处于开启状态灯就会亮 (2)只有两个开关之一处于开启状态灯才亮 请具体列出灯c在开关A和B处于什么情况下 会亮
数理逻辑 电灯开关 两个开关A、B同时控制一盏灯C, (1)只要有一个开关处于开启状态灯就会亮 (2)只有两个开关之一处于开启状态灯才亮 请具体列出灯C在开关A和B处于什么情况下 会亮
集合 口自然数集合 口实数集合 口集合的运算 口幻方、数独问题( Magic square、 Sudoku) 816 357 492 785
集合 自然数集合 实数集合 集合的运算 幻方、数独问题(Magic Square、Sudoku) 8 1 6 3 5 7 4 9 2
图论 口人狼羊菜过河 有一个人带着一只狼,一只羊,一筐菜过河 当这个人在狼和羊身边时,狼不敢吃羊,羊 也不敢吃菜,但是当人不在它们身边时,羊 就可能把羊吃掉,羊也可能把菜吃掉,现在, 渡船时只有一只船,能承载一个人及一件东 西或物品,问怎样渡才能使人.狼羊菜安全 过河?
图论 人狼羊菜过河 有一个人带着一只狼，一只羊，一筐菜过河， 当这个人在狼和羊身边时，狼不敢吃羊，羊 也不敢吃菜，但是当人不在它们身边时，羊 就可能把羊吃掉，羊也可能把菜吃掉，现在， 渡船时只有一只船，能承载一个人及一件东 西或物品，问怎样渡才能使人.狼.羊.菜安全 过河？
离散数学 事实上,从计算机产生到其发展每一步都离不开数学 >1936年A英国数学家周灵 A.M. Turing)发表了著名论文 理想计算机”,从而给出了计算机的理论 導“6逶菁毫蓉騫粑紅义造開"經 (Electronic Discrete Variable Automatic Computer) 为什么离散数学对计算机科学来说如此重要? 花 电子计篡机是一个离散结构,它只能处理离散的或离散 的数量关系 关系建立起来的数学模 陪散化,从而可由计 理
8 离散数学 ➢ 事实上，从计算机产生到其发展每一步都离不开数学 ➢ 1936年，英国数学家图灵(A.M.Turing)发表了著名论文 “理想计算机” ，从而给出了计算机的理论模型 ➢ 1946年在著名数学家冯·诺依曼(J.Von Neumann)的领 导下，制造了世界上第一台现代意义的通用计算机EDVAC (Electronic Discrete Variable Automatic Computer) ➢ ．．． ➢ 为什么离散数学对计算机科学来说如此重要？ ➢ 数字电子计算机是一个离散结构，它只能处理离散的或离散 化了的数量关系 ➢ 无论计算机科学本身，还是与计算机科学及其应用密切相关 的现代科学研究领域，都面临着如何对离散结构建立相应的 数学模型；又如何将已用连续数量关系建立起来的数学模型 离散化，从而可由计算机加以处理
离散数学与计算机科学的关系 口数理逻辑:人工智能、程序正确性证明、 程序验证等 口集合论:关系数据库模型等 口图论 数据结构、数据库模型 网络模型等 口代数结构:软件规范、形式语义、编译系统、 编码理论、密码学、数据仓库等 口组合数学:算法分析与设计、编码理论、容错等
9 离散数学与计算机科学的关系 数理逻辑：人工智能、程序正确性证明、 程序验证等 集合论： 关系数据库模型等 图论： 数据结构、数据库模型、 网络模型等 代数结构：软件规范、形式语义、编译系统、 编码理论、密码学、数据仓库等 组合数学：算法分析与设计、编码理论、容错等
离散数学课程说明 口研究对象--离散个体及其结构 口研究思想-以集合和映射为工具、体现公理化和结构的思想 口研究内容-·包含不同的数学分支,模块化结构 数理逻辑:推理、形式化方法 集合论:离散结构的表示、描述工具 图论:离散结构的关系模型 代数结构:离散结构的代数模型 组合数学:离散结构的存在性、计数、枚举、优化、设计 离散概率(概率统计课程) 10
10 离散数学课程说明 研究对象----离散个体及其结构 研究思想----以集合和映射为工具、体现公理化和结构的思想 研究内容----包含不同的数学分支，模块化结构 ◼ 数理逻辑：推理、形式化方法 ◼ 集合论：离散结构的表示、描述工具 ◼ 图论：离散结构的关系模型 ◼ 代数结构：离散结构的代数模型 ◼ 组合数学：离散结构的存在性、计数、枚举、优化、设计 ◼ 离散概率（概率统计课程）
希望 口掌握离散数学的各个分支的基本概念、基本理 论和基本方法 口提高概括抽象能力、逻辑思维能力、归纳构造 能力 口培养严谨、完整、规范的科学态度 12
12 希望 掌握离散数学的各个分支的基本概念、基本理 论和基本方法 提高概括抽象能力、逻辑思维能力、归纳构造 能力 培养严谨、完整、规范的科学态度
第一部分数理逻辑 口逻辑学 研究人的思维形式和规律的科学.由于研究的对象 和方法各有侧重而又分为形式逻辑、辮证逻辑和数 理逻辑 口数理逻辑 用数学方法研究推理,是研究推理中前题和结论之 问的形式关系的科学 所谓推理就是由一个或几个判断推出一个新判断的思维 形式 这里所说的数学方法就是建立一套表意符号体系,对具 体事物进行抽象的形式研究的方法。因此数理逻辑又称 符号逻辑 15
15 第一部分 数理逻辑 逻辑学 研究人的思维形式和规律的科学．由于研究的对象 和方法各有侧重而又分为形式逻辑、辩证逻辑和数 理逻辑 数理逻辑 用数学方法研究推理，是研究推理中前题和结论之 间的形式关系的科学 ◼ 所谓推理就是由一个或几个判断推出一个新判断的思维 形式 ◼ 这里所说的数学方法就是建立一套表意符号体系，对具 体事物进行抽象的形式研究的方法. 因此, 数理逻辑又称 符号逻辑