This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Types of Relations”.

1. 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

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.

2. Consider the relation: R’ (x, y) if and only if x, y>0 over the set of non-zero rational numbers,then R’ is ______

a) not equivalence relation

b) an equivalence relation

c) transitive and asymmetry relation

d) reflexive and antisymmetric relation

View Answer

Explanation: Reflexive: a, a>0

Symmetric: if a, b>0 then both must be +ve or -ve, which means b, a > 0 also exists

Transitive: if a, b>0 and b, c>0 then to have b as same number, both pairs must be +ve or -ve which implies a, c>0. Hence, R’ is an equivalence relation.

3. Let S be a set of n>0 elements. Let be the number B_{r} of binary relations on S and let B_{f} be the number of functions from S to S. The expression for B_{r} and B_{f}, in terms of n should be:

a) n^{2} and 2(n+1)^{2}

b) n^{3} and n^{(n+1)}

c) n and n^{(n+6)}

d) 2^{(n*n)} and n^{n}

View Answer

Explanation: For a set with n elements the number of binary relations should be 2

^{(n*n)}and the number of functions should be n

^{n}. Hence B

_{r}= 2

^{(n*n)}and B

_{f}= n

^{n}.

4. Let A be a set of k (k>0) elements. Which is larger between the number of binary relations (say, N_{r}) on A and the number of functions (say, N_{f}) from A to A?

a) number of relations

b) number of functions

c) the element set

d) number of subsets of the relation

View Answer

Explanation: For a set with k elements the number of binary relations should be 2

^{(n*n)}and the number of functions should be n

^{n}. Now, 2

^{(n*n)}=> n

^{2}log (2) [taking log] and n

^{n}=> nlog (n) [taking log]. It is known that n

^{2}log (2) > nlog (n). Hence, the number of binary relations > the number of functions i.e, N

_{r}> N

_{f}.

5. 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

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.

6. Let R_{1} be a relation from A = {1, 3, 5, 7} to B = {2, 4, 6, 8} and R2 be another relation from B to C = {1, 2, 3, 4} as defined below:

i. An element a in A is related to an element b in B (under R_{1}) if a * b is divisible by 3.

ii. An element a in B is related to an element b in C (under R_{2}) if a * b is even but not divisible by 3. Which is the composite relation R_{1}R_{2} from A to C?

a) R_{1}R_{2} = {(1, 2), (1, 4), (3, 3), (5, 4), (5,6), (7, 3)}

b) Φ

c) R_{1}R_{2} = {(1, 2), (1,6), (3, 2), (3, 4), (5, 4), (7, 2)}

d) R_{1}R_{2} = {(2,2), (3, 2), (3, 4), (5, 1), (5, 3), (7, 1)}

View Answer

Explanation: By definition, i) R

_{1}= {(1,6), (3,2), (3,4), (3,6), (3,8), (5,6), (7,6)} and ii) R

_{2}= {(1,2), (1,4), (1,8), (5,2), (5,4), (5,8), (7,2), (7,4), (7,8)}. So, R

_{1}R

_{2}= Φ .

7. 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^{(n+(3/2))})

d) O(n^{3})

View Answer

Explanation: Calculation of transitive closure results into matrix multiplication. We can do matrix multiplication in O(n

^{3}) time. There are better algorithms that do less than cubic time.

8. Let A and B be two non-empty relations on a set S. Which of the following statements is false?

a) A and B are transitive ⇒ A∩B is transitive

b) A and B are symmetric ⇒ A∪B is symmetric

c) A and B are transitive ⇒ A∪B is not transitive

d) A and B are reflexive ⇒ A∩B is reflexive

View Answer

Explanation: In terms of set theory, the binary relation R defined on the set X is a transitive relation if, for all a, b, c ∈ X, if aRb and bRc, then aRc. If there are two relations on a set satisfying transitive property then there union must satisfy transitive property.

9. Determine the characteristics of the relation aRb if a^{2} = b^{2}.

a) Transitive and symmetric

b) Reflexive and asymmetry

c) Trichotomy, antisymmetry, and irreflexive

d) Symmetric, Reflexive, and transitive

View Answer

Explanation: Since, x

^{2}= y

^{2}is just a special case of equality, so all properties that apply to x = y also apply to this case. Hence, the relation satisfies symmetric, reflexive and transitive closure.

10. Let R be a relation between A and B. R is asymmetric if and only if ________

a) Intersection of D(A) and R is empty, where D(A) represents diagonal of set

b) R^{-1} is a subset of R, where R^{-1} represents inverse of R

c) Intersection of R and R^{-1} is D(A)

d) D(A) is a subset of R, where D(A) represents diagonal of set

View Answer

Explanation: A relation is asymmetric if and only if it is both antisymmetric and irreflexive. As a consequence, a relation is transitive and asymmetric if and only if it is a strict partial order. If D(A) is a diagonal of A set and intersection of D(A) and R is empty, then R is asymmetric.

**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__.