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) reflexive, symmetric and transitive
b) irreflexive, symmetric and transitive
c) neither reflexive, nor irreflexive and not 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. It is also not transitive closure of relation because (3,2) and (2,3) are there in the relation but (3,3) is missing.
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 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
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
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
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 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
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
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
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
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.
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.
- Apply for Computer Science Internship
- Check Discrete Mathematics Books
- Practice BCA MCQs
- Check BCA Books
- Practice Computer Science MCQs
