第四章二元关系和函数精选文档.ppt

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

1、第四章二元关系和函数本讲稿第一页，共五十二页4.1 4.1 集合的笛卡儿积与二元关系集合的笛卡儿积与二元关系一一.集合的笛卡儿积集合的笛卡儿积1.定义:设A,B为集合,则A和B的笛卡儿积为 AB=|xAyB 其中叫做有序对或序偶;例如:A=a,b,B=0,1,2,则 AB=,BA=,说明:如果A中有m个元素,B中有n个元素,则AB和BA中都有m*n个元素;若AB,则有 xA且yB 若 AB,则有 x A或y B本讲稿第二页，共五十二页2.性质:B=A=若 AB且A,B,则ABBA 若A,B,C,则(AB)CA(BC)A(BC)=(AB)(AC)(BC)A=(BA)(CA)A(BC)=(AB)(

2、AC)(BC)A=(BA)(CA)证明:A(BC)xAyBCxA(yByC)(xAyB)(xAyC)ABAC(AB)(AC)所以,A(BC)=(AB)(AC)本讲稿第三页，共五十二页例4.1 设A=1,2,求P(A)A解:P(A)A=,1,2,1,21,2=,;例4.2 设 A,B,C,D为任意集合,判断以下等式是否成立,说明为什麽?(1)(AB)(CD)=(AC)(BD)(2)(AB)(CD)=(AC)(BD)(3)(A-B)(C-D)=(AC)-(BD)(4)(AB)(CD)=(AC)(BD)本讲稿第四页，共五十二页解:(1)成立:(AB)(CD)xAByCD (xAxB)(yCyD)(x

3、AyC)(xByD)AC BD(AC)(BD)(2)不成立:若A=D=,B=C=1 则(AB)(CD)=BC=而(AC)(BD)=(C)(D)=(3)不成立:若A=B=1,C=2,D=则(A-B)(C-D)=C=而(AC)-(BD)=-=(4)不成立:若A=B=1,C=2,D=则(AB)(CD)=2=而(AC)(BD)=本讲稿第五页，共五十二页例4.3 设A,B,C,D为任意集合,判断以下命题的真假.(1)若 AC 且 BD,则ABCD (2)若 ABCD,则AC 且 BD解:(1)为真:ABxAyBxCyD CD (2)为假:若A=C=D=,B=1;则ABCD 但BD 3.n个(n2)集合的

4、笛卡儿积 A1A2An=|x1A1,x2A2,xnAn 当A1=A2=An=A时,An=|xiA,i=1,2,n本讲稿第六页，共五十二页二二.二元关系二元关系1.定义:若R=|x,yA;则R为A的二元关系,记作xRy,否则xRy 注)若|A|=n,则|AA|=n2,|P(AA)|=所以A上有 不同的二元关系,其中有3种特殊关系:空关系,全域关系EA和恒等关系IA.全域关系EA=x,y|xA yA=AA 恒等关系IA=x,x|xA例如：，则 EA=,IA=,本讲稿第七页，共五十二页小于等于关系:LA=|x,yA xy整除关系:DB=|x,yB x|y例如:A=4,0.5,-1,B=1,2,3,6

5、 则LA=,DB=,例:4.4 设A=a,b,R是P(A)上的包含关系 R=|x,yP(A)xy 则有P(A)=,a,b,A R=,本讲稿第八页，共五十二页2.二元关系的矩阵表示法和图表示法 设A=1,2,3,4,R=,关系矩阵关系图本讲稿第九页，共五十二页4.2 4.2 关系的运算关系的运算一一.关系的定义域关系的定义域.值域和域值域和域定义域：dom R=x|y(R)值域：ran R=y|x(R)域：fld R=domRranR例4.5 下列关系都是整数集Z上的关系,分别求他们的定义域和值域(1)R1=|x,yZ xy(2)R2=|x,yZ x2+y2=1(3)R3=|x,yZ y=2x(

6、4)R4=|x,yZ|x|=|y|=3本讲稿第十页，共五十二页解:(1)domR1=ranR1=Z (2)R2=,domR2=ranR2=0,-1,1 (3)domR3=Z,ranR3=2x|xZ (4)domR4=ranR4=-3,3图示本讲稿第十一页，共五十二页二二.关系运算关系运算F的逆:F-1=|xFyF与G的合成:FoG=|z(xGz zFy)F在A上的限制:FA=|xFy xAA在F下的像:FA=ran(FA)本讲稿第十二页，共五十二页例4.6设F,G是N上的关系,其定义为 F=|x,yN y=x2 G=|x,yN y=x+1 求G-1,FoG,GoF,F1,2,F1,2 解:G-

7、1=|x,yN y=x-1 (or G-1=|x,yN x=y-1)G-1=,FoG=|x,yN y=(x+1)2 GoF=|x,yN y=x2+1 F1,2=,F1,2=ran(F1,2)=1,4本讲稿第十三页，共五十二页例4.7 设F=,求FoF,Fa,Fa 解:FoF=Fa=Fa=ran(Fa)=a 三三.关系运算的性质关系运算的性质定理1:设F,G,H是任意的关系,则有 (1)(F-1)-1=F (2)domF-1=ranF,ranF-1=domF (3)(FoG)oH=Fo(GoH)(4)(FoG)-1=G-1oF-1本讲稿第十四页，共五十二页证明:(4)(FoG)-1 FoG z(

8、G F)z(G-1 F-1)z(F-1 G-1)G-1oF-1 所以(FoG)-1=G-1oF-1定理2:设F,G,H为任意的关系,则有 (1)Fo(GH)=FoGFoH (2)Fo(GH)FoGFoH (3)(GH)oF=GoFHoF (4)(GH)oFGoFHoF本讲稿第十五页，共五十二页证明:(1)Fo(GH)z(GH F)z(GH)F)z(GF)(HF)z(GF)z(HF)FoG FoHFoGFoH所以 Fo(GH)=FoGFoH(2)Fo(GH)z(GH F)z(G F)FoG所以 Fo(GH)FoG 同理可证Fo(GH)FoH故Fo(GH)FoGFoH本讲稿第十六页，共五十二页四四

9、.关系运算的幂关系运算的幂设R为A上的关系,n为自然数,则R的n次幂规定如下:(1)R0=|xA(R0=IA是A上的恒等关系)(2)Rn=Rn-1oR,n1例4.8 设A=a,b,c,d,R=,求R0,R1,R2,R3,R4和R5解:关系运算:R0=,R1=,R2=R1oR1=,R3=R2oR1=,R4=R3oR1=,R5=R4oR1=,本讲稿第十七页，共五十二页关系图法=,R1=,=,=,本讲稿第十八页，共五十二页关系矩阵R0=,R1=,R2=R1oR1=,R3=R2oR1=,本讲稿第十九页，共五十二页定理3:设R为A上的关系,m,n是自然数,则下面的等式成立:(1)RmRn=R m+n (

10、2)(Rm)n=Rm n本讲稿第二十页，共五十二页4.3 4.3 关系的性质关系的性质一一.关系的定义和性质关系的定义和性质:设设R R是是A A上的关系上的关系,则有则有本讲稿第二十一页，共五十二页例如:设 A=1,2,3 令 R1=,R2=,R3=,R4=,R5=,R6=R7=,则R1是自反的,反对称的;R2是反自反的,对称的;R3既是对称的,又是反对称的;R4是对称的;R5是反自反的,反对称的;R6既是对称的，又是反对称的;R7是反自反的.本讲稿第二十二页，共五十二页例4.9 试判断图中的关系性质解:(1)是对称的 (2)是反自反的,反对称的;(3)是自反的,反对称的;本讲稿第二十三页，

11、共五十二页二二.关系运算的性质关系运算的性质设R1，R2为A上的对称关系,可证R1R2也是A上的对称关系.证明:R1R2R1R2 R1 R2R1R2设R1,R2为A上反对称关系,但R1R2不一定是A上的反对称关系例如:A=x1,x2,R1=,R2=;R1R2=,本讲稿第二十四页，共五十二页4.4 4.4 关系的闭包关系的闭包定义:设R是非空集合A上的关系,R的自反闭包(对称闭包或传递闭包)是A上的R,且R满足以下条件:(1)R是自反的(对称的或传递的)(2)RR (3)对A上的任何包含R的自反关系(对称或传递关系)R”都有RR”一般:将R的自反闭包,记作r(R);对称闭包,记作s(R);传递闭

12、包,记作t(R);定理:设R为非空集合A上的关系,则有 (1)r(R)=RR0 (2)s(R)=RR-1 (3)t(R)=RR2R3本讲稿第二十五页，共五十二页例4.10 设A=a,b,c,d,R=,求R和r(R),s(R),t(R)关系运算,关系图和关系矩阵解:关系运算:r(R)=RR0=,(,=,s(R)=RR-1=,R2=RoR=,R3=R2oR=,R4=R3oR=,R5=R3;t(R)=RR2R3=,本讲稿第二十六页，共五十二页关系图本讲稿第二十七页，共五十二页关系矩阵Mr=M+E;Ms=M+M;Mt=M+M2+M3+本讲稿第二十八页，共五十二页4.5 4.5 等价关系和偏序关系等价关

13、系和偏序关系一一.等价关系等价关系1.等价关系 定义:设R为非空集合A上的关系,如果R是自反的,对称的和传递的,则R为A上的等价关系.对x,yA,若R,则记作xy例4.11 A=1,2,8,R=|x,yAxy(mod 3)其中xy(mod 3)是x-y可以被3整除.解:R1=,R2=,R3=,R=R1R2R3本讲稿第二十九页，共五十二页2.等价类定义:设R是非空集合A上的等价关系,对xA,令xR=y|yA xRy则称xR为x关于R的等价类,简称为x的等价类,简记为x.例如:例4.11有 1=4=7=1,4,7 2=5=8=2,5,8 3=6=3,6定理(等价类的性质):设R是非空集合A上的等价

14、关系,对x,yA,则有(1)x,且xA (2)若xRy,则x=y (3)若xRy,则xy=(4)X=A例如:例4.111,4,72,5,83,6=1,2,8本讲稿第三十页，共五十二页3.商集定义:设R为非空集合A上的等价关系,以R的不交的等价类为元素的集合叫做A在R下的商集,记作A/R.即A/R=xR|xA如:例4.11中,A在R下的商集为A/R=1,4,7,2,5,8,3,64.划分定义:设A是非空集合,如果存在一个A的子集族(P(A)满足以下条件(1)(2)中任意两个元素不交,(3)中所有元素的并集等于A,则称为A的一个划分,且称中的元素为划分块.本讲稿第三十一页，共五十二页例4.14考虑

15、集合A=a,b,c,d的下列子集族 (1)a,b,c,d (2)a,b,c,d (3)a,b,c,a,d (4),a,b,c,d (5)a,b,c则有(1)(2)都是A的划分,(3)(4)(5)不是A的划分.注)所有等价类的集合,即商集A/R,就是A的一个划分,称为由R所诱导的划分.本讲稿第三十二页，共五十二页例4.15 设A=1,2,3,求出A上所有的等价关系解:A的所有划分 1=1,2,3 2=1,2,3 3=2,1,3 4=3,1,2 5=1,2,3对应划分i的等价关系为Ri(i=1,2,3,4,5);IA=,R1=IA,R2=IA,R3=IA,R4=IA,R5=IA本讲稿第三十三页，共

16、五十二页二二.偏序关系偏序关系1.偏序关系:设R为非空集合A上的关系,如果R是自反的,反对称的和传递的,则称R为A上的偏序关系,简称偏序,记作例如:任何集合A上的恒等关系,集合的幂集P(A)上的包含关系,实数集上的小于等于关系,正整数集上的整除关系,都是偏序关系.例:集合A=1,2,3上的大于等于关系,是A的偏序关系即=,所以有32.22.31表示,属于偏序;本讲稿第三十四页，共五十二页2.偏序集一个集合A与A上的偏序关系R一起叫做偏序集;记作.例如:其中R表示通常数小于等于关系,其中R表示集合的包含关系 都是偏序集.3.可比与盖住设为偏序集,x,yA,如果xy或yx成立,则称x与y是可比的.

17、如果xy(即xyxy),且不存在zA,使xzy,则称y盖住x.例如:是偏序集,其中A=1,2,3,4,5,是整除关系,有1与1,2,3,4,5是可比的,2,3,5盖住1,4盖住2.4不能盖住1。本讲稿第三十五页，共五十二页4.全序关系和全序集设为偏序集,若 x,yA,x和y都可比,则称为A上的全序关系,且称为全序集.例如:A=1,2,3,4,5上的小于等于关系是全序关系,而整除关系不是全序关系.5.哈斯图例4.16画出和哈斯图.本讲稿第三十六页，共五十二页例4.17设偏序集的哈斯图如图所示,求出集合A的偏序.解:A=a,b,c,d,e,f,g,h=,IA本讲稿第三十七页，共五十二页6.最小元与

18、最大元,极小元与极大元定义:设为偏序集,BA(1)若yB,使x(xB-yx)成立,则称y是B的最小元.(2)若yB,使x(xB-xy)成立,则称y是B的最大元.(3)若yB,x(xBxy)成立,则称y是B的极小元.(4)若yB,x(xByx)成立,则称y是B的极大元.例4.16(1)有最小元1;无最大元,有极大元7,8,9,10,11,12;(2)有最小元;有最大元a,b,c本讲稿第三十八页，共五十二页例4.17无最小元和最大元,但有极小元a,b,f,h和极大元e,g,h.7.上确界和下确界定义:设为偏序集,BA(1)若yA,使x(xB-xy)成立,则称y为B的上界.(2)若yA,使x(xB-

19、yx)成立,则称y为B的下界.(3)令C=y|y为B的上界,则C的最小元为B的最小上界或上确界.(4)令D=y|y为B的下界,则D的最大元为B的最大下界或下确界.本讲稿第三十九页，共五十二页例4.16在整除关系的偏序集里,取B=2,3,6,那么B的上界为6和12,上确界为6,B的下界是1,下确界是1;取B=A,则B的上确界为a,b,c,下确界为.例4.17取B=c,d,e,则B的上界和上确界为e,B的下界为a,b,但没有下确界.本讲稿第四十页，共五十二页4.6 4.6 函数的定义和性质函数的定义和性质一一.函数函数(映射映射)定义1:设F为二元关系,若xdom F,唯一的yran F,使xFy

20、成立,则称F为函数,记作F(x)=y.例如 F1=,是函数.F2=,不是函数.定义2:设A,B是集合,如果函数f满足以下条件 (1)dom f=A (2)ran fB 则称f是从A到B的函数,记作f:A-B本讲稿第四十一页，共五十二页定义3:设A,B为集合,所有从A到B的函数构成集合BA 有BA=f|f:A-B;例如:A=0,1,2,B=a,b f1=,f2=,f3=,f4=,f5=,f6=,f7=,f8=,所以,BA=f1,f2,f8注)若|A|=m,|B|=n,则BA=nm本讲稿第四十二页，共五十二页定义4:设f:A-B,AA,则A在f下的象是 f(A)=f(x)|xA=fA 当A=A时,

21、称f(A)=f(A)=ran f是函数的象.例如:f:R-R,如f(x)=ex f-1,0,1=e-1,e0,e1=e-1,1,e,即f(R)=R+二二.双射双射定义:设函数f:A-B(1)若ran f=B,则称f是满射,(2)若x1,x2A且x1x2,都有f(x1)f(x2),则称f是单射.(3)若f既是满射,又是单射,则称f是双射.本讲稿第四十三页，共五十二页例如:函数f:1,2-0,f(1)=f(2)=0是满射.函数f:N-N,f(x)=2x 是单射.函数f:Z-Z,f(x)=x+1是双射.例4.18分别确定以下各题中的f是否为从A到B的函数,并对 其中的f:A-B指出它是否为单射,满射

22、或双射,说明理由.设A=1,2,3,4,5,B=6,7,8,9,10(1)f=,是函数,不是单射,也不是满射.(2)f=,不是函数.(3)f=,不是函数.本讲稿第四十四页，共五十二页设A,B为实数集(4)f(x)=x2-x是函数 由于x2-x=x(x-1)=0,可知x=0和x=1 都有f(0)=f(1)=0 所以f不是单射;由于,当x=1/2,f(x)有最小值-1/4,即ran f=-1/4,+)所以,f不是满射.(f(x)=2x-1,f”(x)=2)(5)f(x)=x3是函数,x1,x2A且 x1x2,则有x13x23,所以f是单射;yB,都有x3=y,即 ,所以f是满射,故f是双射.不是函

23、数(x1 由于f(1)=f(2)=1,所以f不是单射;yB,若y=1,则有x=1,其它有y=x-1,即x=y+1,所以,f是满射.本讲稿第四十六页，共五十二页 设A,B为正实数集,(10)是函数,由于 知(x1x2-1)(x1-x2)=0 若x1x2,可知x1x2-1=0,故取x1=1/4,x2=4,有f(x1)=f(x2)所以,f不是单射,由于,当x=1时,f(x)有最大值1/2;(如取y=1,找不到x0,使 成立),即ran fB,故f不是满射.例4.19判断以下函数的单射,满射和双射性 (1)f:RR-RR,R为实数集,f()=(2)f:NN-N,N为自然数集(0N),f()=|x2-y

24、2|本讲稿第四十七页，共五十二页解:(1),RR,若 只要证明,就说明f是单射,用反证法:假设=则有x+y=u+v,x-y=u-v,得x=u,y=v,即=这与已知矛盾,故f是单射.又RR,使f()=从而u=x+y,v=x-y,解之得x=(u+v)/2,y=(u-v)/2,且RR,满足 所以f是满射,故f是双射.(2)由于f()=|1-1|=0,f()=|22-22|=0 因为,所以f不是单射;又由于2N,x,yN,满足f()=|x2-y2|=2 所以,f不是满射.本讲稿第四十八页，共五十二页4.7 4.7 函数的复合和反函数函数的复合和反函数一一.复合函数复合函数设f:B-C,g:A-B(1)

25、如果f,g是满射的,则fg:A-C也是满射的;(2)如果f,g是单射的,则fg:A-C也是单射的;(3)如果f,g是双射的,则fg:A-C也是双射的;二二.反函数反函数设f:A-B是双射的,则f-1是函数,并且是从B到A的双射函数.本讲稿第四十九页，共五十二页例4.21 设f,g,hRR,且有 f(x)=x+3,g(x)=2x+1,h(x)=x/2 求fg,gf,ff,gg,hf,gh,fh,fhg解:所求的复合函数都是R到R的函数,且满足 fg(x)=f(g(x)=(2x+1)+3=2x+4 gf(x)=g(f(x)=2(x+3)+1=2x+7 ff(x)=f(f(x)=(x+3)+3=x+

26、6 gg(x)=g(g(x)=2(2x+1)+1=4x+3 hf(x)=h(f(x)=(x+3)/2 gh(x)=g(h(x)=x+1 fh(x)=f(h(x)=x/2+3 fhg(x)=f(h(g(x)=f(x+1/2)=x+7/2本讲稿第五十页，共五十二页例4.22 如图定义函数f,g,h如下:(1)求f,g,h的象(2)求gf,fh,gg(3)指出f,g,h中哪些函数是单射的,哪些函数是满射的?(4)f,g,h哪些函数存在反函数,给出其反函数的表达式.本讲稿第五十一页，共五十二页解:(1)f(1,2,3,4)=1,2,4 g(1,2,3,4)=1,2,3,4 h(1,2,3,4,)=1,3 (2)gf(1,2,3,4)=g(1,2,4)=2,3,4 gf:1|-4,2|-2,3|-2,4|-3;fh(1,2,3,4)=f(1,3)=1,2 fh:1|-2,2|-1.3|-2,4|-1;gg(1,2,3,4)=g(1,2,3,4)=1,2,3,4 gg:1|-4,2|-3,3|-2,4|-1;(3)只有g是单射的的,满射的(即双射的)(4)只有g有反函数g-1:A-A,且满足g-1:1|-3,2|-1,3|-4,4|-2f:1|-2,2|-1,3|-1,4|-4g:1|-2,2|-4,3|-1,4|-3h:1|-1,2|-3,3|-1,4|-3本讲稿第五十二页，共五十二页