离散数学-二元关系和函数

*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,4.6 函数的定义与性质,函数的定义,函数定义,从,A,到,B,的函数,函数的像,函数的性质,函数的单射、满射、双射性,构造双射函数,应用实例：问题描述,1,函数定义,定义,设,F,为二元关系,若,x,dom,F,都存在唯一的,y,ran,F,使,xFy,成立,则称,F,为,函数,.对于函数,F,如果有,xFy,则记作,y,=,F,(,x,),并称,y,为,F,在,x,的,值,.,例1,F,1,=,F,2,=,F,1,是函数,F,2,不是函数,2,函数相等,定义,设,F,G,为函数,则 ,F,=,G,F,G,G,F,如果两个函数,F,和,G,相等,一定满足下面两个条件：(1)dom,F,=dom,G,(2),x,dom,F,=dom,G,都有,F,(,x,)=,G,(,x,),实例 函数,F,(,x,)=(,x,2,1)/(,x,+1),G,(,x,)=,x,1,不相等,因为 dom,F,dom,G,.,3,从,A,到,B,的函数,定义,设,A,B,为集合,如果,f,为函数,dom,f,=,A,ran,f,B,则称,f,为,从,A,到,B,的函数,记作,f,：,A,B,.,实例,f,：,N,N,f,(,x,)=2,x,是从,N,到,N,的函数,g,：,N,N,g,(,x,)=2也是从,N,到,N,的函数,4,B,上,A,定义,所有从,A,到,B,的函数的集合记作,B,A,读作“,B,上,A,”，符号化表示为 ,B,A,=,f,|,f,：,A,B,计数：,|,A,|=,m,|,B,|=,n,且,m,n,0,|,BA,|=,n,m,.,A,=,则,B,A,=,B,=,.,A,且,B,=,则,B,A,=,A,=,.,5,实例,例2 设,A,=1,2,3,B,=,a,b,求,B,A,.,解,B,A,=,f,0,f,1,f,7,其中,f,0,=,f,1,=,f,2,=,，,f,3,=,f,4,=,，,f,5,=,f,6,=,f,7,=,6,函数的像,定义,设函数,f,：,A,B,A,1,A,.,A,1,在,f,下的像,：,f,(,A,1,)=,f,(,x,)|,x,A,1,函数的像,f,(,A,)注意：函数值,f,(,x,),B,而像,f,(,A,1,),B,.,例3,设,f,：,N,N,且,令,A,=0,1,B,=2,那么有,f,(,A,)=,f,(0,1)=,f,(0),f,(1)=0,2,7,函数的性质,定义,设,f,：,A,B,（1）若ran,f,=,B,则称,f,：,A,B,是,满射,的.（2）若,y,ran,f,都存在唯一的,x,A,使得,f,(,x,)=,y,则称,f,：,A,B,是,单射,的.（3）若,f,：,A,B,既是满射又是单射的,则称,f,：,A,B,是,双射,的,f,满射意味着：,y,B,都存在,x,A,使得,f,(,x,)=,y,.,f,单射意味着：,f,(,x,1,)=,f,(,x,2,),x,1,=,x,2,8,实例,例4,判断下面函数是否为单射,满射,双射的,为什么?(1),f,：RR,f,(,x,)=,x,2,+2,x,1(2),f,：Z,+,R,f,(,x,)=ln,x,Z,+,为正整数集(3),f,：RZ,f,(,x,)=,x,(4),f,：RR,f,(,x,)=2,x,+1(5),f,：R,+,R,+,f,(,x,)=(,x,2,+1)/,x,其中R,+,为正实数集.,9,解(1),f,：RR,f,(,x,)=,x,2,+2,x,1,在,x,=1取得极大值0.既不单射也不满射.(2),f,：Z,+,R,f,(,x,)=ln,x,单调上升,是单射.但不满射,ran,f,=ln1,ln2,.,(3),f,：RZ,f,(,x,)=,x,满射,但不单射,例如,f,(1.5)=,f,(1.2)=1.(4),f,：RR,f,(,x,)=2,x,+1,满射、单射、双射,因为它是单调的并且ran,f,=R.(5),f,：R,+,R,+,f,(,x,)=(,x,2,+1)/,x,有极小值,f,(1)=2.该函数既不单射也不满射.,实例（续）,10,构造从,A,到,B,的双射函数,有穷集之间的构造,例5,A,=,P,(1,2,3),B,=0,1,1,2,3,解,A,=,1,2,3,1,2,1,3,2,3,1,2,3.,B,=,f,0,f,1,f,7,其中,f,0,=,f,1,=,f,2,=,f,3,=,f,4,=,f,5,=,f,6,=,f,7,=,.,令,f,：,A,B,f,(,)=,f,0,f,(1)=,f,1,f,(2)=,f,2,f,(3)=,f,3,f,(1,2)=,f,4,f,(1,3)=,f,5,f,(2,3)=,f,6,f,(1,2,3)=,f,7,11,实数区间之间构造双射,构造方法：直线方程,例6,A,=0,1,B,=1/4,1/2构造双射,f,:,A,B,构造从,A,到,B,的双射函数（续）,解,令,f,：0,11/4,1/2,f,(,x,)=(,x,+1)/4,12,构造从,A,到,B,的双射函数（续）,A,与自然数集合之间构造双射,方法：将A中元素排成有序图形，然后从第一个元素开始,按照次序与自然数对应,例7 A=Z,B,=N，构造双射,f,：,A,B,将Z中元素以下列顺序排列并与N中元素对应：,Z：0,11,22,33 N：0 1 2 3 4 5 6,则这种对应所表示的函数是：,13,常函数、恒等函数、单调函数,1.,设,f,：,A,B,若存在,c,B,使得,x,A,都有,f,(,x,)=,c,则称,f,：,A,B,是,常函数,.,2.称,A,上的恒等关系,I,A,为,A,上的,恒等函数,对所有,的,x,A,都有,I,A,(,x,)=,x,.,3.设,f,：,R,R,，如果对任意的,x,1,x,2,R，x,1,x,2,就,有,f,(,x,1,),f,(,x,2,),则称,f,为,单调递增,的；如果对任意,的,x,1,x,2,A,x,1,x,2,就有,f,(,x,1,),f,(,x,2,),则称,f,为,严,格单调递增,的.,类似可以定义,单调递减,和,严格单调递减,的函数,.,14,集合的特征函数,设,A,为集合,A,A,A,的,特征函数,A,：,A,0,1,定义为,实例 集合：,X,=A,B,C,D,E,F,G,H,子集：,T,=A,C,F,G,H,T,的特征函数,T,：,x,A,B,C,D E,F G H,T,(,x,),1 0 1 0 0 1 1 1,15,5.设,R,是,A,上的等价关系,令,g,：,A,A,/,R,g,(,a,)=,a,a,A,称,g,是从,A,到商集,A,/,R,的,自然映射,.,自然映射,16,实例,例8 (1),A,的每一个子集,A,都对应于一个特征函数,不同的子集对应于不同的特征函数.例如,A,=,a,b,c,则有 ,=,，,a,b,=,(2)给定集合,A,，,A,上不同的等价关系确定不同的自然映射,其中恒等关系确定的自然映射是双射,其他的自然映射一般来说是满射.例如,A,=1,2,3,R,=,I,A,g,(1)=,g,(2)=1,2,g,(3)=3,17,4.7 函数的复合与反函数,函数的复合,函数复合的定理,函数复合的性质,反函数,反函数存在的条件,反函数的性质,18,函数复合的定理,定理,设,F,G,是函数,则,F,G,也是函数,且满足 (1)dom(,F,G,)=,x,|,x,dom,F,F,(,x,)dom,G,(2),x,dom(,F,G,)有,F,G,(,x,)=,G,(,F,(,x,),推论1,设,F,G,H,为函数,则(,F,G,),H,和,F,(,G,H,),都是函数,且(,F,G,),H,=,F,(,G,H,),推论2,设,f,：,A,B,g,：,B,C,则,f,g,：,A,C,且,x,A,都有,f,g,(,x,)=,g,(,f,(,x,).,19,函数复合运算的性质,定理,设,f,：,A,B,g,：,B,C,.(1)如果,f,：,A,B,g,：,B,C,都是满射的,则,f,g,：,A,C,也是满射的.(2)如果,f,：,A,B,g,：,B,C,都是单射的,则,f,g,：,A,C,也是单射的.(3)如果,f,：,A,B,g,：,B,C,都是双射的,则,f,g,：,A,C,也是双射的.,证(1),c,C,由,g,：,B,C,的满射性,b,B,使得,g,(,b,)=,c,.对这个,b,由,f,：,A,B,的满射性，,a,A,使得,f,(,a,)=,b,.由合成定理有,f,g,(,a,)=,g,(,f,(,a,)=,g,(,b,)=,c,从而证明了,f,g,：,A,C,是满射的.,20,函数复合运算的性质,(2)假设存在,x,1,x,2,A,使得,f,g,(,x,1,)=,f,g,(,x,2,)由合成定理有,g,(,f,(,x,1,)=,g,(,f,(,x,2,).,因为,g,：,B,C,是单射的,故,f,(,x,1,)=,f,(,x,2,).又由,于,f,：,A,B,也是单射的,所以,x,1,=,x,2,.从而证,明,f,g,：,A,C,是单射的.,(3)由(1)和(2)得证.,定理,设,f,:,A,B,，则,f,=,f,I,B,=,I,A,f,21,反函数存在的条件,任给函数,F,它的逆,F,1,不一定是函数,是二元关系.,实例：,F,=,，,F,1,=,任给单射函数,f,：,A,B,则,f,1,是函数,且是从 ran,f,到,A,的双射函数,但不一定是从,B,到,A,的双射函数.,实例：,f,:N N,f,(,x,)=2,x,f,1,:ran,f,N,f,1,(,x,)=,x,/2,22,反函数,定理,设,f,：,A,B,是双射的,则,f,1,：,B,A,也是双射的.,证 因为,f,是函数,所以,f,1,是关系,且,dom,f,1,=ran,f,=,B,ran,f,1,=dom,f,=,A,对于任意的,y,B,=dom,f,1,假设有,x,1,x,2,A,使得,f,1,f,1,成立,则由逆的定义有,f,f,根据,f,的单射性可得,x,1,=,x,2,从而证明了,f,1,是函数，且是满射的.下面证明,f,1,的单射性.,若存在,y,1,y,2,B,使得,f,1,(,y,1,)=,f,1,(,y,2,)=,x,从而有,f,1,f,1,f,f,y,1,=,y,2,23,反函数的定义及性质,对于双射函数,f,：,A,B,称,f,1,：,B,A,是它的,反,函数,.,反函数的性质,定理,设,f,：,A,B,是双射的,则,f,1,f,=,I,B,f,f,1,=,I,A,对于双射函数,f,：,A,A,有,f,1,f,=,f,f,1,=,I,A,24,函数复合与反函数的计算,例 设,f,：RR,g,：RR,求,f,g,g,f,.如果,f,和,g,存在反函数,求出它们的反函数.,解,f,：RR不是双射的,不存在反函数.,g,：RR是双射的,它,的反函数是,g,1,：RR,g,1,(,x,)=,x,2,25,问题：,有2台机器,c,1,c,2,；,6项任务,t,1,t,2,t,6,.每项任务的加工时间分别为：,l,(,t,1,)=,l,(,t,3,)=,l,(,t,5,)=,l,(,t,6,)=1,l,(,t,2,)=,l,(,t,4,)=2,任务之间的顺序约束是：,任务,t,3,只有在,t,6,和,t,5,完成之后才能开始加工；,任务,t,2,只有在,t,6,t,5,和,t,4,都完成后才能开始加工；,任务,t,1,只有在,t,3,和,t,2,完成之后才能开始加工,.,调度：任务安排在机器上加工的方案,截止时间：开始时刻0，最后停止加工机器的停机时刻,问题描述多机调度,26,两个调度方案,D,=6,t,1,t,2,t,3,t,4,t,5,t,6,D,=5,t,1,t,3,t,5,t,2,t,6,t,4,t,5,t,6,t,4,t,3,t,2,t,