Explore topic-wise InterviewSolutions in .

Right ANSWER is (C) {-17, 17}

Explanation: We can FIND that [17] = {a ∈ R|a = 17} = {a ∈ R||a| = |17|} = {-17, 17} and [−17] = {a ∈ R|a = −17} = {a ∈ R||a| = |−17|}= {−17, 17}. Hence, the REQUIRED equivalence relation is {-17, 17}.

The correct answer is (b) {−21, −18, −11, −4, 3, 10, 17, 24}

For explanation I would say: For an INTEGER a we have X ≡ 3 (mod 7) if and only if a = 7m + 3. Thus, by calculating multiples of 7, add 3 and RESTRICT the value of a, so that −21 ≤ x ≤ 21. The SET for a = {−21, −18, −11, −4, 3, 10, 17, 24}.

Correct option is (c) A and B are transitive ⇒ A∪B is not transitive

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

Correct option is (d) O(n^3)

For explanation I would say: 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.

The correct answer is (a) 12

To explain I would say: In the case of smallest equivalence RELATION, each element is in one equivalence class like {a1}, {a2}, … are equivalence CLASSES. So, the rank or NUMBER of equivalence classes is n for a SET with n elements and so the answer is 12.

Right answer is (b) 8

Explanation: Let R is an equivalence relation on the set S with N elements and so it satisfies reflexive, symmetric and transitive PROPERTIES. The smallest equivalence relation MEANS it should contain minimum number of ordered pairs i.e along with symmetric and transitive properties it MUST always satisfy reflexive property. So, the smallest equivalence relation will have n ordered pairs and so the answer is 8.

The correct choice is (b) reflexive RELATION and symmetric relation

Explanation: Suppose, a=0, then we know that 0 does not divide 0, 0 ∤ 0 and it is not reflexive. Again, 2 | 4 but 4 does not 2 and so it is not a symmetric relation.

The correct option is (a) {…, 0, 7, 14, 28, …}

To elaborate: Note that a set of class representatives is the subset of a set which contains exactly one element from each equivalence class. Now, for integers n, a and B, we have CONGRUENCE a≡b(MOD n), then the set of equivalence classes are{…, -2n, -n, 0, n, 2n,…}, {…, 1-2n, 1-n, 1, 1+n, 1+2n,…}. The required answer is {…, 0, 7, 14, 28, …}.

The CORRECT option is (b) {(1,1), (1,2), (2,2), (3,3), (4,3), (4,4)}

For explanation I would SAY: {(1,1), (1,2), (2,2), (3,3), (4,3), (4,4)} is a REFLEXIVE relation because it contains set = {(1,1), (2,2), (3,3), (4,4)}.

Right option is (b) {3}, {4,6}, {5}, {7}

To EXPLAIN I would SAY: {3,5}, {3,6,7}, {4,5,6}. It is not a PARTITION because these sets are not pairwise disjoint. The elements 3, 5 and 6 appear repeatedly these sets. {1}, {2,3,6}, {4}, {5} – this is a partition as they are pairwise disjoint. {3,4,6}, {7} – this is not a partition as ELEMENT 5 is missing.

{5,6}, {5,7} – this is not a partition because it is missing the elements 3, 4 in any of the sets.

The correct CHOICE is (a) equivalence relation

To explain: Here, [3] = {3, 5}, [5] = {3, 5}, [5] = {5}. We can SEE that [3] = [5] and that S/R will be {[3], [6]} which is a partition of S. Thus, we can choose either {3, 6} or {5, 6} as a set of REPRESENTATIVES of the equivalence classes.

The correct choice is (d) P(x) = False for all x ∈ S such that a ≤ x and b ≤ x

To explain I WOULD say: Here, maximum element is c and so c is of a higher order than any other element in A. Minimal elements are a and b: No other element in A is of lower order than either a or b.

We are GIVEN P(a) = True. So, for all x such that a≤x, P(x) must be True. We do have at least one such x, which is c as it is the maximum element. So, P(x) = False for all x ∈ S such that a ≤ x and b ≤ x -> cannot be true. P(x) = True for all xS such that x ≠ b -> can be True as all elements mapped to TRUE doesn’t violate the given implication. P(x) = False for all x ∈ S such that x ≠ a and x ≠ c -> can be True if a is RELATED only to c. P(x) = False for all x ∈ S such that b ≤ x and x ≠ c -> can be True as b≤x ensures x≠a and for all other elements P(x) can be False without violating the given implication.

The correct OPTION is (a) Every non-empty subset of has a greatest lower BOUND

To explain I would say: Consider any sequence like “45, 8, 7, 2” – it can have many (infinite) LEAST upper bounds like “45, 8, 7, 2, 5”, “45, 8, 7, 2, 1” and so on but it can have only 1 greatest lower bound – “45, 8, 7” because we are using the prefix relation. So, every non-empty subset has a greatest lower bound.

The correct choice is (c) n!

Easy EXPLANATION: To MAKE this partial order a total order, we need the relation to hold for every TWO element of the partial order. Currently, there is no relation between any bi and bj. So, for every bi and bj, we have to add either (bi, bj) or (bj, bi) in total order. So, this TRANSLATES to giving an ordering for n elements between x and y, which can be done in n! WAYS.

The correct CHOICE is (d) (N,|) is a lattice but not a COMPLETE lattice

To explain: A set is called lattice if every finite subset has a least upper bound and greatest LOWER bound. It is TERMED as a complete lattice if every subset has a least upper bound and greatest lower bound. As every subset of this will not have LUB and GLB so (N,|) is a lattice but not a complete lattice.

Correct choice is (c) {1}

Easiest explanation: A lattice is complete if every subset of partial order set has a supremum and infimum element. For example, here we are given a partial order set R. Now it will be a complete lattice if whatever be the subset we choose, it has a supremum and infimum element. Here relation given is set containment, so supremum element will be just union of all sets in the subset we choose. Similarly, the infimum element will be just an intersection of all the sets in the subset we choose. As R now is not complete lattice, because although it has a supremum for every subset we choose, but some subsets have no infimum. For example, if we take subset {{1, 3, 5}, {1, 2, 4}}, then intersection of sets in this is {1}, which is not PRESENT in R. So clearly, if we add set {1} in R, we will SOLVE the problem. So adding {1} is NECESSARY and sufficient condition for R to be a complete lattice.

Correct answer is (b) 10

To explain: The ordered pairs of the equivalence RELATIONS induced = {(a,a), (a,b), (a,c), (b,a), (b,b), (b,c), (c,a), (c,b), (c,c), (d,d)}. Poset -> equivalence relations = each PARTITION power set – Φ.

The correct option is (a) not a partial ordering because it is not asymmetric and irreflexive equals antisymmetric

To explain I WOULD say: Relation LESS than a set of REAL numbers is not antisymmetric and reflexive. Relation is not POSET because it is irreflexive. Again, ARB != bRa unless a=b and so it is antisymmetric. A relation may be ‘not asymmetric and not reflexive but still antisymmetric, as {(1,1) (1,2)}. So, the relation is not a partial ordering because it is not asymmetric and irreflexive equals antisymmetric.

The correct CHOICE is (a) Intersection of D(A) and R is EMPTY, where D(A) represents diagonal of SET

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

The correct CHOICE is (a) {(a,b) | a >= b and a, b belong to {1, 2, 3}}

To elaborate: 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.

Right answer is (a) number of RELATIONS

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^2log (2) [TAKING log] and n^n => nlog (n) [taking log]. It is known that n^2log (2) > nlog (n). Hence, the number of binary relations > the number of functions i.e, Nr > Nf.

Correct OPTION is (d) 2^(n*n)and n^n

Best 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 Br = 2^(n*n)and Bf = n^n.

Right choice is (b) an EQUIVALENCE relation

The explanation is: 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.

The correct option is (c) neither reflective, nor irreflexive but TRANSITIVE

To explain I would SAY: 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.

Right option is (a) an equivalence RELATION

The EXPLANATION is: 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.

The correct option is (d) TRANSITIVE and symmetric

To explain: 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.

The correct answer is (a) 4

For EXPLANATION I would say: 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.

Correct choice is (d) {(0,1), (0,2), (1,2), (2,2), (3,4), (5,3), (5,4)}

Easiest 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)}.

The CORRECT answer is (b) 6

For EXPLANATION: The reflexive CLOSURE of R is the relation, R ∪ Δ = { (a,b) | (a,b) R(a,a) | aA }. Hence, R ∪ Δ ={(0,1), (1,1), (1,3), (2,1), (2,2), (3,0)} and the answer is 6.

The CORRECT option is (c) R = R^c

Explanation: If ∈ R then ∈ R, where a and b belong to TWO different sets and so its symmetric.

R^c ALSO CONTAINS

R^c = R.

The correct ANSWER is (C) (R1 U R2)^c = R1^c ∪ R2^c

The BEST I can explain: To PROOF (R1 U R2)^c = R1^c ∪ R2^c,

if belongs to (R1 U R2)^c

⇔ ∈ (R1 U R2)

⇔ ∈ R1or ∈ R2

⇔ ∈ R1^cor ∈ R2^c

⇔ ∈ R1^c ∪ R2^c.

The correct OPTION is (d) 2^80

The BEST I can explain: Let, a RELATION R from A to B is a subset of A×B. As the maximum number of subsets (Elements in the POWERSET) is 2^mn, there are 2^mn number of relations from A to B and so the answer is 2^80.

The correct choice is (d) 1

To EXPLAIN I would say: The RANK of an equivalence relation is the number of an equivalence classes. If we have a1, a2, A3, …, an elements then a1 and a2 will be in the same equivalence class because everything is RELATED and so on. In this CASE, there is only one equivalence class.

The correct choice is (c) 49

Easiest explanation: Let R is an equivalence relation on the set S and so it satisfies the reflexive, symmetric and TRANSITIVE property. The largest equivalence relation means it should CONTAIN the largest number of ORDERED pairs. Since we can have n^2 ordered pairs in R x R where n belongs to S and all these ordered pairs are PRESENT in this relation; its the largest equivalence relation.So there are n^2 ELEMENTS i.e 7^2 = 49 elements in the largest equivalence relation.

The correct option is (a) 2^196

The best explanation: Let S be a SET consists of n DISTINCT ELEMENTS. There are 2^(n-1)*(n-1) number of reflexive and SYMMETRIC relations that can be formed. So, here the answer is 2^(15-1)*(15-1) = 2^196.

Correct option is (a) 2^110

Easy EXPLANATION: Let A be a set consists of n DISTINCT elements. There are 2^(n*n)-n number of reflexive RELATIONS that can be FORMED. So, here the ANSWER is 2^(11*11)-11 = 2^110.