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

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

1、关于离散数学二元关系和函数现在学习的是第1页，共36页 在高等数学中，函数是在实数集合上进行讨论的，在高等数学中，函数是在实数集合上进行讨论的，其定义域是连续的。其定义域是连续的。本章把函数概念予以推广本章把函数概念予以推广 定义域为一般的集合，支持离散应用。定义域为一般的集合，支持离散应用。把函数看作是一种特殊的关系：单值二元关系。把函数看作是一种特殊的关系：单值二元关系。4.6函函数数的的定定义义与与性性质质现在学习的是第2页，共36页函数定义函数定义定义定义设设F 为二元关系为二元关系,若若 xdomF 都存在唯一的都存在唯一的yranF 使使xFy 成立成立,则称则称F 为函数为函数.

2、对于函数对于函数F,如果有如果有xFy,则记作则记作y=F(x),并称并称y 为为F 在在x 的函数值的函数值.例例1F1=,F2=,F1是函数是函数,F2不是函数不是函数4.6函函数数的的定定义义与与性性质质现在学习的是第3页，共36页函数与关系的区别函数与关系的区别从从A A到到B B的函数的函数f f与一般从与一般从A A到到B B的二元关系的二元关系R R有如下有如下区别：区别：A A的每一元素都必须是的每一元素都必须是f f的序偶的第一坐标，的序偶的第一坐标，即即dom(f)=Adom(f)=A；但；但dom(R)dom(R)R R若若f(x)=yf(x)=y，则则函函数数f f在在

3、x x处处的的值值是是惟惟一一的的，即即(f(x)=y)f(x)=y)(f(x)=z)(f(x)=z)(y=z)(y=z)，；但但(xRy)(xRy)(xRz)(xRz)得不到得不到y=zy=z4.6函函数数的的定定义义与与性性质质现在学习的是第4页，共36页例例1 1 设设A=1,2,3,4,5A=1,2,3,4,5，B=6,7,8,9,10B=6,7,8,9,10，分别确定，分别确定下列各式中的下列各式中的f f是否为由是否为由A A到到B B的函数。的函数。(1)f=(1,8),(3,9),(4,10),(2,6),(5,9)(1)f=(1,8),(3,9),(4,10),(2,6),(

4、5,9)(2)f=(1,9),(3,10),(2,6),(4,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)(3)f=(1,7),(2,6),(4,5),(1,9),(5,10),(3,9)解解（1 1）能构成函数，因）能构成函数，因为为符合函数的定符合函数的定义义条件。条件。（2 2）不不能能构构成成函函数数，因因为为A A中中的的元元素素5 5没没有有像像，不不满满足像的存在性。足像的存在性。（3 3）不能构成函数，因）不能构成函数，因为为A A中的元素中的元素1 1有两个像有两个像7 7和和

5、9 9，不，不满满足像的惟一性。足像的惟一性。4.6函函数数的的定定义义与与性性质质现在学习的是第5页，共36页函数相等函数相等定义定义设设F,G为函数为函数,则则F=G F GG F一般使用下面两个条件一般使用下面两个条件：(1)domF=domG(2)xdomF=domG 都有都有F(x)=G(x)实例实例函数函数F(x)=(x2 1)/(x+1),G(x)=x 1不相等不相等,因为因为domF domG.4.6函函数数的的定定义义与与性性质质现在学习的是第6页，共36页从从A A到到B B的函数的函数定义定义设设A,B为集合为集合,如果如果f 为函数为函数domf=A ranf B,则称

6、则称f 为为从从A到到B的函数的函数,记作记作f：AB.实例实例f：NN,f(x)=2x 是从是从N 到到N 的函数的函数 g：NN,g(x)=2也是从也是从N 到到N 的函数的函数4.6函函数数的的定定义义与与性性质质现在学习的是第7页，共36页B B上上A 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=.4.6函函数数的的定定义义与与性性质质现在学习的是第8页，共36页实例实例例例2设设

7、A=1,2,3,B=a,b,求求BA.解解BA=f0,f1,f7,其中其中f0=,f1=,f2=,，f3=,f4=,，f5=,f6=,f7=,4.6函函数数的的定定义义与与性性质质现在学习的是第9页，共36页函数的像函数的像定义定义设函数设函数f：AB,A1 A.A1在在f 下的像下的像：f(A1)=f(x)|xA1函数的像函数的像f(A)=ranf 注意：注意：函数值函数值f(x)B,而像而像f(A1)B.例例3 设设 f：NN,且且 令令A=0,1,B=2,那么有那么有f(A)=f(0,1)=f(0),f(1)=0,24.6函函数数的的定定义义与与性性质质现在学习的是第10页，共36页函数

8、的性质函数的性质定义定义设设f：AB,（1）若）若ranf=B,则称则称f：AB是是满射满射的的.（2）若）若任意任意x1，x2 A而且不相等，都有而且不相等，都有f(x1)与与f(x2)不相等不相等,则称则称f：AB是是单射单射的的.（3）若）若f：AB既是满射又是单射的既是满射又是单射的,则称则称f：AB是是双射双射的的f满射意味着：满射意味着：y B,都存在都存在x使得使得 f(x)=y.f 单射意味着：单射意味着：f(x1)=f(x2)x1=x24.6函函数数的的定定义义与与性性质质现在学习的是第11页，共36页注意：注意：由单射的定义可知，设由单射的定义可知，设X X和和Y Y是有限

9、集是有限集合，若存在单射函数合，若存在单射函数f:XYf:XY，则则|X|Y|X|Y|。由满射的定义可知，设由满射的定义可知，设X X和和Y Y是有限集合，是有限集合，若存在满射函数若存在满射函数f:XYf:XY，则则|X|Y|X|Y|。由由双双射射的的定定义义可可知知，设设X X和和Y Y是是有有限限集集合合，若存在双射函数若存在双射函数f:XYf:XY，则则|X|=|Y|X|=|Y|。4.6函函数数的的定定义义与与性性质质现在学习的是第12页，共36页实例实例例例4判断下面函数是否为单射判断下面函数是否为单射,满射满射,双射的双射的,为什么为什么?(1)f：RR,f(x)=x2+2x 1(

10、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+为正实数集为正实数集.4.6函函数数的的定定义义与与性性质质现在学习的是第13页，共36页解解(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 满射满射,但不单射但不单射,例如例如f(1.5)=f(1.2)=1.(4)f

11、：RR,f(x)=2x+1满射、单射、双射满射、单射、双射,因为它是单调的并且因为它是单调的并且ranf=R.(5)f：R+R+,f(x)=(x2+1)/x有极小值有极小值f(1)=2.该函数既不单射也不满射该函数既不单射也不满射.实例（续）实例（续）4.6函函数数的的定定义义与与性性质质现在学习的是第14页，共36页构造从构造从A A到到B 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=,f7=

12、,.令令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)=f74.6函函数数的的定定义义与与性性质质现在学习的是第15页，共36页实数区间之间构造双射实数区间之间构造双射构造方法：直线方程构造方法：直线方程例例6A=0,1B=1/4,1/2构造双射构造双射f:AB构造从构造从A A到到B B的双射函数（续）的双射函数（续）解解令令f：0,11/4,1/2 f(x)=(x+1)/44.6函函数数的的定定义义与与性性质质现在学习的是第16页，共36页构造从构造从A A到到B B的双射函数（续）的双射

13、函数（续）A A 与自然数集合之间构造双射与自然数集合之间构造双射方法：将方法：将A中元素排成有序图形，然后从第一个元素开始中元素排成有序图形，然后从第一个元素开始按照次序与自然数对应按照次序与自然数对应例例7A=Z,B=N，构造双射，构造双射f：AB将将Z中元素以下列顺序排列并与中元素以下列顺序排列并与N中元素对应：中元素对应：Z：0 11 22 33N：0123456则这种对应所表示的函数是则这种对应所表示的函数是：4.6函函数数的的定定义义与与性性质质现在学习的是第17页，共36页常函数、恒等函数、单调函数常函数、恒等函数、单调函数 1.设设f：AB,若存在若存在cB 使得使得 xA 都

14、有都有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,x1x2,就有就有f(x1)f(x2),则称则称f 为为严严格单调递增格单调递增的的.类似可以定义类似可以定义单调递减单调递减和和严格单调递减严格单调递减的函数的函数.4.6函函数数的的定定义义与与性性质质现在学习的是第18页，共36页集合的特征函数

15、集合的特征函数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)101001114.6函函数数的的定定义义与与性性质质现在学习的是第19页，共36页5.设设R 是是A 上的等价关系上的等价关系,令令g：AA/Rg(a)=a,aA称称g 是从是从A 到商集到商集A/R 的的自然映射自然映射.自然映射自然映射 4.6函函数数的的定定义义与与性性质质现在学习的是第20页，共36页实例实例例例8(1)A的每一个子集的每一个子

16、集A都对应于一个特征函数都对应于一个特征函数,不同的子集对应于不同的特征函数不同的子集对应于不同的特征函数.例如例如A=a,b,c,则有则有=,，a,b=,(2)给定集合给定集合A，A 上不同的等价关系确定不同的自上不同的等价关系确定不同的自然映射然映射,其中恒等关系确定的自然映射是双射其中恒等关系确定的自然映射是双射,其他其他的自然映射一般来说是满射的自然映射一般来说是满射.例如例如 A=1,2,3,R=,IA g(1)=g(2)=1,2,g(3)=34.6函函数数的的定定义义与与性性质质现在学习的是第21页，共36页函数复合的定理函数复合的定理定理定理设设F,G是函数是函数,则则F F G

17、 G也是函数也是函数,且满足且满足(1)dom(FG)=x|xdomG G(x)domF(2)xdom(F F G G)有有FG(x)=F(G(x)推论推论1设设F,G,H为函数为函数,则则(F G)H 和和F(G H)都是函数都是函数,且且(F G)H=F(G H)推论推论2设设f：BC,g：AB,则则f g：AC,且且 xA 都有都有f g(x)=f(g(x).4.7函函数数复复合合和和反反函函数数现在学习的是第22页，共36页函数复合运算的性质函数复合运算的性质定理定理设设g：AB,f：BC.(1)如果如果f,g都是满射都是满射,则则fg：AC也是满射也是满射.(2)如果如果g,f 都是

18、单射都是单射,则则f f g:g:AC也是单射也是单射.(3)如果如果g,f 都是双射都是双射,则则f g：AC也是双射也是双射.证证(1)cC,由由f：BC 的满射性的满射性,bB 使得使得f(b)=c.对这个对这个b,由由g：AB 的满射性，的满射性，aA 使得使得f(a)=b.由合成定理由合成定理f g(a)=f(g(a)=f(b)=c从而证明了从而证明了f g：AC是满射的是满射的.现在学习的是第23页，共36页函数复合运算的性质函数复合运算的性质(2)假设存在假设存在x1,x2A使得使得f g(x1)=f g(x x2 2)由合成定理有由合成定理有f(g(x1)=f(g(x2).因为

19、因为f：BC是单射的是单射的,故故g(x1)=g(x2).又由又由于于g：AB也是单射的也是单射的,所以所以x1=x2.从而证从而证明明f g：AC是单射的是单射的.(3)由由(1)和和(2)得证得证.定理定理设设f:AB，则，则f=f IB=IA f 现在学习的是第24页，共36页定理定理 设设f:XYf:XY，g:YZg:YZ，那么那么（1 1）若）若gfgf是单射，则是单射，则f f是单射。是单射。（2 2）若）若gfgf是满射，则是满射，则g g是满射。是满射。（3 3）若）若gfgf是双射，则是双射，则f f是单射，是单射，g g是满射。是满射。函数复合运算的性质函数复合运算的性质现

20、在学习的是第25页，共36页反函数存在的条件反函数存在的条件任给函数任给函数F,它的逆它的逆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/2现在学习的是第26页，共36页反函数反函数定理定理设设f：AB是双射的是双射的,则则f 1：BA也是双射函数也是双射函数.证证因为因为f 是函数是函数,所以所以f 1是关系是关系,

21、且且dom f 1=ranf=B,ran f 1=domf=A,对于任意的对于任意的yB=dom f 1,假设有假设有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=y2现在学习的是第27页，共36页反函数的定义及性质反函数的定义及性质对于双射函数对于双射函数f：AB,称称f 1：BA是它的是它的反反函数函数.反函数

22、的性质反函数的性质定理定理 设设f：AB是双射的是双射的,则则f 1f=IA,ff 1=IB对于双射函数对于双射函数f：AA,有有f 1f=ff 1=IA现在学习的是第28页，共36页定理定理 若若f:XYf:XY是可逆的，那么是可逆的，那么 （l l）(f(f-1-1)-1-1=f=f （2 2）f f-1-1f=If=IX X，f ff f-1-1=I=IY Y定理定理3.93.9 设设X,Y,ZX,Y,Z是集合，如果是集合，如果f:XYf:XY，g:YZg:YZ都是可逆的，那么都是可逆的，那么g gf f也是可逆的，且也是可逆的，且(g gf)f)-1-1=f=f-1-1g g-1-1

23、。现在学习的是第29页，共36页函数复合与反函数的计算函数复合与反函数的计算例例设设f：RR,g：RR 求求f g,g f.如果如果f 和和g 存在反函数存在反函数,求出它们的反函数求出它们的反函数.解解 f：RR不是双射的不是双射的,不存在反函数不存在反函数.g：RR是双射的是双射的,它它的反函数是的反函数是g 1：RR,g 1(x)=x 2现在学习的是第30页，共36页一、两个有限集如何比较多少。一、两个有限集如何比较多少。设两个班级A 和B，要比较这两个班级的学生哪班多，哪班少，可采取两种方法。方法1：报数。报数后看谁的数目大，数目大的就表示这个班上学生人数多。但这个方法对无限集却行不通

24、。方法2：配对。将A 中的一个学生a1 和B 中的一个学生b1 配成一对，配好以后，不许他们再和别人配对了。然后再把A 中的另一个学生a2 和B 中的一个学生b2 配成一对，同样，配好以后也不准他们再和其他人配对了。这样一对一配下去，如果A中的人都配完了，而B还剩下一些人，则说B中的学生比A多；如果B 中的人都配完了，而A 剩下一些人，则说A中的学生比B多；如果A和B中的学生正好都能一对一地搭配起来，则说A和B的学生人数一样多。这种“配对”的办法可以应用到无限集中去。现在学习的是第31页，共36页定义一定义一 设设A A与与B B为集合，若存在从为集合，若存在从A A到到B B的双射，则的双射

25、，则称称A A和和B B为等势，记为为等势，记为A AB B。例例6.13(-1,1)6.13(-1,1)(-,+)(-,+)。证明证明 因存在着双射因存在着双射 ，x(-1,1)x(-1,1)，所以，所以(-(-1,1)1,1)(-,+)(-,+)。等势关系具有如下性质等势关系具有如下性质 A AA A。若若A AB B，则，则B BA A。若若A AB B，B BC C，则，则A AC C。所以等势关系是等价关系。所以等势关系是等价关系。现在学习的是第32页，共36页定义二定义二 设设N Nn n=0,1,2,n-1=0,1,2,n-1，A A 为任一集合。若为任一集合。若A=A=或或A

26、A 与某个与某个N Nn n等势，则称等势，则称A A为有限集；否则称为有限集；否则称A A 为无限集。为无限集。定理一定理一 自然数集N为无限集。证明 任取nN，f 是从Nn 到N 的任意一个函数。令k=1+maxf(0),f(1),f(n-1)，则kN。但对每个xNn，都有f(x)k，因此f不是满射，从而f 不是双射。由n和f的任意性得知N 是无限的。现在学习的是第33页，共36页定义三定义三 （1 1）对于有限集合）对于有限集合A A，有唯一的，有唯一的NnNn与其等势，与其等势，对应的对应的n n称为称为A A的基数，记为的基数，记为|A|A|（2 2）自然数集）自然数集N N 的基数

27、记为的基数记为 0 0（读作阿列夫零）。（读作阿列夫零）。（3 3）实数集）实数集R R 的基数记为的基数记为（读作阿列夫）。（读作阿列夫）。由定义可知，有限集合的基数就是其所含元素的由定义可知，有限集合的基数就是其所含元素的个数。两个有限集合等势当且仅当个数。两个有限集合等势当且仅当A A和和B B 的元素个数相的元素个数相同。同。现在学习的是第34页，共36页定义四定义四 与自然数集N 等势的集合叫做可数集或可列集，其基数记为0。与自然数集N不等势的无限集叫做不可数集或不可列集。下面介绍可数集的一些性质。定理五定理五 集合A 为可数集的充要条件是A 的元素可以排列成无限序列的形式（即A=a0,a1,an,）。定理二定理二 任一无限集必含有可数子集。定理三定理三 任一无限集必与其某一真子集等势。定理四定理四 可数集的任何无限子集是可数的。定理五定理五 两个可数集的并集仍是可数集。现在学习的是第35页，共36页感感谢谢大大家家观观看看现在学习的是第36页，共36页