复合关系与关系的闭包.ppt

集合与关系3-4 复合关系与关系的闭包,湖北汽车工业学院计算机工程系彭彬,3-7 复合关系和逆关系,3-7.1复合关系 定义1复合 (合成)(composite)关系: 设R为X到Y的关系，S为从Y到Z上的关系，则RS称为R和S的复合关系，表示为： RS= | xXzZ(y)(yYRS). 注意：从左到右依次复合，不同教材处理方式不同。,3-7.2逆关系,定义2逆(inverse)关系 : 设R是X到Y的二元关系，则从Y到X的二元关系Rc定义为：Rc = |R. 整数集合上的“”关系的逆关系是“”关系。 人群中的父子关系的逆关系是子父关系。 容易看出(Rc) c=R,例1: 设 R= , , S= , . 求: (1)Rc ，Sc. (2) RS, SR 解: (1) Rc = , Sc = ,. (2) RS= , SR=. 例2:（书上的例题2，第115页）,定理1: 设R1,R2,R3为关系， R1 是X到Y的关系， R2是Y到Z的关系， R3是Z到W的关系则(R1R2)R3 = R1 (R2 R3) 证明: , (R1 R2) R3 z(zZ x (R1R2)z zR3w ) z(zZ y(yY xR1y yR2z ) zR3w) zy(zZ yY xR1y yR2z zR3w) ytz(zZ yY xR1y (yR2z zR3w) ) y(yY xR1y z(zZ yR2z zR3w) y(yY xR1y y(R2R3)w ) xR1(R2R3)w R1(R2R3) (R1R2) R3 = R1(R2 R3). # 说明: 本定理说明复合运算满足结合律.,由复合关系满足结合律，可以把关系R本身所组成的复合关系写成： RR， RRR， RRR(m个)， 分别记作 R(2)， R(3)， ， R(m)。 特别 可以证明复合关系不满足交换律。 R1R2 R2R1,7-3.3关系矩阵的性质：,(1) MRc = (MR)T. ( T表示矩阵转置) (2) MR1 R2 = MR1MR2 (表示布尔乘法, 其中加法使用逻辑, 乘法使用逻辑 ),3-7.4逆关系关系图的性质：,关系 Rc 的图形是将关系R图形中弧的箭头方向反置。,定理2: 设R、 R1 、 R2都是从A到B的二元关系，则有 (1)( R1 R2) c= R1 c R2 c (2) ( R1R2) c= R1 c R2 c (3)(AB) c= B A (4)(R) c = Rc, 这里R AB-R (5) ( R1-R2) c = R1 c - R2 c 注：证明(1)(4)(5)见书117页。,定理3: 设R,S为二元关系, 则(RS)c =S c Rc. 证明: , (RS)c (RS) z( yRz zSx ) z( zRcy xScz ) z( xScz zRcy) Sc Rc.,定理4:设R为X上的二元关系，则 (1) R是对称的R=Rc 证明：设R是对称的，则R R Rc,即R=Rc 反之：若R=Rc ，R RC R，故R是对称的 (2) 是反对称的RRc IX 证明：设R是反对称的， RRc ，则 R且 Rc，即 R且 R。由反对称定义，则x=y，从而= IX,故RRc IX。 反之: RRc ,则 IX ，从而x=y，故 R，即R是反对称的。,定理5:P119 (2)设R为X上的二元关系，则 R是传递的 (RR) R 证明：RR,则c满足R且R。由R的传递性，R，故(RR)R。 反之， R，R，则RR。由于R是传递的，故R，从而(RR) R (2) R是自反的 IX R 证明：xA,则IXRR是自反的。 反之， IX，若R是自反的，则xA,且 R，从而IX R,例题: 设 A=a,b,c, R1=, R2=, 用MR1, MR2确定MR1c , MR2c, MR1R1, MR1R2, MR2R1, 从而求出它们的集合表达式.,1 1 0 1 1 0 MR1= 1 0 1 MR1c= 1 0 0 0 0 0 0 1 0 0 1 1 0 0 0 MR2= 0 0 1 MR2c= 1 0 0 0 0 0 1 1 0 0 1 1 MR1R2 =MR1 MR2= 0 1 1 0 0 0 R1R2 = ,.,1 1 0 1 1 0 1 1 1 MR1R1 =MR1 MR1= 1 0 1 1 0 1 = 1 1 0 0 0 0 0 0 0 0 0 0 R1R1 = ,. 0 1 1 1 1 0 1 0 1 MR2R1 =MR2 MR1= 0 0 1 1 0 1 = 0 0 0 0 0 0 0 0 0 0 0 0 R2R1 = ,.,解: R1c = , R2c = , R1R1 = ,. R1R2 = ,. R2R1 = ,.,作业(3-7)：,P118 (1) (5),3-8 关系的闭包运算,有些关系有特殊的性质：如自反性、对称性、传递性等。 没有上述性质的关系，能否补充部分序偶，使之具有相应关系呢？ 如果可行，如何补充？（越简单越好） 如果可行，补充多少？（越少越好）,3-8.1自反闭包(reflexive closure),定义1自反闭包: 包含给定关系R的最小自反关系, 称为R的自反闭包, 记作r( R ). (1) r( R )是自反的; (2) R r( R ); (3)(S)( (RS S自反) r(R)S). 理解：r(R)是包含R且具有自反性的最小集合。,3-8.2对称闭包(symmetric closure),定义2对称闭包: 包含给定关系R的最小对称关系, 称为R的对称闭包, 记作s( R ). (1) s(R)是对称的; (2) R s(R); (3) (S)( (RS S对称) s(R)S ). 理解：s(R)是包含R且具有对称性的最小集合。,3-8.3传递闭包(transitive closure),定义3传递闭包: 包含给定关系R的最小传递关系, 称为R的传递闭包, 记作t(R). (1) t(R)是传递的; (2) R t(R); (3) (S)( (RS S传递) t(R)S ). 理解：t(R)是包含R且具有传递性的最小集合。,定理1: 设RAA且A,则 (1) R自反 r(R) = R; (2) R对称 s(R) = R; (3) R传递 t(R) = R; 证明: (1) 设R自反，由自反闭包的最小性有 r(R)R；又 R r(R), r(R) = R. 反之：xA，由于r(R)是A上自反关系，则(x,x)r(R) ,从而(x,x)R，故R是自反的 (2)(3) 完全类似.,*（补充）定理1:设 R1R2AA 且 A, 则 (1) r(R1) r(R2); (2) s(R1) s(R2); (3) t(R1) t(R2); 证明: (1) R1R2 r(R2)自反, r(R1) r(R2) (2)(3) 类似可证.,*（补充）定理2:设 R1,R2AA 且 A, 则 (1) r(R1R2) = r( R1 )r( R2 ); (2) s(R1R2) = s( R1 )s( R2 ); (3) t(R1R2) t( R1 )t( R2 ). 证明: (1) 由 R1 R1R2 , R2 R1R2 则 r(R1) r(R1R2 ) ,r(R2) r(R1R2 ) 从而 r(R1)r(R2) r(R1R2) 另一方面， r(R1)r(R2)自反且包含R1R2,所以 r(R1R2)r(R1)r(R2). r( R1R2) = r( R1 )r( R2 ),定理2: 设 RAA 且 A, 则 (1) r( R ) = RIA;（证明用定义） (2) s( R ) = RRc; （证明用定义） (3) t( R ) = RR2R3. 对比: R自反 IAR R对称 R=Rc R传递 R2R,构造闭包的方法,定理3：设X是含有n个元素的集合，R是X上的二元关系，则存在一个正整数kn，使得 t( R ) = RR2R3Rk,利用关系矩阵求闭包,设关系R，r(R),s(R),t(R)的关系矩阵分别为M,Mr,Ms,Mt,则 (1)Mr=M+I (2)Ms=M+MT (3)Mt=M+M2+.+MK(k=n),求传递闭包的另一种方法：,当有限集X的元素较多时，矩阵运算很繁琐，Warshall 在1962年提出了R+的一个有效算法如下：,利用关系图求闭包,引出下面定理： 闭包运算是否可以交换顺序?即： (1) rs( R ) = sr( R ) ? (2) rt( R ) = tr( R ) ? (3) st( R ) = ts( R ) ?,定理4：设 RAA 且 A, 则 (1) rs(R) = sr(R); (2) rt(R) = tr(R); (3) st(R) ts(R); 证明： (1) rs(R) = r(s(R) = r(RRc) = IA(RRc) = (IAR)(IAcRc) = (IAR)(IAR)c = r(R)r(R)c = s(r(R) = sr(R). rs(R) = sr(R).,(2)证明: rt(R) = r(t(R) = r(RR2 R3 ) = IA(RR2 R3 ) = (IAR)(IARR2)(IARR2R3) = (IAR)(IAR)2 (IAR)3 = r(R)r(R)2 r(R)3 =t(r