《北大离散数学》PPT课件.ppt

2023/7/11,集合论与图论第5讲,1,第5讲 二元关系的基本概念北京大学,内容提要 1.有序对与卡氏积 2.二元关系 3.二元关系的基本运算,2023/7/11,集合论与图论第5讲,2,有序对与卡氏积,有序对(有序二元组)有序三元组,有序n元组卡氏积卡氏积性质,2023/7/11,集合论与图论第5讲,3,有序对(ordered pair),有序对:=a,a,b 其中,a是第一元素,b是第二元素.也记作(a,b)定理1:=a=cb=d推论:ab,2023/7/11,集合论与图论第5讲,4,有序对(引理1),引理1:x,a=x,b a=b证明:()显然.()分两种情况.(1)x=a.x,a=x,b a,a=a,b a=a,b a=b.(2)xa.ax,a=x,b a=b.#,2023/7/11,集合论与图论第5讲,5,有序对(引理2),引理2:若A=B,则(1)A=B(2)A=B证明:(1)x,xA z(zA xz)z(zB xz)xB.(2)x,xA z(zA xz)z(zB xz)xB.#,2023/7/11,集合论与图论第5讲,6,有序对(定理1),定理1:=a=cb=d证明:()显然.()由引理2,=a,a,b=c,c,d a,a,b=c,c,da,b=c,d.又 a,a,b=c,c,d a,a,b=c,c,d a=c a=c.再由引理1,得b=d.#,2023/7/11,集合论与图论第5讲,7,有序对(推论),推论:ab 证明:(反证)=a=b,与ab矛盾.#,2023/7/11,集合论与图论第5讲,8,有序三元组(ordered triple),有序三元组:=,c有序n(2)元组:=,an定理2:=ai=bi,i=1,2,n.#,2023/7/11,集合论与图论第5讲,9,卡氏积(Cartesian product),卡氏积:AB=|xAyB.例:A=,a,B=1,2,3.AB=,.BA=,.AA=,.BB=,.#,2023/7/11,集合论与图论第5讲,10,卡氏积的性质,非交换:AB BA(除非 A=B A=B=)非结合:(AB)C A(BC)(除非 A=B=C=)分配律:A(BC)=(AB)(AC)等其他:AB=A=B=等,2023/7/11,集合论与图论第5讲,11,卡氏积非交换性,非交换:AB BA(除非 A=B A=B=)反例:A=1,B=2.AB=,BA=.,2023/7/11,集合论与图论第5讲,12,卡氏积非结合性,非结合:(AB)C A(BC)(除非 A=B=C=)反例:A=B=C=1.(AB)C=,1,A(BC)=.,2023/7/11,集合论与图论第5讲,13,卡氏积分配律,1.A(BC)=(AB)(AC)2.A(BC)=(AB)(AC)3.(BC)A=(BA)(CA)4.(BC)A=(BA)(CA),2023/7/11,集合论与图论第5讲,14,卡氏积分配律(证明1),A(BC)=(AB)(AC).证明:,A(BC)xAy(BC)xA(yByC)(xAyB)(xAyC)(AB)(AC)(AB)(AC)A(BC)=(AB)(AC).#,2023/7/11,集合论与图论第5讲,15,例题1,例题1:设A,B,C,D是任意集合,(1)AB=A=B=(2)若A,则 ABAC BC.(3)AC BD ABCD,并且当(A=B=)(AB)时,ABCD ACBD.,2023/7/11,集合论与图论第5讲,16,卡氏积图示,A,B,C,A(BC)=(AB)(AC),ACBDABCD,B,A,C,D,2023/7/11,集合论与图论第5讲,17,例题1(证明(2),(2)若A,则ABAC BC.证明:()若 B=,则 BC.设 B,由A,设xA.y,yBAB AC xAyC yC.BC,2023/7/11,集合论与图论第5讲,18,例题1(证明(2),续),(2)若A,则ABACBC.证明(续):()若B=,则AB=AC.设 B.,AB xAyB xAyC AC ABAC.#讨论:在()中不需要条件 A.,2023/7/11,集合论与图论第5讲,19,n维卡氏积,n维卡氏积:A1A2An=|x1A1x2A2xnAn An=AAA|Ai|=ni,i=1,2,n|A1A2An|=n1n2nn.n维卡氏积性质与2维卡氏积类似.,2023/7/11,集合论与图论第5讲,20,n维卡氏积(性质),非交换:ABCBCA(要求A,B,C均非空,且互不相等)非结合:(非2元运算)分配律:例如AB(CD)=(ABC)(ABD)其他:如 ABC=A=B=C=.,2023/7/11,集合论与图论第5讲,21,二元关系,n元关系二元关系A到B的二元关系A上的二元关系一些特殊关系,2023/7/11,集合论与图论第5讲,22,n元关系(n-ary relation),n元关系:是集合,其元素全是有序n元组.例1:F1=,F1是4元关系.例2:F2=,F2是3元关系.#,2023/7/11,集合论与图论第5讲,23,二元关系(binary relation),2元关系(简称关系):是集合,其元素全是有序对.例3:R1=,R1是2元关系.例4:R2=,R2是2元关系.例5:A=,a,1 A不是关系.#,2023/7/11,集合论与图论第5讲,24,二元关系的记号,设F是二元关系,则F x与y具有F关系 xFy对比:xFy(中缀(infix)记号)F(x,y)(前缀(prefix)记号)F(后缀(suffix)记号)例如:2.,2023/7/11,集合论与图论第5讲,25,A到B的二元关系,A到B的二元关系:是AB的任意子集.R是A到B的二元关系 RAB RP(AB)若|A|=m,|B|=n,则|AB|=mn,故|P(AB)|=2mn即A到B不同的二元关系共有2mn个,2023/7/11,集合论与图论第5讲,26,A到B的二元关系(举例),例:设 A=a1,a2,B=b,则A到B的二元关系共有4个:R1=,R2=,R3=,R4=,.B到A的二元关系也有4个:R5=,R6=,R7=,R8=,.#,2023/7/11,集合论与图论第5讲,27,A上的二元关系,A上的二元关系:是AA的任意子集 R是A上的二元关系 RAA RP(AA)若|A|=m,则|AA|=m2,故|P(AA)|=即A上不同的二元关系共有 个,2023/7/11,集合论与图论第5讲,28,A上的二元关系(例1),例1:设 A=a1,a2,则A上的二元关系共有16个:R1=,R2=,R3=,R4=,R5=,2023/7/11,集合论与图论第5讲,29,A上的二元关系(例1,续1),R6=,R7=,R8=,R9=,R10=,R11=,2023/7/11,集合论与图论第5讲,30,A上的二元关系(例1,续2),R12=,R13=,R14=,R15=,R16=,.#,2023/7/11,集合论与图论第5讲,31,A上的二元关系(例2),例2:设 B=b,则B上的二元关系共有2个:R1=,R2=.#例3:设 C=a,b,c,则C上的2元关系共有29=512个!#,2023/7/11,集合论与图论第5讲,32,一些特殊关系,空关系恒等关系全域关系整除关系小于等于关系,包含关系,真包含关系,2023/7/11,集合论与图论第5讲,33,特殊关系,设A是任意集合,则可以定义A上的:空关系:恒等关系:IA=|xA 全域关系:EA=AA=|xA yA,2023/7/11,集合论与图论第5讲,34,特殊关系(续),设AZ,则可以定义A上的:整除关系:DA=|xA yA x|y 例:A=1,2,3,4,5,6,则 DA=,.#,2023/7/11,集合论与图论第5讲,35,特殊关系(续),设AR,则可以定义A上的:小于等于(less than or equal to)关系:LEA=|xA yA xy 小于(less than)关系,LA=|xA yA xy 大于等于(greater than or equal to)关系大于(great than)关系,2023/7/11,集合论与图论第5讲,36,特殊关系(续),设A为任意集合,则可以定义P(A)上的:包含关系:A=|xA yA xy 真包含关系:A=|xA yA xy,2023/7/11,集合论与图论第5讲,37,与二元关系有关的概念,定义域,值域,域逆,合成(复合)限制,象单根,单值,2023/7/11,集合论与图论第5讲,38,定义域,值域,域,对任意集合R,可以定义:定义域(domain):dom R=x|y(xRy)值域(range):ran R=y|x(xRy)域(field):fld R=dom R ran R,2023/7/11,集合论与图论第5讲,39,定义域,值域,域图示,A,B,dom R,ran R,2023/7/11,集合论与图论第5讲,40,定义域,值域,域(举例),例:R1=a,b,R2=a,b,R3=,.当a,b不是有序对时,R1和R2不是关系.dom R1=,ran R1=,fld R1=dom R2=c,e,ran R2=d,f,fld R2=c,d,e,fdom R3=1,3,5,ran R3=2,4,6,fld R3=1,2,3,4,5,6.#,2023/7/11,集合论与图论第5讲,41,逆,合成(复合),对任意集合F,G,可以定义:逆(inverse):F-1=|yFx 合成(复合)(composite):FG=|z(xGz zFy),x,z,y,G,F,2023/7/11,集合论与图论第5讲,42,关于合成,顺序合成(右合成):FG=|z(xFz zGy)逆序合成(左合成):FG=|z(xGz zFy),2023/7/11,集合论与图论第5讲,43,限制,象,对任意集合F,A,可以定义:限制(restriction):FA=|xFy xA 象(image):FA=ran(FA)FA=y|x(xA xRy),2023/7/11,集合论与图论第5讲,44,单根,单值,对任意集合F,可以定义:单根(single rooted):F是单根的y(yran F!x(xdom F xFy)(yran F)(!xdom F)(xFy)单值(single valued):F是单值的x(xdom F!y(yran F xFy)(xdom F)(!yran F)(xFy),2023/7/11,集合论与图论第5讲,45,例题2,例2:设 A=a,b,c,d,B=a,b,R=,F=,G=,.求:(1)A-1,B-1,R-1.(2)BR-1,GB,GR,RG.(3)Fa,Fa,Fa,a,F-1a.(4)Fa,Fa,a,F-1a,F-1a.,2023/7/11,集合论与图论第5讲,46,例题2(解(1),已知:A=a,b,c,d,B=a,b,R=,求:(1)A-1,B-1,R-1.解:(1)A-1=,B-1=,R-1=,.,2023/7/11,集合论与图论第5讲,47,例题2(解(2),已知:B=a,b,R=,G=,.求:(2)BR-1,GB,GR,RG.解:(2)BR-1=,GB=,GR=,RG=.,2023/7/11,集合论与图论第5讲,48,例题2(解(3),已知:F=,求:(3)Fa,Fa,Fa,a,F-1a.解:(3)Fa=,Fa=,Fa,a=F,F-1a=.,2023/7/11,集合论与图论第5讲,49,例题2(解(4),已知:F=,求:(4)Fa,Fa,a,F-1a,F-1a.解:(4)Fa=b,a,Fa,a=b,a,a,a,F-1a=,F-1a=a.#,2023/7/11,集合论与图论第5讲,50,例题3,设 R=|x,yZ y=|x|,A=0,1,2,B=0,-1,-2 求:(1)RAB 和 RARB;(2)RA-RB 和 RA-B.解:(1)RAB=R0=0,RARB=0,1,20,1,2=0,1,2;(2)RA-RB=0,1,2-0,1,2=,RA-B=R1,2=1,2.#,2023/7/11,集合论与图论第5讲,51,定理3,定理3:设F,G是任意集合,则(1)dom(FG)=domF domG(2)ran(FG)=ranF ranG(3)dom(FG)domF domG(4)ran(FG)ranF ranG(5)domF-domG dom(F-G)(6)ran F-ranG ran(F-G),2023/7/11,集合论与图论第5讲,52,定理3(证明(1),(1)dom(FG)=domF domG证明:(1)x,xdom(FG)y(x(FG)y)y(xFy xGy)y(xFy)y(xGy)xdomF xdomG x domF domG dom(FG)=domF domG.,2023/7/11,集合论与图论第5讲,53,定理3(证明(4),(4)ran(FG)ranF ranG证明:(4)x,xran(FG)y(y(FG)x)y(yFx yGx)y(yFx)y(yGx)xranF xranG x ranF ranG ran(F G)ranF ranG.,2023/7/11,集合论与图论第5讲,54,定理3(证明(5),(5)domF-domG dom(F-G)证明:(5)x,xdomF-domG xdomF xdomG y(xFy)y(xGy)y(xFy)y(xGy)y(x(F-G)y)x dom(F-G)domF-domG dom(F-G).#,2023/7/11,集合论与图论第5讲,55,定理4,定理4:设F是任意集合,则(1)domF-1=ranF;(2)ranF-1=domF;(3)(F-1)-1 F,当F是关系时,等号成立.,2023/7/11,集合论与图论第5讲,56,定理4(证明(1),(1)domF-1=ranF;证明:(1)x,xdomF-1 y(xF-1 y)y(yFx)xranF domF-1=ranF.(2)可类似证明.,2023/7/11,集合论与图论第5讲,57,定理4(证明(3),(3)(F-1)-1 F,当F是关系时,等号成立.证明:(1)设F是关系,则,(F-1)-1 x(F-1)-1y yF-1x xFy.这时(F-1)-1=F.当F不是关系时,(F-1)-1F,例如,设 F=,a,则 F-1=,(F-1)-1=F(F-1)-1 F.#,2023/7/11,集合论与图论第5讲,58,定理5,定理5:设R1,R2,R3为集合,则(R1R2)R3=R1(R2R3)证明:,(R1R2)R3 z(xR3z z(R1R2)y)z(xR3z t(zR2t tR1y)zt(xR3z(zR2t tR1y)tz(xR3z zR2t tR1y),2023/7/11,集合论与图论第5讲,59,定理5(续),证明(续):tz(xR3z zR2t tR1y)t(z(xR3z zR2t)tR1y)t(x(R2R3)t tR1y)xR1(R2R3)y R1(R2R3)(R1R2)R3=R1(R2R3).#说明:定理5说明合成运算具有结合律.,x,z,t,y,R3,R2,R1,2023/7/11,集合论与图论第5讲,60,总结,1.有序对与卡氏积:,AB 2.二元关系:RAB,RAA;,IA,EA;xRy 3.二元关系的基本运算:dom(R),ran(R),fld(R);RA,RA;R-1,RS,2023/7/11,集合论与图论第5讲,61,作业(#3),p80,习题二,6,7,11,12,