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 R_{1} and R_{2} are binary relations from set A to set B, then the equality ______ holds.

a) (R^{c})^{c} = R^{c}

b) (A x B)^{c} = Φ

c) (R_{1} U R_{2})^{c} = R_{1}^{c} ∪ R_{2}^{c}

d) (R_{1} U R_{2})^{c} = R_{1}^{c} ∩ R_{2}^{c}

View Answer

Explanation: To proof (R

_{1}U R

_{2})

^{c}= R

_{1}

^{c}∪ R

_{2}

^{c},

if <x,y> belongs to (R

_{1}U R

_{2})

^{c}

⇔ <y,x> ∈ (R

_{1}U R

_{2})

⇔ <y,x> ∈ R

_{1}or <y,x> ∈ R

_{2}

⇔ <x,y> ∈ R

_{1}

^{c}or <x,y> ∈ R

_{2}

^{c}

⇔ <x,y> ∈ R

_{1}

^{c}∪ R

_{2}

^{c}.

3. The condition for a binary relation to be symmetric is _______

a) s(R) = R

b) R ∪ R = R

c) R = R^{c}

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.

R

^{c}also contains <b,a>

R

^{c}= 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) 2^{6}

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* = R

^{1}∪ R

^{2}∪ R

^{3}∪ … ∪ R

^{n}. 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) ∈ N^{2} | 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) 2^{5}

c) 22

d) 90

View Answer

Explanation: Number of equivalence Relations are given by BELL number. The nth of these numbers i.e, B

_{n}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 R_{1} and R_{2} be two equivalence relations on a set. Is R_{1} ∪ R_{2} an equivalence relation?

a) an equivalence relation

b) reflexive closure of relation

c) not an equivalence relation

d) partial equivalence relation

View Answer

Explanation: R

_{1}union R

_{2}is not equivalence relation because transitivity property of closure need not hold. For instance, (x, y) can be in R

_{1}and (y, z) be in R

_{2}and (x, z) not in either R

_{1}or R

_{2}. However, R

_{1}intersection R

_{2}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, smust 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__.