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

《离散数学-二元关系和函数.ppt》由会员分享，可在线阅读，更多相关《离散数学-二元关系和函数.ppt（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、4.6 函数的定义与性质函数的定义与性质n函数的定义函数的定义函数定义函数定义从从A到到B的函数的函数函数的像函数的像n函数的性质函数的性质函数的单射、满射、双射性函数的单射、满射、双射性构造双射函数构造双射函数n应用实例：问题描述应用实例：问题描述1函数定义函数定义定义定义设设F 为二元关系为二元关系,若若 xdomF 都存在都存在唯一的唯一的yranF 使使xFy 成立成立,则称则称F 为为函数函数.对于函数对于函数F,如果有如果有xFy,则记作则记作y=F(x),并称并称y 为为F 在在x 的的值值.例例1F1=,F2=,F1是函数是函数,F2不是函数不是函数2函数相等函数相等定义定义设

2、设F,G为函数为函数,则则F=G F GG F如果两个函数如果两个函数F 和和G 相等相等,一定满足下面两个条件：一定满足下面两个条件：(1)domF=domG(2)xdomF=domG 都有都有F(x)=G(x)实例实例函数函数F(x)=(x2 1)/(x+1),G(x)=x 1不相等不相等,因为因为domF domG.3从从 A 到到B 的函数的函数定义定义设设A,B为集合为集合,如果如果f 为函数为函数domf=A ranf B,则称则称f 为为从从A到到B的函数的函数,记作记作f：AB.实例实例f：NN,f(x)=2x 是从是从N 到到N 的函数的函数 g：NN,g(x)=2也是从也是

3、从N 到到N 的函数的函数4B上上A定义定义所有从所有从A 到到B 的函数的集合记作的函数的集合记作BA,读作读作“B上上A”，符号化表示为，符号化表示为BA=f|f：AB 计数：计数：|A|=m,|B|=n,且且m,n0,|BA|=nm.A=,则则BA=B=.A且且B=,则则BA=A=.5实例实例例例2设设A=1,2,3,B=a,b,求求BA.解解BA=f0,f1,f7,其中其中f0=,f1=,f2=,，f3=,f4=,，f5=,f6=,f7=,6函数的像函数的像定义定义设函数设函数f：AB,A1 A.A1在在f 下的像下的像：f(A1)=f(x)|xA1函数的像函数的像f(A)注意：函数值

4、注意：函数值f(x)B,而像而像f(A1)B.例例3 设设 f：NN,且且 令令A=0,1,B=2,那么有那么有f(A)=f(0,1)=f(0),f(1)=0,27函数的性质函数的性质定义定义设设f：AB,（1）若）若ranf=B,则称则称f：AB是是满射满射的的.（2）若）若 yranf 都存在唯一的都存在唯一的xA使得使得f(x)=y,则称则称f：AB是是单射单射的的.（3）若）若f：AB既是满射又是单射的既是满射又是单射的,则称则称f：AB是是双射双射的的f满射意味着：满射意味着：y B,都存在都存在x A使得使得 f(x)=y.f 单射意味着：单射意味着：f(x1)=f(x2)x1=x

5、28实例实例例例4判断下面函数是否为单射判断下面函数是否为单射,满射满射,双射的双射的,为什么为什么?(1)f：RR,f(x)=x2+2x 1(2)f：Z+R,f(x)=lnx,Z+为正整数集为正整数集(3)f：RZ,f(x)=x(4)f：RR,f(x)=2x+1(5)f：R+R+,f(x)=(x2+1)/x,其中其中R+为正实数集为正实数集.9解解(1)f：RR,f(x)=x2+2x 1在在x=1取得极大值取得极大值0.既不单射也不满射既不单射也不满射.(2)f：Z+R,f(x)=lnx单调上升单调上升,是单射是单射.但不满射但不满射,ranf=ln1,ln2,.(3)f：RZ,f(x)=x

6、 满射满射,但不单射但不单射,例如例如f(1.5)=f(1.2)=1.(4)f：RR,f(x)=2x+1满射、单射、双射满射、单射、双射,因为它是单调的并且因为它是单调的并且ranf=R.(5)f：R+R+,f(x)=(x2+1)/x有极小值有极小值f(1)=2.该函数既不单射也不满射该函数既不单射也不满射.实例（续）实例（续）10构造从构造从A到到B的双射函数的双射函数有穷集之间的构造有穷集之间的构造例例5A=P(1,2,3),B=0,11,2,3解解 A=,1,2,3,1,2,1,3,2,3,1,2,3.B=f0,f1,f7,其中其中f0=,f1=,f2=,f3=,f4=,f5=,f6=,

7、f7=,.令令f：AB,f()=f0,f(1)=f1,f(2)=f2,f(3)=f3,f(1,2)=f4,f(1,3)=f5,f(2,3)=f6,f(1,2,3)=f711实数区间之间构造双射实数区间之间构造双射构造方法：直线方程构造方法：直线方程例例6A=0,1B=1/4,1/2构造双射构造双射f:AB构造从构造从A到到B的双射函数（续）的双射函数（续）解解令令f：0,11/4,1/2 f(x)=(x+1)/412构造从构造从A到到B的双射函数（续）的双射函数（续）A A 与自然数集合之间构造双射与自然数集合之间构造双射方法：将方法：将A中元素排成有序图形，然后从第一个元素开始中元素排成有序

8、图形，然后从第一个元素开始按照次序与自然数对应按照次序与自然数对应例例7A=Z,B=N，构造双射，构造双射f：AB将将Z中元素以下列顺序排列并与中元素以下列顺序排列并与N中元素对应：中元素对应：Z：0 11 22 33N：0123456则这种对应所表示的函数是：则这种对应所表示的函数是：13常函数、恒等函数、单调函数常函数、恒等函数、单调函数 1.设设f：AB,若存在若存在cB 使得使得 xA 都有都有f(x)=c,则称则称f：AB是是常函数常函数.2.称称A 上的恒等关系上的恒等关系IA为为A 上的上的恒等函数恒等函数,对所有对所有的的xA 都有都有IA(x)=x.3.设设f：RR，如果对任

9、意的，如果对任意的x1,x2R，x1x2,就就有有f(x1)f(x2),则称则称f 为为单调递增单调递增的；如果对任的；如果对任意意的的x1,x2A,x1x2,就有就有f(x1)f(x2),则称则称f 为为严严格单调递增格单调递增的的.类似可以定义类似可以定义单调递减单调递减和和严格单调递减严格单调递减的函数的函数.14集合的特征函数集合的特征函数4.设设A 为集合为集合,A A,A的的特征函数特征函数 A：A0,1定义为定义为实例实例集合：集合：X=A,B,C,D,E,F,G,H,子集：子集：T=A,C,F,G,HT 的特征函数的特征函数 T：xABCDEFGH T(x)1010011115

10、5.设设R 是是A 上的等价关系上的等价关系,令令g：AA/Rg(a)=a,aA称称g 是从是从A 到商集到商集A/R 的的自然映射自然映射.自然映射自然映射 16实例实例例例8(1)A的每一个子集的每一个子集A都对应于一个特征函都对应于一个特征函数数,不同的子集对应于不同的特征函数不同的子集对应于不同的特征函数.例如例如A=a,b,c,则有则有=,，a,b=,(2)给定集合给定集合A，A 上不同的等价关系确定不上不同的等价关系确定不同的自然映射同的自然映射,其中恒等关系确定的自然映射其中恒等关系确定的自然映射是双射是双射,其他的自然映射一般来说是满射其他的自然映射一般来说是满射.例如例如 A

11、=1,2,3,R=,IA g(1)=g(2)=1,2,g(3)=3174.7 函数的复合与反函数函数的复合与反函数n函数的复合函数的复合函数复合的定理函数复合的定理函数复合的性质函数复合的性质n反函数反函数反函数存在的条件反函数存在的条件反函数的性质反函数的性质18函数复合的定理函数复合的定理定理定理设设F,G是函数是函数,则则F G也是函数也是函数,且满足且满足(1)dom(F G)=x|xdomF F(x)domG(2)xdom(F G)有有F G(x)=G(F(x)推论推论1设设F,G,H为函数为函数,则则(F G)H 和和F(G H)都是函数都是函数,且且(F G)H=F(G H)推论

12、推论2设设f：AB,g：BC,则则f g：AC,且且 xA 都有都有f g(x)=g(f(x).19函数复合运算的性质函数复合运算的性质定理定理设设f：AB,g：BC.(1)如果如果f：AB,g：BC 都是满射的都是满射的,则则f g：AC也是满射的也是满射的.(2)如果如果f：AB,g：BC 都是单射的都是单射的,则则f g：AC也是单射的也是单射的.(3)如果如果f：AB,g：BC 都是双射的都是双射的,则则f g：AC也是双射的也是双射的.证证(1)cC,由由g：BC 的满射性的满射性,bB 使得使得g(b)=c.对这个对这个b,由由f：AB 的满射性，的满射性，aA 使得使得f(a)=

13、b.由合成定理有由合成定理有f g(a)=g(f(a)=g(b)=c从而证明了从而证明了f g：AC是满射的是满射的.20函数复合运算的性质函数复合运算的性质(2)假设存在假设存在x1,x2A使得使得f g(x1)=f g(x2)由合成定理有由合成定理有g(f(x1)=g(f(x2).因为因为g：BC是单射的是单射的,故故f(x1)=f(x2).又又由由于于f：AB也是单射的也是单射的,所以所以x1=x2.从而证从而证明明f g：AC是单射的是单射的.(3)由由(1)和和(2)得证得证.定理定理设设f:AB，则，则f=f IB=IA f 21反函数存在的条件反函数存在的条件任给函数任给函数F,

14、它的逆它的逆F 1不一定是函数不一定是函数,是二元关系是二元关系.实例：实例：F=,，F 1=,任给单射函数任给单射函数f：AB,则则f 1是函数是函数,且是从且是从ranf 到到A的双射函数的双射函数,但不一定是从但不一定是从B 到到A 的双的双射函数射函数.实例：实例：f:NN,f(x)=2x,f 1:ranfN,f 1(x)=x/222反函数反函数定理定理设设f：AB是双射的是双射的,则则f 1：BA也是双射的也是双射的.证证因为因为f 是函数是函数,所以所以f 1是关系是关系,且且dom f 1=ranf=B,ran f 1=domf=A,对于任意的对于任意的yB=dom f 1,假设

15、有假设有x1,x2A使得使得f 1f 1成立成立,则由逆的定义有则由逆的定义有ff根据根据f 的单射性可得的单射性可得x1=x2,从而证明了从而证明了f 1是函数，且是是函数，且是满射的满射的.下面证明下面证明f 1的单射性的单射性.若存在若存在y1,y2B 使得使得f 1(y1)=f 1(y2)=x,从而有从而有f 1f 1ffy1=y223反函数的定义及性质反函数的定义及性质对于双射函数对于双射函数f：AB,称称f 1：BA是它的是它的反反函数函数.反函数的性质反函数的性质定理定理 设设f：AB是双射的是双射的,则则f 1 f=IB,f f 1=IA对于双射函数对于双射函数f：AA,有有f

16、 1 f=f f 1=IA24函数复合与反函数的计算函数复合与反函数的计算例例设设f：RR,g：RR 求求f g,g f.如果如果f 和和g 存在反函数存在反函数,求出它们的反函数求出它们的反函数.解解 f：RR不是双射的不是双射的,不存在反函数不存在反函数.g：RR是双射的是双射的,它它的反函数是的反函数是g 1：RR,g 1(x)=x 225问题：问题：有有2台机器台机器c1,c2；6项任务项任务t1,t2,t6.每项任务的加工时间分别为：每项任务的加工时间分别为：l(t1)=l(t3)=l(t5)=l(t6)=1,l(t2)=l(t4)=2任务之间的顺序约束是：任务之间的顺序约束是：任务

17、任务t3只有在只有在t6和和t5完成之后才能开始加工；完成之后才能开始加工；任务任务t2只有在只有在t6,t5和和t4都完成后才能开始加工；都完成后才能开始加工；任务任务t1只有在只有在t3和和t2完成之后才能开始加工完成之后才能开始加工.调度：任务安排在机器上加工的方案调度：任务安排在机器上加工的方案截止时间：开始时刻截止时间：开始时刻0，最后停止加工机器的停机时刻，最后停止加工机器的停机时刻问题描述问题描述多机调度多机调度26两个调度方案两个调度方案 D=6t1t2t3t4t5t6D=5t1t3t5t2t6t4t5 t6t4t3 t2t127n集合集合任务集任务集T=t1,t2,.,tn,

18、n Z+机器集机器集M=c1,c2,.,cm，m Z+时间集时间集Nn函数函数和关系和关系加工时间加工时间函数函数l:TZ+.顺序约束顺序约束R T上的上的偏序关系偏序关系，定义为，定义为R=|ti,tj T,i=j 或或ti完成后完成后tj 才可以开始加工才可以开始加工问题描述问题描述28问题描述（续）问题描述（续）n可行调度可行调度分配到机器：分配到机器：T 的的划分划分=T1,T2,.,Tm，划分块，划分块Tj 是是T 的非空子集，的非空子集，由安排在机器由安排在机器cj上加工的所有任务组成上加工的所有任务组成.每个机器上的任务开始时间每个机器上的任务开始时间 Tj，存在，存在调度函数调

19、度函数 j:TjN，满足以下条件：满足以下条件：(1)任意时刻任意时刻i，每台机器上正在加工至多，每台机器上正在加工至多1个任务个任务 i,0 iD,|tk|tk Tj,j(tk)i j(tk)+l(tk)|1,j=1,2,m(2)任务的安排满足偏序约束任务的安排满足偏序约束 ti Ti,tj Tj,R i(ti)+l(ti)j(tj)i,j=1,2,m29问题描述（续）问题描述（续）机器机器j 的停止时间的停止时间Dj=max j(tk)|tk Tj+l(tk)所有任务的截止时间所有任务的截止时间D=maxDj|j=1,2,.,m.我们的问题就是确定使得我们的问题就是确定使得D达到最小的可行调度达到最小的可行调度.30