This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Closure on Relations”.
1. R is a binary relation on a set S and R is reflexive if and only if _______
a) r(R) = R
b) s(R) = R
c) t(R) = R
d) f(R) = R
View Answer
Explanation: Let reflexive closure of R:r(R) = R. If R is reflexive, it satisfies all the condition in the definition of reflexive closure. So, a reflexive closure of a relation is the smallest number of reflexive relation contain in R. Hence, R = r(R).
2. If R1 and R2 are binary relations from set A to set B, then the equality ______ holds.
a) (Rc)c = Rc
b) (A x B)c = Φ
c) (R1 U R2)c = R1c ∪ R2c
d) (R1 U R2)c = R1c ∩ R2c
View Answer
Explanation: To proof (R1 U R2)c = R1c ∪ R2c,
if <x,y> belongs to (R1 U R2)c
⇔ <y,x> ∈ (R1 U R2)
⇔ <y,x> ∈ R1 or <y,x> ∈ R2
⇔ <x,y> ∈ R1c or <x,y> ∈ R2c
⇔ <x,y> ∈ R1c ∪ R2c.
3. The condition for a binary relation to be symmetric is _______
a) s(R) = R
b) R ∪ R = R
c) R = Rc
d) f(R) = R
View Answer
Explanation: If <a,b> ∈ R then <b,a> ∈ R, where a and b belong to two different sets and so its symmetric.
Rc also contains <b,a>
Rc = R.
4. ______ number of reflexive closure exists in a relation R = {(0,1), (1,1), (1,3), (2,1), (2,2), (3,0)} where {0, 1, 2, 3} ∈ A.
a) 26
b) 6
c) 8
d) 36
View Answer
Explanation: The reflexive closure of R is the relation, R ∪ Δ = { (a,b) | (a,b) R (a,a) | a A }. Hence, R ∪ Δ = {(0,1), (1,1), (1,3), (2,1), (2,2), (3,0)} and the answer is 6.
5. The transitive closure of the relation {(0,1), (1,2), (2,2), (3,4), (5,3), (5,4)} on the set {1, 2, 3, 4, 5} is _______
a) {(0,1), (1,2), (2,2), (3,4)}
b) {(0,0), (1,1), (2,2), (3,3), (4,4), (5,5)}
c) {(0,1), (1,1), (2,2), (5,3), (5,4)}
d) {(0,1), (0,2), (1,2), (2,2), (3,4), (5,3), (5,4)}
View Answer
Explanation: Let R be a relation on a set A. The connectivity relation on R* consists of pairs (a,b) such that there is a path of length at least one from a to b in R. Mathematically, R* = R1 ∪ R2 ∪ R3 ∪ … ∪ Rn. Hence the answer is {(0,1), (0,2), (1,2), (2,2), (3,4), (5,3), (5,4)}.
6. Amongst the properties {reflexivity, symmetry, antisymmetry, transitivity} the relation R={(a,b) ∈ N2 | a!= b} satisfies _______ property.
a) symmetry
b) transitivity
c) antisymmetry
d) reflexivity
View Answer
Explanation: It is not reflexive as aRa is not possible. It is symmetric as if aRb then bRa. It is not antisymmetric as aRb and bRa are possible and we can have a!=b. It is not transitive as if aRb and bRc then aRc need not be true. This is violated when c=a. So the answer is symmetry property.
7. The number of equivalence relations of the set {3, 6, 9, 12, 18} is ______
a) 4
b) 25
c) 22
d) 90
View Answer
Explanation: Number of equivalence Relations are given by BELL number. The nth of these numbers i.e, Bn counts the number of different ways to partition a set that has exactly n elements, or equivalently, the number of equivalence relations on it. Let’s say, 1 -> Equivalence relation with 1 element; 1 2 -> Equivalence relation with 2 element; 2 3 5 -> Equivalence relation with 3 element; 5 7 10 15 -> Equivalence relation with 4 element. Hence, the answer is 4.
8. Let R1 and R2 be two equivalence relations on a set. Is R1 ∪ R2 an equivalence relation?
a) an equivalence relation
b) reflexive closure of relation
c) not an equivalence relation
d) partial equivalence relation
View Answer
Explanation: R1 union R2 is not equivalence relation because transitivity property of closure need not hold. For instance, (x, y) can be in R1 and (y, z) be in R2 and (x, z) not in either R1 or R2. However, R1 intersection R2 is an equivalence relation.
9. A relation R is defined on the set of integers as aRb if and only if a+b is even and R is termed as ______
a) an equivalence relation with one equivalence class
b) an equivalence relation with two equivalence classes
c) an equivalence relation
d) an equivalence relation with three equivalence classes
View Answer
Explanation: R is reflexive as (a+b) is even for any integer; R is symmetric as if (a+b) is even (b+a) is also even; R is transitive as if ((a+b)+c) is even, then (a+(b+c)) is also even.
So, R is an equivalence relation. For set of natural numbers, sum of even numbers always give even, sum of odd numbers always give even and sum of any even and any odd number always give odd. So, must have two equivalence classes -> one for even and one for odd.
{…, -4, -2, 0, 2, … } and {…, -3, -1, 1, 3, … }.
10. The binary relation U = Φ (empty set) on a set A = {11, 23, 35} is _____
a) Neither reflexive nor symmetric
b) Symmetric and reflexive
c) Transitive and reflexive
d) Transitive and symmetric
View Answer
Explanation: U = Φ (empty set) on a set A = {11, 23, 35} need to be hold Irreflexive, symmetric, anti-symmetric, asymmetric and transitive closure property, but it is not Reflexive as it does not contain any self loop in itself.
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.
If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]
- Practice BCA MCQs
- Check Discrete Mathematics Books
- Practice Information Technology MCQs
- Apply for Computer Science Internship
- Check BCA Books
