离散数学屈婉玲第七章

1主要内容有序对与笛卡儿积二元关系的定义与表示法关系的运算关系的性质关系的闭包等价关系与划分偏序关系第七章二元关系27.1有序对与笛卡儿积定义7.1由两个元素x和y，按照一定的顺序组成的二元组称为有序对，记作x,y.有序对性质:(1)有序性x,yy,x（当xy时）(2)x,y与u,v相等的充分必要条件是x,y=u,vx=uy=v.3笛卡儿积定义7.2设A,B为集合，A与B的笛卡儿积记作AB，且AB={x,y|xAyB}.例1A={1,2,3},B={a,b,c}AB={1,a,1,b,1,c,2,a,2,b,2,c,3,a,3,b,3,c}BA={a,1,b,1,c,1,a,2,b,2,c,2,a,3,b,3,c,3}A={},B=P(A)A={,,{},}P(A)B=4笛卡儿积的性质(1)不适合交换律ABBA(AB,A,B)(2)不适合结合律(AB)CA(BC)(A,B,C)(3)对于并或交运算满足分配律A(BC)=(AB)(AC)(BC)A=(BA)(CA)A(BC)=(AB)(AC)(BC)A=(BA)(CA)(4)若A或B中有一个为空集，则AB就是空集.A=B=(5)ACBDABCD.(6)若|A|=m,|B|=n,则|AB|=mn5性质证明证明A(BC)=(AB)(AC)证任取x,yx,y∈A×(B∪C)x∈A∧y∈B∪Cx∈A∧(y∈B∨y∈C)(x∈A∧y∈B)∨(x∈A∧y∈C)x,y∈A×B∨x,y∈A×Cx,y∈(A×B)∪(A×C)所以有A×(B∪C)=(A×B)∪(A×C).6实例例2(1)证明A=B,C=DAC=BD(2)AC=BD是否推出A=B,C=D?为什么？解(1)任取x,yx,yACxAyCxByDx,yBD(2)不一定.反例如下：A={1}，B={2},C=D=,则AC=BD但是AB.77.2二元关系定义7.3如果一个集合满足以下条件之一：(1)集合非空,且它的元素都是有序对(2)集合是空集则称该集合为一个二元关系,简称为关系，记作R.如果x,y∈R,可记作xRy；如果x,yR,则记作xy实例：R={1,2,a,b},S={1,2,a,b}.R是二元关系,当a,b不是有序对时，S不是二元关系根据上面的记法，可以写1R2,aRb,ac等.8A到B的关系与A上的关系定义7.4设A,B为集合,A×B的任何子集所定义的二元关系叫做从A到B的二元关系,当A=B时则叫做A上的二元关系.22n例3A={0,1},B={1,2,3},那么R1={0,2},R2=A×B,R3=,R4={0,1}R1,R2,R3,R4是从A到B的二元关系,R3和R4也是A上的二元关系.计数:|A|=n,|A×A|=n2,A×A的子集有个.所以A上有个不同的二元关系.例如|A|=3,则A上有=512个不同的二元关系.9A上重要关系的实例定义7.5设A为集合,(1)是A上的关系，称为空关系(2)全域关系EA={x,y|x∈A∧y∈A}=A×A恒等关系IA={x,x|x∈A}小于等于关系LA={x,y|x,y∈A∧x≤y},A为实数子集整除关系DB={x,y|x,y∈B∧x整除y},A为非0整数子集包含关系R={x,y|x,y∈A∧xy},A是集合族.10实例例如,A={1,2},则EA={1,1,1,2,2,1,2,2}IA={1,1,2,2}例如A={1,2,3},B={a,b},则LA={1,1,1,2,1,3,2,2,2,3,3,3}DA={1,1,1,2,1,3,2,2,3,3}例如A=P(B)={,{a},{b},{a,b}},则A上的包含关系是R={,,,{a},,{b},,{a,b},{a},{a},{a},{a,b},{b},{b},{b},{a,b},{a,b},{a,b}}类似的还可以定义：大于等于关系,小于关系,大于关系,真包含关系等.11关系的表示1.关系矩阵若A={x1,x2,…,xn}，R是A上的关系，R的关系矩阵是布尔矩阵MR=(rij)nn,其中rij=1xi,xjR2.关系图若A={x1,x2,…,xm}，R是从A上的关系，R的关系图是GR=A,R,其中A为结点集，R为边集.如果xi,xj属于关系R，在图中就有一条从xi到xj的有向边.注意：关系矩阵适合表示有穷集A上的关系（可推广为从A到B的关系）关系图适合表示有穷集A上的关系12实例例4A={1,2,3,4},R={1,1,1,2,2,3,2,4,4,2},R的关系矩阵MR和关系图GR如下：0010000011000011RM137.3关系的运算关系的基本运算定义7.6关系的定义域、值域与域分别定义为domR={x|y(x,yR)}ranR={y|x(x,yR)}fldR=domRranR例5R={1,2,1,3,2,4,4,3},则domR={1,2,4}ranR={2,3,4}fldR={1,2,3,4}14关系运算(逆与合成)定义7.7关系的逆运算R1={y,x|x,yR}定义7.8关系的合成运算FG={x,y|t(x,tFt,yG)}例6R={1,2,2,3,1,4,2,2}S={1,1,1,3,2,3,3,2,3,3}R1={2,1,3,2,4,1,2,2}RS={1,3,2,2,2,3}SR={1,2,1,4,3,2,3,3}15合成的图示法利用图示（不是关系图）方法求合成RS={1,3,2,2,2,3}SR={1,2,1,4,3,2,3,3}16关系运算(限制与像)定义7.9设R为二元关系,A是集合(1)R在A上的限制记作R↾A,其中R↾A={x,y|xRy∧x∈A}(2)A在R下的像记作R[A],其中R[A]=ran(R↾A)说明：R在A上的限制R↾A是R的子关系，即R↾ARA在R下的像R[A]是ranR的子集，即R[A]ranR17实例例7设R={1,2,1,3,2,2,2,4,3,2},则R↾{1}={1,2,1,3}R↾=R↾{2,3}={2,2,2,4,3,2}R[{1}]={2,3}R[]=R[{3}]={2}18关系运算的性质定理7.1设F是任意的关系,则(1)(F1)1=F(2)domF1=ranF,ranF1=domF证(1)任取x,y,由逆的定义有x,y∈(F1)1y,x∈F1x,y∈F.所以有(F1)1=F.(2)任取x,x∈domF1y(x,y∈F1)y(y,x∈F)x∈ranF所以有domF1=ranF.同理可证ranF1=domF.19定理7.2设F,G,H是任意的关系,则(1)(FG)H=F(GH)(2)(FG)1=G1F1关系运算的性质证(1)任取x,y,x,y(FG)Ht(x,t∈FG∧t,y∈H)t(s(x,s∈F∧s,t∈G)∧t,y∈H)ts(x,s∈F∧s,t∈G∧t,y∈H)s(x,s∈F∧t(s,t∈G∧t,y∈H))s(x,s∈F∧s,y∈GH)x,y∈F(GH)所以(FG)H=F(GH)20证明(2)任取x,y,x,y∈(FG)1y,x∈FGt(y,t∈F∧t,x∈G)t(x,t∈G1∧t,y∈F1)x,y∈G1F1所以(FG)1=G1F121关系运算的性质定理7.3设R为A上的关系,则RIA=IAR=Rx,yx,y∈RIAt(x,t∈R∧t,y∈IA)t(x,t∈R∧t=y∧y∈A)x,y∈R22关系运算的性质定理7.4(1)F(GH)=FG∪FH(2)(G∪H)F=GF∪HF(3)F(G∩H)FG∩FH(4)(G∩H)FGF∩HF只证(3)任取x,y,x,y∈F(G∩H)t(x,t∈F∧t,y∈G∩H)t(x,t∈F∧t,y∈G∧t,y∈H)t((x,t∈F∧t,y∈G)∧(x,t∈F∧t,y∈H))t(x,t∈F∧t,y∈G)∧t(x,t∈F∧t,y∈H)x,y∈FG∧x,y∈FHx,y∈FG∩FH所以有F(G∩H)=FG∩FH23推广定理7.4的结论可以推广到有限多个关系R(R1∪R2∪…∪Rn)=RR1∪RR2∪…∪RRn(R1∪R2∪…∪Rn)R=R1R∪R2R∪…∪RnRR(R1∩R2∩…∩Rn)RR1∩RR2∩…∩RRn(R1∩R2∩…∩Rn)RR1R∩R2R∩…∩RnR24关系运算的性质定理7.5设F为关系,A,B为集合,则(1)F↾(A∪B)=F↾A∪F↾B(2)F[A∪B]=F[A]∪F[B](3)F↾(A∩B)=F↾A∩F↾B(4)F[A∩B]F[A]∩F[B]25证明证只证(1)和(4).(1)任取x,yx,y∈F↾(A∪B)x,y∈F∧x∈A∪Bx,y∈F∧(x∈A∨x∈B)(x,y∈F∧x∈A)∨(x,y∈F∧x∈B)x,y∈F↾A∨x,y∈F↾Bx,y∈F↾A∪F↾B所以有F↾(A∪B)=F↾A∪F↾B.26证明(4)任取y,y∈F[A∩B]x(x,y∈F∧x∈A∩B)x(x,y∈F∧x∈A∧x∈B)x((x,y∈F∧x∈A)∧(x,y∈F∧x∈B))x(x,y∈F∧x∈A)∧x(x,y∈F∧x∈B)y∈F[A]∧y∈F[B]y∈F[A]∩F[B]所以有F[A∩B]=F[A]∩F[B].27关系的幂运算定义7.10设R为A上的关系,n为自然数,则R的n次幂定义为：(1)R0={x,x|x∈A}=IA(2)Rn+1=RnR注意：对于A上的任何关系R1和R2都有R10=R20=IA对于A上的任何关系R都有R1=R28例8设A={a,b,c,d},R={a,b,b,a,b,c,c,d},求R的各次幂,分别用矩阵和关系图表示.0000100001010010M解R与R2的关系矩阵分别是：0000000010100101000010000101001000001000010100102M幂的求法29R3和R4的矩阵是：因此M4=M2,即R4=R2.因此可以得到R2=R4=R6=…，R3=R5=R7=…R0的关系矩阵是0000000010100101,000000000101101043MM10000100001000010M幂的求法30关系图R0,R1,R2,R3,…的关系图如下图所示.R0R1R2=R4=…R3=R5=…31幂运算的