第1讲 集合基本概念.ppt

什么是离散数学？ 离散数学是研究离散量的结构及其相互关系 的一门学科，它与当今计算机所处理的对象 相一致。 注：传统的分析为中心的数学所研究的对象大部分是连续的，所以微 分积分成为基本的运算。随着计算机科学的发展，人们解决具体 问题的能力越来越强，而很多具体问题所研究的对象是离散的， 所以离散数学成为利用计算机解决问题的一个重要理论基础。 有关计算机与现代数学发展可阅读 李文林 《数学史教程》325-338. 通过前面的例子，以及后面的学习，我们可以看到，很多生活中 的问题，都可以利用离散数学的知识来解决。 为什么要学习离散数学？ 是计算机及相关专业的核心课程，计算机专业基础课程。 为后继课程如数据结构、操作系统、计算机组成原理、 数据库原理、算法设计与分析、编译原理、计算机网络及人工智能的学习提供必要的学习基础。 培养抽象思维能力和严密的逻辑推理能力，为进一步学习打下坚实基础。 离散数学主要内容  离散数学 邓辉文编著 清华大学出版社 ISBN 7-302-13711-0/TP·8265 考核办法及答疑时间 成绩 考试成绩80%+平时成绩20% 答疑时间：每周二下午，1：00~3：00 地点：教3楼 305 第一章 集合、映射与运算 集合是现代数学的最基本概念. 映射又称为函数, 它是现代数学的基本概念, 可以借助于集合下定义. 运算本质上是映射, 但其研究有其特殊性. 集合、映射、运算及关系(第二章)是贯穿于本书的一条主线. 集合通常用大写字母A,B,C,D等表示。 常见的集合：N、Z、Q、R、C 给定一个集合，比如A，对于全集中的任意元素x，有且只有下述两种情形出现： 1）若x是集合A中的元素,则称x属于A，记为x?A； 2）否则x不是集合A中的元素，称x不属于A，记为x?A. 例：A = {红球,白球,兰球} P(A)= { ?, {红球}, {白球}, {兰球}, {红球, 白球}, {红球, 兰球}, {白球, 兰球}, {红球, 白球, 兰球} } |P(A)| = 8 (1)加法原理：一步做,做一件事，完成它可以有n类办法，在第一类办法中有m_1种不同的方法，在第二类办法中有m_2种不同的方法，……，在第n类办法中有m_n种不同的方法，那么完成这件事共有N＝m_1＋m_2＋m_3＋…＋m_n种不同方法．  (2)乘法原理：几步做,做一件事，完成它需要分成n个步骤，做第一步有m_1种不同的方法，做第二步有m_2种不同的方法，……，做第n步有m_n种不同的方法，那么完成这件事共有 N＝m_1×m_2×m_3×…×m_n种不同的方法． * * 离 散 数 学 中国地质大学(北京) 信息工程学院 李明霞 几个问题 问题一： 对100名学生进行调查，得到如下结果：34人爱好音乐，24人爱好美术，48人爱好舞蹈，13人既爱好音乐又爱好舞蹈，14人既爱好音乐又爱好美术，15人既爱好美术又爱好舞蹈，有25人这三种爱好都没有，问这三种爱好都有的学生人数是多少？ 问题二： 一个农夫要用船把狼、羊、和一箱卷心菜运到河对面。但是，一次只能运一样，而且当农夫不在时，狼会吃羊，羊也会吃卷心菜，请问应该怎样运？ 问题三： 某件事情是甲、乙、丙、丁四个人中的某个人干的。询问四人回答如下： 甲说是丙干的； 乙说我没干； 丙说甲讲的不符合事实； 丁说是甲干的。 如果有三个人讲真话，有一个人在说谎。问这件事情到底是谁干的? 1.集合、映射与运算；2.关系 3.命题逻辑 5.群、环和域 7.图论 4.谓词逻辑 6.格与布尔代数 8.特殊的图 二 离散数学与其它专业课的关系 离散数学 对应专业课程 集合 形式语言、编译技术、计算复杂性、 软件形式化方法 关系 关系数据库 函数 算法设计与分析、软件形式化方法 图 数据结构、网络技术 算法设计与分析、人工智能 离散数学 对应专业课程 树 数据结构、网络技术、 算法设计与分析 计数技术 算法设计与分析、计算复杂性、 编码 数理逻辑 人工智能、形式语义学 代数系统 数字电路设计、密码学、 软件形式化方法 教材 基