Discrete Mathematics Questions and Answers – Types of Relations

«
»

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

Answer: 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.
advertisement

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

Answer: b
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 Br of binary relations on S and let Bf be the number of functions from S to S. The expression for Br and Bf, in terms of n should be ____________
a) n2 and 2(n+1)2
b) n3 and n(n+1)
c) n and n(n+6)
d) 2(n*n) and nn
View Answer

Answer: d
Explanation: For a set with n elements the number of binary relations should be 2(n*n) and the number of functions should be nn. Hence Br = 2(n*n) and Bf = nn.

4. Let A be a set of k (k>0) elements. Which is larger between the number of binary relations (say, Nr) on A and the number of functions (say, Nf) 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

Answer: a
Explanation: For a set with k elements the number of binary relations should be 2(n*n) and the number of functions should be nn. Now, 2(n*n) => n2log (2) [taking log] and nn => nlog (n) [taking log]. It is known that n2log (2) > nlog (n). Hence, the number of binary relations > the number of functions i.e, Nr > Nf.

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

Answer: 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.
advertisement

6. Let R1 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 R1) if a * b is divisible by 3.
ii. An element a in B is related to an element b in C (under R2) if a * b is even but not divisible by 3. Which is the composite relation R1R2 from A to C?
a) R1R2 = {(1, 2), (1, 4), (3, 3), (5, 4), (5,6), (7, 3)}
b) Φ
c) R1R2 = {(1, 2), (1,6), (3, 2), (3, 4), (5, 4), (7, 2)}
d) R1R2 = {(2,2), (3, 2), (3, 4), (5, 1), (5, 3), (7, 1)}
View Answer

Answer: b
Explanation: By definition, i) R1 = {(1,6), (3,2), (3,4), (3,6), (3,8), (5,6), (7,6)} and ii) R2 = {(1,2), (1,4), (1,8), (5,2), (5,4), (5,8), (7,2), (7,4), (7,8)}. So, R1R2 = Φ.

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(n3)
View Answer

Answer: d
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.

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

Answer: c
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 a2 = b2.
a) Transitive and symmetric
b) Reflexive and asymmetry
c) Trichotomy, antisymmetry, and irreflexive
d) Symmetric, Reflexive, and transitive
View Answer

Answer: d
Explanation: Since, x2 = y2 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.
advertisement

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

Answer: a
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.

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn