44 ~ Theory of Computer Science
Note: For getting the elements of R 1 0 R 2 , we combine (a, b) in R 1 and
(b, c) in R 2 to get (a, c) in R r 0 R 2 .
Theorem 2.2 Let 5 be a finite set and R be a relation in 5. Then the
transitive closure R+ of R exists and R+ = R U R
2 U R
3 .. , •
EXAMPLE 2.8
Let R = {(L 2). (2. 3), (2, 4)} be a relation in {l. 2, 3, 4}. Find R+.
Solution
R = {(1, 2), (2, 3), (2, 4)}
R
2 = {(1, 2), (2, 3), (2, 4)} 0 {(L 2), (2, 3), (2, 4)}
= {(1, 3), (1, 4)}
(We combine (a. b) and (b, c) in R to get (a, c) in R
2 .)
R
3
= R
2 0 R = {(l. 3). (1, 4)} 0 {(1, 2), (2, 3), (2, 4)} = 0
(Here no pair (a, b) in R
2 can be combined with any pair in R+--R 4 = R S = . . . = 0
~,
R+ = R U R
2 = {(1, 2), (2. 3). (2. 4). (1, 3), (1, 4)}
EXAMPLE 2.9
Let R = (Ca. b), (b, c). (c. a)}. Find R+.
Solution
R = {(a. b), (b, c), (c, a)}
R 0 R = {(a. b), (b. c), (c, a)} 0 {(a, b), (b, c), (c. a)}
= {(a. c), (b, a), (c. b)}
(This is obtained by combining the pairs: (a, b) and (b, c), (b, c) and (c, a),
and (c, a) and (a, b).)
R
3
= R
2 0 R = {(a, c), (b, a), (c, b)} 0 {(a, b), (b, c), (c, a)}
= {(a, a), (b, b), (c. c)}
R
4
= R
3 0 R = {(a, a), (b. b), (c, c)} 0 {(a, b), (b. c), (c, a)}
= {(a, b), (b, c), (c, a)} = R
So.
~=~oR=RoR=~
~=~oR=~oR=~
R
7
=R
6
0 R =R
3
0 R =~ =R
Then any R
I1 is one of R. R
2 or R
3 . Hence,
R+ =R U R
2 U R
3
={(a, b), (b, c), (c. a), (a, c). (b, a), (c, b), (a, a), (b, b), (c, c)}
Note: R* = R+ U {(a, a)! a E 5}.