广东工业大学离散数学第七章课件

广东工业大学计算机学院1主要内容7.1有序对与笛卡儿积7.2二元关系7.3关系的运算7.4关系的性质第七章二元关系7.5关系的闭包7.6等价关系与划分7.7偏序关系广东工业大学计算机学院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|=m,|B|=n,则|AB|=mn广东工业大学计算机学院5笛卡尔积图示ABCA(BC)=(AB)(AC)ACBDABCDBACD广东工业大学计算机学院6性质证明证明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).广东工业大学计算机学院7实例例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.广东工业大学计算机学院87.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等.RR注意：关系是笛卡尔积的子集广东工业大学计算机学院9A到B的关系与A上的关系定义7.4设A,B为集合,A×B的任何子集所定义的二元关系叫做从A到B的二元关系,当A=B时则叫做A上的二元关系.例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个不同的二元关系.n22n22广东工业大学计算机学院10A上重要的关系的实例定义7.5设A为集合,(1)是A上的关系，称为空关系(2)全域关系EA={x,y|x∈A∧y∈A}=A×A例如A={1,2},则EA={1,1,1,2,2,1,2,2}恒等关系IA={x,x|x∈A}例如A={1,2},则IA={1,1,2,2}小于等于关系LA={x,y|x,y∈A∧x≤y},A为实数子集例如A={1,2,3},B={a,b},则LA={1,1,1,2,1,3,2,2,2,3,3,3}广东工业大学计算机学院11A上重要关系的实例(续)定义7.5设A为集合,(2)(续)整除关系DB={x,y|x,y∈B∧x整除y},B为非0整数子集例如A={1,2,3},B={a,b},则DA={1,1,1,2,1,3,2,2,3,3}包含关系R={x,y|x,y∈A∧xy},A是集合族.例如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}}类似的还可以定义：大于等于关系,小于关系,大于关系,真包含关系等.广东工业大学计算机学院12关系的表示1.关系矩阵若A={x1,x2,…,xm}，B={y1,y2,…,yn}，R是从A到B的关系，R的关系矩阵是布尔矩阵MR=[rij]mn,其中rij=1xi,yjR.2.关系图若A={x1,x2,…,xm}，R是从A上的关系，R的关系图是GR=A,R,其中A为结点集，R为边集.如果xi,xj属于关系R，在图中就有一条从xi到xj的有向边.注意：(1)关系矩阵适合表示从A到B的关系或A上的关系（A,B为有穷集）(2)关系图适合表示有穷集A上的关系广东工业大学计算机学院13实例例4A={1,2,3,4},R={1,1,1,2,2,3,2,4,4,2},R是A上的关系，其关系矩阵MR和关系图GR如下：0010000011000011RM广东工业大学计算机学院147.3关系的运算关系的基本运算1.定义域、值域与域定义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}广东工业大学计算机学院15定义域,值域,域(举例)设A={1,2,3,4,5,6},B={a,b,c,d},R是从A到B关系R={2,a,2,b,3,b,4,d›,6,d},则domR=???ranR=???{2,3,4,6}{a,b,d}广东工业大学计算机学院162.关系运算——逆与合成定义7.7关系的逆运算R1={y,x|x,yR}定义7.8关系的合成运算RS={x,z|y(x,yRy,zS)}例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}广东工业大学计算机学院17合成的图示法利用图示（不是关系图）方法求合成R={1,2,2,3,1,4,2,2}S={1,1,1,3,2,3,3,2,3,3}RS=???SR=???{1,3,2,2,2,3}{1,2,1,4,3,2,3,3}广东工业大学计算机学院183.关系运算——限制与像定义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]ranR广东工业大学计算机学院19实例(1)R↾A={x,y|xRy∧x∈A}(2)R[A]=ran(R↾A)例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}广东工业大学计算机学院204.关系运算的性质(1)定理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.广东工业大学计算机学院21定理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)关系运算的性质(2)广东工业大学计算机学院22定理7.2证明(续)定理7.2设F,G,H是任意的关系,则(1)(FG)H=F(GH)(2)(FG)1=G1F1(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1拆解靠拢封装广东工业大学计算机学院23关系运算的性质(3)定理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∈R广东工业大学计算机学院24关系运算的性质(4)定理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H广东工业大学计算机学院25推广定理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R广东工业大学计算机学院26关系运算的性质(5)定理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]广东工业大学计算机学院27证明(1)F↾(A∪B)=F↾A∪F↾B证明：(1)任取x,yx,y∈F↾(A∪B)x,y∈F∧x∈A∪