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
Ans : C
Explanation: Relations may exist between objects of the same set or between objects of two or more sets.
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
Ans : A
Explanation: A binary relation R on a single set A is a subset of A×A.
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
Ans : B
Explanation: 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 mn
4. A relation can be represented using a?
A. Indirected graph
B. Pie graph
C. Directed graph
D. Line graph
View Answer
Ans : C
Explanation: A relation can be represented using a directed graph.
5. The ______ Relation between sets X and Y is the set X×Y
A. Empty
B. Full
C. Identity
D. Inverse
View Answer
Ans : B
Explanation: The Full Relation between sets X and Y is the set X×Y.
6. A relation R on set A is called _________ if xRy implies yRx.
A. Irreflexive
B. Reflexive
C. Anti-Symmetric
D. Symmetric
View Answer
Ans : D
Explanation: A relation R on set A is called Symmetric if xRy implies yRx.
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
Ans : A
Explanation: The relation R={(a,b),(b,a)} on set X={a,b} is irreflexive.
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
Ans : C
Explanation: Not reflexive -> (3,3) not present; not irreflexive -> (1, 1) is present; not symmetric -> (2, 1) is present but not (1, 2); not antisymmetric – (2, 3) and (3, 2) are present; not asymmetric -> asymmetry requires both antisymmetry and irreflexivity. So, it is transitive closure of relation.
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
Ans : A
Explanation: By definition of Transitive closure we have that a is related to all smaller b (as every a is related to b – 1) and from the reflexive property a is related to a.
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
Ans : C
Explanation: Calculation of transitive closure results into matrix multiplication. We can do matrix multiplication in O(n3) time. There are better algorithms that do less than cubic time.
Discussion