离散数学-函数课件.ppt
《离散数学-函数课件.ppt》由会员分享,可在线阅读,更多相关《离散数学-函数课件.ppt(53页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第5章 函数第5章 函数5.1 函数的基本概念5.2 反函数和复合函数5.3 集合的基数返回总目录第5章 函数5.1函数的基本概念定义5.1.1设A和B是两个任意集合,f是A到B的二元关系,如果对于A中的每一个元素x,都存在B中惟一元素y,使得x,y f,则称f是A到B的函数或映射。记为f:AB。x,y f,常记为y=f(x),x称为自变元或像源,y称为在f作用下x的函数值或像。由函数的定义可以看出,函数是一种特殊的二元关系。若f是A到B的函数。它与一般二元关系的区别如下:函数的定义中强调A中的每一个元素x有像,所以A=domf。这称为像的存在性。函数的定义中还强调像y是唯一的,称做像的惟一性
2、。像的惟一性可以描述为:设f(x1)=y1且f(x2)=y2。如果x1=x2,那么y1=y2。或者,如果y1y2,那么x1x2。第5章函数第5章 函数【例5.2】设N为自然数集合,下列N上的二元关系是否为函数?f=x,2x|x N g=x,2|x N解:f和g都是从自然数集合N到自然数集合N的函数,常记为f:NN,f(x)=2x和g:NN,g(x)=2。设A和B是两个任意集合,AB任意子集是A到B的二元关系,但不一定是A到B的函数。当A和B是有限集时,由定理4.1.1的证明过程可以看出,A到B的二元关系共有2|A|B|个,A到B的函数有多少个呢?以下研究这个问题。设A和B是两个任意的集合,f|
3、f:AB 是A到B的所有函数构成的集合,常记为BA。读作B上A。第5章 函数【例5.3】设A=1,2,3,B=a,b,求BA。解:由A到B的函数有以下8个:f0=1,a,2,a,3,a f1=1,a,2,a,3,b f2=1,a,2,b,3,a f3=1,a,2,b,3,b f4=1,b,2,a,3,a f5=1,b,2,a,3,b f6=1,b,2,b,3,a f7=1,b,2,b,3,b BA=f0,f1,f2,f3,f4,f5,f6,f7 A到B的函数共8个,8=23=|B|A|。当A和B都是有限集时,这个结论可以推广。一般地说,若|A|=m,|B|=n,则|BA|=nm=|B|A|。第
4、5章 函数定义5.1.2设A和B是两个任意的集合,f:AB,A1A,集合f(x)|x A1称为集合A1在f下的像,记为f(A1)。集合A在f下的像f(A)=f(x)|x A 称为函数f的像。显然,函数f的像f(A)就是二元关系f的值域,即f(A)=ranf。【例5.4】设f:1,2,3a,b,f=1,a,2,a,3,b,A1=1,2,试求A1在f下的像f(A1)和函数f的像f(A)。解:f(A1)=f(x)|x A1=f(1),f(2)=a f(A)=f(x)|x A=f(1),f(2),f(3)=a,b第5章 函数定义5.1.3 设f:AB,g:CD,若A=C,B=D且x A,有f(x)=g
5、(x),则称函数f和g相等,记为f=g。例如,函数f:NN,f(x)=x3函数g:1,2,3N,g(x)=x3虽然函数f和g有相同的表达式x3,但是它们是两个不同的函数。如果把f和g看成二元关系,f NN,用列举法表示为:0,0,1,1,2,8,3,27,4,64,g1,2,3N,用列举法表示为:0,0,1,1,2,8,3,27按二元关系相等的条件衡量,它们也是不等的。函数相等和二元关系相等是一致的。第5章 函数定义5.1.4 设f:AB,若f的值域ranf=B,则称f为满射。设f是A到B的函数,由定义不难看出,如果y B,都存在x A,使得f(x)=y,则f是满射函数。例如,A=a,b,c,
6、d,B=1,2,3,f是由A到B的函数,定义为:f=a,1,b,1,c,3,d,2因为ranf=f(A)=1,2,3=B,所以f是满射。图5.2是f的示意图。由图5.2可得出如下的结论:若A、B是有限集,f:AB是满射,在f的示意图中,B中每个元素至少是一个有向边的终点且|A|B|第5章 函数定义5.1.5设f:AB,若y ranf,存在惟一的x A,使得f(x)=y,则称f为单射。设f是A到B的函数,由定义不难看出,如果对于x1A,x2A,f(x1)=y1,f(x2)=y2。当y1=y2时,一定有x1=x2,则f是单射函数。当x1x2时,一定有y1y2,则f是单射函数。【例5.5】设f:a,
7、b2,4,6,定义 f=a,2,b,6函数f是否为单射?f是否为满射?第5章 函数解:因为f(a)=2,f(b)=6,所以f是单射。因为f 的值域ranf=2,6 2,4,6,所以f不是满射。图5.3是f 的示意图。由图5.3可得出如下的结论:若A、B是有限集,f:AB是单射,在f 的示意图中,B中每个像点是且仅是一条有向边的终点且|A|B|第5章 函数定义5.1.6 设f:AB,若f既是单射,又是满射,则称f为双射。例如:A=1,2,3,B=a,b,c,f=1,a,2,c,3,b,f是A到B的双射函数,图5.4是f的示意图。第5章 函数若A、B是有限集,f:AB是双射,则f一定是满射。故B中
8、每个元素至少是一个有向边的终点;f 也是单射,故B中每个像点是且仅是一条有向边的终点。所以,在双射函数的示意图中,B中每一个元素是且仅是一条有向边的终点。若A、B是有限集,f:AB是双射,则f 一定是满射,所以|A|B|;f 也是单射,所以|A|B|。于是|A|=|B|。第5章 函数【例5.6】判断下列函数是否为单射、满射或双射。为什么?f:RR,f(x)=-x2+2x-1,其中,R是实数集合f:IR,f(x)=lnx,其中,I是正整数集合f:RI,f(x)=x,其中,x是不大于x的最大整数f:RR,f(x)=2x+1f:RR,f(x)=,其中,R是正实数集合第5章 函数解:f(x)=-x2+
9、2x-1=-(x-1)2,f 是开口向下的抛物线,不是单调函数,所以不是单射。在x=1处取得极大值0,所以f 不是满射。f 既不是单射也不是满射。f 是单调增加函数。因此是单射,但不是满射,因为ranf=ln1,ln2,Rf是满射,但不是单射,例如f(1.5)=1.5=1,而f(1.2)=1.2=1f是单调增加函数且ranf=R,它既是单射,也是满射,因此它是双射。f 不是单射也不是满射。当x0时,f(x);而当x时,f(x)。在x=1处函数f(x)取得极小值f(1)=2。因此它既不是单射也不是满射。第5章 函数定义5.1.7设f:AB,若y B,x A,都有f(x)=y,则称f为常函数。设I
10、A是A上的恒等关系,它是A到A的函数,IA叫做A上的恒等函数。常记为y=IA(x)。设A是任意集合,A A,x A,定义:A0,1如下:叫做A的特征函数。设R是A上的等价关系,xR是x形成的R等价类,A/R是A关于R的商集,f:AA/R,定义为:f(x)=xR,称f为A到商集A/R的自然函数或自然映射。第5章 函数例如,设A=a,b,c,A=b,B=a,b,则 A的特征函数xA=a,0,b,1,c,0。B的特征函数xB=a,1,b,1,c,0。显然A的每一个子集都对应一个特征函数。又例如,设A=a,b,c,A上的等价关系R为:R=a,a,b,b,b,c,c,b,c,c,商集A/R=a,b,c
11、f:AA/R f(a)=a f(b)=f(c)=b,c 不同的等价关系确定不同的自然映射,其中恒等关系确定的自然映射是双射,而其它的自然映射一般地说是满射。返回章目录第5章 函数5.2反函数和复合函数5.2.1反函数定理5.2.1设f:AB是双射函数,则f 的逆关系f C是B到A的双射函数。证明:先证逆关系f C是B到A的函数。因为f 是函数,所以f C是B到A的二元关系。以下证明B到A的二元关系f C是B到A的函数。y B,因为f:AB是满射,所以,x A,使x,y f,由逆关系的定义得,y,x f C。设y1,x1fC,y2,x2fC,y1=y2,由逆关系的定义知,x1,y1f,x2,y2
12、f,因为f是单射,所以x1=x2故f C是B到A的函数。第5章 函数再证f C是满射。由定理4.2.7有ranf C=domf。又因为f 是A到B的函数,所以domf=A。于是ranf C=A。所以f C是B到A的满射。最后证f C是单射。设y1,x1f C,y2,x2f C且x1=x2,由逆关系的定义有x1,y1f,x2,y2f,又因为f是函数,必有y1=y2。所以f C是单射。这就证明了f C是双射函数。第5章 函数定义5.2.1设f:AB是双射函数,f的逆关系f C是B到A的双射函数。称双射函数f C为f的反函数,记为:f-1。例如,设A=1,2,3,B=a,b,c。f=1,a,2,c,
13、3,b 显然,f是A到B的双射函数。f的逆关系 f C=a,1,c,2,b,3是B到A的双射函数,记为f-1,f 1是f 的反函数。又如g=1,a,2,a,3,b也是A到B的函数,但g不是满射,也不是单射,因而不是双射。逆关系 gC=a,1,a,2,b,3不是B到A的函数。第5章 函数定理5.2.2 设f:AB为双射函数,f-1:BA是f的反函数,则(f-1)-1=f。证明:由定理5.2.1和定义5.2.1知(f-1)-1:AB,且为双射。x A,设f(x)=y,则f-1(y)=x,(f-1)-1(x)=y=f(x),所以(f-1)-1=f。例如,设A=a,b,c,B=1,2,3。f:AB为双
14、射函数,定义为:f=a,2,b,3,c,1则f-1=2,a,3,b,1,c(f-1)-1=a,2,b,3,c,1=f第5章 函数5.2.2复合函数第4章介绍了二元关系的复合运算。在那儿,二元关系的复合关系定义为:设X,Y,Z是集合,RXY,SYZ,集合x,z x X z Z(y)(y Y x,y R y,z S)叫做R和S的复合关系。记为R S。即 R S=x,z x X z Z(y)(y Y x,y R y,zS)将R S=x,z x X z Z(y)(y Y x,y R y,zS)记为SR,即 SR=x,z x X z Z(y)(y Y x,y R y,zS)第5章 函数前者叫做R和S的复
15、合关系。为了与前者区别,后者叫做二元关系S在二元关系R左边的复合关系,简称为S和R的左复合关系。前面已经讲过,函数是满足一定条件的二元关系,当然它可以进行左复合运算。函数的左复合关系描述为:设f:AB,g:CD,若f(A)C,集合 gf=a,d|aA dD(b)(bB a,bf b,dg)=a,d|aA dD(b)(bB b=f(a)d=g(b)第5章 函数定义5.2.2 设f:AB,g:CD,若f(A)C,集合a,d|aA dD(b)(bB b=f(a)d=g(b)称为函数g在函数f左边的复合关系,记为gf。定理5.2.3设f:AB,g:CD,f(A)C,则函数g在函数f左边的复合关系gf是
16、A到D的函数。证明:aA,因为f是A到B函数,必存在惟一的bB,使得a,bf。即b=f(a)。而b=f(a)f(A)C,故bC。又因为g是C到D函数,必存在惟一的dD,使得b,dg。即d=g(b)。故由定义5.2.2,a,dgf,即gf(a)=d。所以gf是A到D的函数。第5章 函数定义5.2.3 设f:AB,g:CD,若f(A)C,函数g在函数f左边的复合关系gf称为函数g在函数f左边可复合函数,简称为g和f的左复合函数或g和f的复合函数。仍然记为gf。gf是A到D的函数。推论设f:AB,g:CD,f(A)C,则gf(x)=g(f(x)。证明:由定理5.2.3的证明过程可以看出,aA,b=f
17、(a)且d=g(b),gf(a)=d,于是,gf(a)=d=g(b)=g(f(a)。所以,gf(x)=g(f(x)。第5章 函数定理5.2.4设f:AB,g:BC,g f:AC。如果f和g都是满射,则gf也是满射。如果f和g都是单射,则gf也是单射。如果f和g都是双射,则gf也是双射。证明:c C,因为g是B到C的满射,bB,使c=g(b)。又因为f是A到B满射,aA,使b=f(a)。于是,gf(a)=g(f(a)=g(b)=c,所以gf是满射。设a1A且a2A,a1a2,因为f是A到B单射,f(a1)f(a2),f(a1)B,f(a2)B。又因为g是B到C单射,所以g(f(a1)g(f(a2
18、),即gf(a1)gf(a2),故gf是单射。f和g都是双射,则f和g都是满射和单射,由和知,gf是满射和单射,故gf是双射。第5章 函数在第4章的第2节中定义了二元关系的复合运算,介绍了复合运算性质。这些性质有:设R XY,SYZ,T ZW。(R S)T=R(ST)R IY=IXR=RR RC=IX,RCR=IY(R S)C=SCRC函数的复合运算也有类似的性质。以下几个定理介绍了这些性质。第5章 函数定理5.2.5设f:AB,g:BC,h:CD,则 h(gf)=(hg)f 证明:由定义5.2.3知,gf:AC,h(gf):AD。类似地hg:BD,(hg)f:AD。令f(x)=y,g(y)=
19、z,h(z)=u。由定理5.2.3的推论知,gf(x)=g(f(x)=g(y)=z,hg(y)=h(g(y)=h(z)=u h(gf)(x)=h(gf)(x)=h(z)=u=hg(y)=hg(f(x)=(hg)f(x)所以h(gf)=(hg)f 因为函数的复合运算满足结合律,所以可略去函数复合运算中的括号,即用hgf记h(gf)=(hg)f,另外,还可以定义函数的幂:f 2=f f,f 3=f f f,第5章 函数【例 5.8】设 R是实数集合,下面是 R到 R的函数f(x)=x+2,g(x)=x-2,h(x)=3x先求g和f的复合函数gf,h和g的复合函数hg。再验证h(gf)=(hg)f解
20、:显然h(gf):RR(hg)f:RR gf(x)=g(f(x)=g(x+2)=(x+2)-2=x hg(x)=h(g(x)=h(x-2)=3(x-2)=3x-6 h(gf)(x)=h(gf(x)=h(x)=3x(hg)f(x)=hg(f(x)=hg(x2)=3(x2)-6=3x所以h(gf)(x)=(hg)f(x)故h(gf)=(hg)f 第5章 函数定理5.2.6设f:AB,IA是A上的恒等函数,IB是B上的恒等函数,则IBf=f IA=f证明:先证f IA=f由定义5.2.3知,f IA:AB,再由定理5.2.3的推论知 f IA(x)=f(IA(x)=f(x)所以f IA=f类似地可以
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 函数 课件
限制150内