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

The answer of Question 7 is A and D.
Kindly update !