SRM Institute of Science and Technology
College of Engineering and Technology
Department of Mathematics
SRM Nagar, Kattankulathur – 603203, Chengalpattu District, Tamilnadu
Academic Year: 2023-2024(ODD)
Tutorial sheet - 2
Date: 24/07/2023
Course Code &Title: 18MAB302T-Discrete Mathematics for Engineers
Year & Sem: III/V
Q. Questions Answer keys
No
1 State TRUE or FALSE with proper justification for each of the (a) False, (b) True,
(c) True, (d) False.
following statements:
(a) If 𝑅1 and 𝑅2 are partial order relation on 𝐴, then 𝑅1 − 𝑅2 is a
partial order relation.
(b) If 𝑅1 and 𝑅2 are equivalence relations on 𝐴, then 𝑅1 ∩ 𝑅2 is an
equivalence relation.
(c) If 𝑅1 and𝑅2 are transitive, then 𝑅1 ∪ 𝑅2 need not be transitive.
(d) If 𝑅1 and 𝑅2 are both symmetric, then 𝑅1 ∘ 𝑅2 is symmetric.
2 For the poset {3,5,9,15,24,45}, with divisibility relation defined on it.
Draw the Hasse diagram of the poset.
3 Let𝑅bethefollowingequivalencerelationontheset𝐴 = {1,2,3,4,5,6}, and
𝑅 = {(1,1), (1,5), (2,2), (2,3), (2,6), (3,2), (3,3), [1] = {1,5}, [2]
(3,6), (4,4), (5,1), (5,5), (6,2), (6,3), (6,6)} = {2,3,6},
Find the equivalence classes of 𝑅. Hence find the partition of [3] = {2,3,6}, [4]
𝐴 induced by 𝑅. = {4,4},
[5] = {1,5}, [6]
= {2,3,6}.
𝑃(𝐴)
= {{1,5}, {2,3,6}, {4}}
4 For the relation 𝑅 = {(1,2), (2,3), (3,3), (3,4), (4,2)} defined on 𝑋 = 0 1 1 1
{1,2,3,4}, find the transitive closure of 𝑅 using Warshall’s algorithm. (0 1 1 1)
0 1 1 1
0 1 1 1
5 Given A = {1, 2, 3, 4} and R = {(1,2), (1,1), (1,3), (2,4), (3,2)} and S 𝑆 ∘ 𝑅 = {(1,3),(1,4),
= {(1,4), (1,3), (2,3), (3,1), (4,1)} are relations on A. Find 𝑆 ∘ 𝑅 and (2,1),(3,3)}
write its matrix representation. 1 0 1 1
(1 0 0 0)
0 0 1 0
0 0 0 0
6 Let D be a set of all positive divisor of 30. A relation is defined on D as “a
R b iff a divides b”, for a, b in D. Prove that R is a partial ordered relation.
Hence draw the Hasse diagram of the poset.
7 Show that 𝑅 = {(𝐴, 𝐵) | 𝐴 ⊆ 𝐵} on the power set of {𝑎, 𝑏, 𝑐} is a
partial order relation.
8 Let 𝐴 = {1, 2, 3, 4, 5, 6 } and P = {{1, 5}, {2, 3, 6}, {4}} be a partition
on A. Find the equivalence relation R determines P. R= {(1,1), (1,5), (5,
1), (5,5), (2,2),
(2,3), (2,6), (3,2),
(3,3), (3,6), (6,2),
(6,3), (6,6), (4,4)}
9 Let 𝑅 is the relation on 𝐴 = {1, 2, 3} such that (𝑎, 𝑏) ∈ 𝑅 if and only if 1 0 1
𝑀𝑅 = ( 0 1 0 )
𝑎 + 𝑏 is even, find the relational matrix 𝑀𝑅 and 𝑀𝑅′ .
1 0 1
0 1 0
𝑀𝑅′ = ( 1 0 1 )
0 1 0
10 Let R be a relation defined on the set of all real numbers, by ‘if x, y
are real numbers, x R y ⟺ x – y is a rational number’.
Show that R is an equivalence relation.