Mathematics Division, School of Advanced Sciences and Languages

VIT Bhopal University

MAT2002-Discrete Mathematics and Graph Theory

ny
Practice Set-2
Prepared by: Dr. Juhi Kesarwani & Dr. Ashish Kumar Kesarwany

wa
============================================

ar
es
1 Basic Set Theory

K
Exercise 1:

ar
Let R, S and T be sets. Then,

um
1. S ∪ T = T ∪ S and S ∩ T = T ∩ S
(union and intersection are commutative operations).

K
2. R ∪ (S ∪ T ) = (R ∪ S) ∪ T and R ∩ (S ∩ T ) = (R ∩ S) ∩ T
(union and intersection are associative operations).
ish
sh
3. S ⊆ S ∪ T , T ⊆ S ∪ T .
.A

4. S ∩ T ⊆ S, S ∩ T ⊆ T .
Dr

5. S ∪ ϕ = S, S ∩ ϕ = ϕ.
i&

6. S ∪ S = S ∩ S = S.

7. R ∪ (S ∩ T ) = (R ∪ S) ∩ (R ∪ T ).
n
wa

(union distributes over intersection).

ar

8. R ∩ (S ∪ T ) = (R ∩ S) ∪ (R ∩ T ).
(intersection distributes over union).
es
iK

Exercise 2:
Let U be the universal set and S, T ⊆ U . Then,
uh

1. U c = ϕ and ϕc = U .
.J

2. S ∪ S c = U and S ∩ S c = ϕ.
Dr

1
 3. S ∪ U = U and S ∩ U = S.

4. (S c )c = S.

ny
5. S ⊆ S c if and only if S = ϕ.

wa
6. S c ⊆ T c if and only if T ⊆ S.

ar
7. S = T c if and only if S ∩ T = ϕ and S ∪ T = U .

es
8. S − T = S ∩ T c and T − S = T ∩ S c .

K
9. S∆T = (S ∪ T ) − (S ∩ T ).

ar
10. De-Morgan’s Laws:

um
(a) (S ∪ T )c = S c ∩ T c .
(b) (S ∩ T )c = S c ∪ T c .

K
The De-Morgan’s laws help us to convert arbitrary set expressions into those that involve only

ish
complements and unions or only complements and intersections.
sh
Exercise 3:
.A

1. Complete the proof of Lemma ??.

Dr

2. Prove the following:

(a) S ∪ (S ∩ T ) = S ∩ (S ∪ T ) = S.
i&

(b) S ∪ T = T if and only if S ⊆ T .

n
wa

(c) If R ⊆ T and S ⊆ T then R ∪ S ⊆ T .

ar

(d) If R ⊆ S and R ⊆ T then R ⊆ S ∩ T .

es
iK

(e) If S ⊆ T then R ∪ S ⊆ R ∪ T and R ∩ S ⊆ R ∩ T .

(f) If S ∪ T ̸= ϕ then either S ̸= ϕ or T ̸= ϕ.

uh
.J

(g) If S ∩ T ̸= ϕ then both S ̸= ϕ and T ̸= ϕ.

Dr

2
 (h) S ∪ T = S ∩ T if and only if S = T .

ny
Exercise 4:

wa
Let S and T be subsets of a universal set U.

1. Then prove Lemma ??.

ar
es
2. Suppose that S∆T = T . Is S = ϕ?

K
ar
Exercise 5:
Determine whether each of these statements is true or false.

um
1. 0 ∈ ϕ.

K
2. ϕ ∈ {0}.

ish
3. {0} ⊆ ϕ

4. ϕ ⊆ {0}
sh
5. {0} ∈ {0}.
.A

6. {0} ⊆ {0}
Dr

7. {ϕ} ⊆ {ϕ}
i&

Exercise 6:
What is the cardinality of each of these sets?
n
wa

1. {a}.

2. {{a}}.
ar

3. {a, {a}}.
es

4. {a, {a}, {a, {a}}}.

iK
uh

Exercise 7:
Find the power set of each of these sets, where a and b are distinct elements.
.J

1. {a}.
Dr

3
 2. {a, b}.

3. {ϕ, {ϕ}}.

ny
wa
Exercise 8:
Let A, B, and C be sets. Show that A ∪ (B ∩ C) = (C̄ ∪ B̄) ∩ Ā.

ar
es
Exercise 9:
Let A and B are sets. Show that

K
1. (A ∩ B) ⊆ A.

ar
2. A ⊆ (A ∪ B)

um
3. A − B ⊆ A.

K
4. A ∩ (B − A) = ϕ

ish
5. A ∪ (B − A) = A ∪ B.
sh
Exercise 10:
.A

Show that if A and B are sets, then A − B = A ∩ B̄.

Exercise 11:
Dr

Show that if A and B are sets, then (A ∩ B) ∪ (A ∩ B̄) = A.

i&

Exercise 12:
There are total of 200 students in class XI. 120 of them study mathematics, 50 students study commerce
n

and 30students study both mathematics and commerce. Find the number of students who
wa

(i) Study mathematics but not commerce

ar

(ii) Study commerce but not mathematics

es

(iii) Study mathematics or commerce.

iK

Exercise 13:
uh

Among a group of students, 50 played cricket, 50 played hockey and 40 played volley ball. 15 played
both cricket and hockey, 20 played both hockey and volley ball, 15 played cricket and volley ball and 10
.J

played all three. If every student played at least one game, find the number of students and how many
played only cricket, only hockey and only volley ball?
Dr

4
 Exercise 14:
In a cricket school, 12 players like bowling, 15 like batting, and 5 like both. Then how many players
like either bowling or batting.

ny
wa
Exercise 15:
Consider the following Venn diagram. Find the following

ar
1. The number of students that prefer either burger or pizza or both.

es
2. The number of students that prefer both burger and pizza.

K
3. The number of students that prefer a burger, pizza as well as hotdog.

ar
4. The number of students that do not prefer a burger.

um
K
ish
sh
.A
Dr
i&

Equivalence relation
n
wa

Exercise 16:
Let A=Z+ , the positive integers, and R be the relation defined by aRb if and only if there exists a k in
ar

Z+ so that a = bk . Which of the following belong to R?

es

1. (4,16)
iK

2. (1,3)
uh

3. (4,2)
.J

4. (2,8)

5. (4,4)
Dr

5
 6. (2,16)

ny
Exercise 17:
Let A = 2, 4 and B = 6, 8, 10 and define binary relations R and S from A and B as follows:

wa
for all (x, y) ∈ A × B, xRy ⇔ x/y

ar
for all (x, y) ∈ A × B, xSy ⇔ y − 4 = x

es
State explicitly which ordered pairs are in A × B, R, S, R ∪ S, R ∩ S.

K
ar
Exercise 18:
Give example of a relation on the set of positive integers which is

um
1. symmetric and reflexive butt not transitive,

K
2. reflexive and transitive but not symmetric,

ish
3. symmetric, transitive but not reflexive,

4. reflexive but neither symmetric nor transitive,

sh
5. neither symmetric nor antisymmetric.
.A

Exercise 19:
Dr

Determine whether the relation R on the set of all integers is reflexive, symmetric, antisymmetric,
and/or transitive, where (x, y) ∈ R if and only if
i&

(a) x ̸= y, (b) xy ≥ 1, (c) x = y 2 .

(d) x ≥ y 2 , (e) x ≤ y + 1, (f ) |x + y| = 2.
n
wa

Exercise 20:
ar

Which of the relations defined in the set of real numbers are equivalence relation?
es

(a) aRb if and only if |a| = |b|

iK

(b) aRb if and only if a ≥ b

uh

(c) aRb if and only if |a| > |b|

.J
Dr

6
 Exercise 21:
Show that the relation R on the set of all triangles in the plane defined by

ny
R = {(a, b) : triangle a is similar to triangle b}

wa
is an equivalence relation.

ar
Exercise 22:

es
Show that the relation R over the set of all straight lines in the plane defined by ’is perpendicular to’
is symmetric but neither reflexive nor transitive.

K
Exercise 23:

ar
Let A be the set of non-zero integers and let R be the relation on A × A defined by

um
(a, b)R(c, d) ⇔ ad = bc

K
1. Show that R is an equivalence relation.

ish
2. Find [(2, 5)], i.e., the equivalence class of (2, 5). sh
Exercise 24:
.A

Let R be the relation of congruence modulo 3. Which of the following equivalence classes are equal?

[7], [−4], [−6], [17], [4], [27], [19]

Dr

Exercise 25:
i&

Let R = (1, 2), (1, 6), (2, 4), (3, 4), (3, 6), (3, 8) and S = (2, u), (4, s), (4, t), (6, t)(8.u). Find RoS.
n
wa

Exercise 26:
Let R and S be the relations on 1, 2, 3 defined by
ar

R = (1, 1), (1, 2), (3, 4), (4, 2)

es

and
iK

S = (1, 1), (2, 1), (3, 1), (4, 4), (2, 2)

. Find RoS and SoR.
uh

Exercise 27:
.J

Let A = {0, 1, 2, 3}, R = {(x, y) : x + y = 3}, S = {(x, y) : 3|(x + y)}, T = {(x, y) : max(x, y) = 3}.
Compute RoT , T oR, and SoS.
Dr

7
 Exercise 28:
If R is the relation on the set of positive integers such that (a, b) ∈ R if and only if a2 + b is even, prove
that R is an equivalence relation.

ny
wa
Exercise 29:
If R is the relation on the set of integers such that (a, b) ∈ R if and only if 3a + 4b = 7n for some

ar
integers n , prove that R is an equivalence relation.

es
Exercise 30:

K
If R is the relation defined by
(i) (a, b)R(c, d) if and only if a2 + b2 = c2 + d2

ar
um
(ii) (a, b)R(c, d) if and only if a + 2b = c + 2d.
Check whether the relations R defined as above are equivalence relations.

K
Exercise 31:

ish
Let R be the relation on the set of real numbers such that aRb if and only if a − b is an integer. Is R
an equivalence relation?
sh
Exercise 32:
.A

Let A = {1, 2, . . . , 9, 10} and let R be the relation on A defined by (a, b)R(c, d) if and only if ad = bc.
(i) Prove that R is an equivalence relation.
Dr

(ii) Find the equivalence class of .

n i&

Posets
wa

Exercise 33:
ar

Which of the following are posets?

es

(a) (Z, =) (b) (Z, ̸=) (c) (Z, >) (d) (Z, ≥) (e) (Z, ≤) (f) Relation R on Z defined by |x+y| =
2.
iK

Exercise 34:
uh

Which of the following are partial orders?

.J

(i) R = {(a, b) ∈ Z × Z : |a − b| ≤ 1}

(ii) R = {(a, b) ∈ Z × Z : |a| ≤ |b|}

Dr

8
 (iii) R = {(a, b) ∈ Z × Z : a divides b}

(iv) R = {(a, b) ∈ Z × Z : a − b ≤ 0}

ny
wa
Exercise 35:
Define a relation R on Z as

ar
mRn ⇐⇒ m + n is even.

es
Is R a partial order relation? Prove or give a counterexample.

K
Exercise 36:

ar
Consider the divides relation on each of the following sets. Draw the Hasse diagram for each relation.
Find

um
(a) All minimal and maximal elements.

K
(b) Greatest and least element.

ish
(i) S = {3, 5, 30, 60, 120, 180, 360}

(ii) S = {2, 3, 4, 6, 9}
sh
.A

Exercise 37:
Answer the following questions concerning the poset
Dr

({{1}, {2}, {4}, {1, 2}, {1, 4}, {2, 4}, {3, 4}, {1, 3, 4}, {2, 3, 4}} , ⊆)
i&

(a) Find the maximal elements.

(b) Find the minimal elements.

n
wa

(c) Find all upper bounds of {{2}, {4}} and the least upper bound, if it exists.

(d) Find all upper bounds of {{1, 3, 4}, {2, 3, 4}} and the least upper bound.
ar
es
iK

Exercise 38:
Let R be the relation on the set of people such that xRy if x and y are people and x is older than y.
Show that R is not a partial ordering.
uh

Exercise 39:
.J

Draw the Hasse diagram for

Dr

9
 1. {1, 2, 3} × {1, 2, 3, 4} under lexicographic order.

ny
2. {1, 2, 3, 6, 9, 18} (all positive divisors of 18) with the relation as ‘divides’.

wa
3. {2, 3, 4, 5, 6, 7, 8} with the ‘divides’ relation.

ar
es
Exercise 40:
g

K
h

ar
Let A = {a, b, c, d, e, f, g, h, i} have the a
partial ordering ⪯ defined by the following f

um
Hasse diagram. Find all maximal, mini- b
mal, greatest, and least elements of A. e i

K
ish
c d
sh
Exercise 41:
Draw the Hasse diagram for the “greater than or equal to” relation on {0, 1, 2, 3, 4, 5}.
.A

Exercise 42:
Dr

Draw the Hasse diagram for divisibility on the set

(a) {1, 2, 3, 4, 5, 6}
i&

(b) {3, 5, 7, 11, 13, 16, 17}

n

(c) {2, 3, 5, 10, 11, 15, 25}

wa

(d) {1, 3, 9, 27, 81, 243}

ar
es

Exercise 43:
Draw the Hasse diagram for the PoSET ({2, 4, 6, 8, 10, 12}, |).
iK

Exercise 44:
uh

Draw the Hasse diagram for the POSET ({2, 4, 8, 16, 32}, |).
.J

Exercise 45:
Given the poset ({1, 2, 3, 5, 6, 7, 10, 20, 30, 60, 70}, |)
Dr

10
 a) Draw the Hasse Diagram for this poset.

b) Find the maximal elements.

ny
c) Find the minimal elements.

wa
d) Find the greatest element

ar
e) Find the least element

es
f) Find all upper bounds of {2, 5}.

K
g) Find the least upper bound of {2, 5} (if it exists)

ar
h) Find all lower bounds of {6, 10}

um
i) Find the greatest lower bound of {6, 10} (if it exists)

K
Exercise 46:

ish
Consider the two posets X = {a, b, c} and Y = {a, b, c, d} described by the following Hasse diagrams:
d
sh
b c
b c
.A

a
a
Dr

Figure 1: X
Figure 2: Y
Fill in the blanks:
i&

1. Let A = X. Then,
n

(a) The maximal elements of A are .

wa

(b) The minimal element of A is .

ar

(c) The lower bound of A in X is .

es

(d) The upper bound of A in X is .

(e) The greates element of A is .
iK

(f) The minimum element of A is .

uh

(g) The lub of A in X is .

(h) The glb of A in X .
.J
Dr

11
 2. Fill in the blanks:

ny
A = {b, c} ⊆ X A = {a, c} ⊆ X A = {b, c} ⊆ Y
Maximal element(s) of A

wa
Minimal element(s) of A
Lower bound(s) of A in X

ar
Lower bound(s) of A in Y

es
Upper bound(s) of A in X
Upper bound(s) of A in Y

K
Greatest element of A
Minimum element of A

ar
lub of A in X

um
lub of A in Y
glb of A in X

K
glb of A in Y

Exercise 47:
ish
sh
Let A = {1, 2, 3} and S be the set of all proper non-empty subsets of A. In the poset (S, ⪯), where
⪯ is the set inclusion relation. Draw the diagraph of the relation ⪯ and the Hasse diagram of the poset.
.A

Find the maximal and minimal elements.

Dr

Exercise 48:
Draw the diagraph of the divisibility relation and Hasse diagram of the poset (D20 , |).
i&

Exercise 49:
Define a relation R on set of integers Z by mRn if and only if m2 = n2 . Is R a partial order relation?
n
wa

Exercise 50:
Find all the equivalence relation on the A = {1, 2, 3}.
ar
es

Exercise 51:
The following relations are defined on the set of real numbers R. Determine whether these relations
iK

are reflexive, symmetric, or transitive?

uh

1. aRb if and only if |a − b| > 0.

2. aRb if and only if 1 + ab > 0.

.J

3. aRb if and only if |a| ≤ b.

Dr

12
 Exercise 52:
The following relations are defined on the set of integers Z. Determine whether these relations are
equivalence relation.

ny
1. aRb if and only if |a − b| ≤ 4.

wa
2. aRb if and only if 7 | (b − a).

ar
es
Exercise 53:

K
Let A = {1, 2, 3, 4, 5} and a relation A be defined by

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

um
compute R2 and R3 .

K
Exercise 54:
For each of the following relations on A = {1, 2, 3, 4}, determine whether it is reflexive, symmetric, or

ish
transitive.

1. R = {(1, 4), (4, 1)}

sh
2. R = {(1, 1)}
.A

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

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

i&

Exercise 55:
Define a relation R on the set Z of all integers as follows: For all m, n ∈ Z,
n
wa

mRn ⇐⇒ m + n is even.
ar

Is R a partial order relation? Prove or give a counterexample.

es

Exercise 56:
iK

For the Hasse diagram given below, find maximal, minimal, greatest, least, LB, glb, UB, lub for the
subsets;
uh

(i) {d, k, f } (iii) {d} (v) {l, m}

.J

(ii) {b, h, f } (iv) {a, b, c}

Dr

13
 l m

ny
j k

wa
i h g

ar
e f

es
d

K
a b c

ar
um
Exercise 57:
Draw the Hasse diagram for (S, ⪯), where S = {2, 3, 6, 12, 24, 36} and x ⪯ y if and only if ‘x divides y ′ .

K
Also
(i) Find the least upper bound and greatest lower bound of A = {2, 3, 6}.

ish
(ii) Find the least upper bound and greatest lower bound of A = {6, 12}.
sh
(iii) Find the least upper bound and greatest lower bound of A = {24, 36}.
.A

Exercise 58:
Let the set D120 = {1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120} and let the relation ‘≤’ be the
Dr

relation ‘| divides’, i.e., a partial ordering on D120 .

1. Draw the Hasse Diagram of D120 .
i&

2. Determine lower bounds and the greatest lower bound (GLB) of B, where
n

B = {4, 6, 10}
wa

3. Determine upper bounds and the least upper bound (LUB) of B, where
ar

B = {4, 6, 10}
es

4. Determine lower bounds and the greatest lower bound (GLB) of B, where
iK

B = {12, 20, 30}

uh

5. Determine upper bounds and the least upper bound (LUB) of B, where
.J

B = {12, 20, 30}

Dr

14