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

离散数学是计算机学科的重要数学基础 课之一 离散数学是以离散(即非连续)对象的数 量和空间关系为研究内容的数学若干个 分支的总称。 包括数理逻辑、近世代数、古典概率、 组合学、图论、集合论、数论、自动机 和形式语言、可计算性和可判定性、离 散几何等。 18世纪以前, 数学基本上是研究离散对 象的数量和空间关系的科学, 之后,因天文学,物理学的发展,如行星轨 道,牛顿三大力学定律等研究,极大地推 动了连续数学(以微积分,数学物理方程, 实、复变函数论为代表)的发展。 离散对象的研究则处于停滞状态 20世纪30年代, 图灵提出计算机的理论模 型图灵机。 这种模型早于实际制造计算机十多年, 现 实的计算机的计算能力, 本质上和图灵机 的计算能力一样。 这是理论指导实际的典型范例。 由于在计算机内,机器字长总是有限的, 它 代表离散的数或其它离散对象。 因此随着计算机科学和技术的迅猛发展, 离散数学就显得重要。 离散数学是学习数据结构与算法、数据 库、编译原理、算法设计与分析、计算 机网络等课程的主要基础 对开发大型软件、研究信息安全和密码 学、开展计算机理论研究以及开发新型 计算机都提供了不可缺少的基础知识。 本课程是离散数学的一部分,包括： 集合论 组合学 图论 集合论初步 集合论是现代数学的基础,它已深入到各种科 学和技术领域中,被广泛应用到数学和计算机 科学的各分支中去。在开关理论、形式语言 、数据库等领域得到了卓有成效的应用。 集合论的创始人康托尔(Cantor,1845-1918), 德国著名数学家 在1874年,发表了题为“关于所有实代数数所 成集合的一个性质”的论文，开创了现代集合 论的研究，为现代数学奠定了基础. 集合理论中出现了悖论。 为了解决集合论的悖论, 上世纪初开始 了集合论公理学方向的研究,它是数理逻 辑的中心问题之一。 从集合的基本概念和例子着手,对关系、 函数、基数等进行讨论,并简单介绍集合 论的悖论。 第一章 集合的基本概念 1.1 集合的表示 所谓集合是指具有共同性质的一些东西(对象) 汇集成一个整体。 用大写英文字母表示,例如S,A等。 构成一个集合中的那些对象称为该集合的元素, 用小写英文字母或数字等表示。 aA表示a是集合A的元素。 aA表示a不是集合A的元素。 例：所有整数全体构成的集合，记为Z, 则3Z,-8Z,6.5Z, 今后我们将用 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,yZ+ D=x|-10, n个对象的序列形如 a1,a2,an组成一组称为有序n元组, 记为 (a1,a2,an),其中ai称为第i个分量。两个有 序n元组相等当且仅当它们的每个对应分 量相等。 定义1.8：设A和B是两个集合, 定义A与B的 笛卡尔积为AB=(a, b)| aA且bB,又称 AB为A与B的直积。 例:设A=1,2, B=x,y,C=a,b,c,则 AB=(1,x),(1,y),(2,x),(2,y); BA=(x,1),(x,2),(y,1),(y,2); BAAB 由此可知A与B的直积是不满足交换律的。 AC=(1,a),(1,b),(1,c),(2,a),(2,b),(2,c); AA=(1,1),(1,2),(2,1),(2,2)。 A=A= 定义1.9:设A1,A2,An是任意n个集合, 定义笛 卡尔积A1A2An为 (a1,a2,an)|aiAi,i=1,2,n。 例:ABC=(1,x,a),(1,x,b),(1,x,c),(1,y,a),(1,y,b), (1,y,c),(2,x,a), (2,x,b),(2,x,c),(2,y,a),(2,y,b),(2,y,c)。 A=1,2, B=x,y,C=a,b,c 若对所有i,Ai=A, 则A1A2An记为An。 例：A=a,b,c为学生集合，B=x,y,z,w为课程集 合，则笛卡儿积AB就是学生与课程所组成的有 序对全体。 AB=(a,x),(a,y),(a,z),(a,w),(b,x),(b,y),(b,z), (b,w),(c,x),(c,y),(c,z),(c,w) 若(a,x)表示学生a选修课程x，则当a,b,c三个学生 选定课程，其情况是： (a,y),(a,w),(b,x),(b,y),(b,w)，而c什么课也没选， R=(a,y),(a,w),(b,x),(b,y),(b,w) 反映了学生与课程的联系。