This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Relations – Equivalence Classes and Partitions”.

1. Suppose a relation R = {(3, 3), (5, 5), (5, 3), (5, 5), (6, 6)} on S = {3, 5, 6}. Here R is known as _________

a) equivalence relation

b) reflexive relation

c) symmetric relation

d) transitive relation

View Answer

Explanation: Here, [3] = {3, 5}, [5] = {3, 5}, [5] = {5}. We can see that [3] = [5] and that S/R will be {[3], [6]} which is a partition of S. Thus, we can choose either {3, 6} or {5, 6} as a set of representatives of the equivalence classes.

2. Consider the congruence 45≡3(mod 7). Find the set of equivalence class representatives.

a) {…, 0, 7, 14, 28, …}

b) {…, -3, 0, 6, 21, …}

c) {…, 0, 4, 8, 16, …}

d) {…, 3, 8, 15, 21, …}

View Answer

Explanation: Note that a set of class representatives is the subset of a set which contains exactly one element from each equivalence class. Now, for integers n, a and b, we have congruence a≡b(mod n), then the set of equivalence classes are {…, -2n, -n, 0, n, 2n,…}, {…, 1-2n, 1-n, 1, 1+n, 1+2n,…}. The required answer is {…, 0, 7, 14, 28, …}.

3. Which of the following relations is the reflexive relation over the set {1, 2, 3, 4}?

a) {(0,0), (1,1), (2,2), (2,3)}

b) {(1,1), (1,2), (2,2), (3,3), (4,3), (4,4)}

c) {,(1,1), (1,2), (2,1), (2,3), (3,4)}

d) {(0,1), (1,1), (2,3), (2,2), (3,4), (3,1)

View Answer

Explanation: {(1,1), (1,2), (2,2), (3,3), (4,3), (4,4)} is a reflexive relation because it contains set = {(1,1), (2,2), (3,3), (4,4)}.

4. Determine the partitions of the set {3, 4, 5, 6, 7} from the following subsets.

a) {3,5}, {3,6,7}, {4,5,6}

b) {3}, {4,6}, {5}, {7}

c) {3,4,6}, {7}

d) {5,6}, {5,7}

View Answer

Explanation: {3,5}, {3,6,7}, {4,5,6}. It is not a partition because these sets are not pairwise disjoint. The elements 3, 5 and 6 appear repeatedly these sets. {1}, {2,3,6}, {4}, {5} – this is a partition as they are pairwise disjoint. {3,4,6}, {7} – this is not a partition as element 5 is missing.

{5,6}, {5,7} – this is not a partition because it is missing the elements 3, 4 in any of the sets.

5. Determine the number of equivalence classes that can be described by the set {2, 4, 5}.

a) 125

b) 5

c) 16

d) 72

View Answer

Explanation: Suppose B={2, 4, 5} and B×B = (2,2), (4,4), (5,5), (2,4), (4,2), (4,5), (5,4), (2,5), (5,2). A relation R on set B is said to be equivalence relation if R is reflexive, Symmetric, transitive. Hence, total number of equivalence relation=5 out of 2

^{3}=8 relations.

6. Determine the number of possible relations in an antisymmetric set with 19 elements.

a) 23585

b) 2.02 * 10^{87}

c) 9.34 * 7^{91}

d) 35893

View Answer

Explanation: Number of antisymmetric relation is given:-|A|=n, |AxA|=n xn. Then, N=total number of diagonal will n and we know that N = 2

^{n}* 3

^{(n2-n)/2}. So, the number of relations should be = 2.02 * 10

^{87}.

7. For a, b ∈ Z deﬁne a | b to mean that a divides b is a relation which does not satisfy ___________

a) irreflexive and symmetric relation

b) reflexive relation and symmetric relation

c) transitive relation

d) symmetric relation

View Answer

Explanation: Suppose, a=0, then we know that 0 does not divide 0, 0 ∤ 0 and it is not reﬂexive. Again, 2 | 4 but 4 does not 2 and so it is not a symmetric relation.

8. Which of the following is an equivalence relation on R, for a, b ∈ Z?

a) (a-b) ∈ Z

b) (a^{2}+c) ∈ Z

c) (ab+cd)/2 ∈ Z

d) (2c^{3})/3 ∈ Z

View Answer

Explanation: Let a ∈ R, then a−a = 0 and 0 ∈ Z, so it is reflexive. To see that a-b ∈ Z is symmetric, then a−b ∈ Z -> say, a−b = m, where m ∈ Z ⇒ b−a = −(a−b)=−m and −m ∈ Z. Thus, a-b is symmetric. To see that a-b is transitive, let a, b, c ∈ R. Thus, a−b ∈ Z; b−c ∈ Z. Let a−b = i and b−c = j, for integers i,j ∈ Z. Then a−c ='(a−b)+(b−c)=i + j. So, a−c ∈ Z. Therefore a – c is transitive. Hence, (a-b) is an equivalence relation on the set R. Rest of the options are not equivalence relations.

9. Determine the set of all integers a such that a ≡ 3 (mod 7) such that −21 ≤ x ≤ 21.

a) {−21, −18, −11, −4, 3, 10, 16}

b) {−21, −18, −11, −4, 3, 10, 17, 24}

c) {−24, -19, -15, 5, 0, 6, 10}

d) {−23, −17, −11, 0, 2, 8, 16}

View Answer

Explanation: For an integer a we have x ≡ 3 (mod 7) if and only if a = 7m + 3. Thus, by calculating multiples of 7, add 3 and restrict the value of a, so that −21 ≤ x ≤ 21. The set for a = {−21, −18, −11, −4, 3, 10, 17, 24}.

10. For a, b ∈ R deﬁne a = b to mean that |x| = |y|. If [x] is an equivalence relation in R. Find the equivalence relation for [17].

a) {,…,-11, -7, 0, 7, 11,…}

b) {2, 4, 9, 11, 15,…}

c) {-17, 17}

d) {5, 25, 125,…}

View Answer

Explanation: We can find that [17] = {a ∈ R|a = 17} = {a ∈ R||a| = |17|} = {-17, 17} and [−17] = {a ∈ R|a = −17} = {a ∈ R||a| = |−17|}= {−17, 17}. Hence, the required equivalence relation is {-17, 17}.

**Sanfoundry Global Education & Learning Series – Discrete Mathematics.**

To practice all areas of Discrete Mathematics, __here is complete set of 1000+ Multiple Choice Questions and Answers__.

Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!