离散数学左孝凌4

,第二级,第三级,第四级,第五级,计算机学院,第四章 函数（,Functions,）,4.1,函数的基本概念,(The concept of function),4.2,复合函数与逆函数,(Compositions of functions and Inverse functions ),4.1,函数的基本概念,(The concept of function),4.1.1,函数的基本概念,4.1.2,特殊函数类,(Special functions),4.1.1,函数的基本概念,函数概念是最基本的数学概念之一，也是最重要的数学工具。初中数学中函数定义为,对自变量每一确定值都有一确定的值与之对应,的因变量；高中数学中函数又被定义为两集合元素之间的映射。,现在，我们要把后一个定义作进一步的深化，用一个特殊关系来具体规定这一映射，称这个特殊关系为函数，因为关系是一个集合，从而又将函数作为集合来研究。离散结构之间的函数关系在计算机科学研究中也已显示出极其重要的意义。我们在讨论函数的一般特征时，总把注意力集中在离散结构之间的函数关系上，但这并不意味着这些讨论不适用于其它函数关系。,考虑下面几个由图示表示的集合,A,到集合,B,的关系（见图,4.1.1,）。,在这个关系中， 后个关系,R,3,，,R,4,，,R,5,，,R,6,与,R,1,，,R,2,不同， 它们都有下面两个特点：,（,1,） 其定义域为,A,；,（,2,）,A,中任一元素,a,对应唯一一个,B,中的元素,b,。,图,4.1.1,几个关系的示图,图,4.1.1,几个关系的示图,图,4.1.1,几个关系的示图,定义,4-1,.1,设,X,和,Y,是任何两个集合，而,f,是,X,到,Y,的一个关系（,f,X,Y,），如果对于每一个,x,X,，,都有唯一,的,y,Y,，使,f,。则称,f,是,X,到,Y,的,函数,（,functions,），记为,f,：,X,Y,，,当,X=X,1,X,n,时，称,f,为,n,元函数,。函数也称,映射,（,mapping,）或,变换,(,transformation,）,。,换言之，函数是特殊的关系，它满足,（,1,）函数的定义域是,X,，而不能是,X,的某个真子集,(,即,dom(,f,)=X),。,（,2,）若,x,y,f,，,x,y,f,，则,y,y,（单值,性）。,图,4.1.2,由于函数的第二个特性，人们常把,x,y,f,或,xfy,这两种关系表示形式，在,f,为函数时改为,y,=,f,(,x,),。这时称,x,为自变量，,y,为函数在,x,处的值；也称,y,为,x,在,f,作用下的像,(,image of,x under f,),，,x,为,y,的原像。一个自变量只能有唯一的像，但不同的自变量允许有共同的像。,注意，函数的上述表示形式不适用于一般关系。（因为一般关系不具有单值性。）,【,例,1】,设,A,=,a,b,B,=1,2,3,，判断下列集合是否是,A,到,B,的函数。,F,1,=,a,1,b,2,F,2,=,a,1,b,1,，,F,3,=,a,1,a,2,F,4,=,a,3,【,例,2】,下列关系中哪些能构成函数？,（,1,）,x,y,|,x,y,N,x,+,y,10,（,2,）,x,y,|,x,y,N,x,+,y,=10,（,3,）,x,y,|,x,y,R,|,x,|=,y,（,4,）,x,y,|,x,y,R,x,=|,y,|,（,5,）,x,y,|,x,y,R,|,x,|=|,y,|,对于函数,f,：,X,Y,f,的前域,dom(,f,)=,X,就是函数,y= f,(,x,),的定义域,有时也记为,D,f,f,的值域,ran(,f,),Y,有时也记为,R,f,即,R,f,=,Y,称为,f,的共域, ran(,f,)=,R,f,也称为,f,的像集合, dom(,f,)=,X,=,D,f,也称为,f,的原像集。对于,A,X,，称,f,(,A,),为,A,的像（,image of A,），定义为,f,(,A,)=,显然,f,( )= ,f,(,x,)=,f,(,x,)(,x,A,),。,定义,4-1.2,设函数,f:AB,，,g:CD,，如果,A=C,，,B=D,，且对所有,x,A,和,x,C,，都有,f(x)=g(x),，则称,函数,f,等于函数,g,记为,f=g,。,如果,A,C,，,B,D,，且对每一,x,A,，,f(x),g(x),。则称,函数,f,包含于函数,g,，记为,f,g,。,设,X,和,Y,都是有限集合，,X,= m,，,Y,= n,，由于从,X,到,Y,任意一个函数,f,的定义域都是,X,，每一个,f,都有,m,个序偶,（象存在性），那么,f,f: X,Y,的基数为,n,m,。即共有,n,m,个,X,到,Y,的函数,。,【,例,3】,设,A,=,a,b,B,=1,2,3,。由,A,B,能生成多少个不同的函数？由,B,A,能生成多少个不同的函数？,解,:,设,f,i,:,A,B,(,i,=1,2,，,9),g,i,:,B,A,(,i,=1,2,，,8),f,1,=,a,1,b,1,g,1,=1,a,2,a,3,a,f,2,=,a,1,b,2,g,2,=1,a,2,a,3,b,f,3,=,a,1,b,3,g,3,=1,a,2,b,3,a,f,4,=,a,2,b,1,g,4,=1,a,2,b,3,b,f,5,=,a,2,b,2,g,5,=1,b,2,a,3,a,f,6,=,a,2,b,3,g,6,=1,a,2,a,3,b,f,7,=,a,3,b,1,g,7,=1,b,2,a,3,b,f,8,=,a,3,b,2,g,8,=1,b,2,b,3,b,f,9,=,a,3,b,3,定理,设,|X|=,m,，,|,Y,|=,n,，那么,f,|,f,:,X,Y,的基数为,n,m,，即共有,n,m,个,X,到,Y,的函数。,证明,设,X,=,x,1,x,2,x,m,Y,=,y,1,y,2,y,n,，那么每一个,f,:,X,Y,由一张如下的表来规定,:,x,x,1,x,2,x,m,f,(,x,),x,i1,x,i2,x,im,其中,x,i,1,，,x,i,2,，,，,x,im,为取自,y,1,，,y,2,，,，,y,n,的允许元素重复的排列，这种排列总数为,n,m,个。因此，上述形式的表恰有,n,m,张，恰对应全部,n,m,个,X,到,Y,的函数。,由于上述缘故，当,X,Y,是有穷集合时，我们以,Y,X,记所有,X,到,Y,的全体函数的集合：,Y,X,=,f,|,f,:,X,Y,则,|,Y,X,|=|,Y,|,|,X,|,。,特别地,X,X,表示,X,上函数的全体。目前在计算机科学中，也用,X,Y,替代,Y,X,。,定义,4-1.3,、,4,、,5,设,f,：,XY,。,（,1,）如果对任意,y,Y,，均有,x,X,，使,y=f(x),，即,ran f=Y,，则称,f,为,X,到,Y,的满射函数,(,surjection,),，满射函数也称,到上映射,。,（,2,）如果对任意,x,1,，,x,2,X , x,1,x,2,蕴涵,f(x,1,),f(x,2,),。则称,f,为,X,到,Y,的入射函数,(,injection,),， 入射函数也称,一对一,的函数,或,单射函数,。,（,3,）如果,f,既是,X,到,Y,的满射,，,又是,X,到,Y,的入射,，则称,f,为,X,到,Y,的双射函数,（,bijection,）,。双射函数也称,一一对应,。,4-1.2,特殊函数,图,4.1.1,几个关系的示图,图,4.1.1,几个关系的示图,下图说明了这三类函数之间的关系。注意，既非单射又非满射的函数是大量存在的。,【,例,1】,对于给定的,f,和集合,A,，请判断,f,性质,(,类型,),；并求,A,在,f,下的像,f,(,A,),。,(1),f,:,R,R,，,f,(,x,)=,x,，,A,=8,(2),f,:,N,N,N,，,f,(,x,)=,x,x,+1,，,A,=2,5,(3),f,:,Z,N,，,f,(,x,)=|,x,|,，,A,=-1,2,(4),f,:,S,R,，,S,=,0,+),，,A,=,0,7),(5),f,: 0,1,a,b,a,b,f,(,x,)=(,b,-,a,),x,+,a,A,=0,1/2),解,:,（,1,）,f,是双射，,f,(,A,)=,f,(8)=8,(2),f,是单射，,f,(,A,)=,f,(2,5)=2,3, 5,6,(3),f,是满射，,f,(,A,)=,f,(-1,，,2)=1,，,2,(4),f,是单射，,f,(,A,)=,f,(,0,7)=,（,1/8,，,1,(,5,),f,是双射，,f,(,A,)=,f,(0,1/2)=,a,(,a,+,b,)/2),定理,4-1.1,令,X,和,Y,为有限集，若,X,和,Y,的元素个数相同，即,X,=,Y,，则有,f:XY,是入射,当且仅当,它是一个满射,。, 证明思路：,a.,先证,f:XY,是入射,它是一个满射,若,f,是入射，则,X,=,f(X),(,一对一映射源的个数,=,象的个数,),。因为,f(X),=,Y,(,由定理条件,X,=,Y,，,象的个数,=Y,的元素个数,),和,f(X),Y,。又因为,Y,是有限集合，故,f(X),=Y,。,f:XY,是满射，,b.,再证,f:XY,是一个满射,它是入射,若,f,是满射（,f(X),=Y,），则,X,=,Y,=,f(X),。,又因为,X,是有限集合，源的个数,=,象的个数，所以,f:XY,是入射。,此定理不适用于无限集合上的映射。,作业,4-1,P151 (1),(4),(5),(6),4-2.1,逆函数,(Inverse function),4-2.2,复合函数,(Compositions of functions),4-2,逆函数和复合函数,考虑函数,f,：,A,B, f,的逆关系,f,c,是,B,到,A,关系,但,f,c,可能不是函数。一方面,如果,f,不是单射,则,f,c,不是函数,另一方面,如果,f,不是满射,则,f,c,也不是函数。,因此我们有如下定理,:,定理,4-2.1,设,f:XY,是一个双射函数，则,f,c,为,Y,到,X,的双射函数，即有,f,c,:YX,。,此定理可以分三步证明：,4-2.1,逆函数,证明：,a).,先证,f,c,是一个函数,（需要证,存在性,和,唯一性,）,设,f= | x,X,y,Y,f(x)=y,和,f,c,= | ,f,因,f,是双射，所以,f,是满射，即所有的,y,Y,都有,x,与它对应，这正是,f,c,的,存在性,。,又因,f,是双射，所以,f,是入射，即所有的,y,Y,都只有唯一的,x,与它对应，这正是,f,c,的,唯一性,。,b).,二证,f,c,是一个满射,又因,ran,f,c,=dom,f=X, f,c,是满射。,c).,三证,f,c,是一个单射,反设 若,y,1,y,2,有,f,c,(,y,1,)=,f,c,(,y,2,),因为,f,c,(,y,1,)=x,1,f,c,(,y,2,)=x,2,得,x,1,=x,2,，故,f,(x,1,)=,f,(x,2,),，,即,y,1,=,f,(x,1,)=,f,(x,2,)=,y,2,。,得出矛盾，假设不成立。,定理证毕。 ,定义,4-2.1,设,f:XY,是一个,双射函数，称,YX,的双射函数,f,C,为,f,的,逆函数，,记为,f,-1,。,今后谈到一个函数的逆函数时， 都是指双射的逆函数。 由定义知， 若,f,(,a,),b,， 则有,f,-1,(,b,),a,。,因为函数是一种特殊的关系，所以和关系一样也有复合运算。对于函数的复合我们有下面的定义：,4-2.2,复合函数,定义,4-2.2,设函数,f:XY,g:WZ,若,f(X),W,，,则,g,f=,|x,X,z,Z,(,y)(,y,Y,y=f(x),z,=g(y),称,g,在函数,f,的左边可复合。,定理,4-2.2,两个函数的复合是一个函数。,证明：设,g:WZ,f:XY,为左复合,即,f(X),W,，,a).,先证象,存在性,对于任意,x,X,因为,f,为函数，故必有唯一的序偶,使,y=f(x),成立。而,f(x),f(X),，即,f(x), W,，又因为,g,是函数，,故,对于任意的,y,Y,必有唯一的序偶,使,z=g(y),成立,根据复合定义，,g,f,。即,X,中的每个,x,对应,Z,中的某个,z,。,b).,再证象,唯一性,假定,g,f,中包含序偶,和,且,z,1,z,2,，这样在,Y,中必存在,y,1,和,y,2,，使得在,f,中有,和,在,g,中有,和,。因为,f,为函数，故,y,1,=y,2,。于是,g,中有,和,但,g,为函数,，,故,z,1,=z,2,。即每个,x,只能对应一个唯一的,z,，满足,g,f,。,由,a).,和,b).,知,g,f,是一个函数。,定理证毕。 ,我们注意到，,x,z,f,g,是指有,y,使,x,y,f,，,y,z,g,，即,y,=,f,(,x,),，,z=,g,(,y,)=,g,(,f,(,x,),，因而,f,g,(,x,)=,g,(,f,(,x,),。,这就是说，当,f,g,为函数时，它们的复合作用于自变量的次序刚好与合成的原始记号的顺序相反。故我们约定把两个函数,f,和,g,的复合记为,g,f,复合函数的图示,【,例,1】,设,A,=1, 2,3,4,B,=1,2,3,4,5,C,=1, 2, 3,。,f,:,A,B,，,f,=1,2,2,1,3,3,4,5,g,:,B,C,，,g,=1,1,2,2,3,3, 4,3, 5,2,求,g,。,f,。,解,:,g,。,f,=1,2,2,1,3,3,4,2,用关系图图示,g,。,f,，其中表示,g,。,f,见图,【,例,2】,设,f,，,g,均为实函数，,f,(,x,)=2,x,+1,g,(,x,)=,x,2,+1,求,f,。,g,，,g,。,f,，,f,。,f,，,g,。,g,。,解,f,。,g,(,x,)=,f,(,g,(,x,)=2(,x,2,+1)+1=2,x,2,+3,g,。,f,(,x,)=,g,(,f,(,x,)=(2,x,+1),2+1=4,x,2,+4,x,+2,f,。,f,(,x,)=,f,(,f,(,x,)=2(2,x,+1)+1=4,x,+3,g,。,g,(,x,)=,g,(,g,(,x,)=(,x,2,+1),2,+1=,x,4,+2,x,2,+2,定理,4-2.3,设,f:XY,，,g:YZ,，,g,f,是一个复合函数，则,（,1,）如果,f,和,g,是满射的，则,g,f,也是满射的。,（,2,）如果,f,和,g,是单射的，则,g,f,也是单射。,（,3,）如果,f,和,g,是双射的，则,g,f,也是双射的。,证明：,a).,设,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,因此，,R,g,f,=Z,，,g,f,是满射的。,b).,设令,x,1,、,x,2,为,X,的元素，假定,x,1,x,2,，因为,f,是入射的,故,f(x,1,),f(x,2,),。又因为,g,是入射的,故,g(f(x,1,),g(f(x,2,),于是,x,1,x,2,g,f(x,1,) g,f(x,2,),，,因此，,g,f,是入射的,。,c).,因为,g,和,f,是双射，故根据,a).,和,b),，,g,f,为满射和入射的，即,g,f,是双射的。,定理证毕。 ,定义,4-2.3,函数,f:XY,叫做常函数,如果存在某个,y,0,Y,对于每个,x,X,都有,f(x)=,y,0,即,f(X)=,y,0,。,定义,4-2.4,如果,I,x,= | x,X,则称函数,I,x,:XX,为恒等函数。,证明：,a).,f,-1,f,与,I,x,的定义域都是,X,。,b).,因为,f,是一一对应的函数，故,f,-1,也是一一对应的函数。,若,f: x,f(x),则,f,-1,(f(x) =x,由,a).,和,b).,得,f,-1,f=,I,x,。故,x,X,(,f,-1,f)(x),=,f,-1,(f(x) =x,。,定理证毕。,例题,3,见,P-155,页,定理,4-2.5,如果函数,f:XY,，有逆函数,f,-1,:YX,则,f,-1,f =,I,x,且,f,f,-1,=,I,y,定理,4-2.4,设,f,：,XY,，则,f=f,I,x,=,I,y,f,证明：,a).,因,f,:XY,是一一对应的函数，故,f,-1,:YX,也是一一对应的函数。因此,(f,-1,),-1,:XY,又是一一对应的函数。显然,dom,f,= dom,(f,-1,),-1,=,X,b).,设,x,X,f: x,f(x),f,-1,:,f(x),x,(f,-1,),-1,: x,f(x),。,由,a).,和,b).,得,(f,-1,),-1,= f,。,定理证毕。,定理,4-2.6,若,f:XY,是一一对应的函数，则,(f,-1,),-1,= f,。,定理,4-2.7,设,f:XY,g:YZ,均为一一对应函数,则,(g,f),1,=,f,-1,g,1,。,证明：,a).,因,f:XY,g:YZ,都是,一一对应的函数,故,f,-1,和,g,-1,均存在，且,f,-1,:YX,，,g,-1,:ZY,，,所以,f,-1,g,1,:ZX,。,根据定理,4-2.3,，,g,f:XZ,是双射的，故,(g,f),1,存在且,(g,f),1,:ZX,。,dom,(,f,-1,g,1,),= dom,(g,f),1,=,Z,b).,对任意,z,Z,存在唯一,y,Y,使得,g(y)=z,存在唯一,x,X,使得,f(x)=y,故,(,f,-1,g,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,-1,g,1,)(z),由,a).,和,b).,得,(,f,-1,g,1,),=,(g,f),1,。,定理证毕。,作业,4-2,P156 (1),(3),结 束,谢 谢,!,