## 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