《离散数学 第2版 教学课件 ppt 作者 尤枫 第05章 函数》由会员分享，可在线阅读，更多相关《离散数学 第2版 教学课件 ppt 作者 尤枫 第05章 函数（103页珍藏版）》请在金锄头文库上搜索。
1、第5章 函 数,第5章 函数,5.1 基本概念,第5章 函数,定义5-1 设A和B是任意给定的两个集合，f是从A 到B的二元关系，若对于任意的xA，存在 唯一的yB，使得f，则称关系f为 从A到B的一个函数。记作f:AB。 若有f，则称x是像源或自变量，y称为在 f作用下x的像，或f在x处的函数值。一般用y=f(x)表 示f。 显然，f的定义域D(f)=A，值域V(f)B，并且 V(f)=y|yB(x)(xAy=f(x),5.1 基本概念,第5章 函数,【例5-1】设X=a,b,c,d，Y=1,2,3,4,5， f=,， 则f是一个从X到Y的函数，并且 D(f)=a,b,c,d V(f)=1,
2、3,4 f(a)=1,f(b)=3,f(c)=4,f(d)=4。,5.1 基本概念,第5章 函数,关系和函数的区别如下： (1)函数的定义域必须等于A，而关系的定义域可以 是A，也可以是A的一个真子集； (2)作为关系，一个x可以对应多个不同的y；而作为 函数，一个x只能对应一个y。 所以说，函数一定是关系，而关系未必是函数。,5.1 基本概念,第5章 函数,【例5-2】设X=1,2,3,4，Y=a,b,c,d。下列关系 中哪些是函数？哪些不是函数？ f1=, f2=, f3=, f4=, 解 f1和f2都是函数； f3不是，因为3X，但没有对应的y值； f4也不是，因为1对应了两个不同的值a
3、和b。,5.1 基本概念,第5章 函数,定理5-1 设A,B都是有限集，|A|=m,|B|=n， 则从A到B共有nm个不同的函数。 证明 因为任何一个从A到B的函数f，其定义域都是 A，即f中共有m个序偶；另外，对于任意的 xA，可以对应Y的n个元素中的任何一个。 因此，从A到B共有nm个不同的函数。 通常用BA表示从A到B的所有不同函数构成的集合， 即 BA =f|f:AB,5.1 基本概念,第5章 函数,【例5-3】设X=a,b,c,Y=0,1，求YX。 解 从X到Y共有23=8个不同的函数，因此， YX =f1,f2,f3,f4,f5,f6,f7,f8 其中， f1=, f2=, f3=
4、, f4=, f5=, f6=, f7=, f8=,5.1 基本概念,第5章 函数,定义5-2 设f,g都是从A到B的函数，它们有相同的定 义域和值域，并且对任意的xA，都有 f(x)=g(x)，则称函数f与g相等，记作f=g。 定义5-3 设有函数f:XY，AX， (1) 构造一个函数g:AY，使得对任意的 xA，都有g(x)=f(x),则称g是f的缩小， 记作f/A； (2) 若g是f的缩小，则称f是g的扩大。,5.1 基本概念,第5章 函数,【例5-4】设X=a,b,c,d,Y=0,1， 函数f:XY定义为 f(a)=f(b)=0 f(c)=f(d)=1 令A=a,c，函数g:AY定义为
5、 g(a)=0，g(c)=1 则是的缩小，同时，是的扩大。,5.1 基本概念,第5章 函数,定义5-4 设有集合A和B，AA，若函数f:AB在 A-A上无定义，则称f是从A到B的偏函数。 【例5-5】设R是实数集合，R+是正实数集合，显然 有R+R。函数f:R+R定义为：对任意的 xR+， 则f是从R到R的偏函数。 因为在R-R+区域内，f没有定义。,5.1 基本概念,第5章 函数,定义5-5 给定函数f:XY (1) 若V(f)=Y，则称f是满射的； (2) 对任意的x1,x2X，当x1x2时必有f(x1)f(x2)或 当f(x1)=f(x2)时必有x1=x2，则称f是单射的（一对 一映射）
6、； (3) 若f既是满射的又是单射的，则称f为双射的(一一 对应映射)。 具有这些性质的函数分别叫做满射函数、单射函 数或双射函数。,5.1 基本概念,第5章 函数,【例5-6】设有如下4个函数： f1:a,b,c,d1,2,3, f1=, f2:a,b,c1,2,3,4，f2=, f3:a,b,c1,2,3，f3=, f4:a,b,c1,2,3，f4=, 则 f1是满射的，f2是单射的， f3是双射的，f4非满射非单射。,5.1 基本概念,第5章 函数,当X,Y都是有限集合时 1) f为满射的必要条件是|Y|X|； 2) f为单射的必要条件是|X|Y|； 3) f为双射的必要条件是|X|=|
7、Y|。,5.1 基本概念,第5章 函数,定义5-6 设有函数f：AB，若存在某个y0B,使得 对任意的xA，都有f(x)=y0，即V(f)=y0， 则称f为常值函数。 常值函数不是单射函数。,5.1 基本概念,第5章 函数,【例5-7】设A=a,b,c,B=0,1， 函数f：AB定义为： f(a)=f(b)=f(c)=1 即 f=, 函数g：AB定义为： g(a)=g(b)=g(c)=0 即 g=, 则f,g都是常值函数。,5.1 基本概念,第5章 函数,定义5-7 若函数Ix:XX，对任意的xX， 都有Ix(x)=x，即：Ix=(x,x)|xX， 则称Ix是恒等函数。 恒等函数是双射函数。,
8、5.1 基本概念,第5章 函数,【例5-8】设A=a,b,c,B=1,2,3，下列函数中哪些 是恒等函数？ f1=, f2=, f3=, f4=, f5=, f6=, 解 f2和f4都是恒等函数。,5.2 复合函数和逆函数,第5章 函数,定义5-8 设有函数f:XY，g:YZ，则 gf=|xXzZ (y)(yYy=f(x)z=g(y) 称为f和g的复合函数。 复合函数的写法gf相当于复合关系的fg 由复合函数定义，有(gf)(x)=g(f(x)。,5.2 复合函数和逆函数,第5章 函数,定理5-2 设f:XY，g:YZ是两个函数， 则gf是XZ的函数。 证明 因f是函数，故对任意的xX，必存在
9、唯一的 yY，使得y=f(x)；又因g也是函数，对这个 y，必有唯一的zZ，使得 z=g(y)=g(f(x)=(gf)(x)， 即对任意的xX，存在唯一的zZ，使得 z=(gf)(x)。所以，gf是XZ的函数。,5.2 复合函数和逆函数,第5章 函数,【例5-9】设有集合X=a,b,c,Y=,Z=0,1， 函数f:XY定义为： f=, 函数g:YZ定义为： g=, 求复合函数gf。 解 gf=,。,5.2 复合函数和逆函数,第5章 函数,【例5-10】设有集合X=1,2,3，f,g都是定义在X上 的函数，并且 f=, g=, 求复合函数gf和fg。 解 fg=, gf=, 显然fggf。,5.
10、2 复合函数和逆函数,第5章 函数,定理5-3 函数的复合运算满足结合律。即若 f:XY, g:YZ, h:ZW都是函数， 则h(gf)=(hg)f。 证明 对于任意的xX，由合成函数的定义，有 (h(gf)(x)=h(gf)(x) =h(g(f(x) =(hg)(f(x) =(hg)f)(x) 所以 h(gf)=(hg)f,5.2 复合函数和逆函数,第5章 函数,由于函数复合满足结合律，因此，当有多个函 数复合时，为书写简洁起见，往往省去括号。如 h(gf)或(hg)f就直接写成hgf。 特别地，当f是定义在某个集合X上的函数时，f 可与其自身进行任意次复合。归纳定义如下： (1) f 0(
11、x)=x，f 0=Ix； (2) f n+1(x)=f(f n(x)=f n(f(x)。,5.2 复合函数和逆函数,第5章 函数,定义5-9 给定函数f:XX，如有f 2=f， 则称f是幂等函数。 【例5-11】设I=0,1,2,3，函数f:II定义为 f(i)=i(mod 2) 问f是否是幂等函数？ 解 因f=,， 且容易验证f 2=f，故f是幂等函数。 若f是幂等函数，则对任意的正整数n，都有f n=f。,5.2 复合函数和逆函数,第5章 函数,定理5-4 设有函数f：XY,g：YZ， (1) 若f,g都是满射的，则gf也是满射的； (2) 若f,g都是单射的，则gf也是单射的； (3)
12、若f,g都是双射的，则gf也是双射的。 证明(1) 任取一个zZ，因g是满射的，故至少存在 一个yY，使得g(y)=z，因f也是满射的，对这个y， 至少存在一个xX，使得f(x)=y，即 z=g(y)=g(f(x)=gf(x)。所以，gf是满射的。,5.2 复合函数和逆函数,第5章 函数,证明(2) 设有x1,x2X，并且x1x2。因f是单射的，故 f(x1)f(x2)，又因g也是单射的，故 g(f(x1)g(f(x2)，即(gf)(x1)(gf)(x2)。 于是，由x1x2得出(gf)(x1)(gf)(x2)。所 以，gf也是单射的。 证明(3) 因f,g都是双射的，即f,g既是满射的又是单
13、 射的，由(1), (2)知，gf既是满射的又是单 射的，因此，gf是双射的。,5.2 复合函数和逆函数,第5章 函数,定理5-5 设有函数f:XY，Ix是X上的恒等函数，Iy是 Y上的恒等函数，则f=fIx=Iyf。 证明 对任意的xX，因Ix(x)=x，于是有 (fIx)(x)=f(Ix(x)=f(x)，所以 fIx=f。 同理可证 fIy=f 定义5-10 设f：XY是一个双射函数，称f的逆关系 为f的逆函数，记作f- -1 。 若f的逆函数f- -1存在，则称f是可逆的。,5.2 复合函数和逆函数,第5章 函数,【例5-12】设A=a,b,c，B=1,2,3， f:AB，f=, g:A
14、B，g=, h:AB，h=, 问函数f,g和h是否可逆？若是，求逆函数。 解 f是可逆的。 f-1:BA，f-1=, 因g和h都不是双射函数，故都不存在逆函数。,5.2 复合函数和逆函数,第5章 函数,定理5-6 若f:XY是双射函数，则逆函数f-1：YX 也是双射函数。 定理5-7 若函数f:XY是可逆的，则 (1) f-1f=Ix (2) ff-1=Iy (3) (f-1)-1=f,5.2 复合函数和逆函数,第5章 函数,证明 (1) 由复合函数的定义知， f-1f是从X到X的函数。 对于任意的xX，设f(x)=y，则f -1(y)=x， 于是 (f -1f)(x)=f -1(f(x)=
15、f -1(y)=x 由于x是任意的，因此，f -1f=Ix。 证明(2) 证明过程与(1)类似。,5.2 复合函数和逆函数,第5章 函数,证明(3) 因f可逆，故f是一个从X到Y的双射函数， 由定理5-6， f-1是从Y到X的双射函数， (f-1)-1是从X到Y的双射函数。 对任意的 ff -1 (f-1)-1 因此 (f -1)-1=f。,5.2 复合函数和逆函数,第5章 函数,定理5-8 若f:XY，g:YZ都是可逆函数，则gf也 是可逆函数，并且 (gf)-1=f -1g-1 证明 因f,g都是可逆的，故f,g都是双射的， 由定理5-4，gf也是双射的， 因此，gf也是可逆的。,5.2 复合函数和逆函数,第5章 函数,对任意的zZ，存在唯一的yY，使得g(y)=z， 对这个y，又存在唯一的xX，使得f(x)=y， 因此，g-1(z)=y，f -1(y)=x。 (f -1
