《集合映射与运算.ppt》由会员分享，可在线阅读，更多相关《集合映射与运算.ppt（96页珍藏版）》请在三一办公上搜索。
1、离散数学Discrete Mathematics,邓辉文编著清华大学出版社2010.3ISBN 978-7-302-21193-8,十一五国家级规划教材 计算机系列教材,离散数学是计算机各专业的专业基础课.(1)程序设计语言(2)离散数学(3)数据结构与算法(4)计算机组成原理(5)计算机网络(6)操作系统(7)数据库(8)软件工程,离散数学研究的对象:离散量及其之间的关系.离散量与连续量及其之间的转换.现今计算机的处理对象是非常特殊的离散量:0和1.学习离散数学的目的:1.培养各种能力.2.为后继专业课程的学习作知识上的准备.,离散数学的主要内容:1.集合与关系Chapter 1 集合、映射
2、与运算 Chapter 2 关系2.数理逻辑Chapter 3 命题逻辑Chapter 4 谓词逻辑3.代数结构(Chapter 5)4.图论Chapter 6 图论Chapter 7 几类特殊的图5.组合计数(Chapter 8),学习离散数学的方法:1.预习.2.听课.3.复习.4.(分组)作业.,参考文献:屈婉玲,耿素云,张立昂,离散数学,高等教育出版社,2007.(108144学时)傅彦,顾小丰,王庆先,离散数学及其应用,高等教育出版社,2008.(两个学期),Chapter 1 Sets,Mappings and Operations,集合是现代数学的最基本概念(?).映射又称为函数
3、,它是现代数学的基本概念,可以借助于集合下定义.运算本质上是映射,但其研究有其特殊性.(关系也是集合)集合、映射、运算及关系(Chapter 2)是贯穿于本书的一条主线.,1.1 集合的有关概念,1.集合在一定范围内,集合(set)是其具有某种特定性质的对象汇集成的一个整体,其中的每一个对象都称为该集合的元素(element).这里所指范围是全集U(见图1-1).(避免悖论!)在数学中常用 表示整体.,若x是集合A中元素,则记xA,否则xA.Fuzzy set?集合通常用大写字母A,B,C,D,表示.N是自然数集合,包括数0；Z是整数集合；Q是有理数集合；R是实数集合；C是复数集合.,P:2,
4、3,5,7,11,13,17,19,23等.(1)m|n:n=mq.(2)Dn.(3)素数测试与Mersenne素数:2p-1.,表示集合的常用方法:(1)列举法:0,2,4,6,8,N=0,1,2,3,.(2)描述法:x|x满足的条件.可简记:直角三角形,所有人(3)递归法自然数集合N可递归定义,在后面章节定义命题公式及谓词公式时还会用此法.有限集合A的元素个数|A|,card(A).,Remarks 1.集合中的元素可以是集合,例如A=a,a,b,b,c.a,bA,a,bA.2.集合之间的元素原则上是没有次序的,如 A=a,a,b,b,c就是 a,b,c,a,b;3.集合中的元素原则上不重
5、复,如a,a,b,b,b,c还是集合A.不含有任意元素的集合称为空集(empty set),记为或.,2.子集A B,特别地是任意集合的子集.A=B.Theorem 1-2(P3)(1)A A.(2)A B,B A A=B.(3)A B,B C A C.Theorem 1-3 A=B A B 且 B A.,注意 与 的不同.例1-2 由A B,B C可否得出A C?Solution 不成立,例如A=a,b,B=a,b,c,C=a,a,b,c.课堂练习:4,5.,3.幂集(power set)X=a,b P(X)=,a,b,a,b.P(P()=P()=,(P5,6(1).,(P5,2),Theo
6、rem 1-4 Proof(加法原理)由乘法原理证明?,4.n元组Def 1-4 将n个元素(?)x1,x2,xn按一定顺序排列就得到一个n元(有序)组(n-tuple).线性代数中的n维向量(?):n=2,n=3(see below),n=2:(x,y).n=3:(x,y,z)4元组?显然,一般说来(x,y)(y,x).注意区别(a,b,c),(a,b),c),(a,(b,c)的不同.,n维向量是n元组,长度为n的线性表是n元组,抽象数据结构Data_Structure=(D,S)本身是一个2 元组.2元组常称为有序对(ordered pair)或序偶.5.笛卡儿积(cross produc
7、t),例1-4(P4)设A=a,b,B=1,2,C=,求A B,B A,A B C,B C.SolutionAB C=(a,1,),(b,1,),(a,2,),(b,2,).BC=(1,),(2,)Remark A=B=.P5,10?,Theorem Hint 可推广到更多个集合的笛卡儿积的情形:作业 习题1.1 6,9,10.,1.2 映射的有关概念,1.映射的定义映射mapping=函数function.C语言是一种函数型语言:从main开始.DefA,B:,A,B,Ceiling function:Floor function:(取整函数)复杂度:,函数的表示:(1)解析式(2)图形(3
8、)表格(数值计算中出现较多)函数符号的选取(P6):f,g,F,G,sin,exp,main,add,average,注意区别函数f与函数表达式f(x).映射的两个特点:(1)全函数;(2)唯一性.,B上A:例1-5 Theorem 1-6 注意B上A的记号与该结论的关系.,x1x2x3,y1y2,X,f(X),Y,f-1(Y),n元函数(n 1):float average(flot array,int n)n=0:C语言中的无参函数?一般处理方式:A到B的一个0元函数是B中某一个元素(see P136).,2.映射的性质(1)单射(injection),(2)满射(surjection)例
9、1-7 是Z到N的满射,但不是Z到Z的满射(?).,(3)双射(bijection,one-to-one correspondence)双射又称为一一对应:既单又满.例1-8例1-9(P8),Def 1-11 有限集合A上自身的双射称为A上的置换(permutation).例1-10第一种方式:,123,123,第二种方式:A=1,2,3,4上的所有置换有多少个?4!,3.逆映射设f:AB,将对应关系f逆转(改变方向),一般来说,不能得到B到A的映射:,abc,123,Def 1-12 设f:AB,若将对应关系f逆转后能得出一个得到B到A的映射,则称该映射为f的逆映射(invertible f
10、unction),记为f-1.,abc,123,Theorem 1-7 f 的逆映射存在的充要条件是f是双射.对于y=sin x,当 时,有反函数,常记为当 时,y=sin x仍有反函数,但不能 记为arcsin.显然,当 时,无反函数.,4.复合映射(composition function)Theorem1-8 设f:A B,g:B C:则h:A C.,x,y=f(x),z=g(y)=g(f(x),Def 1-13 例1-12,abc,123,Remarks(1)y=sin u,u=x2未引入运算符号,有时是不方便的.(2)顺序问题:有些专业书但会出现一些混乱.,例1-13(P9)f:RR
11、,f(x)=x2,g:RR,g(x)=x+2,求fg和gf.Solution x R:(fg)(x)=g(f(x)=g(x2)=x2+2.(gf)(x)=f(g(x)=f(x+2)=(x+2)2.Remark fg gf.,IA:A ATheorem 1-9理解:,abc,123,abc,123,abc,123,Theorem 1-10(1)若f和g是单射,则fg是单射.(2)若f和g是满射,则fg是满射.(3)若f和g是双射,则fg是双射.Proof(2)任意z C,由于g是满射,存在y B,使得z=g(y).又由于f是满射,存在x A,使得y=f(x).于是z=g(y)=g(f(x)=(f
12、g)(x).故fg是满射(see below).,Theorem 1-11(1)若fg是单射,则f是单射,g不一定.(2)若fg是满射,则g是满射,f 不一定.(3)若fg是双射,则f是单射且g是满射.Proof(1)任意x1,x2 A,若f(x1)=f(x2),显然,g(f(x1)=g(f(x2),即(fg)(x1)=(fg)(x2).由于fg是单射,因此 x1=x2.故f是单射.g不一定(见上图)?,一般来说fg gf,但Theorem 1-12作业 习题1.2:3,4,7,8,12.Hint 7.使用定理1-10和第3题.8.使用第7题结论.12.使用第7题结论.,1.3 运算的定义及性
13、质,运算是讨论对象之间有何联系的一种方法.其实，我们已经接触过很多运算,如数之间的加法运算、多项式之间的乘法运算、矩阵的逆运算、向量的线性运算等.在讨论离散数据结构时也会经常遇到各种各样的运算，如在下节即将研究的集合间的运算.虽然运算本质上是映射，但研究的侧重点不同，在运算中更注重于运算满足的一些运算性质，而根据这些性质可以对一些离散对象分门别类进行讨论.因此，有必要先把运算的一般定义及其性质进行讨论.,1.运算的定义(1)定义 A1,A2,An到B的n元运算(n-ary operation):A到B(或A上)的n元运算:A上的n元封闭运算(代数运算):,(n=0?一般处理方式:A到B的一个0
14、元运算可理解为B中某一个元素.)例1-14 f:Z N,f(x)=|x|.例1-15(模运算)f:Z N,f(x)=x(mod k),x=qk+r,0 r k:8=2 3+2;-5=-2 3+1.模运算的两个简单应用(P15)(1)加密;(2)Hash function.,例1-16例1-17,例1-19 gcd(m,n)lcm(m,n)素因数分解:Euclid算法.,(2)运算符号的选取函数符号f,g,F,G,;常见运算符号+,/,;自定义符号,(3)运算符号的位置,(4)运算表A=a,b,c,*:思考 A上封闭的1元运算,2元运算和3元运算的个数是多少?,2.运算的性质(1)对合(invo
15、lutive)性 Def 设*是A上的1元代数运算,例,(2)幂等(idempotent)性 幂等元x:A关于*具有幂等性:A中每个元素对于*都是幂等元.两个例子:,(3)交换(commutative)性 Def 设*是A上的2元代数运算,若对于任意的x,y A,均有 则称*满足交换律.显然,映射的复合运算不满足交换律:加法运算”+”满足交换律,而减法运算”-”不满足交换律:2 3 3 2.如何根据定义的运算得出运算具有交换性?,(4)结合(associative)性 映射的复合运算满足结合律:加法运算“+”满足结合律,而减法运算“-”不满足结合律:(2-3)-5 2-(3 5).如何根据运算
16、表判断运算是否可(交换)结合?,(5)单位元素.Def 设*是A上的2元代数运算,若存在e A,对于任意的x A,下列条件均成立：则称e为集合A关于*运算的单位元素或幺元素.(幺元律?)例 Z关于加法运算+的单位元素为0,而Z关于乘法运算“.”的单位元素为1,Z关于减法运算-没有单位元素.,(6)零元素(zero element).Def 设*是A上的2元代数运算,若存在 A,对于任意的x A,下列条件均成立：则称为集合A关于*运算的零元素.(零元律?)例1-28 Z关于加法运算+和减法运算-均没有零元素,而Z关于乘法运算的零元素为0.,(7)逆元素(invertible element)若A
17、关于运算*有单位元素e,则可以讨论A中取定的元素x是否有逆元.Def 设*是A上的2元代数运算且有单位元素e,若对于x A,存在y A,使得下列条件均成立:则称y为x的关于*的逆元素.,显然,一个方阵关于乘法运算的逆元就是其逆矩阵,因为单位元素是单位矩阵.对于函数来说,一个映射关于函数的复合运算的逆元就是其逆映射,当然只有双射才有逆元,其单位元素是恒等映射.例1-29 R中各元素关于加法运算+和乘法运算逆元素.,(8)消去(cancellation)性.Def 设*是A上的2元代数运算,若A关于*运算有零元则记为,如果对于任意的x,y,z A,只要x,那么下列条件均成立：则称*具有消去性,或称
18、*满足消去律.例1-31 Z上的加法运算+和乘法运算均满足消去律.例1-32 实数集R上的所有2阶方阵组成的集合,关于矩阵乘法运算不满足消去律.,(9)分配(distributive)性.Def 设*和是集合A上的两个2元代数运算,若对于任意x,y,z A,有 则称*对于是可分配的.例1-33 实数集合R上的乘法运算对加法运算+可分配,但加法运算+对乘法运算不可分配.,(10)吸收(absorptive)性 Def 设*和是集合A上的两个2元代数运算,若对于任意x,y A,有 则称*对于是可吸收的.如果*和是集合A上的两个可交换的2元代数运算,则*运算对运算可吸收只需要满足两条件之一即可,但吸
19、收性本身不需要*和可交换.,(11)德摩根(De Morgan)律 Def 设是集合A上的1元代数运算,*和是A上的两个2元代数运算,若对于任意x,y A,均有下面两个等式成立:则称这三种运算满足德摩根律.课堂练习 习题1.3 4.作业 习题1.3 7,11.,1.4 集合的运算,最常见的集合运算是并、交和补.1.并(union)运算,Theorem 是包含A和B的最小集合.Theorem1-17(并运算满足的性质)(1)(2)(3)(4)A=A=A(5)A U=U A=U,例1-38 设f:A B,X,Y A,则Proof(1)(2),2.交(intersection)运算Theorem 是
20、包含在A和B的最大集合.,Theorem1-19(交运算满足的性质)(1)(2)(3)(4)A=A=(5)A U=U A=A例1-40:举例?,Theorem 1-20(并运算与交运算之间所满足的性质.)(1)吸收性.(2)分配性.例1-41(P20),3.补(complement)运算例1-42(A的补集依赖于全集U的选取.)A=a,b,c:(1)U=a,b,c,d(2)U=a,b,c,d,a,b,b,c,c,排中律成立:.排中律:x U,x A或 x A二者必居其一,没有中间情况.,集合的补运算和集合的并交运算满足De Morgan律:推广?表(P25).(与布尔代数的性质完全类似?!因为
21、它们是特殊的,常见的布尔代数.),4.差(subtraction)运算例1-43,Theorem 1-23(P26)Proof例1-45(P26),例1-46.例1-47(P26)Solution由上例知,A(B C)=,5.对称差(symmetric difference)运算See Venn Figure below.例1-48,Theorem(对称差运算的性质)(1)交换性:(2)单位元:A=A.(3)A A=.(4)结合性:,例1-49(消去律)Hint,例1-50 A B=A=B.Proof()显然.()A B=A B=且B A=例1-51(对 可分配),思考 还能定义集合的其他运算
22、(共9种！)?加法原理.乘法原理.容斥原理:容斥原理的另一种形式:推广到n个集合情形(P28)?作业 习题1.4 5,8,10,13.,1.5 集合的划分与覆盖,集合的划分与覆盖是集合中的重要内容之一.集合的划分就是集合元素间的一种分类.在信息科学中,可以将知识库看作集合的一种划分.因此,研究集合的划分具有特别重要的意义.比集合的划分更广的概念是集合的覆盖.这些内容在下章会用到.1.集合的划分(partition),Def(1),iI.(2),i j.(3)Hard disk?,例1-53 设A=a,b,c,则A的所有不同的划分分别为:,1和2的交叉划分:.1是2的加细划分:,|A|=n,A的
23、不同划分的个数N:S(n,k)?Theorem n 1.Proof(?),2.集合的覆盖Def 设A是集合,由A的若干非空子集构成的集合称为A的覆盖(covering),如果这些非空子集的并等于A.a,b,b,c,集合的划分 集合的覆盖,但反过来不成立.A=a,b,c上所有不同的覆盖有哪些?作业 习题1.5 1,4,7.,1.6 集合的对等,集合的对等,它是集合间的另一种关系.通过集合对等以及相关内容的学习,加深对函数概念的理解,提高正确使用函数工具作为研究手段的能力.1.集合对等(equivalent)Def A B:存在双射f:A B.,N E.ZN?(0,1)R.G.Cantor.N N
24、 N.Theorem 1-28(对等的性质)(1)A A.(2)A B B A.(3)A B,B C A C.,2.无限集合有了集合对等的概念,就可以给出无限集合及有限集合的严格定义.Def 设A是集合,若存在A的一个子集与自然数集合N对等,则称A为无限集合(infinite set),否则称A为有限集合(finite set).N.0,1.,3.集合的基数有限集合的基数就是的元素个数.借助于集合对等概念,可以将其扩展到无限集合.Def 若集合A和B对等,则称这两个集合的基数(cardinality)相同.|A|,card(A),#(A).G.Cantor被这些问题所折磨难以自拔,1884年后
25、患精神病(受到很多人的批评和攻击,包括他的老师,用脑过度?),4.可数集合Def 能与自然数集合N对等的集合称为可数集合(countable set).根据无限集合的定义知：任意无限集合均存在一个可列的子集合.根据这一点,可以证明无限集合的特征性质.Theorem 设A是无限集合,则存在A的一个真子集B,使得 A B.,Proof 因为A是无限集合,存在可数的子集合考虑Q是可列集合.,5.不可数集合是否所有无限集合都是可数的?答案是否定的.例 证明:(0,1)是不可数集合.Proof(反证)取,6.基数的比较Def 给定集合A和B,若存在A到B的单射,则称A的基数小于等于B的基数,记为|A|B|.若进一步,不存在A到B的双射,则称A的基数小于B的基数,记为|A|B|.由定义易知,若存在B到A的满射,则|B|A|.显然,Problem 是否存在集合A,满足(著名的连续统假设?!)作业 习题1.6 2,4,6.,
