《复合关系与关系的闭包》由会员分享，可在线阅读，更多相关《复合关系与关系的闭包（51页珍藏版）》请在金锄头文库上搜索。
1、集合与关系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.整数集合上的“”关系的逆关系是“, , S= , . 求: (1)Rc ，Sc.(2) RS, SR 解: (1) Rc = ,Sc = ,.(2
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) R
3、3 = R1(R2 R3). # 说明: 本定理说明复合运算满足结合律. 由复合关系满足结合律，可以把关系R本身所组成的复合关系写成：RR， RRR， RRR(m个)，分别记作 R(2)， R(3)， ， R(m)。特别可以证明复合关系不满足交换律。R1R2 R2R17-3.3关系矩阵的性质：(1) MRc = (MR)T. ( T表示矩阵转置)(2) MR1 R2 = MR1MR2 (表示布尔乘法, 其中加法使用逻辑, 乘法使用逻辑 )3-7.4逆关系关系图的性质：关系 Rc 的图形是将关系R图形中弧的 箭头方向反置。定理2: 设R、 R1 、 R2都是从A到B的二元关系，则有(1)( R1
4、 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是对
5、称的 (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=, 用M
6、R1, MR2确定MR1c , MR2c, MR1R1, MR1R2, MR2R1, 从而求出它们的集合表达式.1 1 0 1 1 0 MR1= 1 0 1 MR1c= 1 0 00 0 0 0 1 00 1 1 0 0 0 MR2= 0 0 1 MR2c= 1 0 00 0 0 1 1 00 1 1 MR1R2 =MR1 MR2= 0 1 10 0 0 R1R2 = ,.1 1 0 1 1 0 1 1 1 MR1R1 =MR1 MR1= 1 0 1 1 0 1 = 1 1 00 0 0 0 0 0 0 0 0 R1R1 = ,. 0 1 1 1 1 0 1 0 1 MR2R1 =MR2 MR
7、1= 0 0 1 1 0 1 = 0 0 00 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
8、 )是自反的;(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)是传递的;
9、(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)
10、 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
11、) = r( R1 )r( R2 )定理2: 设 RAA 且 A, 则(1) r( R ) = RIA;（证明用定义）(2) s( R ) = RRc; （证明用定义）(3) t( R ) = RR2R3.对比: R自反 IARR对称 R=RcR传递 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)求传递闭包的另一种方法：当有限
12、集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
13、(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(R). rt(R) = tr(R).(3) st(R) ts(R); 证明: st(R) st(s(R) = sts(R) = s(ts(R) ( ts(R)对称)= ts(R) st(R) ts(R). 本次课小结及要求关系的运算除集合运算外还有复合关系 、逆关系及闭包运算； 要求会做复合关系、逆关系及闭包运算 ，会做相应的证明。作业(3-8)： P127 (1) (2) a)(7) (选作）
