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

14.6函数的定义与性质函数的定义函数定义从A到B的函数函数的像函数的性质函数的单射、满射、双射性构造双射函数应用实例：问题描述2函数定义定义设F为二元关系,若x∈domF都存在唯一的y∈ranF使xFy成立,则称F为函数.对于函数F,如果有xFy,则记作y=F(x),并称y为F在x的值.例1F1={x1,y1,x2,y2,x3,y2}F2={x1,y1,x1,y2}F1是函数,F2不是函数3函数相等定义设F,G为函数,则F=GFG∧GF如果两个函数F和G相等,一定满足下面两个条件：(1)domF=domG(2)x∈domF=domG都有F(x)=G(x)实例函数F(x)=(x21)/(x+1),G(x)=x1不相等,因为domFdomG.4从A到B的函数定义设A,B为集合,如果f为函数domf=AranfB,则称f为从A到B的函数,记作f：A→B.实例f：N→N,f(x)=2x是从N到N的函数g：N→N,g(x)=2也是从N到N的函数5B上A定义所有从A到B的函数的集合记作BA,读作“B上A”，符号化表示为BA={f|f：A→B}计数：|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={f0,f1,…,f7},其中f0={1,a,2,a,3,a},f1={1,a,2,a,3,b}f2={1,a,2,b,3,a}，f3={1,a,2,b,3,b}f4={1,b,2,a,3,a}，f5={1,b,2,a,3,b}f6={1,b,2,b,3,a},f7={1,b,2,b,3,b}7函数的像定义设函数f：A→B,A1A.A1在f下的像：f(A1)={f(x)|x∈A1}函数的像f(A)注意：函数值f(x)∈B,而像f(A1)B.例3设f：N→N,且令A={0,1},B={2},那么有f(A)=f({0,1})={f(0),f(1)}={0,2}为奇数若为偶数若xxxxxf12/)(8函数的性质定义设f：A→B,（1）若ranf=B,则称f：A→B是满射的.（2）若y∈ranf都存在唯一的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(x1)=f(x2)x1=x29实例例4判断下面函数是否为单射,满射,双射的,为什么?(1)f：R→R,f(x)=x2+2x1(2)f：Z+→R,f(x)=lnx,Z+为正整数集(3)f：R→Z,f(x)=x(4)f：R→R,f(x)=2x+1(5)f：R+→R+,f(x)=(x2+1)/x,其中R+为正实数集.10解(1)f：R→R,f(x)=x2+2x1在x=1取得极大值0.既不单射也不满射.(2)f：Z+→R,f(x)=lnx单调上升,是单射.但不满射,ranf={ln1,ln2,…}.(3)f：R→Z,f(x)=x满射,但不单射,例如f(1.5)=f(1.2)=1.(4)f：R→R,f(x)=2x+1满射、单射、双射,因为它是单调的并且ranf=R.(5)f：R+→R+,f(x)=(x2+1)/x有极小值f(1)=2.该函数既不单射也不满射.实例（续）11构造从A到B的双射函数有穷集之间的构造例5A=P({1,2,3}),B={0,1}{1,2,3}解A={,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}.B={f0,f1,…,f7},其中f0={1,0,2,0,3,0},f1={1,0,2,0,3,1},f2={1,0,2,1,3,0},f3={1,0,2,1,3,1},f4={1,1,2,0,3,0},f5={1,1,2,0,3,1},f6={1,1,2,1,3,0},f7={1,1,2,1,3,1}.令f：A→B,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})=f712实数区间之间构造双射构造方法：直线方程例6A=[0,1]B=[1/4,1/2]构造双射f:A→B构造从A到B的双射函数（续）解令f：[0,1]→[1/4,1/2]f(x)=(x+1)/413构造从A到B的双射函数（续）A与自然数集合之间构造双射方法：将A中元素排成有序图形，然后从第一个元素开始按照次序与自然数对应例7A=Z,B=N，构造双射f：A→B将Z中元素以下列顺序排列并与N中元素对应：Z：0112233…↓↓↓↓↓↓↓N：0123456…01202)(,NZxxxxff：14常函数、恒等函数、单调函数1.设f：A→B,若存在c∈B使得x∈A都有f(x)=c,则称f：A→B是常函数.2.称A上的恒等关系IA为A上的恒等函数,对所有的x∈A都有IA(x)=x.3.设f：R→R，如果对任意的x1,x2∈R，x1x2,就有f(x1)f(x2),则称f为单调递增的；如果对任意的x1,x2∈A,x1x2,就有f(x1)f(x2),则称f为严格单调递增的.类似可以定义单调递减和严格单调递减的函数.15集合的特征函数4.设A为集合,A’A,A’的特征函数A’：A→{0,1}定义为',0',1)('AAaAaaA实例集合：X={A,B,C,D,E,F,G,H},子集：T={A,C,F,G,H}T的特征函数T：xABCDEFGHT(x)10100111165.设R是A上的等价关系,令g：A→A/Rg(a)=[a],a∈A称g是从A到商集A/R的自然映射.自然映射17实例例8(1)A的每一个子集A’都对应于一个特征函数,不同的子集对应于不同的特征函数.例如A={a,b,c},则有={a,0,b,0,c,0}，{a,b}={a,1,b,1,c,0}(2)给定集合A，A上不同的等价关系确定不同的自然映射,其中恒等关系确定的自然映射是双射,其他的自然映射一般来说是满射.例如A={1,2,3},R={1,2,2,1}∪IAg(1)=g(2)={1,2},g(3)={3}184.7函数的复合与反函数函数的复合函数复合的定理函数复合的性质反函数反函数存在的条件反函数的性质19函数复合的定理定理设F,G是函数,则F∘G也是函数,且满足(1)dom(F∘G)={x|x∈domFF(x)∈domG}(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)).20函数复合运算的性质定理设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是满射的.21函数复合运算的性质(2)假设存在x1,x2∈A使得f∘g(x1)=f∘g(x2)由合成定理有g(f(x1))=g(f(x2)).因为g：B→C是单射的,故f(x1)=f(x2).又由于f：A→B也是单射的,所以x1=x2.从而证明f∘g：A→C是单射的.(3)由(1)和(2)得证.定理设f:AB，则f=f∘IB=IA∘f22反函数存在的条件任给函数F,它的逆F1不一定是函数,是二元关系.实例：F={a,b,c,b}，F1={b,a,b,c}任给单射函数f：A→B,则f1是函数,且是从ranf到A的双射函数,但不一定是从B到A的双射函数.实例：f:N→N,f(x)=2x,f1:ranf→N,f1(x)=x/223反函数定理设f：A→B是双射的,则f1：B→A也是双射的.证因为f是函数,所以f1是关系,且domf1=ranf=B,ranf1=domf=A,对于任意的y∈B=domf1,假设有x1,x2∈A使得y,x1∈f1∧y,x2∈f1成立,则由逆的定义有x1,y∈f∧x2,y∈f根据f的单射性可得x1=x2,从而证明了f1是函数，且是满射的.下面证明f1的单射性.若存在y1,y2∈B使得f1(y1)=f1(y2)=x,从而有y1,x∈f1∧y2,x∈f1x,y1∈f∧x,y2∈fy1=y224反函数的定义及性质对于双射函数f：A→B,称f1：B→A是它的反函数.反函数的性质定理设f：A→B是双射的,则f1∘f=IB,f∘f1=IA对于双射函数f：A→A,有f1∘f=f∘f1=IA25函数复合与反函数的计算例设f：R→R,g：R→R求fg,gf.如果f和g存在反函数,求出它们的反函数.2)(323)(2xxgxxxxff：R→R不是双射的,不存在反函数.g：R→R是双射的,它的反函数是g1：R→R,g1(x)=x2121)2()(3032)(RR:RR:22xxxxfgxxxxgffggf26问题：有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=6t1t2t3t4t5t6D=5t1t3t5t2t6t4t5t6t4t3t2t128集合任务集T={t1,t2,...,tn},nZ+机器集M={c1,c2,...,cm}，mZ+时间集N函数和关系加工时间——函数l:TZ+.顺序约束R——T上的偏序关系，定义为R={ti,tj|ti,tjT,i=j或ti完成后tj才可以开始加工}问题描述29问题描述（续）可行调度分配到机器：T的划分={T1,T2,...,Tm}，划分块Tj是T的非空子集，由安排在机器cj上加工的所有任务组成.每个机器上的任务开始时间Tj，存在调度函数j:TjN，满足以下条件：(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,ti,tjRi(ti)+l(ti)j(tj)i,j=1,2,…,m30问题描述（续）机器j的停止时间Dj=max{j(tk)|tkTj}+l(tk)所有任务的截止时间D=max{Dj|j=1,2,...,m}.我们的问题就是确定使得D达到最小的可行调度.