离散数学05课件

《离散数学05课件》由会员分享，可在线阅读，更多相关《离散数学05课件（89页珍藏版）》请在金锄头文库上搜索。

1、1,第5章 映射,王瑞民 ,2,引言,映射是一个基本的数学概念，是一个特殊的二元关系 常见映射：程序的输入与输出 映射用于开关理论、自动机理论、可计算理论 主要内容：映射的概念，特殊的映射：单射、满射、双射；映射的合成、集合的特征函数、集合的基数,3,第5章 映射,5.1 映射的概念 5.2 映射的合成 5.3 逆映射 5.4 集合的特征函数 5.5 基数,4,定义5.1.1,X,Y为集合，f是从X到Y的关系 若对xX,1 yY，st.f 称f为从X到Y的映射；记作 f:XY或X f Y x称为自变量，y称为x在f作用下的像；记作 y=f(x) f的前域X称为f的定义域，记作domf=X或Df

2、 Y称为陪域，像的集合称为f的值域，记作ranf或Rf Rf=y|x(xXy=f(x),5,映射与关系的区别,对xX,1 yY，st.f Df=X 每个x，对应唯一的y g=|xR为从R到R的关系，而非从R到R的映射 若X=Y，则从X到Y的映射，称为X上的变换,6,映射是函数概念的推广,函数也是映射 函数的定义域和值域都是关于数的集合 映射是推广了定义域及值域的函数 今后函数与映射不加区别，都为一种特殊的二元关系 特殊的函数举例,7,例5.1.1,皮亚诺后继函数 X=Y为自然数集合 对于nN f:XY为f(n)=n+1,8,例5.1.2,X为命题逻辑的全体，Y=T,F f:XY为对命题的赋值,

3、9,例5.1.3,实函数f=x,x f(x)=x称为x的底 f(3.5)=3,f(3.0)=3,f(2.9)=2 g=x,x g(x)=x称为x的顶,10,例5.1.3,X=,Y为任意集合 空关系是从X到Y的函数，称为空函数 若X,Y=,从X到Y唯一的关系是空关系，此时空关系不是从X到Y的函数 不存在函数：其前域非空，陪域为空,11,定义5.1.2,若 f:XY，AX f在A上的限制是从A到Y的映射，记为：f|A 定义为， f|A：AY， f|A(x)=f(x) 若映射g是f的限制，称f是g的扩展,12,例5.1.4,f:XY是由f(x)=x2给出的一个函数 X=Y为实数集 A=0,1,2,3

4、,4,X f|A=,13,定义5.1.3,若f:AB，g:CD 若A=C，B=D 且对xA,f(x)=g(x) 则称映射f与g相等 记作f=g,14,定义5.1.4,令映射f:X1xX2xxXnXi(1in)为f(x1,x2,xn)=xi，其中xiXi(i=1,2,n) 称映射为从X1xX2xxXn到Xi的射影 若XxY为笛卡儿平面上所有点的集合，则XxY到X的射影是一个函数 每一个点，其函数值为该点的X坐标,15,注意,从X到Y的映射是一特殊的关系 一个从X到Y的映射是XxY的子集 XxY的任一子集并不一定为映射 从X到Y的映射的集合记为YX=f|f:XY X中的每一个元素，Y中的元素有|Y

5、|种可能与之对应 |YX|=|Y|X|,16,定义5.1.5,令映射f:XY,f(x1)=y1,f(x2)=y2 其中x1,x2X,y1,y2Rf 若Rf=Y,则称f为从X到Y上的映射(满射) 若对任意的x1,x2X,当x1x2时有y1y2 ,则称f为从X到Y上的一对一映射(单射) 若f既为满射，又为单射，称f为双射或一一对应映射,17,例5.1.5,皮亚诺函数f(n)=n+1，单射，非满射 g:0,1a,b,a,b为实数,且ab,则g(x)=(b-a)x+a为双射 h:RR+,h(x)=x2是满射但非单射,18,习题,P81 2 3 4,19,第5章 映射,5.1 映射的概念 5.2 映射的

6、合成 5.3 逆映射 5.4 集合的特征函数 5.5 基数,20,定义5.2.1,若f:XY，g:YZ是两个映射 gof=|(xX)(zZ) (y)(yYy=f(x)z=g(y) 称为g与f的左合成映射 例已知两个映射的关系图，求它们的合成映射的关系图,21,定理5.2.1,若f:XY，g:YZ，则合成映射gof是从X到Z的映射，且对xX，(gof)(x)=g(f(x) 证明：g和f都是关系，所以gof是从X到Z的关系；对xX f是映射，1yY，使得f(x)=y g是映射，1zZ，使得f(y)=z 因为f,g，所以(gof)，且对于x，z是唯一的，故(gof)是映射 而(gof)(x)=z=g

7、(y)=g(f(x),22,分析,若f:XY，g:YZ，则有合成映射gof 但合成映射gof可能为空关系 为使gof不空，需要RfDg 若f:XX，g:XX，则fog,gof,fof,gog都能构成合成映射 gof与fog不同，靠近自变量的映射先起作用,23,合成映射为可结合的,若f:XY，g:YZ，h:ZW，可以构成合成映射gof:XZ和hog:YW，并且 可以构成合成映射ho(gof)和(hog)f(为从X到W的合成映射) 则ho(gof)=(hog)of=hogof 映射的合成为关系的合成,24,例5.2.1,X=1,2,3,f,g,h,s均为从X到X的映射 f=, g=, h=, s=

8、, 求fog,gof,fohog,sog,gos,sos,fos sos=s?fos=sof=f?gos=sog=g?hos=soh=h?,25,例5.2.2,X为实数集，xX f(x)=x+2 g(x)=x-2 h(x)=3x 求gof,fog,fof,gog,foh,hog,hof,fohog,26,例5.2.3,设X为实数集；f:XX由f(x)=-x2给定，g:X+X+由g(x)=x1/2给定 求fog 问：gof有定义吗？,27,推广的合成映射,设fi:XiXi+1(i=1,2,n)，则fnofn-1oof1唯一表达了从X1到Xn+1的映射 若Xi=X,fi=f(i=1,2,n)，则从

9、X到X的合成映射fnofn-1oof1记为fn,28,例5.2.4,设Z为整数集；f:ZZ由f(i)=2i+1定义 求f3,29,幂等变换,若f为从X到X的映射(变换)，且f2=f，称f为幂等的 f:ZN，f(i)=i(modm)，则f是幂等的 若f是幂等的，则 f3=fo(f2)=fof=f f4=fo(f3)=fof=f fm=f(对任意m1),30,第5章 映射,5.1 映射的概念 5.2 映射的合成 5.3 逆映射 5.4 集合的特征函数 5.5 基数,31,逆关系,R为从X到Y的关系 R-1为从Y到X的关系，且 R-1R 每个关系的逆关系必存在 映射(为关系)的逆关系，仍然是映射吗？

10、即，每一个映射存在逆映射吗？,32,映射的必要条件,f:XY为映射 Df=X：X中每一个元素，Y中存在元素与之对应。即Df=X 唯一性：X中每一个元素，Y中存在唯一的元素与之对应 例：逆关系非映射 结论：映射f存在逆映射 iff f为双射,33,定义5.3.1,设映射f:XY为双射，则f的逆关系为f的逆映射 记作f-1:YX 若f-1存在，则称f为可逆的 若f-1存在，则f-1也是双射,34,定义5.3.2,映射IX:XX定义为，对xX，IX(x)=x，IX称为X上的恒等映射 函数f:XX，若对xX，f(x)=y，即Rf=f(X)=y，称f为X上常函数,35,定理5.3.1,设映射f:XY，则

11、f=foIX=IYof 证明：因为foIX,IYof为从X到Y的映射，且 Df=DfoIX=DIYof=X 又对xX (foIX)(x)=f(IX(x)=f(x)=IY(f(x)=(IYof)(x),36,定理5.3.2,设映射f:XY，有逆映射，则 f-1of=IX,fof-1=IY 证明：Df-1of=DIX=DIYof=X 又f为双射，所以f-1为双射 对xX (f-1of)(x)=f-1(f(x)=x=IX 所以f-1of=IX,同理可证fof-1=IY,37,定理5.3.3,设映射f:XY为双射，则 (f-1)-1=f 证明： f为双射，所以f-1:YX为双射 所以(f-1)-1:X

12、Y为双射，且 domf=dom(f-1)-1=X xXf:xf(x)f-1:f(x)x(f-1)-1:xf(x) 所以(f-1)-1=f,38,定理5.3.4,设映射f:XY，g:YZ都为双射，则 (gof)-1=f-1og-1 证明： f、g为双射，故f-1、g-1存在，且f-1:YX g-1: ZY，所以f-1og-1:ZX gof:XY为双射，故(gof)-1存在，且 (gof)-1:ZX为双射 dom(gof)-1)=dom(f-1og-1)=Z zZ1yY,g(y)=z1xX,f(x)=y (f-1og-1)(z)=f-1(g-1(z)=f-1(y)=x 但(gof)(x)=g(f(

13、x)=g(y)=z，故(gof)-1)(z)=x 即对zZ，(f-1og-1)(z)=(gof)-1)(z) 所以(gof)-1=f-1og-1,39,第5章 映射,5.1 映射的概念 5.2 映射的合成 5.3 逆映射 5.4 集合的特征函数 5.5 基数,40,定义5.4.1,E是全集,AE,映射A:E0,1定义为 1 if xA A= 0 if xA 称A为A的特征函数 特征函数用于确定集合之间的关系 设E是全集,A、BE，对xE,41,性质,性质1:A(x)0A= 性质2:A(x)1A=E 性质3:A(x)B(x)AB 证明：对xE，若A(x)B(x) 对xA，则A(x)=1B(x)，

14、所以B(x)=1，所以xB，所以AB 若AB， 若xA,xB 若xA,xB 若xA,xB,42,性质,性质4:A(x)=B(x)A=B 性质5:AB(x)=A(x)*B(x) 性质6:AB(x)=A(x)+B(x)-A(x)*B(x) 性质7:A(x)=1-A(x) 性质8:A-B(x)=AB(x)=A(x)-AB(x),43,例5.4.1 求证A(BC)=(AB)(AC),A(BC)(x)=A(x)*(BC)(x) =A(x)*(B(x)+C(x)-(BC)(x) =A(x)*B(x)+A(x)*C(x)-A(x)*(BC)(x) =AB(x)+AC(x)-A(BC)(x) =AB(x)+A

15、C(x)-(AB)(AC)(x) =(AB)(AC)(x),44,例5.4.2 求证(A)=A,证明略,45,极小项的集合的特征函数,全集的有限个子集所生成的极小项可以定义全集E的一个划分 令X1,X2,Xn是E的子集 I1,I2,I2n-1是由X1,X2,Xn生成的极小项 xE 若xIj，则Ij(x)=1，且mj时，且对yIj Im(y)=0,46,第5章 映射,5.1 映射的概念 5.2 映射的合成 5.3 逆映射 5.4 集合的特征函数 5.5 基数,47,集合元素个数的比较,A、B两个集合 都为有限集：报数，配对 一个有限，一个无限：报数、配对 都为无限集：配对,48,势,两个有限集含有相同个数的元素 两个无限集含有“相同个数”的元素，称为两个集合具有相同的势,49,定义5.5.1,集合A与B，若存在A到B的双射，则称A与B为等势的(或等位的)，或A与B对等 记作：AB,50,例5.5.1,双射f:NE+ 非负整数N: 0 1 2 n-1 正偶