《复合关系与关系的闭包》由会员分享,可在线阅读,更多相关《复合关系与关系的闭包(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) (选作)