《离散数学》二元关系和函数-2

第4章二元关系和函数Relation在高等数学中，函数是在实数集合上进行讨论的，其定义域是连续的。本章把函数概念予以推广⑴定义域为一般的集合，支持离散应用。⑵把函数看作是一种特殊的关系：单值二元关系。4.6函数的定义与性质函数定义定义设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不是函数4.6函数的定义与性质函数与关系的区别从A到B的函数f与一般从A到B的二元关系R有如下区别：A的每一元素都必须是f的序偶的第一坐标，即dom(f)=A；但dom(R)R若f(x)=y，则函数f在x处的值是惟一的，即(f(x)=y)(f(x)=z)(y=z)，；但(xRy)(xRz)得不到y=z4.6函数的定义与性质例1设A={1,2,3,4,5}，B={6,7,8,9,10}，分别确定下列各式中的f是否为由A到B的函数。(1)f={(1,8),(3,9),(4,10),(2,6),(5,9)}(2)f={(1,9),(3,10),(2,6),(4,9)}(3)f={(1,7),(2,6),(4,5),(1,9),(5,10),(3,9)}解（1）能构成函数，因为符合函数的定义条件。（2）不能构成函数，因为A中的元素5没有像，不满足像的存在性。（3）不能构成函数，因为A中的元素1有两个像7和9，不满足像的惟一性。4.6函数的定义与性质函数相等定义设F,G为函数,则F=GFG∧GF一般使用下面两个条件：(1)domF=domG(2)x∈domF=domG都有F(x)=G(x)实例函数F(x)=(x21)/(x+1),G(x)=x1不相等,因为domFdomG.4.6函数的定义与性质从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的函数4.6函数的定义与性质B上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=.4.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}4.6函数的定义与性质函数的像定义设函数f：A→B,A1A.A1在f下的像：f(A1)={f(x)|x∈A1}函数的像f(A)=ranf注意：函数值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}/2()1xxfxxx若为偶数若为奇数4.6函数的定义与性质函数的性质定义设f：A→B,（1）若ranf=B,则称f：A→B是满射的.（2）若任意x1，x2A而且不相等，都有f(x1)与f(x2)不相等,则称f：A→B是单射的.（3）若f：A→B既是满射又是单射的,则称f：A→B是双射的f满射意味着：yB,都存在x使得f(x)=y.f单射意味着：f(x1)=f(x2)x1=x24.6函数的定义与性质注意：①由单射的定义可知，设X和Y是有限集合，若存在单射函数f:X→Y，则|X|≤|Y|。②由满射的定义可知，设X和Y是有限集合，若存在满射函数f:X→Y，则|X|≥|Y|。③由双射的定义可知，设X和Y是有限集合，若存在双射函数f:X→Y，则|X|=|Y|。4.6函数的定义与性质实例例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+为正实数集.4.6函数的定义与性质解(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.该函数既不单射也不满射.实例（续）4.6函数的定义与性质构造从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})=f74.6函数的定义与性质实数区间之间构造双射构造方法：直线方程例6A=[0,1]B=[1/4,1/2]构造双射f:A→B构造从A到B的双射函数（续）解令f：[0,1]→[1/4,1/2]f(x)=(x+1)/44.6函数的定义与性质构造从A到B的双射函数（续）A与自然数集合之间构造双射方法：将A中元素排成有序图形，然后从第一个元素开始按照次序与自然数对应例7A=Z,B=N，构造双射f：A→B将Z中元素以下列顺序排列并与N中元素对应：Z：0112233…↓↓↓↓↓↓↓N：0123456…则这种对应所表示的函数是20Z,()210xfNfxxx：4.6函数的定义与性质常函数、恒等函数、单调函数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为严格单调递增的.类似可以定义单调递减和严格单调递减的函数.4.6函数的定义与性质集合的特征函数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)101001114.6函数的定义与性质5.设R是A上的等价关系,令g：A→A/Rg(a)=[a],a∈A称g是从A到商集A/R的自然映射.自然映射4.6函数的定义与性质实例例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}4.6函数的定义与性质函数复合的定理定理设F,G是函数,则FG也是函数,且满足(1)dom(FG)={x|x∈domGG(x)∈domF}(2)x∈dom(FG)有FG(x)=F(G(x))推论1设F,G,H为函数,则(F∘G)∘H和F∘(G∘H)都是函数,且(F∘G)∘H=F∘(G∘H)推论2设f：B→C,g：A→B,则f∘g：A→C,且x∈A都有f∘g(x)=f(g(x)).4.7函数复合和反函数函数复合运算的性质定理设g：A→B,f：B→C.(1)如果f,g都是满射,则fg：A→C也是满射.(2)如果g,f都是单射,则fg:A→C也是单射.(3)如果g,f都是双射,则f∘g：A→C也是双射.证(1)c∈C,由f：B→C的满射性,b∈B使得f(b)=c.对这个b,由g：A→B的满射性，a∈A使得f(a)=b.由合成定理f∘g(a)=f(g(a))=f(b)=c从而证明了f∘g：A→C是满射的.函数复合运算的性质(2)假设存在x1,x2∈A使得fg(x1)=fg(x2)由合成定理有f(g(x1))=f(g(x2)).因为f：B→C是单射的,故g(x1)=g(x2).又由于g：A→B也是单射的,所以x1=x2.从而证明f∘g：A→C是单射的.(3)由(1)和(2)得证.定理设f:AB，则f=f∘IB=IA∘f定理设f:X→Y，g:Y→Z，那么（1）若gf是单射，则f是单射。（2）若gf是满射，则g是满射。（3）若gf是双射，则f是单射，g是满射。函数复合运算的性质反函数存在的条件任给函数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/2反函数定理设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=y2反函数的定义及性质对于双射函数f：A→B,称f1：B→A是它的反函数.反函数的性质定理设f：A→B是双射的,则f1f=IA,ff1=IB对于双射函数f：A→A,有f1f=ff1=IA定理若f:X→Y是可逆的，那么（l）(f-1)-1=f（2）f-1f=IX，ff-1=IY定理3.9设X,Y,Z是集合，如果f:X→Y，g:Y→Z都是可逆的，那么gf也是可逆的，且(gf)-1=f-1g-1。函数复合与反函数的计算例设f：R→R,g：R→R求fg,gf.如果f和g存在反函数,求出它们的反函数.23()()223xxfxgxxxf：R→R不是双射的,不存在反函数.g：R→R是双射的,它的反函数是g1：R→R,g1(x)=x222::23(2)1()()0321fgRRgfRRxxxxfgxgfxxx