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^{90}

b) 2^{100}

c) 2^{81}

d) 2^{60}

View Answer

Explanation: S is the set with 9 elements. A relation on S is defined as S x S. There are 9

^{2}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^{110}

b) 3^{121}

c) 2^{90}

d) 2^{132}

View Answer

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

^{110}.

3. The number of reflexive as well as symmetric relations on a set with 14 distinct elements is __________

a) 4^{120}

b) 2^{70}

c) 3^{201}

d) 2^{91}

View Answer

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

^{91}.

4. The number of symmetric relations on a set with 15 distinct elements is ______

a) 2^{196}

b) 2^{50}

c) 2^{320}

d) 2^{78}

View Answer

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

^{196}.

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

Explanation: Let R is an equivalence relation on the set S and so it satisfies reflexive, symmetric and transitive property. The largest equivalence relation means it should contain largest number of ordered pairs. Since we can have n

^{2}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

^{2}elements i.e 7

^{2}= 49 elements in the largest equivalence relation.

6. _____ is the rank of the largest equivalence relation on a set of 20 elements.

a) 3^{20}

b) 2^{400}

c) 20

d) 1

View Answer

Explanation: The rank of an equivalence relation is the number of an equivalence classes. If we have a

_{1}, a

_{2}, a

_{3}, …, a

_{n}elements then a

_{1}and a

_{2}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^{2}

b) 8

c) 48

d) 32

View Answer

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

Explanation: In the case of smallest equivalence relation, each element is in one equivalence class like {a

_{1}}, {a

_{2}}, … 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^{90}

b) 3^{80}

c) 164

d) 2^{80}

View Answer

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

^{80}.

10. Synonym for binary relation is _______

a) equivalence relation

b) dyadic relation

c) orthogonal relation

d) one to many relation

View Answer

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

^{2}= 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__.