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)
Definition 2. 15: Let r be a relation on A, and neN. The relation rn is defined as follows (1)RO=(a, a)laEA)), we write IA (2R叶+=RRn, Theorem 2. 4: Let r be a relation on A. and m,n∈N.Then (RmoR=Rmtn (2)(Rm=Rmm
Definition 2.15: Let R be a relation on A, and nN. The relation Rn is defined as follows. (1)R0 ={(a,a)|aA}), we write IA . (2)Rn+1=RRn . Theorem 2.4: Let R be a relation on A, and m,nN. Then (1)RmRn=Rm+n (2)(Rm) n=Rmn
A={a1,a2,…,anB,B={b1,b2…,bm R,and r, be relations from a to B. RIX i, mR2=(i M RIUR2(X MRnR2=(xr∧y) V01∧01 001000 111101 Example:A={2,3,4},B={1,3,5,7 R1={(2,3),(2,5),2,7),(3,5)、3,7),(45),(4,7) R2={(25)3,3),(4,1)4,7) Inverse relation R-I of R: MpMp, Mp is the transpose of M R
A={a1 ,a2 ,,an },B={b1 ,b2 ,,bm} R1 and R2 be relations from A to B. MR1=(xij), MR2=(yij) MR1∪R2=(xijyij) MR1∩R2=(xijyij) 0 1 0 1 0 0 1 0 0 0 1 1 1 1 0 1 Example:A={2,3,4},B={1,3,5,7} R1={(2,3),(2,5),(2,7),(3,5),(3,7),(4,5),(4,7)} R2={(2,5),(3,3),(4,1),(4,7)} Inverse relation R-1 of R : MR-1=MR T , MR T is the transpose of MR
A={a1;a2,…,an3,B={b1,b2,…,bm}, C={c1,C2,,}, rI be a relations from a to B, MRI(Ximxn, R2 be a relation from b to c、g2形xThe composition rori ofr, and r2s MRoR-((Xk Ayn)
A={a1 ,a2 ,,an },B={b1 ,b2 ,,bm }, C={c1 ,c2 ,,cr }, R1 be a relations from A to B, MR1=(xij)mn , R2 be a relation from B to C, MR2=(yij) nr . The composition R2 R1 of R1 and R2 , i k kj m r n k R R M x y = = (( )) 1 2 1
Example: R=((a, b),(b, a),(a, c), is not symmetrIc +(c,a)→>R={(a,b),(b,a)2(a2C),(c,a)},R Is symmetric Closure
Example：R={(a,b),(b,a),(a,c)},is not symmetric + (c,a),R'={(a,b),(b,a),(a,c), (c,a)}，R' is symmetric. Closure
2.5 Closures of Relations 1Introduction Construct a new relation r. s.t. rcr particular property, smallest relation closure Definition 2.17: Letr be a relation on a set a R is called the reflexive(symmetric, transitive closure of R, we write r(R)(s(R), t(R)or R), if there is a relation r with reflexivity(symmetry, transitivity) containing R such that R is a subset of every relation with reflexivity (symmetry, transitivity) containing R
2.5 Closures of Relations 1.Introduction Construct a new relation R‘, s.t. RR’, particular property, smallest relation closure Definition 2.17: Let R be a relation on a set A. R' is called the reflexive(symmetric, transitive) closure of R, we write r(R)(s(R),t(R) or R+ ), if there is a relation R' with reflexivity (symmetry, transitivity) containing R such that R' is a subset of every relation with reflexivity (symmetry, transitivity) containing R