离散数学讲义(第4章)课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《离散数学讲义(第4章)课件.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 讲义 课件
- 资源描述:
-
1、1离散数学讲义(电离散数学讲义(电子版)子版)2 3本章包括以下内容:4-1 函数的概念4-2 逆函数和复合函数4-4 基数的概念4-5 可数集与不可数集4-6 基数的比较4在这里把函数看作一种特殊关系。在这里把函数看作一种特殊关系。定义:定义:设X,Y为任意两个集合,f是X到Y的关系,若对于每一个xX,有唯一的yY,使得x,yf,称关系f为函数函数(或映射映射),记作f:X Y其中,x称为自变元,y称在f作用下x的象。x,yf也可记作y=f(x),且记f(X)=f(x)|xX 4-1 函数的概念函数的概念注:注:函数与关系的区别(1)函数的定义域是X,而不能是X的某个真子集(2)一个xX只能
2、对应唯一一个y5在x,y f中,f的前域即dom f=X,f的值域ran f Y,有时也记作Rf。Rf=y|(x)(x X)(y Y)集合Y称为f的共域共域,ran f称为函数的象集合象集合。4-1 函数的概念函数的概念(续)(续)定义:定义:设函数f:A B,g:C D,如果A=C,B=D,且对所有x A和y C,有f(x)=g(x),则称函数f和g相等相等,记作f=g注:注:X Y的子集并不能都成为X到Y的函数。我们用YX表示从X到Y的所有函数的集合,当X和Y是无限集时也可用这个符号。6定义:定义:对于f:X Y的映射中,如果ran f=Y,即Y的每一个元素是X中一个或多个元素的象点,则称
3、这个映射为满满射射(或到上映射到上映射)。即对于任意y Y,必存在x X使得f(x)=y成立。4-1 函数的概念函数的概念(续)(续)定义:定义:从X到Y的映射中,X中没有两个元素有相同的象,则称这个映射为入射入射。定义:定义:从X到Y的映射,若既是满射,又是入射,则称这个映射为双射双射。74-1 函数的概念函数的概念(续)(续)定理:定理:设X,Y为有限集,若X和Y的元素个数相同,即|X|=|Y|,则f:X Y是入射当且仅当它是满射。证明:若f是入射,则|X|=|f(X)|,由于f(X)Y,又因为|f(X)|=|Y|,而Y中的元素是有限的,因此f(X)=Y,即f是满射。若f是满射,则f(X)
4、=Y,于是|X|=|Y|=|f(X)|。因为|X|=|f(X)|,且X是有限的,故f是一个入射。注:注:这个定理必须在有限集情况下才成立。84-2 逆函数和复合函数逆函数和复合函数定理:定理:设f:X Y是双射函数,那么fc:Y X也是双射函数。证明:设f=x,y|(x X)(y Y)(f(x)=y)fc=y,x|x,yf因为f是满射,故对每一个y Y,必存在x,y f,则y,x fc,即fc的前域为Y。又因为f是入射,对每一个y Y,恰有一个x X,使得x,yf。因此仅有一个x X使得y,x fc,即y对应唯一的一个x,故fc是函数。又ran fc=dom f=X,故fc是满射。若y1y2,
5、有fc(y1)=fc(y2),因为fc(y1)=x1,fc(y2)=x2,即x1=x2,故 fc(y1)=fc(y2),即y1=y2,得到矛盾。因此fc是双射函数。94-2 逆函数和复合函数逆函数和复合函数(续)(续)定义:定义:设f:X Y是一个双射函数,称Y X的双射函数fc为f的逆函数逆函数,记作f-1。例1:设X=1,2,3,Y=p,q,Z=a,b,f=1,p,2,p,3,q,g=p,b,q,b,则gf=1,b,2,b,3,b定义:定义:设f:X Y,g:W Z,若f(X)W,则gf=x,z|(xX)(zZ)(y)(yY y=f(x)z=g(y),称g在函数f的左边可复合左边可复合。定
6、义:定义:设f:X Y,g:Y Z,则gf=x,z|(xX)(zZ)(y)(yYy=f(x)z=g(y),称为复合函数复合函数,或gf为g对f的左复合左复合。10定理:定理:两个函数的复合是一个函数。证明:设g:WZ,f:XY,为左复合,即f(X)W。4-2 逆函数和复合函数逆函数和复合函数(续)(续)(1)对任意的x X,因为f为函数,则必有唯一序偶x,y使得y=f(x)成立。而f(x)f(X),即f(x)W,又因为g是函数,故必有唯一的序偶y,z使得z=g(y)成立,根据复合定义,x,z gf,即X中每个x对应Z中某个z。(2)假设gf中包含序偶x,z1和x,z2,且z1 z2,则在Y中必
7、存在y1和y2,满足在f中有x,y1和x,y2,在g中有y1,z1和y2,z2,因为f是一个函数,故y1=y2。于是g中有y1,z1和y2,z2,但g是一个函数,故z1 z2,即每个x X,只能有唯一的x,z gf。11定理:定理:令g f为复合函数。(1)若g和f为满射,则g f为满射。(2)若g和f为入射,则g f为入射。(2)若g和f为双射,则g f为双射。证明:(1)设f:XY,g:YZ,令z为Z的任意元素,因为g是满射,故必有某个元素y Y,使得g(y)=z。又因为f是满射,故必有某个元素x X,使得f(x)=y。故而g f(x)=g(f(x)=g(y)=z因此,Rgf=Z,g f是
8、满射。4-2 逆函数和复合函数逆函数和复合函数(续)(续)12(2)设x1,x2为X的元素,假定x1 x2,因为f是入射,故f(x1)f(x2)。又因为g是入射,且f(x1)f(x2),故g(f(x1)g(f(x2),即x1x2 gf(x1)gf(x2),因此gf是入射。(3)因为g和f是双射,根据(1)(2),g f为满射和入射,则g f为双射。4-2 逆函数和复合函数逆函数和复合函数(续)(续)例2:设R为实数集合,对x R,有f(x)=x+2,g(x)=x-2,h(x)=3x。求g f与h (g f)注:注:一般有h (g f)=(h g)f,即函数的复合是可结合的。因此可以将括号去掉。
9、解:gf=x,x|x Rh (g f)=x,3x|x R134-2 逆函数和复合函数逆函数和复合函数(续)(续)定义:定义:函数f:X Y称作常函数常函数,如果存在某个y0 Y,对于每个x X,都有f(x)=y0,即f(X)=y0。定理:定理:若函数f:X Y有逆函数f-1:Y X,则f=f Ix=Iy f。定理:定理:若函数f:X Y有逆函数f-1:Y X,则f-1f=Ix,ff-1=Iy证明:f-1f与Ix的定义与均为X。因为f为一一对应的函数,因此f-1也为一一对应。若f:x f(x),则f-1(f(x)=x,得到f-1f=Ix,故x X f-1f(x)=f-1(f(x)=x定义:定义:
10、如果Ix=x,x|xX,则称函数Ix:X X为恒恒等函数等函数。144-2 逆函数和复合函数逆函数和复合函数(续)(续)定理:定理:若f:X Y是一一对应的函数,则(f-1)-1=f。证明:(1)因为f为一一对应的,因此f-1也为一一对应。则(f-1)-1也是一一对应的。显然dom f=dom(f-1)-1=X。(2)x X f:x f(x)f-1:f(x)x (f-1)-1:x f(x)。得证(f-1)-1=f。154-2 逆函数和复合函数逆函数和复合函数(续)(续)定理:定理:若函数f:X Y,g:Y X均为一一对应的函数,则(g f)-1=f-1g-1证明:(1)因为f,g为一一对应的函
11、数,因此f-1,g-1存在,且f-1:Y X,g-1:Z Y,所以f-1g-1:Z X。又,f,g为双射,故g f为双射,因此(g f)-1存在且(g f)-1:Z X。dom(f-1g-1)=dom(g f)-1=Z(2)对任意z Z 存在唯一y Y,使得g(y)=z 存在唯一x X,使得f(x)=z,故(f-1g-1)(z)=(f-1(g-1(z)=f-1(y)=x。但(g f)(x)=g(f(x)=g(y)=z,故(g f)-1(z)=x,因此对任意z Z,有(g f)-1(z)=(f-1g-1)(z)。可知(g f)-1=(f-1g-1)。164-4 基数的概念基数的概念定义:定义:给
展开阅读全文