离散数学第4章关系.ppt

1,第4章关系,2,第4章关系,4.1关系的定义及其表示4.2关系运算4.3关系的性质4.4等价关系与偏序关系,3,4.1关系的定义及其表示,4.1.1有序对与笛卡儿积4.1.2二元关系的定义4.1.3二元关系的表示,4,定义4.1由两个元素，如x和y，按照一定的顺序组成的二元组称为有序对，记作实例：点的直角坐标(3,4)有序对的性质有序性（当xy时）与相等的充分必要条件是=x=uy=v例1=，求x,y.解3y4=2,x+5=yy=2,x=3,有序对,5,笛卡儿积,定义4.2设A,B为集合，A与B的笛卡儿积记作AB，AB=|xAyB.例2A=0,1,B=a,b,cAB=,BA=,A=,B=P(A)A=,P(A)B=,6,【例】设A=a,b，B=1,2,3，试求AB和BA验证|AB|=|A|B|和|BA|=|B|A|,解：AB=a,1,a,2,a,3,b,1,b,2,b,3BA=1,a,1,b,2,a,2,b,3,a,3,b|AB|=6=23=|A|B|BA|=6=32=|B|A|,7,笛卡儿积的性质,对于并或交运算满足分配律A(BC)=(AB)(AC)(BC)A=(BA)(CA)A(BC)=(AB)(AC)(BC)A=(BA)(CA)幻灯片9,若A或B中有一个为空集，则AB就是空集.A=B=,不适合交换律ABBA(AB,A,B)幻灯片6,不适合结合律(AB)CA(BC)(A,B,C)幻灯片8,若|A|=m,|B|=n,则|AB|=mn幻灯片6,8,解：ABC=(AB)C=1,a,1,b,2,a,2,bx,y=1,a,x,1,b,x,2,a,x,2,b,x,1,a,y,1,b,y,2,a,y,2,b,yA(BC)=1,2a,x,a,y,b,x,b,y=1,a,x,1,a,y,1,b,x,1,b,y2,a,x,2,a,y,2,b,x,2,b,y显然ABCA(BC)。,【例】设A=1,2，B=a,b，A=x,y，求：ABC，A(BC)。,9,证明：仅证明任取a,ba,bA(BC)aAbBCaA(bBbC)(aAbB)(aAbC)a,bABa,bACa,b(AB)(AC)故A(BC)=(AB)(AC)可类似地证明、。,A(BC)=(AB)(AC),10,有序n元组和n阶笛卡尔积,定义4.3(1)由n个元素x1,x2,xn按照一定的顺序排列构成有序n元组，记作(2)设A1,A2,An为集合，称A1A2An=|xiAi,i=1,2,n为n阶笛卡儿积.实例(1,1,0)为空间直角坐标，(1,1,0)RRR,11,二元关系的定义,定义4.4如果一个集合满足以下条件之一：（1）集合非空,且它的元素都是有序对（2）集合是空集则称该集合为一个二元关系,简称为关系，记作R.如R,可记作xRy；如果R,则记作xy实例：R=,S=,a,b.R是二元关系,当a,b不是有序对时，S不是二元关系根据上面的记法，可以写1R2,aRb,ac等.,12,实例,例3(1)R=|x,yN,x+y,(2)C=|x,yR,x2+y2=1，其中R代表实数集合，C是直角坐标平面上点的横、纵坐标之间的关系，C中的所有的点恰好构成坐标平面上的单位圆.(3)R=|x,y,zR,x+2y+z=3，R代表了空间直角坐标系中的一个平面.,13,5元关系的实例数据库实体模型,5元组：，,14,从A到B的关系与A上的关系,定义4.5设A,B为集合,AB的任何子集所定义的二元关系叫做从A到B的二元关系,当A=B时则叫做A上的二元关系.例4A=0,1,B=1,2,3,R1=,R2=AB,R3=,R4=,从A到B的关系:R1,R2,R3,R4,A上的关系R3和R4.计数：|A|=n,|B|=m,|AB|=nm,AB的子集有个.所以从A到B有个不同的二元关系.|A|=n,A上有不同的二元关系.例如|A|=3,则A上有512个不同的二元关系.,15,A上重要关系的实例,设A为任意集合，是A上的关系，称为空关系定义4.6EA,IA分别称为全域关系与恒等关系，其中EA=|xAyA=AAIA=|xA例如,A=1,2,则EA=,IA=,16,A上重要关系的实例（续）,小于等于关系LA,整除关系DA,包含关系R定义如下：定义4.7LA=|x,yAxy,这里AR，R为实数集合DB=|x,yBx整除y,BZ*,Z*为非0整数集R=|x,yAxy,这里A是集合族.例如A=1,2,3,B=a,b,则LA=,DA=,A=P(B)=,a,b,a,b,则A上的包含关系是R=,类似的还可以定义大于等于关系,小于关系,大于关系,真包含关系等等.,17,关系的表示,表示方式：关系的集合表达式、关系矩阵、关系图定义4.8关系矩阵若A=x1,x2,xm，B=y1,y2,yn，R是从A到B的关系，R的关系矩阵是布尔矩阵MR=rijmn,其中rij=1R.定义4.9关系图若A=x1,x2,xm，R是从A上的关系，R的关系图是GR=,其中A为结点集，R为边集.如果属于关系R，在图中就有一条从xi到xj的有向边.注意：设A,B为有穷集关系矩阵适合于表示从A到B的关系或者A上的关系关系图适合于表示A上的关系,18,2.用关系矩阵表示二元关系如果A，B是有限集，A=a1,a2,am，B=b1,b2,bn，R是A到B的二元关系，R的关系矩阵MR定义为：MR=mn,i=1,mj=1,n称为二元关系R的关系矩阵。,19,【例】设A=a1,a2,a3,a4，B=b1,b2,b3，R是A到B的二元关系，定义为：R=a1,b1,a1,b3,a2,b2,a2,b3,a3,b1,a4,b1,a4,b2写出R的关系矩阵。解：R的关系矩阵为：,MR=,20,【例】设A=1,2,3,4，R是A的二元关系，定义为：R=1,1,1,2,2,1,3,2,3,1,4,3,4,2,4,1写出A上二元关系R的关系矩阵。解：R的关系矩阵为：,MR=,21,3.用关系图表示二元关系如果A和B是有限集，R是A到B二元关系，还可以用图表示二元关系R。表示二元关系R的图叫做R的关系图。A到B二元关系的关系图和A上的二元关系的关系图的定义是不一样的。分别描述如下：,22,A到B二元关系R的关系图设A=a1,a2,am，B=b1,b2,bn，R是A到B二元关系，R的关系图的绘制方法如下：画出m个小点表示A的元素，再画出n个小点表示B的元素。这些小点叫做关系图的顶点(下同)。如果ai,bjR，则从ai到bj画一根有方向(带箭头)的线。这些有方向(带箭头)的线叫做关系图的边(下同)。,23,【例】设A=a1,a2,a3,a4，B=b1,b2,b3，R是A到B的二元关系，定义为：R=a1,b1,a1,b3,a2,b2,a2,b3,a3,b1,a4,b1,a4,b2R的关系图如下：,24,A上的二元关系R的关系图设A=a1,a2,am，R是A上的二元关系，其关系图如下绘制：画出m个小点表示A的元素。如果ai,ajR，则从ai到aj画一根有方向(带箭头)的线。,25,例5A=a,b,c,d,R=,R的关系矩阵MR和关系图GR如下：,26,【例】设A=1,2,3,4，R是A的二元关系，R=1,1,1,2,2,1,3,2,3,1,4,3,4,24,1A上二元关系R的关系图如下：,27,4.2.1关系的基本运算定义域、值域、域、逆、合成基本运算的性质4.2.2关系的幂运算幂运算的定义幂运算的方法幂运算的性质,4.2关系运算,28,关系的基本运算,定义4.10定义域、值域和域domR=x|y(R)ranR=y|x(R)fldR=domRranR,例1R=,则domR=ranR=fldR=,a,c,a,d,b,d,a,c,a,d,b,d,d,29,关系的基本运算（续）,定义4.11R的逆R1=|R定义4.12R与S的合成RS=|y(RS),例2R=,S=,R1=RS=SR=,30,合成运算的图示方法,利用图示（不是关系图）方法求合成RS=,SR=,31,基本运算的性质,定理4.1设F是任意的关系,则(1)(F1)1=F(2)domF1=ranF,ranF1=domF证(1)任取,由逆的定义有(F1)1F1F所以有(F1)1=F(2)任取x,xdomF1y(F1)y(F)xranF所以有domF1=ranF.同理可证ranF1=domF.,32,定理4.2设F,G,H是任意的关系,则(1)(FG)H=F(GH)(2)(FG)1=G1F1证(1)任取,(FG)Ht(FGH)t(s(FG)H)ts(FGH)s(Ft(GH)s(FGH)F(GH)所以(FG)H=F(GH),基本运算的性质（续）,33,(2)任取,(FG)1FGt(F(t,x)G)t(G1(t,y)F1)G1F1所以(FG)1=G1F1,基本运算的性质（续）,34,定理4.3设R为A上的关系,则RIA=IAR=R证明任取RIAt(RIA)t(Rt=yyA)R从而有RIA=R.同理可证IAR=R.,基本运算的性质（续）,35,A上关系的幂运算定义,定义4.13设R为A上的关系,n为自然数,则R的n次幂是(1)R0=|xA=IA(2)Rn+1=RnR注意：对于A上的任何关系R1和R2都有R10=R20=IA对于A上的任何关系R都有R1=R,36,幂运算的方法,对于集合表示的关系R，计算Rn就是n个R合成.矩阵表示的关系就是矩阵相乘,其中相加采用逻辑加.例3设A=a,b,c,d,R=,求R的各次幂,分别用矩阵和关系图表示.解R与R2的关系矩阵分别为,37,同理R3和R4的矩阵是：因此M4=M2,即R4=R2.因此可以得到R2=R4=R6=,R3=R5=R7=而R0=IA的关系矩阵,幂运算的方法（续）,38,用关系图的方法得到R0,R1,R2,R3,的关系图如下图所示,幂运算的方法（续）,39,幂运算的性质,定理4.4设A为n元集,R是A上的关系,则存在自然数s和t,使得Rs=Rt.证R为A上的关系,由于|A|=n,A上的不同关系只有个.当列出R的各次幂R0,R1,R2,必存在自然数s和t使得Rs=Rt.,40,定理4.5设R是A上的关系,m,nN,则(1)RmRn=Rm+n(2)(Rm)n=Rmn证用归纳法(1)对于任意给定的mN,施归纳于n.若n=0,则有RmR0=RmIA=Rm=Rm+0假设RmRn=Rm+n,则有RmRn+1=Rm(RnR)=(RmRn)R=Rm+n+1,所以对一切m,nN有RmRn=Rm+n.,幂运算的性质（续）,41,(2)对于任意给定的mN,施归纳于n.若n=0,则有(Rm)0=IA=R0=Rm0假设(Rm)n=Rmn,则有(Rm)n+1=(Rm)nRm=(Rmn)Rm=Rmn+m=Rm(n+1)所以对一切m,nN有(Rm)n=Rmn.,幂运算的性质（续）,42,定理4.6设R是A上的关系,若存在自然数s,t(st)使得Rs=Rt,则(1)对任何kN有Rs+k=Rt+k(2)对任何k,iN有Rs+kp+i=Rs+i,其中p=ts(3)令S=R0,R1,Rt1,则对于任意的qN有RqS证明(1)Rs+k=RsRk=RtRk=Rt+