离散数学函数.ppt

单击此处编辑母版标题样式,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,离散数学,西安交通大学,电子与信息工程学院,计算机系,1,离散数学,第三章 函数,1.函数的基本概念,2.函数的复合,2,离散数学,第三章 函数（function）,1.函数基本概念,定义1.,函数(映射(map)、变换(transformation),函数是后者唯一的关系。即,f,是由X到Y的函数，记为,f,:,X,Y,f,XY(,x,X)(,y,Y)(,z,Y)(,x,y,),f,(,x,z,),f,y=z,),。,注：函数概念主要是限制了关系概念中的一对多；但允许多对一；,f,Y,f,(,a,),a,X,函数的图象,3,离散数学,b,a,1,a,2,X,Y,函数允许的情况：多对一,f,a,b,1,b,2,f,函数不允许的情况：一对多,X,Y,4,离散数学,D(,f,),R(,f,),X,Y,f,函数的定义域和值域,5,离散数学,与函数概念关联着的一些概念,(1)若,(,x,y,),f,，则,函数惯用的记法是,y,=,f,(,x,)；称,x,为自变量，,称,y,为因变量。,(2)此定义可容纳多值函数,f,:,X,Y ，,f,(,x,),=,y,1,y,2,y,k,其修改为,f,:,X,2,Y,，,f,(,x,),=,y,1,y,2,y,k,2,Y,。,(3)定义域(domain)：称,f,的前域为,f,的定义域。即,D(,f,)=,x,:,x,X(,y,Y)(,x,y,),f,),=,x,:,x,X(,y,Y)(,y,=,f,(,x,),(4)值域(range)：称,f,的后域为,f,的值域。即,R(,f,)=,y,:,y,Y(,x,X)(,x,y,),f,),=,y,:,y,Y(,x,X)(,y,=,f,(,x,)。,6,离散数学,(5)象(image)：子集A X的象定义为,f,(,A,)=,y,:,y,Y(,x,A)(,x,y,),f,),=,y,:,y,Y(,x,A)(,y,=,f,(,x,)。,f,X,Y,集合的象,A,D(,f,),f,(,A,),R(,f,),7,离散数学,(6)逆象(inverse image)：子集BY的逆象定义为,f,-1,(B)=,x,:,x,X(,y,B)(,x,y,),f,),=,x,:,x,X(,y,B)(,y,=,f,(,x,)；,特别地，单元素,y,Y的逆象是,f,-1,(,y,)=,x,:,x,X(,x,y,),f,=,x,:,x,X,f,(,x,),=,y,。,X,Y,f,-1,(,B,),集合的逆象,B,D(,f,),R(,f,),f,8,离散数学,(7)全函数（full function）：处处有定义的函数。即,D(,f,)=X（或者,f,-1,(Y)=X）,今后，在本课程中，除非有特别声明，我们一概研究全函数。,(8)偏函数(partial function)：部分有定义的函数。即,D(,f,)X（或者,f,-1,(Y)X）。,X,D(,f,),D(,f,)X,9,离散数学,例1.,截痕函数(cross function)：,f,:,X,2,XY,，,f,(,x,),=,x,Y,。,例,2.,计算机是一个函数。即,计算机,:,输入空间输出空间；,编译,是一个函数。即,编译,:,源程序目标程序。,XY,x,Y,Y,X,x,10,离散数学,例,3.,绝对值函数(absolute value function),f,=,(,x,|,x,|,),:,x,R(这里R是实数集)或者,f,:,R,R,+,0，,f,(,x,),=,|,x,|,(这里R,+,=,x,:,x,R,x,0是正实数集)，于是,D(,f,)=R,R(,f,)=R,+,0；,绝对值函数可以拆成两个函数的并。即,f,=,f,1,f,2,，这里,f,1,=,(,x,x,),:,x,R,x,0，,D(,f,1,)=R,+,0,R(,f,1,)=R,+,0；,f,2,=,(,x,-x,),:,x,R,x,0，,D(,f,2,)=R,-,R(,f,2,)=R,+,；,(这里R,-,=,x,:,x,R,x,0是负实数集)，于是；,11,离散数学,D(,f,)=D(,f,1,)D(,f,2,)=R,R(,f,)=R(,f,1,)R(,f,2,)=R,+,0；,绝对值函数也可采用下面分段定义的形式。即,。,例,4.,后继函数(successor function),后继函数也称为Peano函数。,设(X,)是一全序集，并且每个元素的后继存在，即,(,x,X)(,y,X)(,x,+,=,y,)，,则关系,P=(,x,y,),:,x,X,y,X,x,+,=,y,是一函数，即所谓的后继函数。记作,12,离散数学,s,:,X,X，对任何,x,X,s,(,x,),=,x,+,=,x,+1,这里加1表示后继，并非都是普通的算术加1。例如,若,就是,普通的小于等于,全序，则,当,X=I(整数集)时，,s,(-6)=-6+1=-5,s,(1)=1+1=2，相当于,普通算术的加1；,当,X=E(偶整数集)时，,s,(-6)=-6+1=-4,s,(2)=2+1=4，相当于,普通算术的加2；,当,X=n,:,n,I,3,n,(3倍数整数集)时，,s,(-3)=-3+1=0,s,(9)=9+1=12，相当于,普通算术的加3。,例,5.,第一章2定义2定义的集合的并运算是一函数。即,f,(2,X,2,X,),2,X,，,f,=(,(,x,y,),z,),:,x,y,z,2,X,z=x,y,13,离散数学,这里(,x,y,)是前者，,z,是后者；或者,f,:,2,X,2,X,2,X,，,f,(,x,y,),=,z=x,y，,这里(,x,y,)是自变量，,z,是因变量；,因此,f,=,。,例,6.,函数未必都有统一的表达式。不象连续函数那样大多都有统一的表达式，离散函数大多都没有统一的表达式。,一种定义离散函数的方式是采用下面的分段定义形式。即,f,:,N N,。,14,离散数学,例,7.,函数未必都很复杂。一些简单的函数可以逐点来定义。,g,:,1,2,3 A,B,C,g,(1)=A，,g,(2)=C，,g,(3)=C,其函数映射可用图形表示如下：,例,8.,投影函数（projection function）,u,n,i,:,X,1,X,2,X,n,X,i,u,n,i,(,x,1,x,2,x,n,),=,x,i,(i=1,2,n),g,1,2,3,A,B,C,15,离散数学,定义2.,函数的相等,函数的相等是,逐点,相等。即,设,f,g,是由X到Y的两个函数，,f,g,:,X,Y，,则,f,=,g,(,x,X)(,f,(,x,),=,g,(,x,),)。,定义3.,运算(operation),对于任何自然数n,1,，n元运算,f,是一个从n维叉积X,n,到X的函数。即,f,:,X,n,X,。,一般说来，,运算具有以下两个特点：,(1)定义较,一般,函数特殊；,(2)易可操作性；,特别地，一元运算,f,:,X,X；,二元运算,f,:,X,XX。,16,离散数学,例,9.,集合的补运算,:,2,X,2,X,是,一元运算；,集合的交,，,并运算,:,2,X,2,X,2,X,是二,元运算,。,关于,运算，我们主要考虑其封闭性。,n,元,运算,f,的封闭性,：对于任何,n个元素,x,1,x,2,x,n,，,x,1,x,2,x,n,X,f,(,x,1,x,2,x,n,)X ，,或者(,x,1,x,2,x,n,),X,n,f,(,x,1,x,2,x,n,)X 。,17,离散数学,例,10.,集合的特征函数：对于任何集合AX，我们定义A的特征函数,A,:,X,0,1 如下,A,(,x,)=,于是我们有,A,(,x,)=1-,A,(,x,),AB,(,x,)=,A,(,x,).,B,(,x,),AB,(,x,)=,A,(,x,)+,B,(,x,)-,AB,(,x,),AB(,x,X)(,A,(,x,),B,(,x,),),A=B(,x,X)(,A,(,x,),=,B,(,x,),),A=(,x,X)(,A,(,x,),=0),A=X(,x,X)(,A,(,x,),=1)。,18,离散数学,例,11.,单位函数或幺函数(identity function)：,幺函数即是幺关系。用函数的记法，即是,I,X,:,X,X,对任何,x,X，,I,X,(,x,)=,x,。,显然D(,I,X,)=R(,I,X,)=X 。,19,离散数学,定义4.,单射满射双射,(injection,surjection,bijection),设,f,是从,X,到,Y,的函数，即,f,:,X,Y,。则我们称,(1),f,是单射(内射),函数,(,x,1,X)(,x,2,X)(,x,1,x,2,f,(,x,1,),f,(,x,2,),),(,x,1,X)(,x,2,X)(,f,(,x,1,)=,f,(,x,2,),x,1,=,x,2,)；,(2),f,是满射,函数,(,y,Y)(,x,X)(,f,(,x,)=,y,),R(,f,)=Y,f,(X)=Y,；,(3),f,是双射,函数,f,既是单射,函数,又是满射,函数,。,20,离散数学,注：,单射,函数概念主要是限制了函数概念中的多对一；允许的是一对一；,满射,函数概念主要是不允许函数的后集中有元素无前集中元素和其对应；,在有限集的情况，,双,射,函数的存在，保证前集和后集一样大小。即,|X|,=,|Y|,在有限集的情况，若,|X|,=,|Y|,，则可证：,f,是单射,函数,f,是满射,函数,f,是双射,函数,这可由鸽巢原理证明。留给学者。,21,离散数学,满射函数不允许的情况,b,Y,R(,f,),D(,f,),f,a,1,a,2,b,X,Y,f,单射函数不允许的情况,D(,f,),R(,f,),22,离散数学,例14.,设 X=a,b,c,d,Y=1,2,3,4,f,:,X,Y,f,(a)=1,f,(b)=2,f,(c)=3,f,(d)=4,则,f,是从X到Y的双射函数。,例15.,设X,Y都是实数的集合，,f,:,X,Y,f,=(,x,y,),:,x,X,y,Y,y,=sin(,x,),若,X,=,Y,=R正弦函数,f,既不是满射,函数,也不是单射,函数；,若将Y限制在-1,1 之间，X=R，则,f,是满射函数，但非单射函数；,若将X限制在-/2,/2 之间，Y=R，则,f,是单射函数，但非满射函数；,若将X限制在-/2,/2 之间，Y限制在-1,1 之间，则,f,是双射函数。,23,离散数学,定理1.,逆(反)函数(,inverse function,),双射函数,f,:,X,Y的逆关系,Y,X是一个从Y到X的双射函数；我们称其为,f,的逆函数，记为,f,1,:,Y,X。,证,.,(采用：逻辑法),(1)后者唯一(即 是函数)：,对于任何,y,Y,，对于任何,x,1,x,2,X,(,y,x,1,),(,y,x,2,),(,x,1,y,),f,(,x,2,y,),f,f,(,x,1,)=,y,f,(,x,2,)=,y,f,(,x,1,)=,f,(,x,2,)(等号=的对称性，传递性),x,1,=,x,2,(,f,是,双射，故,f,是,单射),24,离散数学,(2)是全函数：,D(,)=,y,:,y,Y(,x,X)(,y,x,),),=,y,:,y,Y(,x,X)(,x,y,),f,),=R(,f,),=Y (,f,是,双射，故,f,是,满,射),(3)是单射：,对于任何,y,1,y,2,Y,(,y,1,)=(,y,2,),(,x,X)(,(,y,1,)=,x,(,y,2,)=,x,)(是全函数),(,x,X)(,f,(,x,)=,y,1,f,(,x,)=,y,2,),25,离散数学,(,x,X)(,x,y,1,),f,(,x,y,2,),f,),y,1,=,y,2,(,f,是函数,后者唯一；,(4)是满射：,R,()=,x,:,x,X(,y,Y)(,y,x,),),=,x,:,x,X(,y,Y)(,x,y,),f,),=D,(,f,),=X (,f,是全函数)。,定理2.,设,f,:,X,Y是一双射函数。则,f,的逆函数(作为逆运算 ),f,1,:,Y,X满足,反身性：(,f,1,),-1,=,f,；,证,.,函数是关系，关系的反身性前面已证。,26,离散数学,2.函数的复合,定义1.,函数的复合运算,设,f,:,X,Y,g,:,Y,Z 是两个函数。则合成关系,f,g,=(,x,z,),:,x,X,z,Z(,y,Y)(,x,y,),f,(,y,z,),g,),=(,x,z,),:,x,X,z,Z(,y,Y)(,f,(,x,)=,y,g,(,y,)=,z,),称为函数,f,和,g,的复合(运算)，,f,g,称为函数,f,和,g,的复合函数。记为,g,f,:,X,对任何,x,X，有,(,g,f,)(,x,)=,g,(,f,(,x,)。,注：函数的复合其实就是关系的合成；只不过记法上有所不同；,函数的复合是(向)左复合，右(边)优先；而关系的合成是(向)右复合，左(边)优先；,27,离散数学,定义1的合理性证明,.,要证如下两点：,(1),g,f,后者唯一 (即,g,f,是函数),对于任何,x,X，若存在着,z,1,z,2,Z，使,(,g,f,)(,x,)=,z,1,(,g,f,)(,x,)=,z,2,(,x,z,1,),g,f,(,x,z,2,),g,f,(,y,1,Y)(,x,y,1,),f,(,y,1,z,1,),g,),(,y,2,Y)(,x,y,2,),f,(,y,2,z,2,),g,),(,y,Y)(,x,y,),f,(,y,z,1,),g,(,y,z,2,),g,),(由于,f,是函数，故后者唯一，,所以,y,1,=,y,2,=,y,),(,y,Y)(,y,z,1,),g,),(,y,z,2,),g,),z,1,=,z,2,(由于,g,是函数，故后者唯一),28,离散数学,(2),g,f,是全函数,根据复合函数的定义，显然有D,(,g,f,),X；,另一方面：对于任何,x,，,x,X,(,y,Y)(,x,y,),f,)(条件：,f,是全的，故D(,f,)=,X,),对于任何y，,y,Y,(zZ)(y,z,)g)(条件：,g,是全的，故D(,g,)=Y,),x,X,(,y,Y)(,x,y,),f,(y,z)g),(x,z),g,f,x,D(,g,f,),所以,X,D(,g,f,),；,所以 D(,g,f,)=,X,。,29,离散数学,例1.,设 X=1,2,3,f,:,X,X,f,=(1,2),(2,3),(3,1)，,g,:,X,X,g,=(1,2),(2,1),(3,3)，则,g,f,=(1,1),(2,3),(3,2)，,f,g,=(1,3),(2,2),(3,1)。,注：从上例可知：函数复合没有交换律，即,g,f,f,g,；,但是函数复合仍是关系的合成，因此有关关系合成的几乎所有性质都适用于函数的复合，尤其是结合律。,f,:,X,Y,g,:,Y,Z,h,:,Z,W,则有,函数复合的结合律,：,h,(,g,f,),=,(,h,g,),f,。,30,离散数学,定义2.,函数的复合幂,设,f,:,X,X,是一函数。那么我们定义：,(1),f,1,=,f,f,n+1,=,f,f,n,；,（注意与关系合成幂的不同之处）,(2)若,f,2,=,f,，则称,f,是幂等函数。,例2.,设,f,:,I,I,f,(,x,)=3,x,+2,。于是,f,(,x,)=,f,(,f,(,x,)=3,f,(,x,)+2=3(3,x,+2)+2,=3,x,+3,2+2=3,x,+8,f,(,x,)=,f,(,f,(,x,)=3,f,(,x,)+2=3(3,x,+8)+2,=3,x,+3,8+2=3,3,x,+26,一般地，我们猜测,f,n,(,x,)=3,n,x,+3,n,-1，则有,f,n+1,(,x,)=,f,(,f,n,(,x,)=3,f,n,(,x,)+2=3(3,n,x,+3,n,-1,)+2,=3,n+1,x,+3,n+1,-3,+2=3,n+1,x,+3,n+1,-1,。,31,离散数学,定理1.,设,f,:,X,Y,g,:,Y,Z 是两个函数。则,(1),f,和,g,都是单射函数,g,f,也是单射函数；,(2),f,和,g,都是满射函数,g,f,也是满射函数；,(3),f,和,g,都是双射函数,g,f,也是双射函数。,证,.,(采用逻辑法),只证(1)和(2)；(3)由(1)和(2)是显然的。,(1)对于任何,x,1,x,2,X,(,g,f,)(,x,1,)=(,g,f,)(,x,2,),g,(,f,(,x,1,)=,g,(,f,(,x,2,),),f,(,x,1,)=,f,(,x,2,),(,g,是单射),x,1,=,x,2,(,f,是单射),所以,g,f,是单射；,32,离散数学,(2)对于任何,z,z,Z,(,y,Y)(,y,z,),g,),(,g,是满射),(,y,Y)(,x,X)(,x,y,),f,)(,y,z,),g,),(,f,是满射),(,x,X)(,y,Y)(,x,y,),f,(,y,z,),g,),(,x,X)(,x,z,),g,f,),所以 (,z,Z)(,x,X)(,x,z,),g,f,),所以,g,f,是满射。,33,离散数学,定理2.,设,f,:,X,Y 是双射函数。则,(1),f,1,f,=I,X,；,(2),f,f,1,=I,Y,。,证,.,只证(1),对于任何,x,X,(,f,1,f,)(,x,)=,f,1,(,f,(,x,),=,f,1,(,y,),(由于D(,f,)=X，因而有某个,y,Y，使,f,(,x,)=,y,),=,x,(,f,(,x,)=,y,，故,f,1,(,y,)=,x,),=I,X,(,x,),所以,f,1,f,=I,X,。,34,离散数学,定义3.,置换(permutation),设X,，,|X|=n，X=,x,1,x,2,x,n,。则我们,称,P为X上的一个(n次)置换,P是从X到X的一个双射函数，即 P,:,X,X。并且称n为置换P的阶。,注：所有n次置换构成的集合记为S,n,；,在,n,个元素的集合中，不同的,n,阶置换的个数为,n!，即|S,n,|=n!；,35,离散数学,通常用下面的方法表示X上的一个(n次)置换,；,若,x,i,X 有 P(x,i,)=x,i,，则称P是恒等置换,记为I,可表示为,；,P的逆函数,P,-1,称为,P,的逆置换,，,可表示为,置换的合成运算是作为关系的合成运算，而不是作为函数的复合运算,=。,置换的合成运算满足结合律，但不满足交换律。,36,离散数学,重点要求,要求掌握函数的基本概念,弄清单射,、,满射,、,双射之间的区别。给定一个函数,要能够确定它是否是单射,、,满射,、,双射等。,掌握反函数和复合函数的定义和性质,并弄清楚它们存在的条件。,理解元素及集合的象及原象的定义及相关的性质。给定一个函数,能够确定一个点的象,一个集合的象,能够确定一个点的原象,一个集合的原象,能够确定两个函数的复合函数等。,掌握集合的势,、可数集、不可数集等概念,。,37,离散数学,第三章函数,到此已经结束！,谢谢读者收看！,38,