4.2关系的运算 S={K4,1>}, RUS={K1,1>,<1,3>,<2,2>,<2,4>,<3,1>, <3,3>,<4,2>,<4,4>,4,1>}; R∩S=0;S-R=S={K4,1>}; R=AXA-R={K1,2>,<1,4>,<2,1>,<2,3>,3,2> ,<3,4>,<4,1>,<4,3>}; R⊕S=(RUS)-(R∩S)=RUS. >关系的补运算是对全关系而言的； >关系的并，交，差，补的矩阵可用如下方法求取： MRUS MRV Ms,MROS MRAMs, MR-s MROS MRMs,Ms Ms 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 = = = = = − , , ,
4.2关系的运算 ·2.关系的逆运算 由于关系是序偶的集合，除了集合的一般运算外， 还有一些特有的运算。 ·定义4.11：设R是A到B的关系，R的逆关系或逆是B 到A的关系，记为R1,定义为：R1={<y,x>xy} >显然对任意x∈A,y∈B,有x台yRx; >MR为R的关系矩阵，则MR=MR 例：14=14,01=0； A={a,b,c,d},B={1,2,3},R={Ka,1>,<c, 2> <b ,2>,<d,3>},R-1=K1,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 −
4.2关系的运算 ·定理4.1：设R和S都是A到B上的二元关系，那么 1).(R1)1=R; (2).(R)=R1; (3).(R∩S)=R∩S,(RUS)=R1US,(R-S)1=R1-S； (4).(R≤S)台RsS； (5).domR=ranR,ranR=domR: (6).0=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 = = = = = = − = − = = − − − − − − − − − − − − − − − − − − −
4.2关系的运算 •3.关系的复合运算 定义4.12：设R,S为二元关系，则R与S的复合关 ● 系RoS定义为：RoS={<x,y>3t(xRt∧tSy)},其中 “o”为复合运算，RoR也记为R。 例：设R表示父子关系，则R表示祖孙关系。 例4-4：设集合A={0,1,2,3,4},R,S均为A上的二 元关系，且R={Kx,y>x+y=4}={K0,4>,<4,0>, <1,3>,<3,1>,<2,2>},S={Kx,y>y- x=1}={<0,1>,<1,2>,<2,3>,<3,4>}；求 RoS,SoR,RoR,SoS,(RoS)oR,Ro(SoR) >一般地，RoS≠SoR 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为任意二元关系，则 (I).(F。G)oH=Fo(GoH),(2).(FoG)1=G1。F-1 ·定理4.3：设R为A上的关系，则 (1).RoI4=I4oR,(2).0oR=Ro0=0 ●定理4.4：设F,G,H为任意二元关系，则 (1).Fo(GUH)=FoGUFH. (2).(GUH)F=GoFUHF, (3).Fo(G∩H)=F。G∩FoH, (4).(G∩H)oF=GoF∩HoF. 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 = = = =