复旦大学计算机院赵鸣离散数学中文课件.ppt

离散数学是计算机学科的重要数学基础课之一 离散数学是以离散(即非连续)对象的数量和空间关系为研究内容的数学若干个分支的总称。 包括数理逻辑、近世代数、古典概率、组合学、图论、集合论、数论、自动机和形式语言、可计算性和可判定性、离散几何等。 18世纪以前, 数学基本上是研究离散对象的数量和空间关系的科学, 之后,因天文学,物理学的发展,如行星轨道,牛顿三大力学定律等研究,极大地推动了连续数学(以微积分,数学物理方程, 实、复变函数论为代表)的发展。 离散对象的研究则处于停滞状态 20世纪30年代, 图灵提出计算机的理论模型——图灵机。 这种模型早于实际制造计算机十多年, 现实的计算机的计算能力, 本质上和图灵机的计算能力一样。 这是理论指导实际的典型范例。 由于在计算机内,机器字长总是有限的, 它代表离散的数或其它离散对象。 因此随着计算机科学和技术的迅猛发展,离散数学就显得重要。 离散数学是学习数据结构与算法、数据库、编译原理、算法设计与分析、计算机网络等课程的主要基础 对开发大型软件、研究信息安全和密码学、开展计算机理论研究以及开发新型计算机都提供了不可缺少的基础知识。 本课程是离散数学的一部分,包括： 集合论 组合学 图论 Ⅰ集合论初步 集合论是现代数学的基础,它已深入到各种科学和技术领域中,被广泛应用到数学和计算机科学的各分支中去。在开关理论、形式语言、数据库等领域得到了卓有成效的应用。 集合论的创始人康托尔(Cantor,1845--1918),德国著名数学家 在1874年,发表了题为“关于所有实代数数所成集合的一个性质”的论文，开创了现代集合论的研究，为现代数学奠定了基础. 集合理论中出现了悖论。 为了解决集合论的悖论, 上世纪初开始了集合论公理学方向的研究,它是数理逻辑的中心问题之一。 从集合的基本概念和例子着手,对关系、函数、基数等进行讨论,并简单介绍集合论的悖论。 第一章 集合的基本概念 1.1 集合的表示 所谓集合是指具有共同性质的一些东西(对象)汇集成一个整体。 用大写英文字母表示,例如S,A等。 构成一个集合中的那些对象称为该集合的元素,用小写英文字母或数字等表示。 a?A表示a是集合A的元素。 a?A表示a不是集合A的元素。 例：所有整数全体构成的集合，记为Z, 则3?Z,-8?Z,6.5?Z, 今后我们将用 I或Z表示整数集; I+(Z+)表示正整数集; Q表示有理数集; Q+表示正有理数集; Q-表示负有理数集; R表示实数集; R+表示正实数集。 集合中的元素可以是具体的事物,也可以是抽象的符号 一、集合的表示方法 (1)列举法：列出集合中的所有元素来表示一个集合。 例：集合A的元素为1, 3, 5, 7, 9, 则A可表示为A={1, 3, 5, 7, 9}。 B={x1,x2,x3}也是采用了列举法。 (2)特性刻画法(描述法)：描述集合中元素具有共同性质的方法来表示某个集合。 我们用P(A)表示元素a满足特性P，则A={a|P(a)}就表示集合A是所有使P(a)成立的元素所构成的集合。 例：C={x|x=y3,y?Z+} D={x|-1x2} E={x|x为年龄小于20岁的人} 列举法用于元素个数较少的情况, 描述法用于元素个数较多(或无限),且各对象具有共同性质的情况 (3)递归定义法：通过某规则的计算来定义集合中的元素,在此情况下的集合常称为递归定义的集合。我们将在第四章对此方法作进一步介绍。 如果一个集合元素个数有限，则称该集合为有限集，否则称为无限集。 前面例子中的集合C、D是无限集，而A、B、E则是有限集。 有限集A的元素个数称为集合A的基数,记为|A|。 A={x|x是大于1小于6的质数}, |A|=3。 如果一个集合不含有任何元素,称为空集,记为?或{ }。 例：A={x|x2+1=0,x为实数}是空集?,|A|=|?|=0. 但{?}不是空集，它是以?为元素的集合 在集合中要注意， (1) 集合中的元素之间的次序是无关紧要的 例:{a, b, c}与{b, a, c}是完全相同的集合。 (2)集合中的元素是不能重复出现的 即{a,b,c,b,d}是不允许出现的 一个集合可以是其他集合的元素。 例:S={{a,b},{a,b,c},{d,e}} {a,b},{a,b,c},{d,e}都是集合S的元素。 {a,b,c}本身又是集合，其元素是a,b,c。 a,b,c都不是集合S的元素。 象这种以集合作为元素所组成的集合称为集合族。 S={?,{?}}的元素是?,{?}。 1.2 集合的子集 用平面上封闭曲线包围点集的图形来表示集合,该图形称为文氏图(Venn Diagrams)。 文氏图还能表示集合之间的相互关系,集合A中元素全部是集合B的元素,可用下图表示: 定