《离散数学-二元关系和函数.ppt》由会员分享，可在线阅读，更多相关《离散数学-二元关系和函数.ppt（30页珍藏版）》请在三一办公上搜索。
1、1,4.6 函数的定义与性质,函数的定义函数定义从A到B的函数函数的像函数的性质函数的单射、满射、双射性构造双射函数应用实例：问题描述,2,函数定义,定义 设 F 为二元关系,若 xdomF 都存在唯一的yranF 使 xFy 成立,则称 F 为函数.对于函数F,如果有 xFy,则记作 y=F(x),并称 y 为 F 在 x 的值.,例1 F1=,F2=,F1是函数,F2不是函数,3,函数相等,定义 设F,G为函数,则 F=G FGGF 如果两个函数 F 和 G 相等,一定满足下面两个条件：(1)domF=domG(2)xdomF=domG 都有 F(x)=G(x)实例 函数 F(x)=(x2
2、1)/(x+1),G(x)=x1不相等,因为 domFdomG.,4,从 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也是从 N 到 N 的函数,5,B上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=.,6,实例,例2 设 A=1,2,3,B=a,b,求BA.解 BA=
3、f0,f1,f7,其中 f0=,f1=,f2=,，f3=,f4=,，f5=,f6=,f7=,7,函数的像,定义 设函数 f：AB,A1A.A1 在 f 下的像：f(A1)=f(x)|xA1 函数的像 f(A)注意：函数值 f(x)B,而像 f(A1)B.,例3 设 f：NN,且 令A=0,1,B=2,那么有 f(A)=f(0,1)=f(0),f(1)=0,2,8,函数的性质,定义 设 f：AB,（1）若ranf=B,则称 f：AB是满射的.（2）若 yranf 都存在唯一的 xA使得 f(x)=y,则称 f：AB是单射的.（3）若 f：AB既是满射又是单射的,则称 f：AB是双射的f 满射意味
4、着：y B,都存在 xA 使得 f(x)=y.f 单射意味着：f(x1)=f(x2)x1=x2,9,实例,例4 判断下面函数是否为单射,满射,双射的,为什么?(1)f：RR,f(x)=x2+2x1(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+为正实数集.,10,解(1)f：RR,f(x)=x2+2x1 在x=1取得极大值0.既不单射也不满射.(2)f：Z+R,f(x)=lnx 单调上升,是单射.但不满射,ranf=ln1,ln2,.(3)f：RZ,f(x)=x 满射,但不单
5、射,例如 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.该函数既不单射也不满射.,实例（续）,11,构造从A到B的双射函数,有穷集之间的构造例5 A=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=,f7=,.,令 f：AB,f()=f0,f(1)=f1,f(2)=f2,f(3)=f3,f(1,2)=f4,f(1,3)=f5,
6、f(2,3)=f6,f(1,2,3)=f7,12,实数区间之间构造双射构造方法：直线方程例6 A=0,1 B=1/4,1/2构造双射 f:AB,构造从A到B的双射函数（续）,解 令 f：0,11/4,1/2 f(x)=(x+1)/4,13,构造从A到B的双射函数（续）,A 与自然数集合之间构造双射方法：将A中元素排成有序图形，然后从第一个元素开始 按照次序与自然数对应例7 A=Z,B=N，构造双射 f：AB将Z中元素以下列顺序排列并与N中元素对应：Z：011 2233 N：0 1 2 3 4 5 6 则这种对应所表示的函数是：,14,常函数、恒等函数、单调函数,1.设f：AB,若存在 cB 使
7、得 xA 都有 f(x)=c,则称 f：AB是常函数.2.称 A 上的恒等关系 IA为 A 上的恒等函数,对所有 的 xA 都有 IA(x)=x.3.设 f：RR，如果对任意的 x1,x2R，x1x2,就 有 f(x1)f(x2),则称 f 为单调递增的；如果对任意 的 x1,x2A,x1 x2,就有 f(x1)f(x2),则称 f 为 严 格单调递增 的.类似可以定义单调递减 和严格单调递减 的函数.,15,集合的特征函数,设 A 为集合,A A,A 的 特征函数 A：A0,1 定义为,实例 集合：X=A,B,C,D,E,F,G,H,子集：T=A,C,F,G,H T 的特征函数T：x A B
8、 C D E F G H T(x)1 0 1 0 0 1 1 1,16,5.设 R 是 A 上的等价关系,令g：AA/Rg(a)=a,aA称 g 是从 A 到商集 A/R 的自然映射.,自然映射,17,实例,例8(1)A的每一个子集A都对应于一个特征函数,不同的子集对应于不同的特征函数.例如 A=a,b,c,则有=,，a,b=,(2)给定集合 A，A 上不同的等价关系确定不同的自然映射,其中恒等关系确定的自然映射是双射,其他的自然映射一般来说是满射.例如 A=1,2,3,R=,IA g(1)=g(2)=1,2,g(3)=3,18,4.7 函数的复合与反函数,函数的复合函数复合的定理函数复合的性
9、质反函数反函数存在的条件反函数的性质,19,函数复合的定理,定理 设F,G是函数,则FG也是函数,且满足(1)dom(FG)=x|xdomF F(x)domG(2)xdom(FG)有 FG(x)=G(F(x)推论1 设F,G,H为函数,则(FG)H 和 F(GH)都是函数,且(FG)H=F(GH)推论2 设 f：AB,g：BC,则 fg：AC,且 xA 都有 fg(x)=g(f(x).,20,函数复合运算的性质,定理 设 f：AB,g：BC.(1)如果 f：AB,g：BC 都是满射的,则 fg：AC也是满射的.(2)如果 f：AB,g：BC 都是单射的,则 fg：AC也是单射的.(3)如果 f
10、：AB,g：BC 都是双射的,则 fg：AC也是双射的.证(1)cC,由 g：BC 的满射性,bB 使得 g(b)=c.对这个b,由 f：AB 的满射性，aA 使得 f(a)=b.由合成定理有 fg(a)=g(f(a)=g(b)=c 从而证明了 fg：AC是满射的.,21,函数复合运算的性质,(2)假设存在 x1,x2A使得 fg(x1)=fg(x2)由合成定理有 g(f(x1)=g(f(x2).因为 g：BC是单射的,故 f(x1)=f(x2).又由 于 f：AB也是单射的,所以 x1=x2.从而证 明 fg：AC是单射的.(3)由(1)和(2)得证.定理 设 f:AB，则 f=fIB=IA
11、f,22,反函数存在的条件,任给函数 F,它的逆F 1不一定是函数,是二元关系.实例：F=,，F 1=,任给单射函数 f：AB,则 f 1是函数,且是从 ranf 到 A的双射函数,但不一定是从 B 到 A 的双射函数.实例：f:N N,f(x)=2x,f 1:ranf N,f 1(x)=x/2,23,反函数,定理 设 f：AB是双射的,则f 1：BA也是双射的.证 因为 f 是函数,所以 f 1 是关系,且 dom f 1=ranf=B,ran f 1=domf=A,对于任意的 yB=dom f 1,假设有x1,x2A使得f 1f 1成立,则由逆的定义有ff根据 f 的单射性可得 x1=x2
12、,从而证明了f 1是函数，且是满射的.下面证明 f 1 的单射性.若存在 y1,y2B 使得 f 1(y1)=f 1(y2)=x,从而有f 1f 1 ff y1=y2,24,反函数的定义及性质,对于双射函数f：AB,称 f 1：BA是它的反函数.反函数的性质定理 设 f：AB是双射的,则f 1f=IB,ff 1=IA对于双射函数 f：AA,有f 1f=ff 1=IA,25,函数复合与反函数的计算,例 设 f：RR,g：RR 求 f g,g f.如果 f 和 g 存在反函数,求出它们的反函数.,解 f：RR不是双射的,不存在反函数.g：RR是双射的,它的反函数是 g1：RR,g1(x)=x2,2
13、6,问题：有2台机器c1,c2；6项任务t1,t2,t6.每项任务的加工时间分别为：l(t1)=l(t3)=l(t5)=l(t6)=1,l(t2)=l(t4)=2任务之间的顺序约束是：任务t3只有在t6和t5完成之后才能开始加工；任务t2只有在t6,t5和t4都完成后才能开始加工；任务t1只有在t3和t2完成之后才能开始加工.调度：任务安排在机器上加工的方案截止时间：开始时刻0，最后停止加工机器的停机时刻,问题描述多机调度,27,两个调度方案,D=6,t1,t2,t3,t4,t5,t6,D=5,t1,t3,t5,t2,t6,t4,28,集合任务集 T=t1,t2,.,tn,nZ+机器集 M=c
14、1,c2,.,cm，mZ+时间集 N函数和关系加工时间函数 l:TZ+.顺序约束R T上的偏序关系，定义为 R=|ti,tjT,i=j 或 ti完成后tj 才可以开始加工,问题描述,29,问题描述（续）,可行调度 分配到机器：T 的 划分=T1,T2,.,Tm，划分块Tj 是T 的非空子集，由安排在机器cj上加工的所有任务组成.每个机器上的任务开始时间Tj，存在调度函数 j:TjN，满足以下条件：(1)任意时刻 i，每台机器上正在加工至多1个任务 i,0 iR i(ti)+l(ti)j(tj)i,j=1,2,m,30,问题描述（续）,机器 j 的停止时间 Dj=maxj(tk)|tkTj+l(tk)所有任务的截止时间 D=maxDj|j=1,2,.,m.我们的问题就是确定使得D达到最小的可行调度.,
