2. 4 Operations on Relations 1.Inverse relation Definition 2.13: let r be a relation from a to B. The inverse relation o ofr is a relation from B to A, we write R-I, defined by R-l= {(b,a)(a2b)∈R}
1.Inverse relation Definition 2.13: Let R be a relation from A to B. The inverse relation of R is a relation from B to A, we write R-1 , defined by R-1= {(b,a)|(a,b)R} 2.4 Operations on Relations
Theorem 2.1: Let R, Ri, and R, be relation from a to B. Then (1)R1)=R; (2)(R1UR2)=R1∪R21; (3)(R1R2)=R1nR21 (4)(×B)=B×A; (5)1= 6)R-1=R (7)(R1R2)=R1R21 (8)If r,sR, then RicR2
Theorem 2.1：Let R,R1 , and R2 be relation from A to B. Then (1)(R-1 ) -1=R; (2)(R1∪R2 ) -1=R1 -1∪R2 -1 ; (3)(R1∩R2 ) -1=R1 -1∩R2 -1 ; (4)(A×B)-1=B×A; (5)-1=; 1 1 (6) − − R = R (7)(R1 -R2 ) -1=R1 -1 -R2 -1 (8)If R1R2 then R1 -1R2 -1
Theorem 22: Letr be a relation on a. Then R is symmetric if only ifR=R-. Proof: (1)IfR is symmetric, then R=R- RcR-I RIcR。 (2)IfR=R-, then r is symmetric For any(a2b)∈R,(b,a)∈?R
Theorem 2.2：Let R be a relation on A. Then R is symmetric if only if R=R-1 . Proof: (1)If R is symmetric, then R=R-1 。 RR-1 and R-1R。 (2)If R=R-1 , then R is symmetric For any (a,b)R, (b,a)?R
2. Composition Definition 2. 14: Letr be a relation from a to B. and r be a relation from b to c. the composition onI and R,, we write N21s IS a relation from a to c. and is defined R,=la, c there exist some beB so that (a2b)∈R1and(b,c∈R2, where aea and ceo (R is a relation from A to B, and R2 is a relation from b to c (2)commutative law? x R1={(a1,b1),(a2b3),(a1,b2)} R2={(b4a1),(b4C1),(b2,a2,(b3C2)
2.Composition Definition 2.14: Let R1 be a relation from A to B, and R2 be a relation from B to C. The composition of R1 and R2 , we write R2 R1 , is a relation from A to C, and is defined R2 R1={(a,c)|there exist some bB so that (a,b)R1 and (b,c)R2 , where aA and cC}. (1)R1 is a relation from A to B, and R2 is a relation from B to C (2)commutative law? R1={(a1 ,b1 ), (a2 ,b3 ), (a1 ,b2 )} R2={(b4 ,a1 ), (b4 ,c1 ), (b2 ,a2 ), (b3 ,c2 )}
Associative law? ForR1cA×B,R2cB×C,andR2cCD R3(R2R1)=(R3R2)R1 subset ofa×D For any(a,d)∈R3(R2R1),(a,d)∈2(R3R2)R1, Similarity, (R3oR)or,CR3(R2oR1) Theorem 2.3: Letr be a relation from a to B.R be a relation fromb to c.r be a relation fromc to D Then R3(R2or=(r3oR)R,(Associative law
Associative law? For R1 A×B, R2B×C, and R3C×D R3 (R2 R1 )=?(R3 R2 )R1 subset of A×D For any (a,d)R3 (R2 R1 ), (a,d)?(R3 R2 )R1 , Similarity, (R3 R2 )R1R3 (R2 R1 ) Theorem 2.3：Let R1 be a relation from A to B, R2 be a relation from B to C, R3 be a relation from C to D. Then R3 (R2 R1 )=(R3 R2 )R1 (Associative law)