42关系的运算 S={4,1, RUS={<1,1>,<1,3》,<2,2>,<2,4),<3,1> <3,3》,<4,2>,<4,4》,<4,1); R∩S=O;SR=S={4,1}; R=AXA-R={<1,2>,<1,4>,<2,1>,<2,3),<3,2> <3,4>,<4,1>,<4,3分 R⊕S=(RUS)-(R∩s)=RUS >关系的补运算是对全关系而言的; 关系的并,交,差,补的矩阵可用如下方法求取: RUS R S4R∩S Ma∧Ms R-S=M RnS=M R ∧ 11157
11/57 4.2 关系的运算 S={<4,1>}， ∴ R∪S={<1,1>，<1,3>，<2,2>，<2,4>，<3,1>， <3,3>，<4,2>，<4,4>，<4,1>}； R∩S= ； S-R= S={<4,1>}； ~R= A×A-R={<1,2>，<1,4>，<2,1>，<2,3>，<3,2> ，<3,4>，<4,1>，<4,3>}； R S=(R∪S)-(R∩S)= R∪S. ➢关系的补运算是对全关系而言的； ➢关系的并，交，差，补的矩阵可用如下方法求取： R S R S R S S S R S R S R S R S M M M M M M M M M M M M = = = = = − , , ,
42关系的运算 2关系的逆运算 由于关系是序偶的集合,除了集合的一般运算外, 还有一些特有的运算。 ·定义4.11:设R是A到B的关系,R的逆关系或逆是B 到A的关系,记为R,定义为:R1={<y,x>xy 显然对任意x∈Ay∈B,有x分wRx; M为R的关系矩阵,则M=MR 例:l4=L4,O-=0 A={a,b,c,d,B=[1,2,3},R=<a,1>,<c,2〉 <b,2>,<d,3},R-={<1,a>,<2,c>,<2, b>,<3,d}。 12/57
12/57 4.2 关系的运算 • 2.关系的逆运算 由于关系是序偶的集合，除了集合的一般运算外， 还有一些特有的运算。 •定义4.11：设R是A到B的关系，R的逆关系或逆是B 到A的关系，记为 ，定义为： ➢显然对任意 ，有 ； ➢ 为R的关系矩阵，则 . 例： ； A={a, b, c, d}，B={1,2,3}，R={<a, 1>，<c, 2> ，<b, 2>，<d, 3>}， ={<1, a>，<2, c>，<2, b>，<3, d>}。 −1 R { , | } 1 R = y x xRy − x A, y B xRy yR x −1 MR M R M R = −1 = = −1 −1 , A A I I 1 R −
42关系的运算 ·定理4.1:设R和S都是A到B上的二元关系,那么 1、-1 (1)(R) R (2)(R)=R (3)(R∩S)=R∩S,(RUS)=RUS,(R-S)=R-S (4)(R∈S)台RcS; (5 ).domR=ranR, ranr =domE (6)O=0,、(A×B)=B×A 13/57
13/57 4.2 关系的运算 •定理4.1：设R和S都是A到B上的二元关系，那么 (6). ,( ) . (5). , ; (4).( ) ; (3).( ) ,( ) ,( ) ; (2).( ) ; (1).( ) ; 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 A B B A domR ranR ranR domR R S R S R S R S R S R S R S R S R R R R = = = = = = − = − = = − − − − − − − − − − − − − − − − − − −
42关系的运算 3关系的复合运算 ·定义4.12:设R,S为二元关系,则R与S的复合关 系RS定义为:RoS={<x,y3(xR∧tSy)},其中 为复合运算,R。R也记为R 例:设R表示父子关系,则R2表示祖孙关系。 例4-4:设集合A={0,1,2,3,4},R,S均为A上的二 元关系,且R={<x,y>|x+y=4}={<0,4>,<4,0 <1,3>,<3,1,<2,2,S=={<x,y>|y- x=1}={<0,1>,<1,2>,<2,3>,<3,4};求 RoS,Sor,RoR,SoS,(RoSoRRoSoR) 一般地,RoS≠S。R 14/57
14/57 4.2 关系的运算 • 3.关系的复合运算 •定义4.12：设R，S为二元关系，则R与S的复合关 系 定义为： ，其中 “ ”为复合运算， 也记为 。 例：设R表示父子关系，则 表示祖孙关系。 • 例4-4：设集合A={0,1,2,3,4}，R，S均为A上的二 元关系，且R={<x, y>|x+y=4}={<0,4>，<4,0>， <1,3>，<3,1>，<2,2>}，S= ={<x, y>|yx=1}={<0,1>，<1,2>，<2,3>，<3,4>}；求 ➢一般地， R S R S ={ x, y | t(xRt tSy)} R R 2 R 2 R R S, S R,R R, S S,(R S)R,R (SR) R S S R
42关系的运算 定理4.2:设F,G,H为任意二元关系,则 ( ). FoGoH=FoGGo,(2). FOG=GOF ·定理4.3:设R为A上的关系,则 (1)Ro4=I4°R(2.O。R=RO=0 定理4.4:设F,G,H为任意二元关系,则 (1)Fo(G∪H)= FoGUFoH (2)(G∪H)F=GoF∪HF, (3).Fo(G∩H)=FoG∩F°H (4)(G∩H)°F=G°F∩H°F 15/57
15/57 4.2 关系的运算 •定理4.2：设F，G，H为任意二元关系，则 •定理4.3：设R为A上的关系，则 •定理4.4：设F，G，H为任意二元关系，则 1 1 1 (1).( ) ( ),(2).( ) − − − F G H = F G H F G = G F RI = I R R = R = A A (1). ,(2). (4).( ) . (3). ( ) , (2).( ) , (1). ( ) , G H F G F H F F G H F G F H G H F G F H F F G H F G F H = = = =