### SET 6

Question 1

**Let A, B and C be non-empty sets and let X = (A - B) - C and Y = (A - C) - (B - C). Which one of the following is TRUE?**

A : X = Y

B : X ⊂ Y

C : Y ⊃ X

D : None of the above

Answer Discuss it!

.

Correct answer is :A

Solution :

We can solve it by making Venn diagram

Question 2

**The following is the Hasse diagram of the poset [{a, b, c, d, e}, <].The poset is**

A : not a lattice

B : a lattice but not a distributive lattice

C : a distributive lattice but not a Boolean algebra

D : a Boolean algebra

Answer Discuss it!

.

Correct answer is :C

Question 3

**Let G be a simple connected planar graph with 13 vertices and 19 edges. Then, the number of faces in the planar embedding of the graph is**

A : 6

B : 8

C : 9

D : 13

Answer Discuss it!

.

Correct answer is :B

Solution :

We can apply Euler's Formula of planar graphs. The formula is v - e + f = 2.

Question 4

**Let G be a simple graph with 20 vertices and 100 edges. The size of the minimum vertex cover of G is 8. Then, the size of the maximum independent set of G is**

A : 12

B : 8

C : less than 8

D : more than 12

Answer Discuss it!

.

Correct answer is :A

Solution :

The number of vertices of a graph is equal to its minimum vertex cover number plus the size of a maximum independent set.

Question 5

**Let f(x) be the continuous probability density function of a random variable X. The probability that a < X <= b, is**

A : f(b-a)

B : f(b) - f(a)

C : D :

Answer Discuss it!

.

Correct answer is :C

Question 6

**The set {1, 2, 4, 7, 8, 11, 13, 14} is a group under multiplication modulo 15. The inverses of 4 and 7 are respectively**

A : 3 and 13

B : 2 and 11

C : 4 and 13

D : 8 and 14

Answer Discuss it!

.

Correct answer is :C

Question 7

**Let P, Q and R be three atomic prepositional assertions. Let X denote (P v Q) → R and Y denote (P → R) v (Q → R). Which one of the following is a tautology?**

A : X = Y

B : X → Y

C : Y → X

D : ¬ Y → X

Answer Discuss it!

.

Correct answer is :B

Question 8

**What is the first order predicate calculus statement equivalent to the following? **

Every teacher is liked by some student

A : ∀(x) [teacher (x) → ∃ (y) [student (y) → likes (y, x)]]

B : ∀ (x) [teacher (x) → ∃ (y) [student (y) ^ likes (y, x)]]

C : ∃ (y) ∀ (x) [teacher (x) → [student (y) ^ likes (y, x)]]

D : ∀ (x) [teacher (x) ^ ∃ (y) [student (y) → likes (y, x)]]

Answer Discuss it!

.

Correct answer is :B

Question 9

**Let R and S be any two equivalence relations on a non-empty set A. Which one of the following statements is TRUE?**

A : R ∪ S, R ∩ S are both equivalence relations

B : R ∪ S is an equivalence relation

C : R ∩ S is an equivalence relation

D : Neither R ∪ S nor R ∩ S is an equivalence relation

Answer Discuss it!

.

Correct answer is :C

Question 10

**Let f: B → C and g: A → B be two functions and let h = f o g. Given that h is an onto function. Which one of the following is TRUE?**

A : f and g should both be onto functions.

B : f should be onto but g need not be onto

C : g should be onto but f need not be onto

D : both f and g need not be onto

Answer Discuss it!

.

Correct answer is :B

Question 11

**What is the minimum number of ordered pairs of non-negative numbers that should be chosen to ensure that there are two pairs (a, b) and (c, d) in the chosen set such that "a = c mod 3" and "b = d mod 5"**

A : 4

B : 6

C : 16

D : 24

Answer Discuss it!

.

Correct answer is :C

Question 12

**Consider the set H of all 3 × 3 matrices of the type given below where a, b, c, d, e and f are real numbers and abc ≠ 0. Under the matrix multiplication operation, the set H is**

A : a group

B : a monoid but not a group

C : a semigroup but not a monoid

D : neither a group nor a semigroup

Answer Discuss it!

.

Correct answer is :C

Question 13

**Which one of the following graphs is NOT planar?**

A : G1

B : G2

C : G3

D : G4

Answer Discuss it!

.

Correct answer is :A

Solution :

A graph is planar if it can be redrawn in a plane without any crossing edges. G1 is a typical example of nonplanar graphs.

Question 14

**Consider the following system of equations in three real variables xl, x2 and x3**

2x1 - x2 + 3x3 = 1

3x1- 2x2 + 5x3 = 2

-x1 + 4x2 + x3 = 3

This system of equations has

A : no solution

B : a unique solution

C : more than one but a finite number of solutions

D : an infinite number of solutions

Answer Discuss it!

.

Correct answer is :B

Solution :

The determinant value of following matrix is non-zero, therefore we have a unique solution.

2 -1 3

3 -2 5

-1 4 1

Question 15

**What are the eigenvalues of the following 2 × 2 matrix?**

A : -1 and 1

B : 1 and 6

C : 2 and 5

D : 4 and -1

Answer Discuss it!

.

Correct answer is :B

Solution :

The eigenvalues of A are precisely the real numbers ? that satisfy the equation det(A - λ I) = 0. Let us find determinant value of A - &lambda I;

2-λ -1
-4 5-λ

Solve the equations and get the correct answer

Question 16

**Let G(x) = the function given below , where |x| <1 . What is g(i)?**

A : i

B : i+1

C : 2i

D : 2^{i}

Answer Discuss it!

.

Correct answer is :B

Solution :

B is the correct option. Let us put values

S = 1 + 2x + 3x2 + 4x3 + ..........

Sx = x + 2x2 + 3x3 + ..........

S - Sx = 1 + x + x2 + x3 + ....

S - Sx = 1/(1 - x) [sum of infinite GP series with ratio < 1 is a/(1-r)]

S = 1/(1 - x)^{2}

Question 17

**Box P has 2 red balls and 3 blue balls and box Q has 3 red balls and 1 blue ball. A ball is selected as follows:**

(i) Select a box

(ii) Choose a ball from the selected box such that each ball in the box is equally likely to be chosen. The probabilities of selecting boxes P and Q are (1/3) and (2/3), respectively.

Given that a ball selected in the above process is a red ball, the probability that it came from the box P is

A : 4/19

B : 5/19

C : 2/9

D : 19/30

Answer Discuss it!

.

Correct answer is :A

Solution :

The probability of selecting a red ball =

(1/3) * (2/5) + (2/3) * (3/4) = 2/15 + 1/2

= 19/30 [Let it be P1]

Probability of selecting a red ball from box P =

(1/3) * (2/5) = 2/15 [Let it be P2]

Given that a ball selected in the above process is
a red ball, the probability that it came from the
box P is

= P1/P2 = (2/15) / (19/30) = 4/19

Question 18

**A random bit string of length n is constructed by tossing a fair coin n times and setting a bit to 0 or 1 depending on outcomes head and tail, respectively. The probability that two such randomly generated strings are not identical is**

A : 1/2^{n}

B : 1-(1/n)

C : 1/n!

D : 1-(1/2^{n})

Answer Discuss it!

.

Correct answer is :D

Solution :

The probability that the two strings are identical is

(1/2) * (1/2) * ..... * (1/2) (n times) which is 1/2^{n}

The probability for not identical is 1 - (1/2^{n})

Question 19

**Consider the polynomial p(x) = a0 + a1x + a2x**^{2} + a3x^{3} , where ai ≠ 0, ∀i. The minimum number of multiplications needed to evaluate p on an input x is:

A : 3

B : 4

C : 6

D : 9

Answer Discuss it!

.

Correct answer is :A

Solution :

Using Horner's Rule, we can write the polynomial as following a0 + (a1 + (a2 + a3x)x)x In the above form, we need to do only 3 multiplications

p = a3 X x ------------ (1)

q = (a2 + p) X x ---------(2)

r = (a1 + q) X x ---------(3)

result = a0 + r

Question 20

**Let X, Y, Z be sets of sizes x, y and z respectively. Let W = X x Y. Let E be the set of all subsets of W. The number of functions from Z to E is:**

A : z^{2xy}

B : z* 2^{xy}

C : z^{2x+y}

D : 2^{xzy}

Answer Discuss it!

.

Correct answer is :A

Solution :

Number of elements in W = 2^{xy}

Number of elements in Z = z Number of functions from Z to E = z^{2xy}

Question 21

**The set {1, 2, 3, 5, 7, 8, 9} under multiplication modulo 10 is not a group. Given below are four plausible reasons. Which one of them is false?**

A : It is not closed

B : 2 does not have an inverse

C : 3 does not have an inverse

D : 8 does not have an inverse

Answer Discuss it!

.

Correct answer is :C

Solution :

A is not closed under multiplication as we may get 0 after multiplication and 0 is not present in set. 2 doesn't have an inverse as there is no x such that (2*x) mod 10 is 1. 3 has an inverse as (3*7) mod 10 is 1. 8 doesn't have an inverse as there is no x such that (2*x) mod 10 is 1.

Question 22

**A relation R is defined on ordered pairs of integers as follows: (x,y) R(u,v) if x < u and y > v. Then R is: Then R is:**

A : Neither a Partial Order nor an Equivalence Relation

B : A Partial Order but not a Total Order

C : A Total Order

D : An Equivalence Relation

Answer Discuss it!

.

Correct answer is :A

Solution :

R is not reflexive

Question 23

**We are given a set X = {x1, .... xn} where xi = 2**^{i}. A sample S ? X is drawn by selecting each xi independently with probability p1 = 1/2. The expected value of the smallest number in sample S is:

A : 1/n

B : 2

C : √n

D : n

Answer Discuss it!

.

Correct answer is :D

Solution :

E = (1/(2^1))*(2^1) + (1/(2^2))*(2^2) + … (1/(2^n))*(2^n) = 1+1+…1 (n times addition of 1) = n

Question 24

**For each element in a set of size 2n, an unbiased coin is tossed. The 2n coin tosses are independent. An element is chosen if the corresponding coin toss were head. The probability that exactly n elements are chosen is:**

A : (2nCn) / (4^n)

B : (2nCn) / (2^n)

C : 1 / (2nCn)

D : 1/2

Answer Discuss it!

.

Correct answer is :A

Solution :

The question is mainly about probability of n heads out of 2n coin tosses. P = 2nCn((1/2)^n)((1/2)^n) = (2nCn) / (4^n)

Question 25

**Let E, F and G be finite sets. Let X = (E ∩ F) - (F ∩ G) and Y = (E - (E ∩ G)) - (E - F). Which one of the following is true?**

A : X ⊂ Y

B : X ⊃ Y

C : X = Y

D : X - Y ≠ ∅ and Y - X ≠ ∅

Answer Discuss it!

.

Correct answer is :C

Solution :

If we draw the venn diagrams of both X and Y, we find that both cover exactly same region

Question 26

**F is an n*n real matrix. b is an n*1 real vector. Suppose there are two n*1 vectors, u and v such that, u ≠ v and Fu = b, Fv = b. Which one of the following statements is false?**

A : Determinant of F is zero.

B : There are an infinite number of solutions to Fx = b

C : There is an x ≠ 0 such that Fx = 0

D : F must have two identical rows

Answer Discuss it!

.

Correct answer is :D

Solution :

Since Fu = b, and also Fv = b, so we have (Fu - Fb) = 0 i.e. F(u-v) = 0. Since u?v, F is a singular matrix i.e. its determinant is 0. Now for a singular matrix F, either Fx = b has no solution or infinitely many solutions, but as we are already given two solutions u and v for x, Fx = b has to have infinitely many solutions. Moreover, by definition of singular matrix, there exists an x?0 such that Fx = 0 . So options (A), (B), and (C) are true. Option (D) is false because it may not be necessary

Question 27

**Given a set of elements N = {1, 2, ..., n} and two arbitrary subsets A ⊆ N and B ⊆ N, how many of the n! permutations π from N to N satisfy min( π(A)) = min( π(B)), where min(S) is the smallest integer in the set of integers S, and π(S) is the set of integers obtained by applying permutation π to each element of S?**

A : ( n - | A ∪ B| ) |A| |B|

B : ( |A|^{2} + |B|^{2} ) n^{2}

C : n! * |A ∩ B| / |A ∪ B|

D : |A ∩ B|^{2} / nC|A ∪ B|

Answer Discuss it!

.

Correct answer is :C

Question 28

**Let S = {1,2,3,........,m},m > 3. Let X1.............. Xn be subsets of S each of size 3. Define a function f from S to the set of natural numbers as, f (i ) is the number of sets Xj that contain the element i. That is f(i) =| { j | i ∈ X**_{j}| } |. &sigma of f(i) from i=1 to m is :

A : 3m

B : 3n

C : 2m+1

D : 2n+1

Answer Discuss it!

.

Correct answer is :B

Solution :

First of all, number of subsets of S of size 3 is mC3 i.e. n=mC3. Now we count number of subsets in which a particular element i appears, that will be (m?1)C2, because 1 element is already known, and we have to choose 2 elements from remaining m-1 elements.Therefore in the same way solution will become 3n

Question 29

**Which one of the first order predicate calculus statements given below correctly express the following English statement? **

Tigers and lions attack if they are hungry or threatened.

A : ∀x [ (tiger(x) ∧ lion(x)) -> {hungry(x) ∨ threatened(x)) -> attacks(x) } ]

B : ∀x [ (tiger(x) ∨ lion(x)) -> {hungry(x) ∨ threatened(x)) ∧ attacks(x) } ]

C : ∀x [ (tiger(x) ∨ lion(x)) -> {attack(x) ->(hungry(x) ∨ threatened(x)) } ]

D : ∀x [ (tiger(x) ∨ lion(x)) -> {hungry(x) ∨ threatened(x)) -> attacks(x) } ]

Answer Discuss it!

.

Correct answer is :D

Solution :

The statement 'Tigers and lions attack if they are hungry or threatened' means that if an animal is either tiger or lion, then if it is hungry or threatened, it will attack. So option (D) is correct. Don't get confused by 'and' between tigers and lions in the statement. This 'and' doesn't mean that we will write 'tiger(x) ∧ lion(x) ', because that would have meant that an animal is both tiger and lion, which is not what we want.

Question 30

**Consider the following propositional statements: **

P1 : ((A ∧ B) -> C)) = ((A -> C) ∧ (B -> C))

P2 : ((A ∨ B) -> C)) = ((A -> C) ∨ (B -> C))

Which one of the following is true?

A : P1 is a tautology, but not P2

B : P2 is a tautology, but not P1

C : P1 and P2 are both tautologies

D : Both P1 and P2 are not tautologies

Answer Discuss it!

.

Correct answer is :D

Solution :

The easiest way to solve this question by creating truth tables for the expressions given. Note that P1 will be a tautology if truth table for left expression is exactly same as truth table for right expression. Same holds for P2 also.

Question 31

**The 2**^{n} vertices of a graph G corresponds to all subsets of a set of size n, for n >= 6 . Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements. The number of vertices of degree zero in G is:

A : 1

B : n

C : n+1

D : 2^{n}

Answer Discuss it!

.

Correct answer is :C

Solution :

There are n nodes which are single and 1 node which belong to empty set. And since they are not having 2 or more elements so they won’t be connected to anyone hence total number of nodes with degree 0 are n+1 hence answer should be none.

Question 32

**The 2**^{n} vertices of a graph G corresponds to all subsets of a set of size n, for n >= 6. Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements. The maximum degree of a vertex in G is:

A : (n/2)C2 x 2^{n/2}

B : 2^{n-2}

C : 2^{n-3} * 3

D : 2^{n-1}

Answer Discuss it!

.

Correct answer is :A

Solution :

Let us take an example {a, b, c, d, e, f} The maximum degree would be of any vertex that corresponds to a sunset with half vertices. For example consider {a, b, c}. It has degree as 24. It intersects with 8 subsets with intersection as {a, b}. The subsets are {a, b}, {a, b, d}, {a, b, e}, {a, b, f}, {a, b, d, e}, {a, b, e, f}, {a, b, d, f} and {a, b, d, e, f}. Similarly, it intersects with 8 vertices with intersection as {a, c} and 8 more vertices with intersection as {b, c}. There are n/2 C 2 w

Question 33

**The 2**^{n} vertices of a graph G corresponds to all subsets of a set of size n, for n >= 6. Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements. The number of connected components in G is:

A : n

B : n+2

C : 2^{n/2}

D : 2^{n}/n

Answer Discuss it!

.

Correct answer is :B

Solution :

n+1 nodes of the graph not connected to anyone as explained in question 70 while others are connected so total number of connected components are n+2 (n+1 connected components by each of the n+1 vertices plus 1 connected component by remaining vertices).

Question 1

.

Correct answer is :A

Solution :

We can solve it by making Venn diagram

Question 2

.

Correct answer is :C

Question 3

.

Correct answer is :B

Solution :

We can apply Euler's Formula of planar graphs. The formula is v - e + f = 2.

Question 4

.

Correct answer is :A

Solution :

The number of vertices of a graph is equal to its minimum vertex cover number plus the size of a maximum independent set.

Question 5

.

Correct answer is :C

Question 6

.

Correct answer is :C

Question 7

.

Correct answer is :B

Question 8

Every teacher is liked by some student

.

Correct answer is :B

Question 9

.

Correct answer is :C

Question 10

.

Correct answer is :B

Question 11

.

Correct answer is :C

Question 12

.

Correct answer is :C

Question 13

.

Correct answer is :A

Solution :

A graph is planar if it can be redrawn in a plane without any crossing edges. G1 is a typical example of nonplanar graphs.

Question 14

2x1 - x2 + 3x3 = 1

3x1- 2x2 + 5x3 = 2

-x1 + 4x2 + x3 = 3

This system of equations has

.

Correct answer is :B

Solution :

The determinant value of following matrix is non-zero, therefore we have a unique solution.

2 -1 3

3 -2 5

-1 4 1

Question 15

.

Correct answer is :B

Solution :

The eigenvalues of A are precisely the real numbers ? that satisfy the equation det(A - λ I) = 0. Let us find determinant value of A - &lambda I;

2-λ -1 -4 5-λ

Solve the equations and get the correct answer

Question 16

.

Correct answer is :B

Solution :

B is the correct option. Let us put values

S = 1 + 2x + 3x2 + 4x3 + ..........

Sx = x + 2x2 + 3x3 + ..........

S - Sx = 1 + x + x2 + x3 + ....

S - Sx = 1/(1 - x) [sum of infinite GP series with ratio < 1 is a/(1-r)]

S = 1/(1 - x)

^{2}

Question 17

(i) Select a box

(ii) Choose a ball from the selected box such that each ball in the box is equally likely to be chosen. The probabilities of selecting boxes P and Q are (1/3) and (2/3), respectively.

Given that a ball selected in the above process is a red ball, the probability that it came from the box P is

.

Correct answer is :A

Solution :

The probability of selecting a red ball =

(1/3) * (2/5) + (2/3) * (3/4) = 2/15 + 1/2

= 19/30 [Let it be P1]

Probability of selecting a red ball from box P =

(1/3) * (2/5) = 2/15 [Let it be P2]

Given that a ball selected in the above process is a red ball, the probability that it came from the box P is

= P1/P2 = (2/15) / (19/30) = 4/19

Question 18

.

Correct answer is :D

Solution :

The probability that the two strings are identical is

(1/2) * (1/2) * ..... * (1/2) (n times) which is 1/2

^{n}

The probability for not identical is 1 - (1/2

^{n})

Question 19

^{2}+ a3x

^{3}, where ai ≠ 0, ∀i. The minimum number of multiplications needed to evaluate p on an input x is:

.

Correct answer is :A

Solution :

Using Horner's Rule, we can write the polynomial as following a0 + (a1 + (a2 + a3x)x)x In the above form, we need to do only 3 multiplications

p = a3 X x ------------ (1)

q = (a2 + p) X x ---------(2)

r = (a1 + q) X x ---------(3)

result = a0 + r

Question 20

.

Correct answer is :A

Solution :

Number of elements in W = 2

^{xy}

Number of elements in Z = z Number of functions from Z to E = z

^{2xy}

Question 21

.

Correct answer is :C

Solution :

A is not closed under multiplication as we may get 0 after multiplication and 0 is not present in set. 2 doesn't have an inverse as there is no x such that (2*x) mod 10 is 1. 3 has an inverse as (3*7) mod 10 is 1. 8 doesn't have an inverse as there is no x such that (2*x) mod 10 is 1.

Question 22

.

Correct answer is :A

Solution :

R is not reflexive

Question 23

^{i}. A sample S ? X is drawn by selecting each xi independently with probability p1 = 1/2. The expected value of the smallest number in sample S is:

.

Correct answer is :D

Solution :

E = (1/(2^1))*(2^1) + (1/(2^2))*(2^2) + … (1/(2^n))*(2^n) = 1+1+…1 (n times addition of 1) = n

Question 24

.

Correct answer is :A

Solution :

The question is mainly about probability of n heads out of 2n coin tosses. P = 2nCn((1/2)^n)((1/2)^n) = (2nCn) / (4^n)

Question 25

.

Correct answer is :C

Solution :

If we draw the venn diagrams of both X and Y, we find that both cover exactly same region

Question 26

.

Correct answer is :D

Solution :

Since Fu = b, and also Fv = b, so we have (Fu - Fb) = 0 i.e. F(u-v) = 0. Since u?v, F is a singular matrix i.e. its determinant is 0. Now for a singular matrix F, either Fx = b has no solution or infinitely many solutions, but as we are already given two solutions u and v for x, Fx = b has to have infinitely many solutions. Moreover, by definition of singular matrix, there exists an x?0 such that Fx = 0 . So options (A), (B), and (C) are true. Option (D) is false because it may not be necessary

Question 27

.

Correct answer is :C

Question 28

_{j}| } |. &sigma of f(i) from i=1 to m is :

.

Correct answer is :B

Solution :

First of all, number of subsets of S of size 3 is mC3 i.e. n=mC3. Now we count number of subsets in which a particular element i appears, that will be (m?1)C2, because 1 element is already known, and we have to choose 2 elements from remaining m-1 elements.Therefore in the same way solution will become 3n

Question 29

Tigers and lions attack if they are hungry or threatened.

.

Correct answer is :D

Solution :

The statement 'Tigers and lions attack if they are hungry or threatened' means that if an animal is either tiger or lion, then if it is hungry or threatened, it will attack. So option (D) is correct. Don't get confused by 'and' between tigers and lions in the statement. This 'and' doesn't mean that we will write 'tiger(x) ∧ lion(x) ', because that would have meant that an animal is both tiger and lion, which is not what we want.

Question 30

P1 : ((A ∧ B) -> C)) = ((A -> C) ∧ (B -> C))

P2 : ((A ∨ B) -> C)) = ((A -> C) ∨ (B -> C))

Which one of the following is true?

.

Correct answer is :D

Solution :

The easiest way to solve this question by creating truth tables for the expressions given. Note that P1 will be a tautology if truth table for left expression is exactly same as truth table for right expression. Same holds for P2 also.

Question 31

^{n}vertices of a graph G corresponds to all subsets of a set of size n, for n >= 6 . Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements. The number of vertices of degree zero in G is:

.

Correct answer is :C

Solution :

There are n nodes which are single and 1 node which belong to empty set. And since they are not having 2 or more elements so they won’t be connected to anyone hence total number of nodes with degree 0 are n+1 hence answer should be none.

Question 32

^{n}vertices of a graph G corresponds to all subsets of a set of size n, for n >= 6. Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements. The maximum degree of a vertex in G is:

.

Correct answer is :A

Solution :

Let us take an example {a, b, c, d, e, f} The maximum degree would be of any vertex that corresponds to a sunset with half vertices. For example consider {a, b, c}. It has degree as 24. It intersects with 8 subsets with intersection as {a, b}. The subsets are {a, b}, {a, b, d}, {a, b, e}, {a, b, f}, {a, b, d, e}, {a, b, e, f}, {a, b, d, f} and {a, b, d, e, f}. Similarly, it intersects with 8 vertices with intersection as {a, c} and 8 more vertices with intersection as {b, c}. There are n/2 C 2 w

Question 33

^{n}vertices of a graph G corresponds to all subsets of a set of size n, for n >= 6. Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements. The number of connected components in G is:

.

Correct answer is :B

Solution :

n+1 nodes of the graph not connected to anyone as explained in question 70 while others are connected so total number of connected components are n+2 (n+1 connected components by each of the n+1 vertices plus 1 connected component by remaining vertices).