上海交通大学：《离散数学》课程教学资源（PPT课件讲稿）第一部分 数理逻辑（主讲：董笑菊）

离散数学 董笑菊 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 第一部分 数理逻辑  逻辑学 研究人的思维形式和规律的科学．由于研究的对象 和方法各有侧重而又分为形式逻辑、辩证逻辑和数 理逻辑  数理逻辑 用数学方法研究推理，是研究推理中前题和结论之 间的形式关系的科学 ◼ 所谓推理就是由一个或几个判断推出一个新判断的思维 形式 ◼ 这里所说的数学方法就是建立一套表意符号体系，对具 体事物进行抽象的形式研究的方法. 因此, 数理逻辑又称 符号逻辑