UCCM1363 DISCRETE MATHEMATICS

TUTORIAL 4

1. If A = {a, b, c}, B = {1, 2} and C = {#, *}, list all the elements of A  B  C.

2. Let A = {a | a is a real number and −2  a  3} and B = {b | b is a real number

and 1  b  5}. Sketch the given set in the Cartesian plane.
(i) AB (b) BA

3. Let A = {a | a is a real number} and B = {1, 2, 3}. Sketch the given set in the
Cartesian plane.
(i) AB (b) BA

4. Let A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} and A1 = {1, 2, 3, 4}, A2 = {5, 6, 7}, A3 =

{4, 5, 7, 9}, A4 = {4, 8, 10}, A5 = {8, 9, 10}, A6 = {1, 2, 3, 6, 8, 10}.
Which of the following are partitions of A?
(a) {A1, A2, A5} (b) {A1, A3, A5}
(c) {A3, A6} (d) {A2, A3, A4}

5. Let A = {a, b, c, …, z}. Give a partition P of A such that |P| = 3 and each
element of P contains at least 5 elements.

6. List all partitions of B = {a, b, c, d}.

7. Let A = the set of real numbers and define a relation R on A as follows:

2
x R y if and only if x, y satisfy the equation x4 + y9 = 1 .
2

Which of the following ordered pairs belong to R?

(a) (2, 0) (b) (0, 2) (c) (0, 3)
3 3
(d) (0, 0) (e) (1, 2 )

8. Find the domain, range, matrix, and when A = B, the digraph of the
relation R.
(a) A = {a, b, c, d}, B = {1, 2, 3}, R = {(a, 1), (a, 2), (b, 1), (c, 2), (d, 1)}.
(b) A = {1, 2, 3, 4}, B = {1, 4, 6, 9}; a R b if and only if b = a2.
(c) A = {1, 2, 3, 4, 8}, B = {1, 4, 6, 9}; a R b if and only if a divides b.
(d) A = {1, 2, 3, 4, 5} = B; a R b if and only if a  b.

9. Let A = the set of real numbers. Consider the following relation R on A:

a R b if and only if a2 + b2 = 25.
Find Dom(R) and Ran(R).

10. Let R be the relation defined in Q7. Find R({1, 7}) and R({3, 4, 5}).

1
UCCM1363 DISCRETE MATHEMATICS
1 1 0 1
0 1 1 0
11. Let A = {1, 2, 3, 4} and MR =  . Give the relation R defined on A
0 0 1 1
 
1 0 0 0
and its digraph.

12. Find the relation determined by the following digraph and give its matrix, and
give the in-degree and the out-degree of each vertex.

2
4

3
5

13. Let R be the relation whose digraph is given as below:

2 3

1 4

6 5

(a) List all paths of length 2 starting from vertex 2.

(b) List all paths of length 2.
(c) Find a cycle starting at vertex 2.
(d) Draw the digraph of R2.
(e) Find M R2 .
(f) Find R.
(g) Find M R .

14. Let A = {1, 2, 3, 4, 5} and R be the relation defined by

a R b if and only if a < b.
Compute R2 and R3.

2
UCCM1363 DISCRETE MATHEMATICS

15. In each of the following, determine whether the relation is reflexive,

irreflexive, symmetric, asymmetric, antisymmetric, or transitive. Hence,
determine which of the following relation on the set A is an equivalence
relation.
(a) A = {1, 2, 3, 4},
(i) R = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (3, 4), (4, 3), (4, 4)}
(ii) R = {(1, 1), (2, 2), (3, 3)}
(iii) R = 
(iv) R=AA
1 1 0 0
 
1 1 0 0
(v) MR = 
0 0 1 0
 
0 0 0 1
 
(vi)
1 2

5 4

(b) A = ℤ; a R b  a  b + 1
(c) A = ℤ; x R y  |x – y|  2.
(d) A = ℝ; a R b  if a2 + b2 = 4.

16. Let A = {1, 2, 3, 4, 5, 6} {1, 2, 3, 4, 5, 6} and define a relation R on A

as follows:
For (a, b), (c, d)  A, (a, b) R (c, d) if and only if ab = cd.
(i) Verify that R is an equivalence relation on A.
(ii) Determine the equivalence class [(2, 3)].

17. Let R be the relation on A = {2, 4, 6, 8} defined by

x R y  GCD(x, y) = 2.
(i) Write R as a set of ordered pairs.
(ii) Determine whether R is an equivalence relation.

18. If {{1, 3, 5}, {2, 4}} is a partition of the set A = {1, 2, 3, 4, 5}, determine the
corresponding equivalence relation R.

3
UCCM1363 DISCRETE MATHEMATICS

19. Let R be the relation on the set of integers ℤ defined as follows:

For x, y  ℤ, x R y if and only if x − y is even.
(i) Show that R is an equivalence relation.
(ii) Find the equivalence class of 1 and the equivalence class of 2.

20. Let A = {1, 2, 3, 4, 5} and R be the relation on A defined by

1 1 1 0 1
1 1 1 0 1
 
M R = 1 1 1 0 1 .
 
0 0 0 1 0 
1 1 1 0 1
Compute A/R.

21. Let S = {1, 2, 3, 4} and A = S  S. Define the equivalence relation R on A as

follows:
(a, b) R (c, d) if and only if a + b = c + d.
Compute A/R.

22. Let A be the set of real numbers, R and S are two relations on A defined as
follows:
For x, y  A, x R y  x < y and x S y  x > y.
Describe
(i) RS (ii) RS
− 1
(iii) R , the inverse relation of R.

23. Let A = {2, 3, 6, 12} and let R and S be the following relations on A:
x R y if and only if 2|(x – y);
x S y if and only if 3|(x – y).
Compute
(a) R (b) RS
(c) RS (d) S−1

24. Let A = {1, 2, 3} and B = {1, 2, 3, 4}. Let R be the relations from A to B
whose matrices are given.
1 1 0 1 0 1 1 0
M R = 0 0 0 1 , M S = 1 0 0 1
 
1 1 1 0 1 1 0 0
Compute
(a) S (b) RS
(c) RS (d) S−1

4
UCCM1363 DISCRETE MATHEMATICS

25. Let A = {1, 2, 3, 4} and R = {(2, 1), (2, 3), (3, 2), (3, 3), (2, 2), (4, 2)}.
(a) Find the reflexive closure of R.
(b) Find the symmetric closure of R.

26. Let A = {1, 2, 3} and R = {(1, 1), (1, 2), (2, 3), (1, 3), (3, 1), (3, 2)}. Compute
the matrix M R of the transitive closure by using the formula
M R = M R  (M R ) 2  ( M R ) 3 .
Then give the relation R  .

27. Let A = {a1, a2, a3, a4, a5} and let R be a relation on A whose matrix is
1 0 0 1 0
 
0 1 0 0 0
MR =  0 0 0 1 1  = W0
 
1 0 0 0 0
0 1 0 0 1
 
Compute W1, W2 and W3 as in Warshall’s algorithm. Find R.

28. Let A = {1, 2, 3, 4}. For the relation R whose matrix is given, find the matrix
of the transitive closure by using Warshall’s algorithm.
1 1 0 0
1 0 0 0
MR =  
0 0 0 0 
 
0 0 1 0 

29. Let A = {a, b, c, d, e} and R and S be the relations on A described by

1 0 1 0 1  0 1 0 1 0 
0 0 0 1 0  1 1 0 0 1
   
MR = 1 0 0 0 0 and MS = 1 1 1 0 0 .
   
0 0 1 1 0  0 1 0 0 0 
1 0 1 0 0 0 1 0 1 0
Use Warshall’s algorithm to compute the transitive closure of R  S.

5
UCCM1363 DISCRETE MATHEMATICS

30. Let A = {1, 2, 3, 4, 5} and let R and S be the equivalence relations on A whose
matrices are given.
1 0 0 0 0 1 1 0 0 0
   
0 1 1 0 0 1 1 0 0 0
MR =  0 1 1 0 0  and MS =  0 0 1 0 0 
   
0 0 0 1 1 0 0 0 1 0
0 0 0 1 1 0 0 0 0 1
   
Compute the matrix of the smallest equivalence relation containing R and S,
and list the elements of this relation.

6
UCCM1363 DISCRETE MATHEMATICS

SOLUTION 4
1. A  B  C = {(a, 1, #), (a, 1, *), (a, 2, #), (a, 2, *), (b, 1, #), (b, 1, *), (b, 2, #),
(b, 2, *), (c, 1, #), (c, 1, *), (c, 2, #), (c, 2, *)}

2.
b a
5 3

1 b
1 5
a −2
−2 3

3.

b a
3
2
1 b
a 1 2 3

4. (a) Yes (b) No

(c) Yes (d) No

5. {{a, b, c, d, e, f}, {g, h, i, j, k}, {l, m, n, o, p, q, r, s, t, u, v, w, x, y, z}}

6. {{a, b, c, d}}
{{a}, {b, c, d}}, {{b}, {a, c, d}}, {{c}, {a, b, d}}, {{d}, {a, b, c}}, {{a, b},
{c, d}}, {{a, c}, {b, d}}, {{a, d}, {b, c}}
{{a}, {b}, {c, d}}, {{a}, {c}, {b, d}}, {{a}, {d}, {b, c}}, {{b}, {c}, {a, d}},
{{b}, {d}, {a, c}}, {{c}, {d}, {a, b}},
{{a}, {b}, {c}, {d}},

7. (a) Yes (b) No

(c) Yes (d) No
(e) Yes

8. (a) Dom(R) = {a, b, c, d}, Ran(R) = {1, 2}

 1 1 0
 
 1 0 0
MR = 
0 1 0
 
 1 0 0
 

7
UCCM1363 DISCRETE MATHEMATICS

(b) R = {(1, 1), (2, 4), (3, 9)}

Dom(R) = {1, 2, 3}, Ran(R) = {1, 4, 9}
1 0 0 0
 
 0 1 0 0
MR = 
0 0 0 1
 
 0 0 0 0
 

(c) R = {(1, 1), (1, 4), (1, 6), (1, 9), (2, 4), (2, 6), (3, 6), (3, 9), (4, 4)}
Dom(R) = {1, 2, 3, 4}, Ran(R) = {1, 4, 6, 9}
 1 1 1 1
 
 0 1 1 0
MR =  0 0 1 1 
 
 0 1 0 0
 0 0 0 0
 

(d) R = {(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 2), (2, 3), (2, 4), (2, 5), (3,
3), (3, 4), (3, 5), (4, 4), (4, 5), (5, 5)}
Dom(R) = {1, 2, 3, 4, 5}, Ran(R) = {1, 2, 3, 4, 5}
 1 1 1 1 1
  1
 0 1 1 1 1
MR =  0 0 1 1 1
  2 5
 0 0 0 1 1
 0 0 0 0 1
  3 4

9. Dom(R) = [−5, 5] b
Ran(R) = [−5, 5] 5

a
−5 5
−5

10. (a) R({1, 7}) = R(1)  R(7) = {− 3 2 3 , 3 2 3 }

(b) R({3, 4, 5}) = R(3)  R(4)  R(5) = { }

11. R = {(1, 1), (1, 2), (1, 4), (2, 2), (2, 3), (3, 3), (3, 4), (4, 1)}

1 2

4 3

8
UCCM1363 DISCRETE MATHEMATICS

12. R = {(1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (4, 1), (4, 4), (4, 5)}
 0 1 1 1 0
 
 0 1 1 0 0
MR =  0 0 0 0 0 
 
1 0 0 1 1
 0 0 0 0 0
 
Vertex a b c d e
In-degree 1 2 2 2 1
Out-degree 3 2 0 3 0

13. (a) 1 = 2, 3, 3, 2 = 2, 3, 4

(b) 1 = 1, 2, 3, 2 = 1, 6, 4, 3 = 2, 3, 3, 4 = 2, 3, 4,
5 = 3, 3, 3 6 = 3, 3, 4 7 = 3, 4, 5, 8 = 3, 4, 3, 9 = 3, 4, 1
10 = 4, 3, 3, 11 = 4, 3, 4, 12 = 4, 1, 2 13 = 4, 1, 6,
14 = 6, 4, 1, 15 = 6, 4, 3 16 = 6, 4, 5

(c) One of the cycle C1: 2, 3, 3, 4, 1, 2

2
(d) R2 = {(1, 3), (1, 4), (2, 3), (2, 4), (3, 3),
(3, 4), (3, 5), (3, 1), (4, 3), (4, 4), 3 6
(4, 2), (4, 6), (6, 1), (6, 3), (6, 5)} 1

0 0 1 1 0 0 4 5
 
0 0 1 1 0 0
1 0 1 1 1 0
(e) M R2 = 
0 1 1 1 0 1
0 0 0 0 0 0 

1 0 
 0 1 0 1

(f) R = {(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 1), (2, 2), (2, 3), (2,
4), (2, 5), (2, 6), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (3, 6), (4, 1), (4, 2),
(4, 3), (4, 4), (4, 5), (4, 6), (6, 1), (6, 2), (6, 3), (6, 4), (6, 5), (6, 6)}

1 1 1 1 1 1
 
1 1 1 1 1 1
1 1 1 1 1 1
(g) M R = 
1 1 1 1 1 1
0 0 0 0 0 0 

1 1 
 1 1 1 1

9
UCCM1363 DISCRETE MATHEMATICS

14. R = {(1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)}
1

2 5

3 4

R2 = {(1, 3), (1, 4), (1, 5), (2, 4), (2, 5), (3, 5)}
R3 = {(1, 4), (1, 5), (2, 5)}

1 1 0 0
 
1 1 0 0
15. (a) (i) MR = 
0 0 1 1
 
0 0 1 1
 
R is reflexive, symmetric and transitive. So R is an
equivalence relation.

1 0 0 0
 
 0 1 0 0
(ii) MR = 
0 0 1 0
 
 0 0 0 0
 
R is symmetric, antisymmetric, and transitive. So R is not an
equivalence relation.

 0 0 0 0
 
 0 0 0 0
(iii) MR = 
0 0 0 0
 
 0 0 0 0
 
R is irreflexive, symmetric, antisymmetric, asymetric and
transitive. So R is not an equivalence relation.

1 1 1 1
 
1 1 1 1
(iv) MR = 
1 1 1 1
 
1 1 1 1
 
R is reflexive, symmetric and transitive. So R is an equivalence
relation.

(v) R is reflexive, symmetric and transitive. So R is an equivalence

relation

10
UCCM1363 DISCRETE MATHEMATICS
1 1 1 0 1
 
0 0 1 0 0
(vi) MR =  0 0 0 0 0
 
0 1 1 1 1
0 0 1 0 0 

R is antisymmetric and transitive. So R is not an equivalence
relation.

(b) a  a + 1, so (a, a)  R.
R is reflexive.

We see that (1, 3)  R but (3, 1)  R, so R is not symmetric.

R is not asymmetric because R is reflexive.
R is not antisymmetric because 1 ≠ 2 but (1, 2)  R and (2, 1)  R.

R is not transitive because (3, 2)  R and (2, 1)  R but (3, 1)  R.

(c) |x – x| = 0  2, so (x, x)  R
R is reflexive and R is not irreflexive.

(x, y)  R  |x – y|  2
 |−(y – x)|  2
 |y – x|  2
 (y, x)  R
So R is symmetric.
R is not antisymmetric and not asymmetric.

We see that 1 R 3 and 3 R 5 but 1 R 5, so R is not transitive.

Hence R is not an equivalence relation.

(d) 12 + 12  4  (1, 1)  R, so R is not reflexive.

( 2) + ( 2)
2 2
=4  ( )
2 , 2  R, so R is not irreflexive.

(a, b)  R  a2 + b2 = 4
 b2 + a2 = 4
 (b, a)  R
 R is symmetric
So R is not asymmetric and not antisymmetric.

R is not transitive because 1 R 3 and 3 R 1 but 1 R 1.

16. (i) ab = ab  (a, b) R (a, b)

 R is reflexive.

11
UCCM1363 DISCRETE MATHEMATICS
((a, b), (c, d))  R  ab = cd
 cd = ab
 ((c, d), (a, b))  R
 R is symmetric.

Let ((a, b), (c, d))  R and ((c, d), (e, f))  R, then
ab = cd and cd = ef
 ab = ef
 ((a, b), (e, f))  R
 R is transitive.

So R is an equivalence relation on A.

(ii) [(2, 3)] = {(1, 6), (2, 3), (3, 2), (6, 1)}

17. (i) R = {(2, 2), (2, 4), (2, 6), (2, 8), (4, 2), (4, 6), (6, 2), (6, 4), (6, 8), (8,
2), (8, 6)}

(ii) R is not reflexive since (4, 4)  R, so R is not an equivalence relation.

18. R = {(1, 1), (1, 3), (1, 5), (2, 2), (2, 4), (3, 1), (3, 3), (3, 5), (4, 2), (4, 4), (5, 1),
(5, 3), (5, 5)}

19. (i) x – x = 0 is even, hence (x, x)  R and R is reflexive.

(x, y)  R  x – y is even
 y – x is even
 (y, x)  R
Hence R is symmetric.

Let (x, y)  R and (y, z)  R, then

x − y = 2k and y − z = 2l for some integer k, l
 x = 2k + y and z = 2l + y
 x − z = 2k − 2l
 x − z is even
 (x, z)  R
Hence R is transitive.

Thus, R is an equivalence relation.

(ii) [1] = {x | x −1 is even} = {x | x = 1 + 2k where k is an integer}

= the set of odd integers.

[2] = {y | y – 2 is even} = {y | y = 2 + 2l where l is an integer}

= the set of even integers

12
UCCM1363 DISCRETE MATHEMATICS
20. A/R = {[1], [4]}

21. [(1, 1)] = {(1, 1)}

[(1, 2)] = {(1, 2), (2, 1)} = [(2, 1)]
[(1, 3)] = {(1, 3), (3, 1), (2, 2)}= [(3, 1)] = [(2, 2)]
[(1, 4)] = {(1, 4), (4, 1), (2, 3), (3, 2)}= [(4, 1)] = [(2, 3)] = [(3, 2)]
[(2, 4)} = {(2, 4), (4, 2), (3, 3)] = [(4, 2)] = [(3, 3)]
[(3, 4)] = {(3, 4), (4, 3)} = [(4, 3)]
[(4, 4)] = {(4, 4)}
A/R = {[(1, 1)], [(1, 2)], [(1, 3)], [(1, 4)], [(2, 4], [(3, 4)], [(4, 4)]}.

22. (i) 
(ii) R  S is the relation consists of all ordered pairs (x, y) where x, y  ℝ
and x  y.
(iii) R−1 is the relation consists of all ordered pairs (x, y) where x, y  ℝ
and y < x.

23. R = {(2, 2), (2, 6), (2, 12), (3, 3), (6, 2), (6, 6), (6, 12), (12, 2), (12, 6), (12,
12)}
S = {(2, 2), (3, 3), (3, 6), (3, 12), (6, 3), (6, 6), (6, 12), (12, 3), (12, 6), (12,
12)}
(a) R = {(2, 3), (3, 2), (3, 6), (3, 12), (6, 3), (12, 3)}
(b) R  S = {(2, 2), (3, 3), (6, 6), (6, 12), (12, 6), (12, 12)}
(c) R  S = {(2, 2), (2, 6), (2, 12), (3, 3), (3, 6), (3, 12), (6, 2), (6, 3), (6,
6), (6, 12), (12, 2), (12, 3), (12, 6), (12,12)}
(d) S−1 = {(2, 2), (3, 3), (3, 6), (3, 12), (6, 3), (6, 6), (6, 12), (12, 3), (12, 6),
(12, 12)}

1 0 0 1
24. (a) M S = 0 1 1 0
0 0 1 1
S = {1, 1), (1, 4), (2, 2), (2, 3), (3, 3), (3, 4)}.

0 1 0 0 
(b) M RS = 0 0 0 1
1 1 0 0
R  S = {(1, 2), (2, 4), (3, 1), (3, 2)}.

1 1 1 1
(c) M RS = 1 0 0 1
1 1 1 0
R  S = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 1), (2, 4), (3, 1), (3, 2), (3, 3)}

13
UCCM1363 DISCRETE MATHEMATICS
0 1 1 
1 0 1
(d) M S −1 =  
1 0 0
 
0 1 0 
S−1 = {(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (4, 2)}

25. (a) Reflexive closure of R = {(1, 1), (2, 1), (2, 2), (2, 3), (3, 2), (3, 3), (2,
2), (4, 2), (4, 4)}.

(b) Symmetric closure of R = {(1, 2), (2, 1), (2, 3), (3, 2), (3, 3), (2, 2), (4,
2), (2, 4)}.

1 1 1
26. M R = 0 0 1
1 1 0
1 1 1 1 1 1 1 1 1
(M R ) = 0 0
2
1  0 0 1 = 1 1 0
1 1 0 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1
(M R ) = 0 0 1  1 1 0 = 1
3
1 1
1 1 0 1 1 1 1 1 1
M R = M R  (M R )  (M R )
2 3

1 1 1 1 1 1 1 1 1
= 0 0 1  1 1 0  1 1 1
1 1 0 1 1 1 1 1 1
1 1 1
= 1 1 1
1 1 1
R = A  A

1 0 0 1 0
 
0 1 0 0 0
(27) MR =  0 0 0 1 1  = W0
 
1 0 0 0 0
0 1 0 0 1
 
To compute W1, k = 1:
Column 1 of W0 has 1’s in location: 1, 4
Row 1 of W0 has 1’s in location: 1, 4

14
UCCM1363 DISCRETE MATHEMATICS
Thus, add (1, 1), (1, 4), (4, 1), (4, 4)
1 0 0 1 0
 
0 1 0 0 0
W1 =  0 0 0 1 1 
 
1 0 0 1 0
0 1 0 0 1
 

To compute W2, k = 2:
Column 2 of W1 has 1’s in location: 2, 5
Row 2 of W2 has 1’s in location: 2
Thus, add (2, 2), (5, 2)
1 0 0 1 0
 
0 1 0 0 0
W2 =  0 0 0 1 1 
 
1 0 0 1 0
0 1 0 0 1
 

To compute W3, k = 3:
Column 3 of W2 has 1’s in location: 2, 5
Row 3 of W2 has 1’s in location: 2
Thus, add (2, 2), (5, 2)
1 0 0 1 0
 
0 1 0 0 0
W3 =  0 0 0 1 1 
 
1 0 0 1 0
0 1 0 0 1
 

To compute W4, k = 4:
Column 4 of W3 has 1’s in location: 1, 3, 4
Row 4 of W3 has 1’s in location: 1, 4
Thus, add (1, 1), (1, 4), (3, 1), (3, 4), (4, 1), (4, 4)
1 0 0 1 0
 
0 1 0 0 0
W4 =  1 0 0 1 1 
 
1 0 0 1 0
0 1 0 0 1
 

To compute W5, k = 5:
Column 5 of W4 has 1’s in location: 3, 5
Row 5 of W4 has 1’s in location: 2, 5
Thus, add (3, 2), (3, 5), (5, 2), (5, 5)

15
UCCM1363 DISCRETE MATHEMATICS
1 0 0 1 0
 
0 1 0 0 0
W5 =  1 1 0 1 1  = M R
 
1 0 0 1 0
0 1 0 0 1
 

R = {(a1, a1), (a1, a4), (a2, a2), (a3, a1), (a3, a2), (a3, a4), (a3, a5), (a4, a1), (a4,
a4), (a5, a2), (a5, a5)}

1 1 0 0
1 0 0 0
(28) MR =   = W0
0 0 0 0 
 
0 0 1 0 
To compute W1, k = 1:
Column 1 of W0 has 1’s in location: 1, 2
Row 1 of W0 has 1’s in location: 1, 2
Thus, add (1, 1), (1, 2), (2, 1), (2, 2)
1 1 0 0
1 1 0 0
W1 =  
0 0 0 0 
 
0 0 1 0 

To compute W2, k = 2:
Column 2 of W1 has 1’s in location: 1, 2
Row 2 of W2 has 1’s in location: 1, 2
Thus, add (1, 1), (1, 2), (2, 1), (2, 2)
1 1 0 0
1 1 0 0
W2 =  
0 0 0 0 
 
0 0 1 0 

To compute W3, k = 3:
Column 3 of W2 has 1’s in location: 4
Row 3 of W2 has 1’s in location: 0
1 1 0 0
1 1 0 0
W3 =  
0 0 0 0 
 
0 0 1 0 

To compute W4, k = 4:
Column 4 of W3 has 1’s in location: 0

16
UCCM1363 DISCRETE MATHEMATICS
Row 4 of W3 has 1’s in location: 3
1 1 0 0
1 1 0 0
W4 =   = M 
0 0 0 0  R

 
0 0 1 0 

1 1 1 1 1
 
1 1 0 1 1
(29) MR  S =  1 1 1 0 0  = W0
 
0 1 1 1 0
1 1 1 1 0
 
To compute W1, k = 1:
Column 1 of W0 has 1’s in location: 1, 2, 3, 5
Row 1 of W0 has 1’s in location: 1, 2, 3, 4, 5
Thus, add (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5),
(3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (5, 1), (5, 2), (5, 3), (5, 4), (5, 5)
1 1 1 1 1
 
1 1 1 1 1
W1 =  1 1 1 1 1 
 
 0 1 1 1 0
1 1 1 1 1
 

To compute W2, k = 2:
Column 2 of W1 has 1’s in location: 1, 2, 3, 4, 5
Row 2 of W2 has 1’s in location: 1, 2, 3, 4, 5
Thus, add (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5),
(3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (4, 1), (4, 2), (4, 3), (4, 4), (4, 5), (5, 1), (5, 2),
(5, 3), (5, 4), (5, 5)
1 1 1 1 1
 
1 1 1 1 1
W2 = 1 1 1 1 1
 
1 1 1 1 1
1 1 1 1 1
 

To compute W3, k = 3:
Column 3 of W2 has 1’s in location: 1, 2, 3, 4, 5
Row 3 of W2 has 1’s in location: 1, 2, 3, 4, 5
W3 = W2

To compute W4, k = 4:
Column 4 of W3 has 1’s in location: 1, 2, 3, 4, 5

17
UCCM1363 DISCRETE MATHEMATICS
Row 4 of W3 has 1’s in location: 1, 2, 3, 4, 5
W4 = W3

To compute W5, k = 5:
Column 5 of W4 has 1’s in location: 1, 2, 3, 4, 5
Row 5 of W4 has 1’s in location: 1, 2, 3, 4, 5
W5 = W4 = M R
(R  S) = A  A

1 1 0 0 0
 
1 1 1 0 0
(30) MR  S =  0 1 1 0 0  = W0
 
0 0 0 1 1
0 0 0 1 1
 
To compute W1, k = 1:
Column 1 of W0 has 1’s in location: 1, 2
Row 1 of W0 has 1’s in location: 1, 2
Thus, add (1, 1), (1, 2), (2, 1), (2, 2)
1 1 0 0 0
 
1 1 1 0 0
W1 =  0 1 1 0 0 
 
0 0 0 1 1
0 0 0 1 1
 

To compute W2, k = 2:
Column 2 of W1 has 1’s in location: 1, 2, 3
Row 2 of W2 has 1’s in location: 1, 2, 3
Thus, add (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)
1 1 1 0 0
 
1 1 1 0 0
W2 =  1 1 1 0 0 
 
0 0 0 1 1
0 0 0 1 1
 

To compute W3, k = 3:
Column 3 of W2 has 1’s in location: 1, 2, 3
Row 3 of W2 has 1’s in location: 1, 2, 3
W3 = W2

To compute W4, k = 4:
Column 4 of W3 has 1’s in location: 4, 5
Row 4 of W3 has 1’s in location: 4, 5

18
UCCM1363 DISCRETE MATHEMATICS
Thus, add (4, 4), (4, 5), (5, 4), (5, 5)
W4 = W3

To compute W5, k = 5:
Column 5 of W4 has 1’s in location: 4, 5
Row 5 of W4 has 1’s in location: 4, 5
W5 = W4 = M R
(R  S) = {(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3), (4, 4),
(4, 5), (5, 4), (5, 5)}

19