Discrete Mathematics Questions and Answers – Relations

This section focuses on "Relations" in Discrete Mathematics. These Multiple Choice Questions (MCQ) should be practiced to improve the Discrete Mathematics skills required for various interviews (campus interviews, walk-in interviews, company interviews), placements, entrance exams and other competitive examinations.

1. Relations may exist between?

A. objects of the same set
B. between objects of two or more sets.
C. Both A and B
D. None of the above

View Answer

2. A binary relation R on a single set A is a subset of?

A. A X A
B. A % A
C. A ^ A
D. A ? A

View Answer

3. For two distinct sets, A and B, having cardinalities m and n respectively, the maximum cardinality of a relation R from A to B is ?

A. m+n
B. m*n
C. m^n
D. None of the above

View Answer

4. A relation can be represented using a?

A. Indirected graph
B. Pie graph
C. Directed graph
D. Line graph

View Answer

5. The ______ Relation between sets X and Y is the set X×Y

A. Empty
B. Full
C. Identity
D. Inverse

View Answer

6. A relation R on set A is called _________ if xRy implies yRx.

A. Irreflexive
B. Reflexive
C. Anti-Symmetric
D. Symmetric

View Answer

7. The relation R={(a,b),(b,a)} on set X={a,b} is?

A. Irreflexive
B. Reflexive
C. Anti-Symmetric
D. Symmetric

View Answer

8. The binary relation {(1,1), (2,1), (2,2), (2,3), (2,4), (3,1), (3,2)} on the set {1, 2, 3} is __________

A. reflective, symmetric and transitive
B. irreflexive, symmetric and transitive
C. neither reflective, nor irreflexive but transitive
D. irreflexive and antisymmetric

View Answer

9. Consider the binary relation, A = {(a,b) | b = a – 1 and a, b belong to {1, 2, 3}}. The reflexive transitive closure of A is?

A. {(a,b) | a >= b and a, b belong to {1, 2, 3}}
B. {(a,b) | a > b and a, b belong to {1, 2, 3}}
C. {(a,b) | a <= b and a, b belong to {1, 2, 3}}
D. {(a,b) | a = b and a, b belong to {1, 2, 3}}

View Answer

10. The time complexity of computing the transitive closure of a binary relation on a set of n elements should be ________

A. O(n)
B. O(logn)
C. O(n^3)
D. O(n^2)

View Answer

Discussion