Relations Questions and Answers

This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Number of Relations”.

1. How many binary relations are there on a set S with 9 distinct elements?
a) 2⁹⁰
b) 2¹⁰⁰
c) 2⁸¹
d) 2⁶⁰
View Answer

Answer: c
Explanation: S is the set with 9 elements. A relation on S is defined as S x S. There are 9² number of ordered pairs in relation. So, the number of binary relations is 2^(9*9) = 281.

2. _________ number of reflexive relations are there on a set of 11 distinct elements.
a) 2¹¹⁰
b) 3¹²¹
c) 2⁹⁰
d) 2¹³²
View Answer

Answer: a
Explanation: Let A be a set consists of n distinct elements. There are 2^(n*n)-n number of reflexive relations that can be formed. So, here the answer is 2^(11*11)-11 = 2¹¹⁰.

3. The number of reflexive as well as symmetric relations on a set with 14 distinct elements is __________
a) 4¹²⁰
b) 2⁷⁰
c) 3²⁰¹
d) 2⁹¹
View Answer

Answer: d
Explanation: Let A be a set consists of n distinct elements. There are 2^(n*(n-1))/2 number of reflexive and symmetric relations that can be formed. So, here the answer is 2^14*(14-1)/2 = 2⁹¹.

4. The number of symmetric relations on a set with 15 distinct elements is ______
a) 2¹⁹⁶
b) 2⁵⁰
c) 2³²⁰
d) 2⁷⁸
View Answer

Answer: a
Explanation: Let S be a set consists of n distinct elements. There are 2^(n-1)*(n-1) number of reflexive and symmetric relations that can be formed. So, here the answer is 2^{(15-1)*(15-1)} = 2¹⁹⁶.

5. Suppose S is a finite set with 7 elements. How many elements are there in the largest equivalence relation on S?
a) 56
b) 78
c) 49
d) 100
View Answer

Answer: c
Explanation: Let R is an equivalence relation on the set S and so it satisfies the reflexive, symmetric and transitive property. The largest equivalence relation means it should contain the largest number of ordered pairs. Since we can have n² ordered pairs in R x R where n belongs to S and all these ordered pairs are present in this relation; its the largest equivalence relation.So there are n² elements i.e 7² = 49 elements in the largest equivalence relation.

Subscribe Now: Discrete Mathematics Newsletter | Important Subjects Newsletters

6. ________ is the rank of the largest equivalence relation on a set of 20 elements.
a) 3²⁰
b) 2⁴⁰⁰
c) 20
d) 1
View Answer

Answer: d
Explanation: The rank of an equivalence relation is the number of an equivalence classes. If we have a₁, a₂, a₃, …, a_n elements then a₁ and a₂ will be in the same equivalence class because everything is related and so on. In this case, there is only one equivalence class.

7. How many elements are there in the smallest equivalence relation on a set with 8 elements?
a) 10²
b) 8
c) 48
d) 32
View Answer

Answer: b
Explanation: Let R is an equivalence relation on the set S with n elements and so it satisfies reflexive, symmetric and transitive properties. The smallest equivalence relation means it should contain minimum number of ordered pairs i.e along with symmetric and transitive properties it must always satisfy reflexive property. So, the smallest equivalence relation will have n ordered pairs and so the answer is 8.

8. The rank of smallest equivalence relation on a set with 12 distinct elements is _______
a) 12
b) 144
c) 136
d) 79
View Answer

Answer: a
Explanation: In the case of smallest equivalence relation, each element is in one equivalence class like {a₁}, {a₂}, … are equivalence classes. So, the rank or number of equivalence classes is n for a set with n elements and so the answer is 12.

9. If a set A has 8 elements and a set B has 10 elements, how many relations are there from A to B?
a) 2⁹⁰
b) 3⁸⁰
c) 164
d) 2⁸⁰
View Answer

Answer: d
Explanation: Let, a relation R from A to B is a subset of A×B. As the maximum number of subsets (Elements in the powerset) is 2^mn, there are 2^mn number of relations from A to B and so the answer is 2⁸⁰.

10. Synonym for binary relation is _______
a) equivalence relation
b) dyadic relation
c) orthogonal relation
d) one to many relations
View Answer

Answer: b
Explanation: A binary relation on a set S is a set of ordered pairs of elements of S. It is a subset of the cartesian product S² = S x S. The terms correspondence, dyadic relation and 2-place relation are synonyms for the binary relation.

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.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]

« Prev - Discrete Mathematics Questions and Answers – Discrete Probability – Power Series

» Next - Discrete Mathematics Questions and Answers – Closure on Relations

Related Posts:

Recommended Articles: