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

集合与关系3-4复合关系与关系的闭包 湖北汽车工业学院计算机工程系彭彬 3-7 复合关系和逆关系 3-7.1复合关系 定义1[复合 (合成)(composite)关系]: 设R为X到Y的关系，S为从Y到Z上的关系，则R°S称为R和S的复合关系，表示为： R°S={ x,z| x?X?z?Z?(?y)(y?Y?x,y?R?y,z?S)}. 注意：从左到右依次复合，不同教材处理方式不同。 3-7.2逆关系 定义2[逆(inverse)关系] : 设R是X到Y的二元关系，则从Y到X的二元关系Rc定义为：Rc = {y,x|x,y?R}. 整数集合上的“”关系的逆关系是“”关系。 人群中的父子关系的逆关系是子父关系。 容易看出(Rc) c=R 例1: 设 R={ a,b, c,d }, S={ b,e,d,c }. 求: (1)Rc ，Sc. (2) R°S, S°R 解: (1) Rc = {b,a,d,c} Sc = {e,b,c,d}. (2) R°S={a,e ,c,c} S°R={d,d}. 例2:（书上的例题2，第115页） 定理1: 设R1,R2,R3为关系， R1 是X到Y的关系， R2是Y到Z的关系， R3是Z到W的关系则(R1°R2)°R3 = R1° (R2° R3)． 证明: ?x,w, x,w?(R1 °R2) °R3 ? ?z(z?Z ? x (R1°R2)z ? zR3w ) ? ?z(z?Z ? ?y(y?Y ? xR1y ?yR2z ) ?zR3w) ? ?z?y(z?Z ? y?Y ? xR1y ?yR2z ?zR3w) ? ?yt?z(z?Z ? y?Y ? xR1y ?(yR2z ?zR3w) ) ? ?y(y?Y ? xR1y ??z(z?Z ? yR2z ?zR3w)) ? ?y(y?Y ? xR1y? y(R2°R3)w ) ? xR1°(R2°R3)w ? x,w?R1°(R2°R3) ? (R1°R2) °R3 = R1°(R2 ° R3). # 说明: 本定理说明复合运算满足结合律. 由复合关系满足结合律，可以把关系R本身所组成的复合关系写成： R°R， R°R°R，?， R°R°?°R(m个)， 分别记作 R(2)， R(3)， ?， R(m)。 特别 可以证明复合关系不满足交换律。 R1°R2? R2°R1 7-3.3关系矩阵的性质： (1) MRc = (MR)T. ( T表示矩阵转置) (2) MR1 ° R2 = MR1?MR2 (?表示布尔乘法, 其中加法使用逻辑?, 乘法使用逻辑? ) 3-7.4逆关系关系图的性质： 关系 Rc 的图形是将关系R图形中弧的箭头方向反置。 定理2: 设R、 R1 、 R2都是从A到B的二元关系，则有 (1)( R1? R2) c= R1 c ? R2 c (2) ( R1?R2) c= R1 c ? R2 c (3)(A×B) c= B ×A (4)(~R) c = ~ Rc, 这里~R ＝A×B-R (5) ( R1-R2) c = R1 c - R2 c 注：证明(1)(4)(5)见书117页。 定理4:设R为X上的二元关系，则 (1) R是对称的?R=Rc 证明：设R是对称的，则x,y?R?y,x ?R ?x,y ?Rc,即R=Rc 反之：若R=Rc ，?x,y?R? x,y?RC ? y,x?R，故R是对称的 (2) 是反对称的?R?Rc ? IX 证明：设R是反对称的， ?x,y? R?Rc ，则x,y? R且x,y? Rc，即 x,y? R且y,x? R。由反对称定义，则x=y，从而x,y=x,x ? IX,故R?Rc ? IX。 反之: ?x,y? R?Rc ,则x,y? IX ，从而x=y，故y,x ? R，即R是反对称的。 定理5:[P119 (2)]设R为X上的二元关系，则 R是传递的? (R°R) ?R 证明：?x,y?R°R,则?c满足x,c?R且c,y?R。由R的传递性，x,y?R，故(R°R)?R。 反之， ?x,y?R，y,z?R，则x,z?R°R。由于R是传递的，故x,z?R，从而(R°R) ?R (2) R是自反的? IX ?R 证明：?x?A,则x,x?IX?x,x?R?R是自反的。 反之， ?x,x?IX，若R是自反的，则x?A,且x,x ?R，从而IX ?R 例题: 设 A={a,b,c}, R1={a,a,a,