Discrete Mathematics Questions and Answers – Number of Relations

«
»

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) 290
b) 2100
c) 281
d) 260
View Answer

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

2. _________ number of reflexive relations are there on a set of 11 distinct elements.
a) 2110
b) 3121
c) 290
d) 2132
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 = 2110.

3. The number of reflexive as well as symmetric relations on a set with 14 distinct elements is __________
a) 4120
b) 270
c) 3201
d) 291
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 214*(14-1)/2 = 291.

4. The number of symmetric relations on a set with 15 distinct elements is ______
a) 2196
b) 250
c) 2320
d) 278
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) = 2196.

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 n2 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 n2 elements i.e 72 = 49 elements in the largest equivalence relation.
advertisement

6. ________ is the rank of the largest equivalence relation on a set of 20 elements.
a) 320
b) 2400
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 a1, a2, a3, …, an elements then a1 and a2 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) 102
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 {a1}, {a2}, … 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) 290
b) 380
c) 164
d) 280
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 2mn, there are 2mn number of relations from A to B and so the answer is 280.
advertisement

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 S2 = 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.

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!

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn