离散数学第8章-函数

CHAPTEREight11/15/20194:41PMDiscreteMath.,ChenChen1离散数学DiscreteMathematicsCHAPTEREight11/15/20194:41PMDiscreteMath.,ChenChen2第八章函数§8.1函数的定义与性质§8.2函数的复合与反函数§8.3双射函数与集合的基数§8.4一个电话系统的描述实例CHAPTEREight11/15/20194:41PMDiscreteMath.,ChenChen3定义8.1设F为二元关系，若xdomF都存在唯一的yranF使xFy成立,则称F为函数。对于函数F,如果xFy，则记y=F(x)，并称y为F在x的值。§8.1函数的定义与性质例8.1设F1={x1,y1,x2,y1,x3,y2}，F2={x1,y1,x1,y2}.则F1是函数，定义8.2设F、G是函数，则而F2不是函数。F=GFG∧GF.(2)xdomF=domG都有F(x)=G(x).注：如果F=G，那么它们满足：定义8.3设A,B为集合,如果f是函数,且domf=A，ranfB，则f称为从A到B的函数，记作f:A→B.(1)domF=domG;CHAPTEREight11/15/20194:41PMDiscreteMath.,ChenChen4定义8.4所有从A到B的函数的集合记作BA，即BA={f|f:A→B}.注：1.若|A|=m,|B|=n,则|BA|=nm;2.ΦΦ={Φ},BΦ={Φ},ΦA=Φ.定义8.5设函数f:A→B，A1A，B1B.(1)令f(A1)={f(x)|xA1}.称f(A1)为A1在f下的像。特别地，当A1=A时，称f(A)为函数的像.(2)令f–1(B1)={x|xA∧f(x)B1}，称f–1(B1)为B1在f下的完全原像。例8.3见教材P137.§8.1函数的定义例8.2见教材P137.CHAPTEREight11/15/20194:41PMDiscreteMath.,ChenChen5(1)若ranf=B，则称f是满射.(2)若yranf都存在唯一的xA使得f(x)=y，则称f是单射.(3)若f既是满射又是单射，则称f是双射(一一映射).注：1.如果f是满射，则对yB，都存在xA，使f(x)=y2.如果f是单射，则对x1,x2A，x1≠x2,必定f(x1)≠f(x2)也就是说，如果f(x1)=f(x2)，则x1=x2。§8.1函数的性质定义8.6设f:A→B.CHAPTEREight11/15/20194:41PMDiscreteMath.,ChenChen6例8.4判断下列函数是否为单射、满射、双射.22(1):,()21.(2):,()ln,:,().(4):,()21.1(5):,(),fRRfxxxfZRfxxZfRZfxxfRRfxxxfRRfxRx为正整数集.(3)其中为正实数集.CHAPTEREight11/15/20194:41PMDiscreteMath.,ChenChen7解：22(1):,()21(2):,()ln{ln1,ln2,...,}:,()(4):,()21.(5):,()fRRfxxxfZRfxxranfRfRZfxxfRRfxxxfRRfx是开口向下的抛物线。在x=1处取得最大值0，既不是单射，也不是满射.是单调增函数,是单射,但不是不是满射，因.(3)是满射，但不是单射.是满射,也是单射,从而是双射1,0();()xfxxxfx当时，而当时，.在x=1处f(x)取得极小值2。故它既不是单射，也不是满射。CHAPTEREight11/15/20194:41PMDiscreteMath.,ChenChen8例8.5对如下给定的A,B和f,判断f是否构成A到B的函数，如果是，说明它是否为单射、满射和双射，并按要求进行计算。32(1){1,2,3,4,5},{6,7,8,9,10},{1,8,3,9,4,10,2,6,5,9}.(2),(1){1,7,2,6,4,5,1,9,5,10},(1){1,8,3,10,2,6,4,9}(4),()(5),()1(6),(ABfABfABfABRfxxxABRfxxABRRf同，(3)同，221,),.{,|,1}.().(7),,(,)||,({0}),({0}).xyxyxyLxyxyRyxfLANNBNfxyxyfNf令计算计算CHAPTEREight11/15/20194:41PMDiscreteMath.,ChenChen9(1){1,2,3,4,5},{6,7,8,9,10},{1,8,3,9,4,10,2,6,5,9}.(2),(1){1,7,2,6,4,5,1,9,5,10}1,71,9.:,(1)ABffABffABffABf能构成A到B的函数。它不是单射也不是满射。因为f(3)=f(5)=9,且7ranf.同，不能构成到的函数。因且(3)同，解{1,8,3,10,2,6,4,9}{1,2,3,4}3(4),()fABdomfAABRfxxfAB不能构成到的函数。因能构成到的函数，且是双射。CHAPTEREight11/15/20194:41PMDiscreteMath.,ChenChen10(5),()2111(23)(23).24(6),(,),.{,|,1}.().22(7),,(,)||xABRfxxfABffABRRfxyxyxyLxyxyRyxfLfABfANNBNfxyxy能构成到的函数，但既不是单射，也不是满射。因，且在x=1处取得最大值令计算能构成到的函数，且是双射(L)={2x+1,-1|xR}1,({0}),({0}).(1,1)(2,2)0,2.2({0}){(,0)|}{|}.1({0}){,|}.fNffABffranffNfnnNnnNfnnnN计算能构成到的函数，但既不是单射，也不是满射。因且CHAPTEREight11/15/20194:41PMDiscreteMath.,ChenChen11例8.6对给定的集合A和B构造双射函数f:A→B.{1,2,3}1142(1)({1,2,3}),{0,1};(2)[0,1],[];3,;(4)[,],[1,1].22APBABAZBNAB(3)，017012345(1){,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}{,,,},{1,0,2,0,3,0},{1,0,2,0,3,1}{1,0,2,1,3,0},{1,1,2,0,3,0}{1,0,2,1,3,1},{1,1,2:,0,3,1ABfffffffff其中：解6707456123}{1,1,2,1,3,0},{1,1,2,1,3,1}::(),({1,2,3}),({1,2}.),({1,3}),({2,3}),({1}),({2}),({3}),fffABffffffffffffffff令使得CHAPTEREight11/15/20194:41PMDiscreteMath.,ChenChen123221(2)[0,1],[]4111:[0,1][,],()424,::01234562,0:()21,03(4)[,],[1,1]22:[1,1],()sin.[,]ABxffxAZBNZZNxxfxxxABffxx1，2令(3)将中元素按下列方式与N中元素对应0-11-22-33这种对应关系表示的函数是令CHAPTEREight11/15/20194:41PMDiscreteMath.,ChenChen13(1)设f:A→B，如果存在cB使得对xA都有f(x)=c，则称f是常函数;(2)称A上的恒等关系IA为A上的恒等函数，对xA，都有IA(x)=x.(3)设(A,≼)，(B,≼)为偏序集，f:A→B。若对x1,x2A，x1≺x2时有f(x1)≼f(x2)，则称f是单调递增的；若对x1,x2A，x1≺x2时f(x1)≺f(x2)，则称f是严格单调递增的，类似可定义单调递减和严格单调递减函数.(4)设A为集合,对A'A，A'的特征函数XA':A→{0,1}定义为定义8.7'1'()0AaAXa否则(5)设R是A上的等价关系，令g:A→A/R,g(a)=[a],(aA),称g是从A到商集A/R的自然映射。CHAPTEREight11/15/20194:41PMDiscreteMath.,ChenChen14函数的复合也就是关系的右复合。定理8.1设F,G是函数，则F。G也是函数，且满足(1)dom(F。G)={x|x∈domF∧F(x)∈domG}(2)x∈dom(F。G)有F。G(x)=G(F(x))§8.2函数的复合与反函数证明：(1)∵F，G是关系，∴F。G也是关系。若x∈dom(F。G)有xF。Gy1和xF。Gy2,则x,y1∈F。G∧x,y2∈F。G=t1(x,t1∈F∧t1,y1∈G)∧t2(x,t2∈F∧t2,y2∈G)=t1(x,t1∈F∧t1,y1∈G)∧t2(x,t2∈F∧t2,y2∈G)=t1t2(t1=t2∧t1,y1∈G∧t2,y2∈G)(∵F为函数)=y1=y2(∵G为函数)∴F。G为函数。CHAPTEREight11/15/20194:41PMDiscreteMath.,ChenChen15（2）对于x,x∈dom(F。G)=ty(x,t∈F∧t,y∈G)=t(x∈dom(F)∧t=F(x)∧t∈dom(G))=x∈{x|x∈dom(F)∧F(x)∈dom(G)}对于x,x∈dom(F)∧F(x)∈dom(G)=x,F(x)∈F∧F(x),G(F(x))∈G=x,G(F(x))∈F。G=x∈dom(F)∧F。G(x)=G(F(x))§8.2函数的复合与反函数CHAPTEREight11/15/20194:41PMDiscreteMath.,ChenChen16推论1设F,G,H为函数，则(F。G)。H和F。(G。H)都是函数，且(F。G)。H=F。(G。H)推论2设f:A→B,g:B→C,则f。g:A→C,且x∈A都有f。g(x)=g(f(x))。§8.2函数的复合与反函数定理8.2设f:A→B,g:B→C(1)若f:A→B,g:B→C都是满射的，则f。g:A→C也是满射的。(2)若f:A→B,g:B→C都是单射的，则f。g:A→C也是单射的。(3)若f:A→B,g:B→C都是双射的，则f。g:A→C也是双射的。证明略，参见P143。CHAPTEREight11/15/20194:41PMDiscreteMath.,ChenChen17定理8.3设f:A→B,则有f=f。IB=IA。f证明:由前定理知f。IB:A→B,IA。f:A→B对于x,y,x,y∈f=x,y∈f∧y∈B=x,y∈f∧y,y∈B=x,y∈f。IBx,y∈f。IB=t(x,t∈f∧t,y∈IB)=x,t∈f∧t=y=x,y∈f∴f=f。IB同