Probability Questions and Answers | Computer Science Quiz

Computer Science Probability MCQ Quiz Questions and Answers PDF Download

Probability Questions and Answers | Computer Science Quiz

Question 1.
Let A and B be any two arbitrary events, then, which one of the following is true?
(a) P (A ∩ B) = P(A) P(B)
(b) P (A ∪ B) = P(A) + P(B)
(c) P (A | B) = P(A ∩ B)/P(B)
(d) P(A ∪ B)< P(A) + P(B)

Answer/Explanation

Answer:(c) P (A | B) = P(A ∩ B)/P(B)
Explanation:
(a) P(A ∩ B) = P(A) P(B) is false since this is true if and only if A and B are independent events.
(b) P (A ∪ B) = P(A) + P(B) is false since P(A ∩ B) is zero if and only if A and B are mutually exclusive.
(c) P (A | B) = P(A ∩ B)/P(B) is true.
(d) P (A ∪ B) < P(A) + P(B) is false.
Since P(A ∪ B) ≤ P(A) + P(B)


Question 2.
A bag contains 10 white balls and 15 black balls. Two balls are drawn in succession. The probability that one of them is black and the other is white is
(a) \(\frac { 2 }{ 3 }\)
(b) \(\frac { 4 }{ 5 }\)
(c) \(\frac { 1 }{ 2 }\)
(d) \(\frac { 1 }{ 3 }\)

Answer/Explanation

Answer: (c) \(\frac { 1 }{ 2 }\)
Explanation:

Probability Questions and Answers Computer Science Quiz chapter 5 img 1

The bag contains 10 white balls and 15 black balls. Required probability

Probability Questions and Answers Computer Science Quiz chapter 5 img 2


Question 3.
Two dice are thrown simultaneously. The probability that at least one of them will have 6 facing up is
(a) \(\frac { 1 }{ 36 }\)
(b) \(\frac { 1 }{ 3 }\)
(c) \(\frac { 25 }{ 36 }\)
(d) \(\frac { 11 }{ 36 }\)

Answer/Explanation

Answer:(d) \(\frac { 11 }{ 36 }\)
Explanation:
P(atleast one of dice will have 6 facing = 1 – P(none of dice have 6 facing up) = 1 – [\(\frac { 5 }{ 6 }\) × \(\frac { 5 }{ 6 }\)] = 1 – \(\frac { 25 }{ 36 }\) = \(\frac { 11 }{ 36 }\)


Probability Questions and Answers | Computer Science Quiz

Question 4.
The probability that top and bottom cards of a randomly shuffled deck are both aces is
(a) \(\frac { 4 }{ 52 }\) x \(\frac { 4 }{ 52 }\)
(b) \(\frac { 4 }{ 52 }\) x \(\frac { 3 }{ 52 }\)
(c) \(\frac { 4 }{ 52 }\) x \(\frac { 3 }{ 51 }\)
(d) \(\frac { 4 }{ 52 }\) x \(\frac { 4 }{ 51 }\)

Answer/Explanation

Answer:(c) \(\frac { 4 }{ 52 }\) x \(\frac { 3 }{ 51 }\)
Explanation:
The probability that the bottom card of a randomly shuffled deck is ace = \(\frac { 4 }{ 52 }\) because there are 4 aces out of total 52 cards. From the remaining 3 aces out of 51 cards the probability that the top card is also an ace = \(\frac { 3 }{ 51 }\). So required probability = \(\frac { 4 }{ 52 }\) × \(\frac { 3 }{ 51 }\).


Question 5.
The probability that it will rain today is 0.5. The probability that it will rain tomorrow is 0.6. The probability that it will rain either today or tomorrow is 0.7. What is the probability that it will rain today and tomorrow?
(a) 0.3
(b) 0.25
(c) 0.35
(d) 0.4

Answer/Explanation

Answer:(d) 0.4
Explanation:
P(Rain today) = 0.5
P(Rain tomorrow) = 0.6
P(Rain today ∪ Rain tomorrow) = 0.7
P(Rain today ∩ Rain tomorrow) = ?
P(rain today ∩ Rain tomorrow) = P(Rain today) + P(rain tomorrow) – P(Rain today ∩ Rain tomorrow)
So; 0.7 = 0.5 + 0.6 – P(Rain today ∩ Rain tomorrow) P(Rain today ∩ Rain tomorrow) = 0.5+ 0.6-0.7 = 0.4
So, the probability that it will rain today and tomorrow is 0.4.


Question 6.
A die is rolled three times. The probability that exactly one odd number turns up among the three outcomes is
(a) \(\frac { 1 }{ 6 }\)
(b) \(\frac { 3 }{ 8 }\)
(c) \(\frac { 1 }{ 8 }\)
(d) \(\frac { 1 }{ 2 }\)

Answer/Explanation

Answer:(b) \(\frac { 3 }{ 8 }\)
Explanation:
Probability of getting an odd number in rolling of a die = \(\frac { 3 }{ 6 }\) = \(\frac { 1 }{ 2 }\). Now using binomial distribution P(Exactly one odd number among three outcomes)
= 3C1( \(\frac { 1 }{ 2 }\))1 ( \(\frac { 1 }{ 2 }\))2 = 3 × ( \(\frac { 1 }{ 2 }\))3 = ( \(\frac { 3 }{ 8 }\))


Probability Questions and Answers | Computer Science Quiz

Question 7.
Suppose that the expectation of a random variable X is 5. Which of the following statements is true?
(a) There is a sample point at which X has the value 5.
(b) There is a sample point at which X has a value greater than 5.
(c) There is a sample point at which X has a value greater than or equal to 5.
(d) None of the above

Answer/Explanation

Answer:(c) There is a sample point at which X has a value greater than or equal to 5.
Explanation:
If all the points have X < 5, then the expectation of a random variable X is surely less than 5. So according to this, there should be at least a sample point at which X ≥ 5.


Question 8.
Consider two events E1 and E2 such that probability of E1 Pr [E1] = \(\frac { 1 }{ 2 }\), probability of E2, Pr [E2] = \(\frac { 1 }{ 3 }\), and probability of E1 and E2, Pr[E1 and E2] = \(\frac { 1 }{ 5 }\) . Which of the following statements is/are true?
(a) Pr[E1 or E2] is \(\frac { 2 }{ 3 }\)
(b) Events E1 and E2 are independent
(c) Events E1 and E2 are not independent
(d) pr \(\left[\frac{\mathrm{E}_{1}}{\mathrm{E}_{2}}\right]\) = \(\frac { 4 }{ 5 }\)

Answer/Explanation

Answer:(c) Events E1 and E2 are not independent
Explanation:
P(E1)= \(\frac { 1 }{ 2 }\) , P(E2) = \(\frac { 1 }{ 3 }\) and P(E1 ∩ E2) = \(\frac { 1 }{ 5 }\)

(a) P(E1 or E2)
= P(E1) + P(E2) – P(E1 ∩ E2)
= \(\frac { 1 }{ 2 }\) + \(\frac { 1 }{ 3 }\) – \(\frac { 1 }{ 5 }\) = \(\frac { 19 }{ 30 }\)
However given in option (a) is \(\frac { 2 }{ 3 }\).
So option (a) is not true.

(b) For independent events P(E1 ∩ E2) = P(E1) P(E2)
Here, P(E1 ∩ E2) = \(\frac { 2 }{ 5 }\)
P(E1) P(E2) = \(\frac { 1 }{ 2 }\) × \(\frac { 1 }{ 3 }\) = \(\frac { 1 }{ 6 }\)
So; (P E1 ∩ E2) ≠ P(E1) P(E2)
So events E1 and E2 are not independent. Option (b) is not true.

(c) Since E1 and E2 are not independent So option (c) is true.

(d) P(E1/E2) =\(\frac{\mathrm{P}\left(\mathrm{E}_{1} \cap \mathrm{E}_{2}\right)}{\mathrm{P}\left(\mathrm{E}_{2}\right)}\) = \(\frac { 3 }{ 5 }\) So option (d) P(E1/E2) = \(\frac { 4 }{ 5 }\) is false.


Question 9.
E1 and E2 are events in a probability space satisfying the following constraints:

  • Pr(E1) = Pr(E2)
  • Pr(E1 ∪ E2) = 1
  • E1 and E2 are independent

The value of Pr(E1), the probability of the event E1, is
(a) 0
(b) \(\frac { 1 }{ 4 }\)
(c) \(\frac { 1 }{ 2 }\)
(d) 1

Answer/Explanation

Answer:(d) 1
Explanation:
Constraints are
(i) P(E1) = P(E2) = x
(ii) P(E1 ∪ E2) = 1
(iii) E1 and E2 are independent so
P(E1 ∩ E2) = P(E1) P(E2) = x × x = x2

NOW,
P(E1 ∪ E2) = P(E1)+P(E2) – P(E1 ∩ E2)
1 = x + x – x2
1 = 2x – x2
x2 – 2x + 1 = 0
(x – 1)2 = 0
x = 1
So; P(E1) = P(E2) = x = 1


Probability Questions and Answers | Computer Science Quiz

Question 10.
Seven (distinct) car accidents occurred in a week. What is the probability that they all occurred on the same day?
(a) \(\frac{1}{7^{7}}\)
(b) \(\frac{1}{7^{6}}\)
(c) \(\frac{1}{2^{7}}\)
(d) \(\frac{7}{2^{7}}\)

Answer/Explanation

Answer:(b) \(\frac{1}{7^{6}}\)
Explanation:
Sample space = 77
All accidents on the same day = 7 ways (all on Monday, all on Tuesday…)
So, required probability = \(\frac{7}{7^{7}}\) = \(\frac{7}{7^{6}}\)


Question 11.
Four fair coins are tossed simultaneously. The probability that at least one head and one tail turn up is
(a) \(\frac { 1 }{ 16 }\)
(b) \(\frac { 1 }{ 8 }\)
(c) \(\frac { 7 }{ 8 }\)
(d) \(\frac { 15 }{ 16 }\)

Answer/Explanation

Answer:(c) \(\frac { 7 }{ 8 }\)
Explanation:
p(atleast one head and one tail)
= 1 – p(no head or no tail)
= 1 – [p(no head) + p(no tail) – p(no head and no tail)]
= 1 – [p (all tails) + p(all heads) – 0]
= 1 – [\(\left[\frac{1}{2^{4}}+\frac{1}{2^{4}}-0\right]\) = 1 – \(\frac { 2 }{ 16 }\) = 1 – \(\frac { 1 }{ 8 }\) = \(\frac { 7 }{ 8 }\).

Or

Alternate Method:
We need atleast one head (≥1H) and atleast one tail (≥ 1 T). First we satisfy ≥ 1H as follows.
1 H, 3T
2 H, 2 T
3H, 1 T
and 4 H, 0 T
now to satisfy the second condition of ≥ 1 T, we have to remove 4 H, 0 T.
So, the favorable cases are only 1 H, 2 H, and 3 H. The probability of this by binomial distribution formula is
= \(\frac{{ }^{4} C_{1}}{2^{4}}\) + \(\frac{{ }^{4} C_{2}}{2^{4}}\) + \(\frac{{ }^{4} C_{3}}{2^{4}}\)= \(\frac { 7 }{ 8 }\)


Question 12.
Let P(E) denote the probability of the event E. Given P(A) = 1, P(B) = 1/2, and A and B are independent, the values of P(A | B) and P(B | A) respectively are
(a) \(\frac { 1 }{ 4 }\) , \(\frac { 1 }{ 2 }\)
(b) \(\frac { 1 }{ 2 }\) , \(\frac { 1 }{ 4 }\)
(c) \(\frac { 1 }{ 2 }\) , 1
(d) 1 , \(\frac { 1 }{ 2 }\)

Answer/Explanation

Answer:(d) 1 , \(\frac { 1 }{ 2 }\)
Explanation:
Given, P(A) = 1
P(B) = \(\frac { 1 }{ 2 }\)
Since both events are independent
P(A|B) = P(A) = 1
P(B|A) = P(B) = \(\frac { 1 }{ 2 }\)


Question 13.
A program consists of two modules executed sequentially. Let f1(t) and f2(t) respectively denote the probability density functions of time taken to execute the two modules. The probability density function of the overall time taken to execute the program is given by
(a) f1(t) + f2(t)
(b) \(\int_{t}^{0}\) f1 (X) f2 (X)dX
(c) \(\int_{t}^{0}\) f1 (X) f2 (t – X)dX
(d) max {f1(t), f2(t)}

Answer/Explanation

Answer:(c) \(\int_{t}^{0}\) f1 (X) f2 (t – X)dX
Explanation:
Let the time taken for first and second modules be represented by x and y and total time = t.
∴ t = x + y is a random variable. Now the joint density function
g(t) = \(\int_{0}^{t}\)f(x,y)dx
= \(\int_{0}^{t}\)f (x, t – x)dx
= \(\int_{0}^{t}\)f1(x) f2(t – x)dx
which is also called as convolution of f1 and f2, abbreviated as f1 * f2.Correct answer is therefore, choice (c).


Probability Questions and Answers | Computer Science Quiz

Question 14.
If a fair coin is tossed four times. What is the probability that two heads and two tails will result?
(a) \(\frac { 3 }{ 8 }\)
(b) \(\frac { 1 }{ 2 }\)
(c) \(\frac { 5 }{ 8 }\)
(d) \(\frac { 3 }{ 4 }\)

Answer/Explanation

Answer:(a) \(\frac { 3 }{ 8 }\)
Explanation:
Given, P(H) = \(\frac { 1 }{ 2 }\)
P(T) = \(\frac { 1 }{ 2 }\)
Apply Bernoulli’s formula for binomial distribution,
P(X = 2) = \({ }^{4} \mathrm{C}_{2}\)(1/2)2(1 – \(\frac { 1 }{ 2 }\))4 – 2
= \({ }^{4} \mathrm{C}_{2}\) ( \(\frac { 1 }{ 2 }\) )2 (1/2)2
= \(\frac{{ }^{4} \mathrm{C}_{2}}{2^{4}}\) = \(\frac { 6 }{ 16 }\) = \(\frac { 3 }{ 8 }\)


Question 15.
In a population of N families, 50% of the families have three children, 30% of the families have two children and the remaining families have one child. What is the probability that a randomly picked child belongs to a family with two children?
(a) \(\frac { 3 }{ 23 }\)
(b) \(\frac { 6 }{ 23 }\)
(c) \(\frac { 3 }{ 10 }\)
(d) \(\frac { 3 }{ 5 }\)

Answer/Explanation

Answer:(b) \(\frac { 6 }{ 23 }\)
Explanation:

Probability Questions and Answers Computer Science Quiz chapter 5 img 3

Total number of children = 50 × 3 + 30 × 2 + 20 × 1 = 230
Favorable cases = The number of children who come from 2 children families = 30 × 2 = 60
So the probability that a randomly picked child belongs to a 2 children families = \(\frac { 60 }{ 230 }\) = \(\frac { 6 }{ 23 }\)


Question 16.
Let X and Y be two exponentially distributed and independent random variables with mean a and β, respectively. If Z = min (X,Y), then the mean of Z is given by
(a) (1/(α + β))
(b) min (α, β)
(c) (αβ/(α + β))
(d) α + β

Answer/Explanation

Answer:(c) (αβ/(α + β))
Explanation:
f(x) = λ.e-λx, x ≥ 0
X and Y are two independent exponentially distributed random variables. Let λ1 and λ2 parameters of X and Y respectively.
P(X ≥ x)= e-λx, x > 0
P(Y ≥ x)=e2x, x > 0
Given Z = min (X, Y)
P(Z ≥ x) = P(X ≥ x, Y ≥ x)
= P(X ≥ x) P(Y ≥ x)
= e1x . e2x = e-(λ1 + λ2)x
Since mean of exponential distribution = 1/Parameter
So, α = 1/λ1 ⇒ λ1 = 1/α
β = 1/λ2 ⇒ λ2 = 1/β
∴ Z is random variable with parameter
Mean of Z = IMG


Question 17.
An examination paper has 150 multiple-choice questions of one mark each, with each question having four choices. Each incorrect answer fetches — 0.25 mark. Suppose 1000 students choose all their answers randomly with uniform probability. The sum total of the expected marks obtained by all these students is
(a) 0
(b) 2550
(c) 7525
(d) 9375

Answer/Explanation

Answer:(d) 9375
Explanation:
Let the marks obtained per question be a random variable X. Its probability distribution table is given below:

Probability Questions and Answers Computer Science Quiz chapter 5 img 4

Expected marks per question = E(x)=ΣXP(X)
= 1 × \(\frac { 1 }{ 4 }\) + (-o.25) × \(\frac { 3 }{ 4 }\)
= \(\frac { 1 }{ 4 }\) – \(\frac { 3 }{ 16 }\) = \(\frac { 1 }{ 16 }\) marks
Total marks expected for 150 questions = \(\frac { 1 }{ 16 }\) × 150 = \(\frac { 75 }{ 8 }\) marks per student
Total expected marks of 1000 students = \(\frac { 75 }{ 8 }\) ×1000 =9375 marks
So correct answer is (d).


Question 18.
Two n bit binary strings, S1 and S2 are chosen randomly with uniform probability. The probability that the Hamming distance between these strings (the number of bit positions where the two strings differ) is equal to d is
(a) nCd/2n
(b) nCd/2d
(c) d/2n
(d) 1/2d

Answer/Explanation

Answer:(a) nCd/2n
Explanation:
If the hamming distance between two n bit strings is d, we are asking that d out of n trials be successful (success here means that the bits are different). So this is a binomial distribution with n trials and d successes and probability of success

P = \(\frac { 2 }{ 4 }\) = \(\frac { 1 }{ 2 }\)

(Since out of the 4 possibilities {(0,0), (0,1), (1, 0), (1,1)} only two of them (0,1) and (1,0) are success)
So p(X = d) = \({ }^{\mathrm{n}} \mathrm{C}_{\mathrm{d}}(1 / 2)^{\mathrm{d}}(1 / 2)^{\mathrm{n}-\mathrm{d}}\) = \(\frac{{ }^{\mathrm{n}} \mathrm{C}_{\mathrm{d}}}{2^{\mathrm{n}}}\)
Correct choice is therefore (a).


Probability Questions and Answers | Computer Science Quiz

Question 19.
A point is randomly selected with uniform probability in the X-Y. Plane within the rectangle with corners at (0, 0), (1, 0), (1, 2) and (0, 2). If p is the length of the position vector of the point, the expected value of p2 is
(a) \(\frac { 2 }{ 3 }\)
(b) 1
(c) \(\frac { 4 }{ 3 }\)
(d) \(\frac { 5 }{ 3 }\)

Answer/Explanation

Answer:
(d) \(\frac { 5 }{ 3 }\)
Explanation:

Probability Questions and Answers Computer Science Quiz chapter 5 img 5

Length of position vector of point = p = \(\sqrt{x^{2}+y^{2}}\)
p2 = x2 + y2
E(p2) = E(x2 + y2) = E(x2) + E(y2)
Now x and y are uniformly distributes 0 ≤ x ≤ 1 and 0 ≤ y ≤ 2 Probability density function of x = \(\frac { 1 }{ 1 – 0 }\) = 1
The probability density function of

Probability Questions and Answers Computer Science Quiz chapter 5 img 6


Question 20.
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) \(\int_{b}^{a}\) f(X)dX
(d) \(\int_{b}^{a}\) xf (X)dX

Answer/Explanation

Answer:(c)\(\int_{b}^{a}\) f(X)dX
Explanation:
If f(x) is the continuous probability density function of a random variable X then, p(a < x ≤ b) = p(a ≤ x ≤ b) = \(\int_{b}^{a}\)f (x)dx


Question 21.
A bag contains 10 blue marbles, 20 green marbles and 30 red marbles. A marble is drawn from the bag, its colour recorded and it is put back in the bag. This process is repeated 3 times. The probability that no two of the marbles drawn have the same colour is
(a) \(\frac { 1 }{ 36 }\)
(b) \(\frac { 1 }{ 6 }\)
(c) \(\frac { 1 }{ 4 }\)
(d) \(\frac { 1 }{ 3 }\)

Answer/Explanation

Answer:
(b) \(\frac { 1 }{ 6 }\)
Explanation:
The given condition corresponds to sampling with replacement and with order. No 2 marbles have the same color i.e. Drawn 3 different marble. So total number of ways for picking 3 different marbles = 3! = 6. Probability of getting blue, green, red in order
= \(\frac { 10 }{ 60 }\) × \(\frac { 20 }{ 60 }\) × \(\frac { 30 }{ 60 }\) × 6
[Since 6 ways to get the marbles] = \(\frac { 1 }{ 6 }\)


Question 22.
An unbiased coin is tossed repeatedly until the outcome of two successive tosses is the same. Assuming that the trials are independent, the expected number of tosses is
(a) 3
(b) 4
(c) 5
(d) 6

Answer/Explanation

Answer:(a) 3
Explanation:
E(X) = S(Xi × Pi)
Where Xi = number of tosses until we get successive HEAD or TAIL.
Pi = Probability that we get in Xi tosses. Total possibilities by tossing a coin two times i.e. HT, HH, TH, TT. Out of which favorable cases are HH, TT.
P(X = 2) = \(\frac { 2 }{ 4 }\)
Similarly for X = 3 only THH and HTT are favorable out of a total of 8 outcomes.
So, P(X = 3) = \(\frac { 2 }{ 8 }\)
Similarly, we can see that in every case we will have only 2 favorable cases and 2n sample space.
So for nth toss probability = P(X = n) = 2/2n So the probability distribution table for X (the number of Tosses) is given below:

X 2 3 4 6
P(X) 2/4 2/8 2/16 2/32

E(X) = 2 × \(\frac { 2 }{ 4 }\) + 3 × \(\frac { 2 }{ 8 }\) + 4 × \(\frac { 2 }{ 16 }\) + …… It is combination of AP and GP form. So multiplying E(X) by \(\frac { 1 }{ 2 }\) and subtracting from E(X)
E(X) = 2 × \(\frac { 1 }{ 2 }\) + 3 × \(\frac { 1 }{ 4 }\) + 4 × \(\frac { 1 }{ 8 }\) + …..
\(\frac { 1 }{ 2 }\) × E(X) = 2 × \(\frac { 1 }{ 4 }\) + 3 × \(\frac { 1 }{ 8 }\) + 4 × \(\frac { 1 }{ 16 }\) + …..
After solving both equations we get,
\(\frac { 1 }{ 2 }\) × E(X) = 1 + \(\frac { 1 }{ 4 }\) + \(\frac { 1 }{ 8 }\) + \(\frac { 1 }{ 16 }\) + ……
\(\frac { 1 }{ 2 }\) × E(X) = 1 + \(\frac{1 / 4}{(1-1 / 2)}\) ⇒ E(X) = \(\frac { 6 }{ 4 }\) × 2 = 3


Probability Questions and Answers | Computer Science Quiz

Question 23.
In a certain town, the probability that it will rain in the afternoon is known to be 0.6. Moreover, meteorological data indicates that if the temperature at noon is less than or equal to 25°C, the probability that it will rain in the afternoon is 0.4. The temperature at noon is equally likely to be above 25°C, or at/below 25°C.
What is the probability that it will rain in the afternoon on a day when the temperature at noon is above 25°C?
(a) 0.4
(b) 0.6
(c) 0.8
(d) 0.9

Answer/Explanation

Answer:(c) 0.8
Explanation:
Let RA : Rain in the afternoon T > 25: Temperature more than 25°C
Let the desired probability = P(RA | T ≤ 25) = x
The tree diagram for this problem is given below:

Probability Questions and Answers Computer Science Quiz chapter 5 img 7

Given P(RA) = 0.6 by rule of total probability P(RA)
= \(\frac { 1 }{ 2 }\) × 0.4 + \(\frac { 1 }{ 2 }\) × x = 0.6 ⇒ x = 0.8


Question 24.
When a coin is tossed, the probability of getting a Head is p, 0 < p < 1. Let N be the random variable denoting the number of tosses till the first Head appears, including the toss where the Head appears. Assuming that successive tosses are independent, the expected value of N is
(a) 1/p
(b) 1/(1 – p)
(c) 1/P2
(d) 1/(1 – p2)

Answer/Explanation

Answer:(a) 1/p
Explanation:
The number of attempts to first succeed follows a geometric distribution. It is well known that the expected value in geometric distribution E(X) = 1/p. Where p is the probability of success in any one attempt.

Alternate Method:

Let X be the number of attempts to first success. Let p be the probability of success in any one attempt. Now the probability distribution table of X is given below:

X 1 2 3 4
P(X) p (1 – p)p (1 – p)2p (1 – p)3p

E(X) = Σ xp(x) = 1 × p + 2 × (p – 1) p + 3 × (p – 1)2 p + ……
This is the arithmetico-geometric series which can be solved as E(X) = 1/p


Question 25.
Suppose there are two coins. The first coin gives heads with probability \(\frac { 5 }{ 8 }\) when tossed, while the second coin gives heads with probability \(\frac { 1 }{ 4 }\). One of the two coins is picked up at random with equal probability and tossed. What is the probability of obtaining heads?
(a) \(\frac { 7 }{ 8 }\)
(b) \(\frac { 1 }{ 2 }\)
(c) \(\frac { 7 }{ 16 }\)
(d) \(\frac { 5 }{ 32 }\)

Answer/Explanation

Answer:(c) \(\frac { 7 }{ 16 }\)
Explanation:
The tree diagram for the problem is given below:

Probability Questions and Answers Computer Science Quiz chapter 5 img 8


Probability Questions and Answers | Computer Science Quiz

Question 26.
Suppose we uniformly and randomly select a permutation from the 20! permutations of 1, 2, 3,…, 20. What is the probability that 2 appears at an earlier position than any other even number in the selected permutation?
(a) \(\frac { 1 }{ 2 }\)
(b) \(\frac { 1 }{ 10 }\)
(c) \(\frac { 9! }{ 20! }\)
(d) None of these

Answer/Explanation

Answer:(d) None of these
Explanation:
The number of permutations with ‘2’ in the first position = 19!
The number of permutations with ‘2’ in the second position = 10 × 18!
(Fill the first space with any of the 10 add numbers and the 18 spaces after the 2 with 18 of the remaining numbers in 18! ways)
A number of permutations with ‘2’ in 3rd position = 10 × 9 × 17!
(Fill the first 2 places with 2 of the 10 odd numbers and then the remaining 17 places with the remaining 17 numbers) and so on until ‘2’ is in 11th place. After that, it is not possible to satisfy the given condition, since there are only 10 odd numbers available to fill before the ‘2’. So the desired number of permutations that satisfy the given condition is 19! + 10 × 18! + 10 × 9 × 17! + 10 × 9 × 8 × 16! + … + 10! × 9!

Now the probability of this happening is given by \(\frac{19 !+10 \times 18 !+10 \times 9 \times 17 ! \ldots+10 ! \times 9 !}{20 !}\)
which is clearly not choices (a), (b) or (c)
∴ Answer is (d) none of these.


Question 27.
In a multi-user operating system on average, 20 requests are made to use a particular resource per hour. The arrival of requests follows a Poisson distribution. The probability that either one, three, or five requests are made in 45 minutes is given by:
(a) 6.9 × 106 × e-20
(b) 1.02 × 106 × e-20
(c) 6.9 × 103 × e-20
(d) 1.02 × 103 × e-20

Answer/Explanation

Answer:(b) 1.02 × 106 × e-20
Explanation:
The requests follow poisson distribution with α = 20 requests/hr
The observation period = △T = 45 minutes = \(\frac { 45 }{ 60 }\) = \(\frac { 3 }{ 4 }\)hr
So the parameter for the poisson distribution = λ = α △ T= 20 × \(\frac { 3 }{ 4 }\) = 15
The required probability P(X = 1) + P(X = 3) + P(X = 5)
= \(\frac{e^{-15} 15^{1}}{1 !}\) + \(\frac{e^{-15} 15^{3}}{3 !}\) + \(\frac{e^{-15} 15^{5}}{5 !}\) = 1.02 × 106 × e-20


Question 28.
A sample space has two events A and B such that probabilities P(A ∩ B) = 1/2, P( \(\overline{\mathrm{A}}\) ) = 1/3, P( \(\overline{\mathrm{B}}\) ) = 1/3. What is P(A ∪ B)?
(a) \(\frac{11}{12}\)
(b) \(\frac{10}{12}\)
(c) \(\frac{ 9}{12}\)
(d) \(\frac{8}{12}\)

Answer/Explanation

Answer:(b) \(\frac{10}{12}\)
Explanation:
We know that:
P(A ∪ B) = P(A) + P(B) – P(A ∩ B)
\(\overline{\mathrm{P}(\mathrm{A})}\) = 1 – P(A) and \(\overline{\mathrm{P}(\mathrm{B})}\) = 1 – P(B)
So, P(A) = ( 1 – \(\overline{\mathrm{P}(\mathrm{A})}\)) and P(B) = (1 – \(\overline{\mathrm{P}(\mathrm{B})}\))
P(A ∪ B) = (1 – \(\overline{\mathrm{P}(\mathrm{A})}\)) + (1 – \(\overline{\mathrm{P}(\mathrm{B})}\)) – P(A ∩ B)
= (1 – 1/3) + (1 – 1/3) – (1/2)
= (2/3) + (2/3) – (1/2)
= (4/3) – (1/2) = (5/6) = (10/12)


Probability Questions and Answers | Computer Science Quiz

Question 29.
What is the probability that in a randomly chosen group of r people at least three people have the same birthday?

Probability Questions and Answers Computer Science Quiz chapter 5 img 9

Answer/Explanation

Answer:
(c) 1 – \(\frac{365.364 \ldots(365-r+1)}{365^{r}}\) – rC2 . 365 . \(\frac{364.363 \ldots(364-(r-2)+1)}{364^{r-2}}\)
Explanation:
P(at least three people have the same birthday) = 1 – P (all have different b’days) – P(exactly two people have same b’day)
Now, P(all have different b’days) = \(\frac{365.364 \ldots(365-r+1)}{365^{r}}\)
P(exactly two people have same b’day) = \({ }^{r} C_{2} \cdot 365 \cdot \frac{364.363 \ldots(364-(r-2)+1)}{364^{r-2}}\)
[rC2 ways to choose who those two people with same b’day are, 365 ways to choose what the b’day is]
Now,
P (at least three people have the same birthday)
= 1 – \(\frac{365.364 \ldots(365-r+1)}{365^{r}}\)
= \({ }^{r} C_{2} \cdot 365 \cdot \frac{364.363 \ldots(364-(r-2)+1)}{364^{r-2}}\)
Which is option (c).


Question 30.
Aishwarya studies either computer science or mathematics every day. If she studies computer science on a day, then the probability that she studies mathematics the next day is 0.6. If she studies mathematics on a day, then the probability that she studies computer science the next day is 0.4. Given that Aishwarya studies computer science on Monday, what is the probability that she studies computer science on Wednesday?
(a) 0.24
(b) 0.36
(c) 0.4
(d) 0.6

Answer/Explanation

Answer:(c) 0.4
Explanation:
Let C denote computes science study and M denotes maths study. The tree diagram for the problem can be represented as shown below:

Probability Questions and Answers Computer Science Quiz chapter 5 img 10

Now by the rule of total probability we total up the desired branches (✓) and get the answer as shown below:
p(C on Monday and C on Wednesday)
= p(C on Monday, C on Tuesday and C on Wednesday) + p(C on Monday, M on Tuesday, and C on Wednesday)
= 1 × 0.4 × 0.4 + 1 × 0.6 × 0.4 = 0.16 + 0.24 = 0.40


Question 31.
Let X be a random variable following a normal distribution with mean +1 and variance 4. Let Y be another normal variable with mean -1 and variance unknown. If P(X ≤ -1) = P(Y ≥ 2) the standard deviation of Y is
(a) 3
(b) 2
(c) \(\sqrt{2}\)
(d) 1

Answer/Explanation

Answer:(a) 3
Explanation:
Given µX = 1, σx2 = 4 => σx = 2 and µY = -1.σY is unknow
Given, p(X ≤ -1) = p(Y ≥ 2)
Converting into standard normal variates

Probability Questions and Answers Computer Science Quiz chapter 5 img 11

Now since we know that in a standard normal distribution,
p(z ≤ -1) = p(z ≥ 1) … (ii)
Comparing (i) and (ii) we can say that
\(\frac{3}{\sigma_{\mathrm{y}}}\) = 1 ⇒σy = 3


Probability Questions and Answers | Computer Science Quiz

Question 32.
An unbalanced dice (with 6 faces, numbered from 1 to 6) is thrown. The probability that the face value is odd is 90% of the probability that the face value is even. The probability of getting any even-numbered face is the same. If the probability that the face is even given that it is greater than 3 is 0.75, which one of the following options is closest to the probability that the face value exceeds 3?
(a) 0.453
(b) 0.468
(c) 0.485
(d) 0.492

Answer/Explanation

Answer:(b) 0.468
Explanation:
It is given that, p(odd) = 0.9p(even)
Now since, Σp(x) = 1
∴ p(odd) + p (even) = 1
⇒ 0.9 p (even) + p (even) = 1
⇒ p(even) = \(\frac { 1 }{ 1.9 }\) = 0.5263
Now, it is given that p (any even face) is same i.e. p(2) = p(4) = p(6)
Now since,
p(even) = p(2) or p(4) or p(6)
= p(2) + p(4) + p(6)
∴ p(2) = p(4) = p(6)
= \(\frac { 1 }{ 3 }\) p (even) = \(\frac { 1 }{ 3 }\) (0.5263) = 0.1754
It is given that
p(even | face > 3) = 0.75
⇒ \(\frac{p(\text { even } \cap \text { face }>3)}{p(\text { face }>3)}\) = 0.75
⇒ \(\frac{\mathrm{p}(\text { face }=4,6)}{\mathrm{p}(\text { face }>3)}\) = 0.75
⇒ p (face>3) = \(\frac{p(\text { face }=4,6)}{0.75}\)
= \(\frac{p(4)+p(6)}{0.75}\)
= \(\frac{0.1754+0.1754}{0.75}\)
= 0.4677 ≃ 0.468


Question 33.
Consider a company that assembles computers. The probability of a faulty assembly of any computer is p. The company, therefore, subjects each computer to a testing process. This testing process gives the correct result for any computer with a probability of q. What is the probability of a computer being declared faulty?
(a) pq+(1 – p) (1 – q)
(b) (1 – q)p
(e) (1 – p)q
(d) pq

Answer/Explanation

Answer:(a) pq+(1 – p) (1 – q)
Explanation:

Probability Questions and Answers Computer Science Quiz chapter 5 img 12

The tree diagram of probabilities is shown above. From above tree, by rule of total probability, p(declared faulty) = pq + (1 – p) (1 – q)


Question 34.
What is the probability that a divisor of 1099 is a multiple of 1096?
(a) \(\frac{1}{625}\)
(b) \(\frac{4}{625}\)
(c) \(\frac{12}{625}\)
(d) \(\frac{16}{625}\)

Answer/Explanation

Answer:(a) \(\frac{1}{625}\)
Explanation:
p(multiple of 1096 | divisor of 1099) = \(\frac{\mathrm{p}\left(\text { multiple of } 10^{96} \& \text { divisor of } 10^{99}\right)}{\mathrm{p}\left(\text { divisor of } 10^{99}\right)}\) = \(\frac{\mathrm{n}\left(\text { multiple of } 10^{96} \& \text { divisor of } 10^{99}\right)}{\mathrm{n}\left(\text { divisor of } 10^{99}\right)}\)
Since, 10 = 2 . 5
1099 = 299. 599
Any divisor of 1099 is of the form 2a . 5b where 0 ≤ a ≤ 99 and 0 ≤ b ≤ 99. The number of such divisors is given by (99+1) × (99 + 1) = 100 × 100.
So, no. of divisors of 10″ = 100 × 100.
Any number which is a multiple of 1096 as well as divisor of 1099 is of the form 2a. 5b where 96 ≤ a ≤ 99 and 96 ≤ b ≤ 99. The number of such combinations of 4 values of a and 4 values of b is 4 × 4 combinations, each of which will be a multiple of 1096 as well as a divisor of 1099.
∴ p(multiple of 1096 | divisor of 1099)
= \(\frac { 4 × 4 }{ 100 × 100 }\) = \(\frac { 1 }{ 625 }\)


Question 35.
If two fair coins are flipped and at least one of the outcomes is known to be ahead, what is the probability that both outcomes are heads?
(a) \(\frac{1}{3}\)
(b) \(\frac{1}{4}\)
(c) \(\frac{1}{2}\)
(d) \(\frac{2}{3}\)

Answer/Explanation

Answer:(a) \(\frac{1}{3}\)
Explanation:
Let A be the event of head in one coin. B be the event of head in second coin. The required probability is
P(A ∩ B | A ∪ B) = \(\frac { P{(A ∩ B) ∩ (A ∪ B)} }{ P(A ∪ B }\) = \(\frac { P(A ∩ B }{ P (A ∪ B)}\)
P( A ∩ B) = p(both coin heads) = p(H , H) = \(\frac { 1 }{ 4 }\)
P(A ∪ B) = p(at least one head)
p(HH, HT, TH) = \(\frac { 3 }{ 4 }\)
So required probability = \(\frac { 1/4 }{ 3/4 }\) = \(\frac { 1 }{ 3 }\)


Probability Questions and Answers | Computer Science Quiz

Question 36.
If the difference between the expectation of the square of a random variable (E [x2] and the square of the expectation of the random variable (E [x])2 is denoted by R, then
(a) R = 0
(b) R < 0 (c) R ≥ 0 (d) R > 0

Answer/Explanation

Answer:
(c) R ≥ 0
Explanation:
V(x) = E(x2) – [E(x)]2 = R
where V(x) is the variance of x,
Since variance is σ2x and hence never negative, R ≥ 0.


Question 37.
Consider the finite sequence of random values X = [x1, x2,…, xn]. Let µx be the mean and σx be the standard deviation of X. Let another finite sequence Y of equal length be derived from this as yi = a * xn + b, where a and b are positive constants. Let µy be the mean and σy be the standard deviation of this sequence. Which one of the following statements INCORRECT?
(a) Index position of the mode of X in X is the same as the index position of the mode of Y in Y.
(b) Index position of the median of X in X is the same as the index position of the median of Y in Y
(c) µy = aµx + b
(d) σy = aσx + b

Answer/Explanation

Answer:
(d) σy = aσx + b
Explanation:
Standard deviation is affected by scale but not by the shift of origin.
So, yi = axi + b
⇒ σy = aσx
if a could be negative then σy = | a | σx is more correct since standard deviation cannot be negative)
Clearly, σy = aσx + b is false
So (d) is incorrect.


Question 38.
A deck of 5 cards (each carrying a distinct number from 1 to 5) is shuffled thoroughly. Two cards are then removed one at a time from the deck. What is the probability that the two cards are selected with the number on the first card being one higher than the number on the second card?
(a) \(\frac { 1 }{ 5 }\)
(b) \(\frac { 4 }{ 25 }\)
(c) \(\frac { 1 }{ 4 }\)
(d) \(\frac { 2 }{ 5 }\)

Answer/Explanation

Answer:
(a) \(\frac { 1 }{ 5 }\)
Explanation:
The five cards are {1, 2, 3, 4, 5}
Sample space = 5 × 4 ordered pairs.
[Since there is a Ist card and IInd card we have to take ordered pairs]
p(Ist card = IInd card + 1)
= P{(2, 1), (3, 2), (4, 3), (5, 4)} = \(\frac { 4 }{ 5 × 4 }\) = \(\frac { 1 }{ 5 }\)


Question 39.
Consider a random variable X that takes values +1 and -1 with probability 0.5 each. The values of the cumulative distribution function F(x) at x = -1 and +1 are (a) 0 and 0.5
(b) 0 and 1
(c) 0.5 and 1
(d) 0.25 and 0.75

Answer/Explanation

Answer:
(c) 0.5 and 1
Explanation:
The p.d.t of the random variable is

Probability Questions and Answers Computer Science Quiz chapter 5 img 14

The cumulative distribution function F(x) is the probability up to x as given below:

Probability Questions and Answers Computer Science Quiz chapter 5 img 15

So the correct option is (c).


Probability Questions and Answers | Computer Science Quiz

Question 40.
Suppose a fair six-sided die is rolled once. If the value on the die is 1, 2, or 3 then the die is rolled a second time. What is the probability that the sum total of values that turn up is at least 6?
(a) \(\frac { 10 }{ 21 }\)
(b) \(\frac { 5 }{ 12 }\)
(c) \(\frac { 2 }{ 3 }\)
(d) \(\frac { 1 }{ 6 }\)

Answer/Explanation

Answer:(b) \(\frac { 5 }{ 12 }\)
Explanation:
If first throw is 1, 2 or 3 then sample space is only 18 possible ordered pairs. Out of this only (1, 5), (1, 6), (2, 4), (2, 5), (2, 6), (3, 3), (3, 4), (3, 5) and (3, 6) i.e. 9 out of 18 ordered pairs gives a Sum ≥ 6.
If first throw is 4, 5 or 6 then second throw is not made and therefore the only way Sum ≥ 6 is if the throw was 6. Which is one out of 3 possible. So the tree diagram becomes as follows:

Probability Questions and Answers Computer Science Quiz chapter 5 img 16

From above diagram
p(sum ≥ 6) = \(\frac { 1 }{ 2 }\) × \(\frac { 9 }{ 18 }\) + \(\frac { 1 }{ 2 }\) × \(\frac { 1 }{ 3 }\) = \(\frac { 15 }{ 36 }\) = \(\frac { 5 }{ 2 }\)


Question 41.
Suppose p is the number of cars per minute passing through a certain road junction between 5 PM, and p has Poisson distribution with a mean 3. What is the probability of observing fewer than 3 cars during any given minute in this interval?
(a) 8/(2e3)
(b) 9/(2e3)
(c) 17/(2e3)
(d) 26/(2e3)

Answer/Explanation

Answer:
(c) 17/(2e3)
Explanation:
Poisson formula for (P = x) given as \(\frac{\mathrm{e}^{-\lambda} \lambda^{\mathrm{x}}}{\mathrm{x} !}\)
α = 3 cars/minute
△T = 1 minute
So λ = α △ T = 3 × 1 = 3
Probability of observing fewer than 3 cars = P(X < 3) = P(X ≤ 2)
= P(X = 0) + P(X = 1) + P(X = 2)
= \(\frac{\mathrm{e}^{-3} 3^{0}}{0 !}\) + \(\frac{\mathrm{e}^{-3} 3^{1}}{1 !}\) + \(\frac{e^{-3} 3^{2}}{2 !}\) = \(\frac{17}{2 \mathrm{e}^{3}}\)
Option (c) is correct.


Question 42.
Suppose you break a stick of unit length at a point chosen uniformly at random. Then the expected length of the shorter stick
is___________ .

Answer/Explanation

Answer:
Explanation:
Suppose you break a stick of unit length at a point chosen uniformly at random, then let the length of the shorter stick = x
x has uniform distribution in the interval [0,1/2] i.e. a = 0 and p – 1/2
In uniform distribution, E(x) = (β + α)/2
So the expected length of the shorter stick = E(x) = (1/2 + 0)/2 = 1/4 = 0.25


Probability Questions and Answers | Computer Science Quiz

Question 43.
Four fair six-sided dice are rolled. The probability that the sum of the results being 22 is \(\frac { x }{ 1296 }\) The value of x is _________.

Answer/Explanation

Explanation:
Sample space = 64= 1296
6,6,6,4 ⇒ 4 ways (\(\frac { 4 ! }{ 3 !}\) = 4)
6,6,5,5 ⇒ 6 ways (\(\frac { 4 ! }{ 2!2!}\) = 6)
probability of sum to be 22 = \(\frac { 6 + 4 }{ 1296 }\) = \(\frac { x }{ 1296 }\)
⇒ x = 10</de


Question 44.
The security system at an IT office is composed of 10 computers of which exactly four are working. To check whether the system is functional, the officials inspect four of the computers picked at random (without replacement). The system is deemed functional if at least three of the four computers inspected are working. Let the probability that the system is deemed functional be denoted by p.
Then 100p = __________.

Answer/Explanation

Explanation:
The tree diagram for the problem is shown below.

Probability Questions and Answers Computer Science Quiz chapter 5 img 17

Required probability = \(\frac{{ }^{4} \mathrm{C}_{3} \cdot{ }^{6} \mathrm{C}_{1}}{{ }^{10} \mathrm{C}_{4}}\) + \(\frac{{ }^{4} \mathrm{C}_{3} \cdot{ }^{6} \mathrm{C}_{0}}{{ }^{10} \mathrm{C}_{4}}\) = \(\frac { 24 }{ 210}\)
+ \(\frac { 1 }{ 210 }\) = \(\frac { 25 }{ 210 }\)
p = 0.1190
⇒ 100 p = 11.90


Question 45.
The probability that a given positive integer lying between 1 and 100 (both inclusive) is NOT divisible by 2, 3 or 5 is _________.

Answer/Explanation

Explanation:
1 ≤ x ≤ 100
P(x is not divisible by 2, 3 or 5) = 1 – P(x is divisible by 2, 3 or 5)

Probability Questions and Answers Computer Science Quiz chapter 5 img 18


Question 46.
Let S be a sample space and two mutually exclusive events A and B be such that A ∪ B = S. If P(.) denotes the probability of the event, the maximum value of P(A) P(B) is ___________.

Answer/Explanation

Explanation:
It is given that A and B are mutually exclusive also it is given that A ∪ B = S which means that A and B are collectively exhaustive. Now if two events A and B are both mutually exclusive and collectively exhaustive, then P(A) + P(B) = 1 ⇒P(B) = 1-P(A)
Now we wish to maximize P(A) P(B) = P(A)(1-P(A))
Let, P(A) = x
Now P(A) (1 – P(A)) = x(1 – x) = x – x2
Say y = x- x2
\(\frac { dy }{ dx }\) = 1 – 2x = 0 ⇒ x = \(\frac { 1 }{ 2 }\)
= \(\frac { d^2y }{ dx^2 }\) = -2 < 0; (\(\frac { d^2y }{ dx^2 }\))x = \(\frac { 1 }{ 2 }\) = -2 < 0
y has maximum at x = \(\frac { 1 }{ 2 }\)
ymax = \(\frac { 1 }{ 2 }\) – (\(\frac { 1 }{ 2 }\))2 = 0.25


Question 47.
Suppose Xi for i = 1, 2, 3 are independent and identically distributed random variables whose probability mass functions are Pr[Xi = 0] = Pr[Xi = 1] = 1/2 for i = 1, 2, 3 Define another random variable Y=X1X2 ⊕ X3, where ⊕ denotes XOR. Then Pr[Y =0 |X3 = 0] =

Answer/Explanation

Explanation:
The p.d.t. for X1, X2, and X3 as given in the problem is shown below:

Probability Questions and Answers Computer Science Quiz chapter 5 img 19

Given, Y = X1X2 ⊕ X3
The required probability – p(Y = 0 | X3 = 0)
= \(\frac{p\left(Y=0 \cap X_{3}=0\right)}{p\left(X_{3}=0\right)}\) …..(1)
Now, p{X3 = 0) = \(\frac { 1 }{ 2 }\) (from p.d.t. of X3) …(2)
p(Y = 0 ∩ X3 = 0)
= p (X1X2 ⊕ X3 = 0 ∩ X3 = 0)
= P((X1X2 ⊕ 0 ) = 0 ∩ X3 = 0)
= p(X1X2 = 0 ∩ X3 = 0)
= p(X1 = 0, X2 = 0, X3 = 0) + p(X1 = 0, X2 = 1, X3 = 0) + p(X1 = 1, X2 = 0, X3 = 0) + P(X1 = 1, X2 = 0, X3 = 0)
= \(\frac { 1 }{ 2 }\) × \(\frac { 1 }{ 2 }\) × \(\frac { 1 }{ 2 }\) × \(\frac { 1 }{ 2 }\) × \(\frac { 1 }{ 2 }\) × \(\frac { 1 }{ 2 }\) × \(\frac { 1 }{ 2 }\) × \(\frac { 1 }{ 2 }\) × \(\frac { 1 }{ 2 }\) = \(\frac { 3 }{ 8 }\)
So, p(Y = 0 ∩ X3 = 0) = \(\frac { 3 }{ 8 }\) ….(3)
Now substituting (2) and (3) in (1), we get
The required probability = p(Y = 0|X3 = 0) = \(\frac { 3/8 }{ 1/2 }\) = \(\frac { 3 }{ 4 }\) = 0.75


Probability Questions and Answers | Computer Science Quiz

Question 48.
A probability density function on the interval [a, 1] is given by 1/x2 and outside this interval, the value of the function is zero. The value of a is ___________.

Answer/Explanation

Explanation:

Probability Questions and Answers Computer Science Quiz chapter 5 img 20


Question 49.
Consider the following experiment:
Step 1. Flip a fair coin twice.
Step 2. If the outcomes are (TAILS, HEADS) then output Yand stop.
Step 3. If the outcomes are either (HEADS, HEADS) or (HEADS, TAILS), then output Wand stop.
Step 4. If the outcomes are (TAILS, TAILS), then go to Step 1.
The probability that the output of the experiment is Y is __________(up to two decimal places)

Answer/Explanation

Explanation:

Probability Questions and Answers Computer Science Quiz chapter 5 img 21

The tree diagram for the problem is given above. The desired output is Y. Now by rule of total probability P(output = Y) = 0.5 × 0.5 + 0.5 × 0.5 × 0.5 × 0.5 +… Infinite geometric series with α = 0.5 × 0.5 and r = 0.5 × 0.5 So p (output = Y)
= \(\frac { 0.5 × 0.5 }{ 1 -0.5 × 0.5 }\) = \(\frac { 0.25 }{ 0.75 }\) = \(\frac { 1 }{ 3 }\) = 0.33 (upto 2 decimal places)


Question 50.
Suppose that a shop has an equal number of LED bulbs of two different types. The probability of an LED bulb lasting more than 100 hours given that it is of Type 1 is 0.7, and given that it is of Type 2 is 0.4. The probability that an LED bulb is chosen uniformly at random lasts more than 100 hours is ___________.

Answer/Explanation

Explanation:

Probability Questions and Answers Computer Science Quiz chapter 5 img 22

P(losts > 100 hr) = 0.5 × 0.7 + 0.5 × 0.4 = 0.35 + 0.2 = 0.55


Question 51.
Let X be a Gaussian random variable with mean 0 and variance σ2. Let Y = max (X, 0) where max (a, b) is the maximum of a and b. The median of Y is ___________.

Answer/Explanation

Explanation:
The Gaussian random variable is the same as the normal random variable.
So, the distribution of X is N(0, σ2)
For X, Median = Mean = Mode = 0 For Y = Max (X, 0)
Now half the data are below 0 and half the data above 0 for X. If we apply Y = Max(X, 0) now, all the negative values will become 0 and all the positive values will remain positive. So, the Median being positional average will not be affected and will remain at 0, since now half will be at 0 and a half will be positive. So, Median (Y) = 0.


Question 52.
P and Q are considering to apply for a job. The probability that P applies for the job is \(\frac { 1 }{ 4 }\) , the probability that P applies for the job given that Q applies for the job is \(\frac { 1 }{ 2 }\) , and the probability that Q applies for the job given that P applies for the job is \(\frac { 1 }{ 3 }\). Then the probability that P does 3 not apply for the job given that Q does not apply for the job is
(a) \(\frac { 4 }{ 5 }\)
(b) \(\frac { 5 }{ 6 }\)
(C) \(\frac { 7 }{ 8 }\)
(d) \(\frac { 11 }{ 12 }\)

Answer/Explanation

Answer:(a) \(\frac { 4 }{ 5 }\)
Explanation:
Given that,
p(P) = \(\frac { 1 }{ 4 }\) …..(1)
p(P | Q) = \(\frac { 1 }{ 2 }\) …..(2)
p(Q | p) = \(\frac { 1 }{ 3 }\) …..(3)
p(\(\bar{P}\) | \(\bar{Q}\) = ?
First solve for p(Q) and p (P ∩ Q) from equation (2) and (3) as follows:
From equation (2)
p(P | Q) = \(\frac { p(P ∩ Q) }{ P(Q) }\) = \(\frac { 1 }{ 2 }\) …(4)
From equation (3)
p(Q | P) = \(\frac { p(P ∩ Q) }{ P(P) }\) = \(\frac { 1 }{ 3 }\)
⇒ p(P ∩ Q) = \(\frac { 1 }{ 3 }\) × p(P) = \(\frac { 1 }{ 3 }\) × \(\frac { 1 }{ 4 }\) = \(\frac { 1 }{ 12 }\)
Now substitute in equation (4) and get
P(Q) = \(\frac { p(P ∩ Q) }{ 1/2 }\) = \(\frac { 1/12 }{ 1/2 }\) = \(\frac { 2 }{ 12 }\) = \(\frac { 1 }{ 6 }\)
So now we have p(P) = \(\frac { 1 }{ 4 }\)
p(Q) = \(\frac { 1 }{ 6 }\)
and p(P ∩ Q) = \(\frac { 1 }{ 12 }\) we need to find
p(\(\bar{P}\) | \(\bar{Q}\) = \(\frac{p(\bar{P} \cap \bar{Q})}{p(\bar{Q})}\)
= \(\frac{1-(P \cup Q)}{1-p(Q)}\) = 1 – \(\frac{[p(P)+p(Q)-p(P \cap Q)]}{1-p(Q)}\)
= \(\frac{1-\left[\frac{1}{4}+\frac{1}{6}-\frac{1}{12}\right]}{1-\frac{1}{6}}\) = \(\frac{\frac{2}{3}}{\frac{5}{6}}\) = \(\frac { 4 }{ 5 }\)
So, p(\(\bar{P}\) | \(\bar{Q}\) = \(\frac { 4 }{ 5 }\)


Probability Questions and Answers | Computer Science Quiz

Question 53.
For any discrete random variable X, with probability mass function P(X = j) = pi, pj ≥ 0, j∈ {0,…, N}, and \(\sum_{j=0}^{N}\) pj = 1, define the polynomial function gx(z) = \(\sum_{j=0}^{N}\) PjZj For a certain discrete random variable Y, there exists a scalar β ∈ [0,1] such that gy (z) = (1- β + βz)N. The expectation of F is
(a) Nβ (1 – β)
(b) Nβ
(c) N (1 – β)
(d) Not expressible in terms of N and β alone

Answer/Explanation

Answer:(b) Nβ
Explanation:
gy(z) = ((1 – β) + βz)N
If gy(z) is expanded, we would get a bionomial distribution with n = N and p = β So the E(Y) = np = Nβ


Question 54.
If a random variable X has a Poisson distribution with mean 5, then the expectation E[(X + 2)2] equals __________.

Answer/Explanation

Explanation:
Given, Poisson distribution λ = 5 We know that in Poisson distribution E (X) = V(X) = λ
So here E(X) = V(X) = 5 Now, we need E[(X + 2)2]
= E(X2 +4X + 4)
= E(X2) + 4E(X) + 4
To find E(X2) we write, V(X) = E(X2) – (E(X))2
5 = E(X2) – 52 So, E(X2) = 52 + 5 = 30
Required value = 30+ 4 × 5 + 4 = 54


Question 55.
Two people, P, and Q, decide to independently roll two identical dice, each with 6 faces, numbered 1 to 6. The person with the lower number wins. In case of a tie, they roll the dice repeatedly until there is no tie. Define a trial as a throw of the dice by P and Q. Assume that all 6 numbers on each dice are equiprobable and that all trials are independent. The probability (rounded to 3 decimal places) that one of them wins on the third trial is ___________.

Answer/Explanation

Explanation:
P(one of them wins in 3rd trial)
= P(Ist trial is Tie) × P(IInd trial is Tie) × P(one of them wins 3rd trial)
P(Tie in any trial) = P(P = 1 and Q = 1) + P(P = 2 and Q = 2) + …. + P(P = 6 and Q = 6)
= \(\frac { 1 }{ 36 }\) + \(\frac { 1 }{ 36 }\) + \(\frac { 1 }{ 36 }\) + \(\frac { 1 }{ 36 }\) + \(\frac { 1 }{ 36 }\) +\(\frac { 1 }{ 36 }\) = \(\frac { 1 }{ 36 }\) = \(\frac { 1 }{ 6 }\)
P(one of them wins) = 1 = p(Tie) = 1 – \(\frac { 1 }{ 6 }\) = \(\frac { 5 }{ 6 }\)
So required probability = \(\frac { 1 }{ 6 }\) × \(\frac { 1 }{ 6 }\) × \(\frac { 5 }{ 6 }\) = \(\frac { 5 }{ 216 }\) = 0.023
(rounded to 3 decimal places)


Probability Questions and Answers | Computer Science Quiz

Question 56.
Consider Guwahati (G) and Delhi (D) whose temperatures can be classified as high (H), medium (M), and low (L). Let P(HG) denote the probability that Guwahati has a high temperature. Similarly, P(MG) and P(LG) denotes the probability of Guwahati having medium and low temperatures respectively. Similarly, we use P(HD), P(MD), and P(LD) for Delhi. The following table gives the conditional probabilities for Delhi’s temperature given Guwahati’s temperature.

HD MD LD
HG 0.40 0.48 0.12
MG 0.10 0.65 0.25
LG 0.01 0.50 0.49

Consider the first row in the table above. The first entry denotes that if Guwahati has high temperature (HG) then the probability of Delhi also having a high temperature (HD) is 0.40; i.e., P(HD | HG) = 0.40. Similarly, the next two entries are P(MD\HG) = 0.48 and P(LD | HG) = 0.12. Similarly for the other rows.
If it is known that P(HG) = 0.2, P(MG) = 0.5 and P(LG) = 0.3, then the probability (correct to two decimal places) that Guwahati has high temperature given that Delhi has high temperature is .

Answer/Explanation

Explanation:
The condition probability table given is

HD MD LD
HG 0.40 0.48 0.12
MG 0.10 0.65 0.25
LG 0.01 0.50 0.49

P(HG) = 0.2, P(MG) = 0.5, P(LG) = 0.3 Drawing the tree diagram for HD we get,

Probability Questions and Answers Computer Science Quiz chapter 5 img 23

From diagram, P(HG ∩ HD) = 0.2 × 0.4
P(HD) = 0.2 × 0.4+ 0.5 × 0.1 + 0.3 × 0.01 = 0.133 Required probability,
P(HG | HD) = \(\frac { 0.2 × 0.4 }{ 0.133 }\) = 0.60 (rounding upto 2 decimal place)


Question 57.
Two numbers are chosen independently and uniformly at random from the set {1, 2, …, 13}. The probability (rounded off to 3 decimal places) that their 4-bit (unsigned) binary representations have the same most significant bit is ____________.

Answer/Explanation

Explanation:

Probability Questions and Answers Computer Science Quiz chapter 5 img 24

p(2 elements out of 13 elements chosen randomly and independently) = (Number of MSB‘0’ × Number of MSB‘0’ + Number of MSB‘1’ × Number of MSB‘1’) / (Total × Total) = \(\frac{7 \times 7+6 \times 6}{13 \times 13}\) = \(\frac{49+36}{169}\) = \(\frac{85}{169}\) = 0.503


Question 58.
Suppose Y is distributed uniformly in the open interval (1,6). The probability that the polynomial 3x2 + 6xY+ 3Y+ 6 has only real roots is (rounded off to 1 decimal place) __________.

Answer/Explanation

Explanation:
polynomial 3x2 + 6xY + 3Y + 6 has only real roots
b2 – 4ax ≥ 0
(6Y)2 – 4(3) (3Y + 6) ≥ 0
Y2 – Y + 2 ≥ 0
Y ∈ (-∞, – 1] ∩ [2, ∞)
⇒ Y ∈ [2 , 6)
Since y is uniformly distributed in (1, 6) probability distributed function f(Y) = \(\frac { 1 }{ 5 }\) 1 p(2 ≤ y < 6) = \(\int_{2}^{6}\)f(Y)dy = \(\frac { 1 }{ 5 }\) \([Y]_{2}^{6}\) = \(\frac { 4 }{ 5 }\) = 0.8


Question 59.
For n > 2, let a e {0,1}n be a non-zero vector. Suppose that x is chosen uniformly at random from {0, 1}n. Then, the probability that \(\sum_{i=1}^{n}\)aixian odd number is _________.

Answer/Explanation

Explanation:

Probability Questions and Answers Computer Science Quiz chapter 5 img 25

Fixed non-Zero
ai = 0 or 1
xi = 0 or 1
\(\sum_{i=1}^{n} a_{i} x_{i}\) value lies between 0 to n.
Total number cases = 2n

Aixi 0 1 2 …………… N
fav nC0 nC1 nC2 …………… nCn

Probability Questions and Answers Computer Science Quiz chapter 5 img 26


Question 60.
Consider the two statements:
S1: There exist random variables X and Y such that(E[X-E(X)) (Y-E(Y))]2)>Var[X] Var[Y])
S2 : For all random variables X and Y Cov[X, Y] = E[| X-E[X] || Y-E[Y] |] Which one of the following choices is correct?
(a) Both S1 and S2 are false.
(b) Both S1 and S2 are true.
(c) S1 is true, but S2 is false.
(d) S1 is false, but S2 is true.

Answer/Explanation

Answer:
(a) Both S1 and S2 are false.
Explanation:
S2 : Cov(x,y) = E{|x – \(\bar{x}\)||y – \(\bar{y}\)|} is false
Case-I: If x > \(\bar{x}\) and y > \(\bar{y}\) then above is true.
Case-II: If x < \(\bar{x}\) and y < \(\bar{y}\) then above is true. Case-III: If x > \(\bar{x}\) but y < \(\bar{y}\) then above is false.
Case-IV: If x < \(\bar{x}\) but y > \(\bar{y}\) then above is false.
∵ Given expression is not always true. So we can conclude that it is false.
S1: It is obviously false,
∵ True statement is
[E{(x – \(\bar{x}\))(y – \(\bar{y}\))}]2 < var(x) . Var(y)
So both S1 and S2 are false.


Question 61.
The lifetime of a component of a certain type is a random variable whose probability density function is exponentially distributed with parameter 2. For a randomly picked component of this type, the probability that its lifetime exceeds the expected lifetime (rounded to 2 decimal places) is __________.

Answer/Explanation

Explanation:
Let, t = {lifetime of component} and μ = 2
Expected lifetime = \(\frac { 1 }{ μ }\)

Probability Questions and Answers Computer Science Quiz chapter 5 img 28
Question 62.
A sender (S) transmits a signal, which can be one of the two kinds: H and L with probabilities 0.1 and 0.9 respectively, to a receiver (R). In the graph below, the weight of edge (u, v) is the probability of receiving v when u is transmitted, where u,v ∈ {H, L}. For example, the probability that the received signal is L given the transmitted signal was H, is 0.7.

Probability Questions and Answers Computer Science Quiz chapter 5 img 29

If the received signal is H, the probability that the transmitted signal was H (rounded to 2 decimal places) is .
Answer:
Explanation:

Probability Questions and Answers Computer Science Quiz chapter 5 img 30


Probability Questions and Answers | Computer Science Quiz

Question 63.
For a given biased coin, the probability that the outcome of a toss is ahead is 0.4. This coin is tossed 1,000 times. Let X denote the random variable whose value is the number of times that head appeared in these 1,000 tosses. The standard deviation of X (rounded to 2 decimal places) is ___________.

Answer/Explanation

Explanation:
n = 1000, p = 0.4, q = 0.6
It is a binomially distributed random variable.
So, S.D. = \(\sqrt{n p q}\)
= \(\sqrt{1000 \times 0.4 \times 0.6}\) = \(\sqrt{240}\) = 15.49


Question 64.
In an examination, a student can choose the order in which two questions (QuesA and QuesB) must be attempted.

  • If the first question is answered wrong, the student gets zero marks.
  • If the first question is answered correctly and the second question is not answered correctly, the student gets the marks only for the first question.
  • If both the questions are answered correctly, the student gets the sum of the marks of the two questions.

The following table shows the probability of correctly answering a question and the marks of the question respectively.

Question Probability of answering correctly Marks
QuesA 0.8 10
QuesB 0.5 20

Assuming that the student always wants to maximize her expected marks in the examination, in which order should she attempt the questions, and what are the expected marks for that order (assume that the questions are independent)?
(a) First QuesA and then QuesB. Expected marks 14.
(b) First QuesB and then QuesA. Expected marks 22.
(c) First QuesB and then QuesA. Expected marks 14.
(d) First QuesA and then QuesB. Expected marks 16.

Answer/Explanation

Answer:
(d) First QuesA and then QuesB. Expected marks 16.
Explanation:
X → Random variable which represents total marks record.
P(X) → Probability of getting those marks.

X → 0 10 20 30
P(x) → 0.2 × 0.5 0.8 × 0.5 0.5 × 0.2 0.8 × 0.5
11 11 11 11
0.1 0.4 0.1 0.4
ΣP(x) = 1

Now, if QuestionA is attempted first and it is correct.
Case-I:
E(x) = Σ(x) . P(x)
= 0.4 × 10 + 0.4 × 30 = 4 + 12 = 16
Case-II:
If QuestionB is attempted first and is correct.
E(x) – Σ(x) . P(x)
= 0.1 (20) + 0.4 (30)
= 2 + 12 = 14

So case-I is giving maximum expected marks. Hence option (d) is correct.


Question 65.
A bag has r red balls and b black balls. All balls are identical except for their colors. In a trial, a ball is randomly drawn from the bag, its color is noted and the ball is placed back into the bag along with another ball of the same color. Note that the number of balls in the bag will increase by one, after the trial. A sequence of four such trials is conducted. Which one of the following choices gives the probability of drawing a red ball in the fourth trial?

Probability Questions and Answers Computer Science Quiz chapter 5 img 32

Answer/Explanation

Answer:
Explanation:
There are 10 favorable ways to calculate the probability of red ball in 4th trial.
(RFR)R = R or (BRR)R ≈ 1 way or (RRR)R ≈ 3 ways or (BBR)R ≈ 3 ways

Probability Questions and Answers Computer Science Quiz chapter 5 img 31


Graph Theory Questions and Answers | Computer Science Quiz

Computer Science Graph Theory MCQ Quiz Questions and Answers PDF Download

Computer Science Graph Theory Questions and Answers
Question 1.
Which of the following graphs is/are planar? (see Figure)

Computer Science Graph Theory Questions and Answers chapter 4 img 1

(a) G1 only
(b) G1 and G2
(c) G2 only
(d) G2 and G3

Answer/Explanation

Answer: (c) G2 only
Explanation:

Computer Science Graph Theory Questions and Answers chapter 4 img 2

G1 is k3, 3 which is a well-known non-planar graph.

Computer Science Graph Theory Questions and Answers chapter 4 img 3

Graph G2 is isomorphic to the following graph:

Computer Science Graph Theory Questions and Answers chapter 4 img 4

The above graph is planar. So G2 is planar.

Computer Science Graph Theory Questions and Answers chapter 4 img 5

G3 is isomorphic to K3, 3 which is well known non-planar graph. Therefore, G3 is a non-planar graph.


Question 2.
A graph is planar if and only if,
(a) If does not contain subgraphs homeomorphic to K5 and K3, 3.
(b) It does not contain subgraphs isomorphic to K5 or K3, 3.
(c) It does not contain subgraphs isomorphic to K5 and K3, 3.
(d) It does not contain subgraph homeomorphic to K5 or K3, 3.

Answer/Explanation

Answer:(d) It does not contain subgraph homeomorphic to K5 or K3, 3.
Explanation:
Kuratowski’s theorem: A graph is planar if and only if, it does not contain a subgraph homeomorphic to K5 or K3, 3.


Question 3.
The maximum number of possible edges in an undirected graph with ‘a’ vertices and ‘k’ components is ________.

Answer/Explanation

Explanation:
The maximum number of possible edges in an undirected graph with “a” vertices and “k” components is \(\frac{(a-k+1)(a-k)}{2}\)


Question 4.
A non-planar graph with a minimum number of vertices has
(a) 9 edges, 6 vertices
(b) 6 edges, 4 vertices
(c) 10 edges, 5 vertices
(d) 9 edges, 5 vertices

Answer/Explanation

Answer:(c) 10 edges, 5 vertices
Explanation:
K5 is the smallest non-planar graph in terms of the number of vertices. The number of vertices in K5 is 5 and number of edges in K5 is \(\frac{5 \times 4}{2}\) = 10


Question 5.
The maximum number of edges in a planar graph with n vertices is ________.

Answer/Explanation

Explanation:
The maximum number of edges in a connected, planar, simple graph with n vertices is 3n – 6.


Question 6.
The number of distinct simple graphs with up to three nodes is
(a) 15
(b) 10
(c) 7
(d) 9

Answer/Explanation

Answer:(c) 7
Explanation:
Assume that the vertices are unlabelled. Number of distinct simple graphs with 1 node = 1

Computer Science Graph Theory Questions and Answers chapter 4 img 6

Therefore, total number of distinct simple graphs up to three nodes = 1 + 2 + 4 = 7.

Computer Science Graph Theory Questions and Answers


Question 7.
Prove that in a finite graph, the number of vertices of odd degrees is always even.

Answer/Explanation

Explanation:
According to the Handshaking theorem, for a graph G = (V, E) with n vertices and e edges then

Computer Science Graph Theory Questions and Answers chapter 4 img 7

Let Ve and V0 respectively the set of vertices of even degree and the set of vertices of odd degree in an undirected graph G = (V, E) then

Computer Science Graph Theory Questions and Answers chapter 4 img 8

Since deg(v) is even for v∈Ve, the first sum on the right-hand side of the equality is even. The total sum must be 2e, which is even, so the second sum must be even too. But all of its terms are odd so there must be an even number of them.


Question 8.
Let G be an undirected connected graph with distinct edge weights. Let emax be the edge with maximum weight and emin be the edge with minimum weight. Which of the following statements is false?
(a) Every minimum spanning tree of G must contain emin
(b) If emax is in a minimum spanning tree, then its removal must disconnect G
(c) No minimum spanning tree contains emax
(d) G has a unique minimum spanning tree

Answer/Explanation

Answer:(c) No minimum spanning tree contains emax
Explanation:
(a) All the edge weights are distinct, so every minimum spanning tree of G must contain emin (Kruskal’s algorithm will pick emin first)
(b) If emax is in a minimum spanning tree, then surely its removal must disconnect G (i.e. emax must be a cut edge).
(c) A minimum spanning tree can contain emax if its removal disconnects G (i.e. it is a cut edge). So this option is false.
For example, in the graph given below, the edge cd is a maximum weight edge but still is present in the minimum spanning tree.

Computer Science Graph Theory Questions and Answers chapter 4 img 9

(d) Since all edge weights are distinct G has a unique minimum spanning tree.


Question 9.
How many undirected graphs (not necessarily connected) can be constructed out of a given set V = {v1, v2, ……. vn} of n vertices?
(a) \(\frac{\mathrm{n}(\mathrm{n}-1)}{2}\)
(b) 2n
(c) n!
(d) 2 \(\frac{\mathrm{n}(\mathrm{n}-1)}{2}\)

Answer/Explanation

Answer:(d) 2 \(\frac{\mathrm{n}(\mathrm{n}-1)}{2}\)
Explanation:
In a graph G with n vertices, maximum number of edges possible = \(\frac{n(n-1)}{2}\)
There are two ways for a edge, (the edge may appear in graph or may absent in graph). So there are two options for each edge.
Total number of graphs with n vertices = 2\(\frac{n(n-1)}{2}\)


Question 10.
Maximum number of edges in a n-node undirected graph without self loops is
(a) n2
(b) n(n – 1)/2
(c) n – 1
(d) (n + 1) (n)/2

Answer/Explanation

Answer:(b) n(n – 1)/2
Explanation:
The graph containing a maximum number of edges in an n-node undirected graph without self-loops is a complete graph. The number of edges incomplete graph with n-node, kn is \(\frac{n(n-1)}{2}\).

Computer Science Graph Theory Questions and Answers


Question 11.
Let G be an arbitrary graph with n nodes and k components. If a vertex is removed from G, the number of components in the resultant graph must necessarily lie between.
(a) k and n
(b) k – 1 and k + 1
(c) k – 1 and n – 1
(d) k + 1 and n – k

Answer/Explanation

Answer:(c) k – 1 and n – 1
Explanation:
Maximum components will result after the removal of a node if graph G is a star graph as shown below.

Computer Science Graph Theory Questions and Answers chapter 4 img 10

or a null graph of n vertices as shown below:

Computer Science Graph Theory Questions and Answers chapter 4 img 11

In either case, if node v is removed, the number of components will be n – 1, where n is the total number of nodes in the star graph.
∴ n – 1 is the maximum number of components possible. Minimum components will result if the node being removed is alone vertex in which case, the number of components will be k – 1.
∴ The number of components must necessarily lie between k – 1 and n – 1.


Question 12.
How many perfect matchings are there in a complete graph of 6 vertices?
(a) 15
(b) 24
(c) 30
(d) 60

Answer/Explanation

Answer:(a) 15
Explanation:
The number of perfect matchings in a complete graph of n vertices, where n is even, reduces to the problem of finding unordered partitions of the vertex set of the type p(2n; 2, 2,2,… n times) = \(\frac{(2 n) !}{(2 !)^{n} n !}\)
For n = 3, 2n = 6, i.e. complete graph k6, we have
Number of perfect matchings = \(\frac{6 !}{(2 !)^{3} 3 !}\)
=\(\frac{6 \times 5 \times 4 \times 3 \times 2 \times 1}{2 \times 2 \times 2 \times 6}\) = 15


Question 13.
A Graph G = (V, E) satisfies | E | ≤ 3 |V| – 6. The min-degree of G is defined as min {degree (v)}. Therefore, min-degree of G cannot be
(a) 3
(b) 4
(c) 5
(d) 6

Answer/Explanation

Answer:
(d) 6
Explanation:
Given |E| < 3 | V| — 6 …(i)
Let δ be the minimum degree of the graph. Now δ cannot exceed the average degree of the graph.
so, \(\delta \leq \frac{2|\mathrm{E}|}{|\mathrm{V}|}\)
Substitute eq. (i) in eq. (ii) and get
\(\delta \leq \frac{2}{|\mathrm{~V}|}\)(3|V|-6)
⇒ δ ≤ 6 – \(\frac{12}{|\mathrm{~V}|}\)
Clearly the minimum degree has to be less than 6 always and hence cannot be equal to 6.


Question 14.
The minimum number of colors required to color the following graph, such that no two adjacent vertices are assigned the same color, is

Computer Science Graph Theory Questions and Answers chapter 4 img 12

(a) 2
(b) 3
(c) 4
(d) 5

Answer/Explanation

Answer:
(c) 4
Explanation:
An assignment of the colors 1, 2, 3, and 4 to the vertices of the graph is shown below such that the graph is properly colored.

Computer Science Graph Theory Questions and Answers chapter 4 img 13

So 4 colors are required.
(Note: The graph is a planar graph. The four-color theorem says that the chromatic number of a planar graph is at most = 4).


Question 15.
How many graphs on n labeled vertices exist which have at least (n2 – 3n)/2 edges?

Computer Science Graph Theory Questions and Answers chapter 4 img 14

Answer/Explanation

Answer:
Computer Science Graph Theory Questions and Answers chapter 4 img 15
Explanation:
Take number of edges available in n labelled vertices is
nc2 = \(\frac{n(n-1)}{2}\) = \(\frac{\mathrm{n}^{2}-\mathrm{n}}{2}\) edges
Now from this we need to choose \(\frac{\mathrm{n}^{2}-\mathrm{3n}}{2}\) edges
or more upto a maximum of \(\frac{\mathrm{n}^{2}-\mathrm{n}}{2}\) edges. Each such choice of edges represents a distinct graph on n labelled vertices.
Total number of such graphs

Computer Science Graph Theory Questions and Answers chapter 4 img 16

Computer Science Graph Theory Questions and Answers


Question 16.
What is the maximum number of edges in an acyclic undirected graph with n vertices?
(a) n – 1
(b) n
(c) n + 1
(d) 2n – 1

Answer/Explanation

Answer:
(a) n – 1
Explanation:
Acyclic graphs are graphs that do not contain cycles. For a maximum number of edges, each vertex connects to another vertex only if it does not form a cycle i.e. from a tree with n vertices, which has maximum n – 1 edge. Ex. with 4 vertices, 3 edges maximum.

Computer Science Graph Theory Questions and Answers chapter 4 img 17


Question 17.
What is the number of vertices in an undirected connected graph with 27 edges, 6 vertices of degree 2, 3 vertices of degree 4, and the remaining of degree 3?
(a) 10
(b) 11
(c) 18
(d) 19

Answer/Explanation

Answer:
(d) 19
Explanation:
Sum of degree of all vertices = 2e (using Handshaking lemma)
So, 6 × 2 + 3 × 4 + x × 3 = 2 × 27
12 + 12 +3x = 54
3x = 54 – 24
x = \(\frac { 30 }{ 3 }\)
x = 10
So, total number of vertices
⇒ x + 6 + 3 = 10 + 6 + 3 = 19


Question 18.
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) 0
(b) 8
(c) 9
(d) 13

Answer/Explanation

Answer:
(b) 8
Explanation:
Given V = 13, E = 19
Let R be the number of regions.
R =E – V + 2
⇒ R = 19 -13 +2
= 8


Question 19.
Which one of the following graphs is NOT planner?

Computer Science Graph Theory Questions and Answers chapter 4 img 18

Answer/Explanation

Explanation:
G1 is the same as K3, 3 which is known to be non-planar. G2, G3, and G4 can be redrawn as follows so that they are planar.

Computer Science Graph Theory Questions and Answers chapter 4 img 19


Question 20.
If all the edge weights of an undirected graph are positive, then any subset of edges that connects all the vertices and has minimum total weight is a
(a) Hamiltonian cycle
(b) Grid
(c) Hypercube
(d) Tree

Answer/Explanation

Answer:
(d) Tree
Explanation:
If the subset of edges connects all the vertices and it has minimum total weight then it never forms a cycle. So it is called a tree.

Computer Science Graph Theory Questions and Answers


Question 21.
Consider the undirected graph G defined as follows. The vertices of G are bit strings of length n. We have an edge between vertex u and vertex v if and only if u and v differ in exactly one-bit position (in other words, v can be obtained from u by flipping a single bit). The ratio of the chromatic number of G to the diameter of G is
(a) 1/(2n – 1)
(b) 1/n
(c) 2/n
(d) 3/n

Common Data for Q.4.22 & Q.4.24
The 2n vertices of graph G correspond 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.

Answer/Explanation

Answer:
(c) 2/n
Explanation:
The hamming distance relation on bit strings has a digraph which will be always an n-cube where n is the number of bits.
An achromatic number of n-cube = 2 (since n-cube is always bipartite). Also the diameter of n- cube = n. So the ratio of a chromatic number to the diameter of the n-cube = 2/n.


Question 22.
The number of vertices of degree zero in G is
(a) 1
(b) n
(c) n + 1
(d) 2n

Answer/Explanation

Answer:
(c) n + 1
Explanation:
Let S contains n elements then S have 2n subsets. Graph G contains 2n vertices.
Let S = {v1; v2,…, vn}. Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements.
So |{Vi} ∩ {Vj}| =2
For this to happen, the subset must have at least 2 elements. There are n sets that contain a single element for V1 to Vn who doesn’t intersect another set such that it contains two elements. Therefore the degree of all these n vertices is zero. G also contains a vertex Φ whose degree is zero. So the number of vertices whose degree is zero is n + 1.


Question 23.
The maximum degree of a vertex in G is
(a) \(\left(\begin{array}{c}
\mathrm{n} / 2 \\
2
\end{array}\right)\) 2n/2
(b) 2n – 2
(c) 2n – 3 × 3
(d) 2n – 1

Answer/Explanation

Answer:
(c) 2n – 3 × 3
Explanation:
Let the set be S = {1, 2, 3, 4, …, n}
Consider a subset containing 2 elements of the form {1, 2}. Now {1, 2} will be adjacent to any subset with which it has exactly 2 elements in common. These sets can be formed by adding zero or more elements from the remaining n – 2 elements, to the set {1, 2}. Since each of these elements may be either added or not added, the number of ways of making such sets containing 1 and 2 is 2n – 2.

∴ Vertices with 2 elements will have 2n – 2 degrees.

Now consider subsets of 3 elements say {1, 2, 3}. Since we want exactly 2 elements in common, we choose these in 3C2 ways, and then we can add or not add the remaining n-3 elements. This can be done in 2n – 3 ways.

∴ A total number of subsets with at least 2 elements common with {1, 2, 3} is given by 3C2 × 2n – 3.

Similarly, we can argue that the number of degrees of 4 element subsets is 4C2 × 2n – 4 and for 5 element subsets is 5C2 × 2n – 5, and so on.

Out of these 2n – 2 = 2 . 2n – 3 is less than 3C2 × 2n – 3 = 3 × 2n – 3.

Then 3C2 × 2n – 3 = 3 × 2n – 3 is same as 4C2 × 2n – 4 = 6 × 2n – 4 = 3 × 2n – 3 and 4C2 × 2n – 4 = 3 × 2n – 3 is greater than 5C2 × 2n – 5 = 10 × 2n – 5 = 2.5 × 2n – 3 maximum degree in this graph is occurring for 3 element and 4 element subsets both of which have 3 × 2n – 3 degree.


Question 24.
The number of connected components in G is
(a) n
(b) n + 2
(c) 2n/2
(d) 2n/n

Answer/Explanation

Answer:
(b) n + 2
Explanation:
The number of the connected components of G is determined by the degree and edges of vertices there are n + 1 vertices whose degree is zero, so they can form n + 1 connected component. The remaining vertices of graph G are all connected as a single component. So the total number of the connected components is n + 2.


Question 25.
Let G be the non-planar graph with the minimum possible number of edges. Then G has
(a) 9 edges and 5 vertices
(b) 9 edges and 6 vertices
(c) 10 edges and 5 vertices
(d) 10 edges and 6 vertices

Answer/Explanation

Answer:
(b) 9 edges and 6 vertices
Explanation:
K5 and K3,3 are the smallest nonplanar graphs. K5 has 5 vertices and 5C2 = 10 edges and K3,3 has 6 vertices and 3 × 3 = 9 edges. So, the non-planar graph with the minimum number of edges is K3,3 with 9 edges and 6 vertices.
Note: K5 is the non-planar graph with a minimum number of vertices.

Computer Science Graph Theory Questions and Answers


Question 26.
Consider the DAG with V = {1, 2, 3, 4, 5, 6}, shown below:

Computer Science Graph Theory Questions and Answers chapter 4 img 20

Which of the following is NOT a topological ordering?
(a) 123456
(b) 132465
(c) 1 3 2 4 5 6
(d) 3 2 4 1 6 5

Answer/Explanation

Answer:
(d) 3 2 4 1 6 5
Explanation:
In topological sorting the partial ordering of the DAG must be preserved i.e. if a ≤ b is in the DAG, then in the topological order, b must come after a, not before. Consider the ordering 3 2 4 16 5. 1 ≤ 4 in the given DAG but 4 is coming before 1 in 3 2 4 1 6 5 order which means that 3 2 416 5 is not a topological order of the given DAG.


Question 27.
Which of the following graphs has an Eulerian circuit?
(a) Any k-regular graph where k is an even number
(b) A complete graph on 90 vertices
(c) The complement of a cycle on 25 vertices
(d) None of the above

Answer/Explanation

Answer:
(c) The complement of a cycle on 25 vertices
Explanation:
Whenever in a graph all vertices have even degrees, it will surely have an Euler circuit.
(a) Since in a k-regular graph, every vertex has exactly k degrees and if k is even, every vertex in the graph has even degrees, k- regular graph need not be connected, hence k-regular may not contain Euler circuit.
(b) Complete graph on 90 vertices does not contain an Euler circuit, because every vertex degree is odd (89)
(c) C25 has 24 edges and each vertex has exactly 2 degrees. So every vertex in the complement of C25 will have 24 – 2 = 22 degrees which is an even number.
Since every vertex in the complement of C25 has even degrees. Also, the complements of all Cn with n ≥ 5 are connected. So, it is an Euler graph.


Question 28.
What is the size of the smallest MIS (Maximal Independent Set) of a chain of nine nodes?
(a) 5
(b) 4
(c) 3
(d) 2

Answer/Explanation

Answer:
(b) 4
Explanation:

Computer Science Graph Theory Questions and Answers chapter 4 img 21

Maximum independent sets:
{a, c, e, g, i} and {b, d, f, h}.
Smallest maximum independent set {b, d, f, h}. Size = 4

Computer Science Graph Theory Questions and Answers


Question 29.
What is the chromatic number of the following graph?

Computer Science Graph Theory Questions and Answers chapter 4 img 22

(a) 2
(b) 3
(c) 4
(d) 5

Answer/Explanation

Answer:
(b) 3
Explanation:
Since there is a 5-cycle (odd cycle) in this graph, this graph is not bipartite and hence its chromatic number is at least 3. A proper coloring with 3 colors, is shown below:

Computer Science Graph Theory Questions and Answers chapter 4 img 23

Hence a minimum number of colors needed to color the given graph is equal to 3.


Question 30.
G is a simple, connected, undirected graph. Some vertices of G are of odd degrees. Add a node v to G and make it adjacent to each odd degree vertex of G. The resultant graph is sure to be
(a) Regular
(b) Complete
(c) Hamiltonian
(d) Euler

Answer/Explanation

Answer:
(d) Euler
Explanation:
In an undirected simple, connected graph number of vertices must be even of odd degree (using Handshaking lemma). Adding a vertex v, adjacent to all odd degree vertices in the graph, so the degree of all odd degree vertices now become even and the degree of vertex v is also even (since the number of odd degrees vertex are even). Now all vertices in the graph are of even degree and the graph is connected, so it must be a Eular graph.


Question 31.
What is the chromatic number of an n-vertex simple connected graph which does not contain any odd-length cycle? Assume n ≥ 2.
(a) 2
(b) 3
(c) n – 1
(d) n

Answer/Explanation

Answer:
(a) 2
Explanation:
If an n-vertex simple connected graph contains no cycles of odd length, then its chromatic number is two since the vertices can be alternately colored with the first color, then the second color, then the first color, and then the second color, and so on.
Alternatively, since a simple connected graph with no cycles of odd length must be bipartite, and since the chromatic number of a non-null bipartite graph is always 2 (in a bipartite graph each partition requires one color (there are no edges within a partition of a bipartite graph) and there are only two partitions).
Note: Since it is given that the graph is connected, it cannot be a null graph (Φn)

Computer Science Graph Theory Questions and Answers


Question 32.
Which one of the following is TRUE for any simple connected undirected graph with more than 2 vertices?
(a) no two vertices have the same degree
(b) At least two vertices have the same degree
(c) At least three vertices have the same degree
(d) All vertices have the same degree

Answer/Explanation

Answer:
(b) At least two vertices have the same degree
Explanation:
In a simple connected undirected graph (with more than two vertices), at least 2 vertices must have the same degree, since if this is not true, then all vertices would have different degrees. A graph with all vertices having different degrees is not possible to construct (can be proved as a corollary to the Havell-Hakimi theorem). Notice that it is possible to construct graphs satisfying choices a, c and d.


Question 33.
Let, G = (V, E) be a graph. Define ε(G) = \(\sum_{d} i_{d}\) × d, where id is the number of vertices of degree d in G. If S and T are two different trees with ε(S) = ε(T), then
(a) |S| = 2|T|
(b) |S| = |T| – 1
(c) |S| = |T|
(d) |S| = |T| + 1

Answer/Explanation

Answer:
(c) |S| = |T|
Explanation:
Given, IMG = Sum of degrees By handshaking theorem, ξ(G) = 2 |EG| where, | EG| is the number of edges in G. If S and T are two trees with ξ(S) = ξ(T).
⇒ 2 |Es| = 2|ET|
⇒ |Es| = |ET|
In a tree, | Es| = |S| – 1 and | ET| = | T | – 1 Where | S | is number of vertices of tree S and |T| is number of vertices of tree T.
∴ |S| – 1 = |T| – 1
⇒ |S| = |T|


Question 34.
In a binary tree with n nodes, every node has an odd number of descendants. Every node is considered to be its own descendant. What is the number of nodes in the tree that have exactly one child?
(a) 0
(b) 1
(c) (n – 1)/2
(d) n – 1

Answer/Explanation

Answer:
(a) 0

Explanation:
A tree with 1 node is not possible, since it is given that every node has exactly 1 child. Now consider a tree with 2 nodes (a is the root)

Computer Science Graph Theory Questions and Answers chapter 4 img 24

Now a has exactly one child. A number of descendants of a = 2. But this contradicts the given fact that every node has an odd number of Descendents. Now consider a tree with 3 nodes. Since every – node has exactly one child, it must be of the form,

Computer Science Graph Theory Questions and Answers chapter 4 img 25

Here a has 3 descendants, b has 2 descendants and c has one. Again we have a contradiction in that b does not have an odd number of descendants. Similarly can show that for trees with 4, 5, 6 … nodes, it is not possible to have all nodes with an odd number of descendants. So the correct answer is the tree has 0 nodes, i.e., choice (a).

Computer Science Graph Theory Questions and Answers


Question 35.
The degree sequence of a simple graph is the sequence of the degrees of the nodes in the graph in decreasing order. Which of the following sequences can not be the degree sequence of any graph?
I. 7, 6, 5, 4, 4, 3, 2, 1
II. 6, 6, 6, 6, 3, 3, 2, 2
III. 7, 6, 6, 4, 4, 3, 2, 2
IV. 8, 7, 7, 6, 4, 2, 1, 1
(a) I and II
(b) III and IV
(c) IV only
(d) II and IV

Answer/Explanation

Answer:
(d) II and IV
Explanation:
Havell-Hakimi algorithm can be used to check whether a given degree sequence is a graph or not.
The algorithm is
1. remove the top node of the sequence.
2. subtract “1” from as many nodes in the remaining sequence as the degree of the top node that was removed.
3. rearrange this sequence in nonincreasing order.
4. check if the resulting sequence is a graph.
5. proceed again to step 1.

If the given sequence is not a graph we will see a violation in step 4, such as the presence of negative degrees in the sequence. Otherwise, the algorithm will bottom out with a degree sequence consisting of only an even number of l’s and any number of 0’s. Now applying the algorithm to the degree sequences I, II, III, and IV, one by one:
I. 7, 6, 5, 4, 4, 3, 2, 1
6, 5, 4, 4, 3, 2, 1                (Step 1)
5, 4, 3, 3, 2, 1, 0                (Step 2)
5, 4, 3, 3, 2, 1, 0                (Step 3)
The sequence is a graph  (Step 4)
4, 3, 3, 2, 1, 0                    (Step 1)
3, 2, 2, 1, 0, 0                    (Step 2)
3, 2, 2, 1, 0, 0                    (Step 3)
The sequence is a graph (Step 4)
2, 2, 1, 0, 0                       (Step 1)
1, 1, 0, 0, 0                       (Step 2)
1, 1, 0, 0, 0                       (Step 3)
A sequence is a graph     (Step 4)

Now, the algorithm ends, since the sequence has only 0’s and an even a number of l’s. The final sequence corresponds to the following valid graph

Computer Science Graph Theory Questions and Answers chapter 4 img 26

Similarly for sequence II.
II. 6, 6, 6, 6, 3, 3, 2, 2
6, 6, 6, 3, 3, 2, 2             (Step 1)
5, 5, 5, 2, 2, 1, 2             (Step 2)
5, 5, 5, 2, 2, 2, 1             (Step 3)
Sequence is a graph     (Step 4)
5, 5, 2, 2, 2, 1                 (Step 1)
4, 4, 1, 1, 1, 1                 (Step 2)
4, 4, 1, 1, 1, 1                 (Step 3)
Sequence is a graph     (Step 4)
4, 1, 1, 1, 1                    (Step 1)
3, 0, 0, 0, 1                    (Step 2)
3, 1, 0, 0, 0                    (Step 3)
Sequence is a graph    (Step 4)
1, 0, 0, 0                       (Step 1)
0,-1,-1,0                       (Step 2)
0, 0, -1, -1                    (Step 3)

The sequence is not a graph (Step 4), since negative degrees are not possible in a valid graph. So, the algorithm ends.
II is cannot be the degree sequence of any graph. Similarly, we can show that III is the degree sequence of some graphs and IV is not the degree sequence of any graph.
So, option (d) is correct.


Question 36.
K4 and Q3 are graphs with the following structures:

Computer Science Graph Theory Questions and Answers chapter 4 img 27

Which one of the following statements is TRUE in relation to these graphs?
(a) K4 is planar while Q3 is not
(b) Both K4 and Q3 are planar
(c) Q3 is planar while K3 is not
(d) Neither K4 nor Q3 is planar

Answer/Explanation

Answer:
(b) Both K4 and Q3 are planar

Explanation:
The planar embedding of K4 and Q3 is shown below:

Computer Science Graph Theory Questions and Answers chapter 4 img 28

So both graphs are planar.

Computer Science Graph Theory Questions and Answers


Question 37.
Let G be a simple undirected planar graph on 10 vertices with 15 edges. If G is a connected graph, then the number of bounded faces in any embedding of G on the plane is equal to
(a) 3
(b) 4
(c) 5
(d) 6

Answer/Explanation

Answer:
(d) 6
Explanation:
n = 10
e = 15
In a simple connected planar graph, Euler’s formula gives the total number of regions as e – n + 2 = 15 – 10 + 2 = 7 Out of this, one region is unbounded and the other 6 are bounded. So the correct answer is 6, which is an option (d).


Question 38.
Which of the following graphs is isomorphic to

Computer Science Graph Theory Questions and Answers chapter 4 img 29

Answer/Explanation

Explanation:
Check invariants are one by one.
Step 1: All 4 choices have the same number of vertices and edges as the given graph.
Step 2: So we find the degree sequence of the given graph which is (1, 1, 2, 2, 2, 2, 2, 4).
Degree sequence of graph in option (a) is (1, 1, 1, 2, 2, 2, 3, 4).
Degree sequence of graph in option (b) is (1, 1, 2, 2, 2, 2, 2, 4)
Degree sequence of graph in option (c) is (1, 1, 2, 2, 2, 2, 3, 3)
Degree sequence of graph in option (d) is (1, 1, 2, 2, 2, 2, 2, 4).
So only options (a) and (c) are not isomorphic to the given graph. since the degree sequence of these graphs is not the same as the given graph.
Step 3: Now to decide between options (b) and (d), which one is isomorphic to the given graph, we check the number of cycles. In given Graph, there is one cycle of length 5 but in Graph (d), there is no cycle of length 5. Graph (b) has one cycle of length 5. So only Graph (b) can be isomorphic to the given Graph.


Question 39.
Let G be a complete undirected graph on 6 vertices. If vertices of G are labeled, then the number of distinct cycles of length 4 in G is equal to
(a) 15
(b) 30
(c) 90
(d) 360

Answer/Explanation

Answer:
(d) 360
Explanation:
The graph given is K6.
In K6, every cycle of length 4 corresponds to selecting 4 vertices out of 6 vertices, which can be done in 6C4 ways, and then ordering the 4 vertices in circular permutation in 3! ways (since vertices are labeled). So the final answer is 6C4 × 3! = 90.

Computer Science Graph Theory Questions and Answers


Question 40.
Consider an undirected random graph of eight vertices. The probability that there is an edge between a pair of vertices is \(\frac { 1 }{ 2 }\). What is the
expected numbers of unordered cycles of length three?
(a) \(\frac { 1 }{ 8 }\)
(b) 1
(c) 7
(d) 8

Answer/Explanation

Answer:
(c) 7
Explanation:
We need to find the unordered cycle of length 3 so we choose any 3 vertices from 8 vertices. This can be done in 8C3 ways To make a cycle we need to choose the edge between the selected vertices probability of choosing any edge is \(\frac { 1 }{ 2 }\).
So for three edges = \(\frac { 1 }{ 2 }\) × \(\frac { 1 }{ 2 }\) × \(\frac { 1 }{ 2 }\) = \(\frac { 1 }{ 8 }\)
Expected no of cycle = np
Here, n = 8C3 and p = \(\frac { 1 }{ 8 }\)
Expected no of cycles = 8C3 × \(\frac { 1 }{ 8 }\) = 7.


Question 41.
Which of the following statements is/are TRUE for an undirected graph?
P: The number of odd degree vertices is even.
Q: The sum of degrees of all vertices is even.
(a) P only
(b) Q only
(c) Both P and Q
(d) Neither P nor Q

Answer/Explanation

Answer:
(c) Both P and Q
Explanation:
Q is the Handshaking theorem and hence true.
P is a corollary to the Handshaking theorem and hence also true.


Question 42.
Let G = (V, E) be a directed graph where V is the set of vertices and E the set of edges. Then which one of the following graphs has the same strongly connected components as G?
(a) G1 = (V, E1) where E1 = {(u,v) | (u,v) ∉ E}
(b) G2 = (V, E2) where E2 = {(u,v) | (v,u)∈ E}
(c) G3 = (V, E3) where E3 = {(u,v) | there is a path of length ≤ 2 from u to v in E}
(d) G4 = (V4, E) where V4 is the set of vertices in G which are not isolated

Answer/Explanation

Answer:
(b) G2 = (V, E2) where E2 = {(u,v) | (v,u)∈ E}
Explanation:
G = (V, E) is directed graph
G2 = (V, E2) where E2 = {(u, v) | (v,u) ∈ E}
G and G2 have the same strongly connected components only the difference in G2 is that all edges of G have been reversed the direction.


Question 43.
Consider an undirected graph G where self-loops are not allowed. The vertex set of G is {(i, j) : 1 ≤ i ≤ 12, 1 ≤ j ≤ 12). There is an edge between (a, b) and (c, d) if | a — c | ≤ 1 and | b – d | ≤ 1. The number of edges in this graph is _____.

Answer/Explanation

Explanation:

Explanation:
The given condition translates into the graph shown below where every vertex is connected only with its neighbors.

Computer Science Graph Theory Questions and Answers chapter 4 img 30

From the above diagram:

  1. The four corner vertices have every 3 degrees which give 4 × 3 = 12 degrees.
  2. The 40 side vertices have 5 degrees each contributing a total of 40 × 5 = 200 degrees.
  3. The 100 interior vertices each have 8 degrees contributing a total of 100 × 8 = 800 degrees.

So total degree of the graph
12 + 200 + 800 = 1012 degrees
Now the number of edges in any undirected graph = \(\frac{\text { Total deg rees }}{2}\)
Therefore the number of edges in this graph = \(\frac{\text { 1012 }}{2}\) = 506

Computer Science Graph Theory Questions and Answers


Question 44.
An ordered n-tuple (d1, d2,…, dn) with d1 ≥ d2 ≥ … ≥ dn is called graphic if there exists a simple undirected graph with n vertices having degrees d1, d2,…, dn respectively. Which of the following 6-tuples is NOT graphic?
(a) (1, 1, 1, 1, 1, 1)
(b) (2, 2, 2, 2, 2, 2)
(c) (3, 3, 3, 1, 0, 0)
(d) (3, 2, 1, 1, 1, 0)

Answer/Explanation

Answer:
(c) (3, 3, 3, 1, 0, 0)

Explanation:
Use the Havell-hakimi algorithm.
The sequence of steps in the algorithm for each graph is shown below:

Computer Science Graph Theory Questions and Answers chapter 4 img 31


Question 45.
The maximum number of edges in a bipartite graph on 12 vertices is _____.

Answer/Explanation

Explanation:
Bipartite graph {u, u} where u and v are partition on vertices:

  • {1, 11} ⇒ 1 × 11 = 11 edges maximum
  • {2, 10} ⇒ 2 × 10 = 20 edges maximum
  • {3, 9} ⇒ 3 × 9 = 27 edges maximum
  • {4, 8} ⇒ 4 × 8 = 32 edges maximum
  • {5, 7} ⇒ 5 × 7 = 35 edges maximum
  • {6, 6} ⇒ 6 × 6 = 36 edges maximum

∴ The maximum number of edges in a bipartite graph on 12 vertices = 36 edges.


Question 46.
A cycle on n vertices is isomorphic to its complement. The value of n is ______.

Answer/Explanation

Explanation:
If a graph is isomorphic to its own complement, then it is a self complementary graph. In a self complementary graph e = \(\frac{\text { n(n – 1) }}{4}\)
but in the cycle Cn, e = n.
Som if a cycle is self complementary, then n = \(\frac{\text { n(n – 1) }}{4}\)

The solution of the above equation is n = 5. So, C5 is the only cycle graph that is self-complementary.


Question 47.
The number of distinct minimum spanning trees for the weighted graph below is ______.

Computer Science Graph Theory Questions and Answers chapter 4 img 32

Answer/Explanation

Explanation:
The edges with weight 1, do not form a cycle. Take all of them. The weight 2 edges can be chosen in 3 × 2 = 6 ways, as shown below.

Computer Science Graph Theory Questions and Answers chapter 4 img 33

Total there is six possible minimum spanning trees. [3 × 2 = 6]

Computer Science Graph Theory Questions and Answers


Question 48.
If G is a forest with n-vertices and k connected components, how many edges does G have?
(a) [n/k]
(b) [n/k]
(c) n – k
(d) n – k + 1

Answer/Explanation

Answer:
(c) n – k
Explanation:
The number of edges in the spanning forest of a graph G with n vertices and k components = Rank (G) = n – k.


Question 49.
Let 8 denote the minimum degree of a vertex in a graph. For all planar graphs on n vertices with 8 ≥ 3 which one of the following is TRUE?
(a) In any planar embedding, the number of faces is at least \(\frac { n }{ 2 }\) + 2
(b) In any planar embedding, the number of faces is less than \(\frac { n }{ 2 }\) + 2
(c) There is a planar embedding in which the number of faces is less than \(\frac { n }{ 2 }\) + 2
(d) There is a planar embedding in which the number of faces is at most \(\frac{\mathrm{n}}{\delta+1}\)

Answer/Explanation

Answer:
(a) In any planar embedding, the number of faces is at least \(\frac { n }{ 2 }\) + 2
Explanation:
Σdeg = 2e
Given δ ≥ 3 also δ ≤ 2e/n
⇒ e ≥ nδ/2
⇒ e ≥ 3n/2
Euler’s formula:
r = e – n + 2 ≥ 3n/2 – n + 2 ≥ n/2 + 2 So the number of faces is atleast n/2 + 2


Question 50.
Let G be a connected planar graph with 10 vertices. If the number of edges on each face is three, then the number of edges in G is ______.

Answer/Explanation

Explanation:
Number of vertices (n) = 10
d(ri) = 3
Number of edges (e) = ?
r = e – v + 2
(euler’s formula for connected planar graphs) r = e – 10 + 2 = e – 8 …(1)
Since every region is bounded by exactly 3 edges and since every edge is exactly double-counted, we have the equation

e = \(\frac { 3r }{ 2 }\) ⇒ r = \(\frac { 2e }{ 3 }\)

Substituting this in equation (1) we get, \(\frac { 2e }{ 3 }\) = e – 8
2e = 3e – 24 ⇒ e = 24


Question 51.
A graph is self-complementary if it is isomorphic to its complement. For all self-complementary graphs on n vertices, n is
(a) A multiple of 4
(b) Even
(c) Odd
(d) Congruent to 0 mod 4, or 1 mod 4

Answer/Explanation

Answer:
(d) Congruent to 0 mod 4, or 1 mod 4

Explanation:
An n-vertex self-complementary graph has exactly half number of edges of the complete graph i.e.\(\frac { n(n – 1) }{ 4 }\) edges. Since n(n – 1) must be divisible by 4, n must be congruent to 0 mod 4 or 1 mod 4.


Question 52.
In a connected graph, a bridge is an edge whose removal disconnects a graph. Which one of the following statements is true?
(a) A tree has no bridges
(b) A bridge cannot be part of a simple cycle
(c) Every edge of a clique with size > 3 is a bridge (A clique is any complete subgraph of a graph)
(d) A graph with bridges cannot have a cycle

Answer/Explanation

Answer:
(b) A bridge cannot be part of a simple cycle
Explanation:
An edge is called a bridge iff it’s removal will disconnect the graph into components. In a cycle, there are two paths between every pair of vertices and so removal of an edge from a cycle does not disconnect the cycle. So a bridge cannot be part of a simple cycle.

Computer Science Graph Theory Questions and Answers


Question 53.
Consider a binary tree T that has 200 leaf nodes. Then, the number of nodes in T that have exactly two children are ________.

Answer/Explanation

Explanation:
n0 : Number of leaf nodes 0 children.
n1 : Number of nodes with 1 child.
n2 : Number of nodes with 2 children.
We have following two equations for binary tree n = n0 + n1 + n2 (where n is the total number of nodes in the tree) …(1)
Accounting for total nodes as sum of those nodes which are children and the root which is not a child of any node,
we get n = n1 × 1 + n2 × 2 + 1 = n1 + 2n2 + 1 ….(2)
Combining equations (1) and (2) we get
n0 + n1 + n2 = n1 + 2n2 + 1
⇒ n2 = n0 – 1

Therefore the number of nodes of degree two in any binary tree = number of leaf nodes -1.
n2 = 200 – 1 = 199


Question 54.
Let G be connected undirected graph of 100 vertices and 300 edges. The weight of a minimum spanning tree of G is 500. When the weight of each edge of G is increased by five, the weight of a minimum spanning tree becomes _______.

Answer/Explanation

Explanation:
G has |V| = 100 vertices and |E| = 300 edges the weight of MST of G = 500 In MST:
Number of vertices = 100
Number of edges = 99
If each edge of G is increased by 5 then MST weight also increased. For each edge of old MST increased by 5.
Total 99 edges.
So 99 × 5 = 445 is increased Total weight of new MST = 500 + 445 = 995


Question 55.
The minimum number of colors that is sufficient to vertex-color any planar graph is _________.

Answer/Explanation

Explanation:
The four-color theorem says that every planar graph can color with 4 colors i.e. four colors are sufficient to properly color any planar graph.


Question 56.
Let T be a tree with 10 vertices. The sum of the degrees of all the vertices in T is ______.

Answer/Explanation

Explanation:
Here in this tree, n = 10
Σdegree = 2 |E|
where |E| represents number of edges. In a tree, |E| = n – 1
= 10 – 1 = 9
So, Σdegree = 2 × 9 = 18


Question 57.
G is an undirected graph with n vertices and 25 edges such that each vertex of G has a degree of at least 3. Then the maximum possible value of n is _______.

Answer/Explanation

Explanation:
The number of vertices: n ≤ ?
Number of vertices: |E| = 25
Now since each vertex has at least 3 degree and 2|E| = Σdegree
i.e., 2|E| ≥ 3n
n ≤ 2 |E| / 3
⇒ n ≤ \(\frac { 2 × 25 }{ 3 }\) ≤ 16.66


So n is at most 16.

Question 58.
The chromatic number of the following graph is _____.

Computer Science Graph Theory Questions and Answers chapter 4 img 34

Answer/Explanation

Explanation:

Computer Science Graph Theory Questions and Answers chapter 4 img 35

Since the largest complete subgraph is K3, the chromatic number is at least 3. We can try for a chromatic number of 3 by using 3 colors, as follows:

Computer Science Graph Theory Questions and Answers chapter 4 img 36

Since we have successfully, properly colored all vertices with only 3 colors, the chromatic number of this graph is 3.

Computer Science Graph Theory Questions and Answers


Question 59.
Let G be a graph with 100! vertices, with each vertex labeled by a distinct permutation of the numbers 1, 2,…………100. There is an edge between vertices u and v if and only if the label of u can be obtained by swapping two adjacent numbers in the label of v. Let y denote the degree of a vertex in G and z denote the number of connected components in G.
Then, y + 10z = _______.

Answer/Explanation

Explanation:
The graph has 100! vertices in which each vertex is labeled by one of the 100! permutation. Let us find the degree of each vertex. Let us take a vertex whose labeling is say 1,2,3,4,100. Now it will be connected to all vertices where exactly 2 of the adjacent numbers are all swapped. The two swapped numbers could be (1,2), (2, 3), (3, 4), etc. up to (99, 100) which makes for 99 edges for each such vertex. So the graph is a regular graph with each vertex connected to 99 other vertices. So y=99 The number of connected components = z = 1 since we can go from any vertex to any other vertex by only swapping 2 adjacent numbers at a time, many times i.e. there is a path from any vertex to any other vertex. The graph is connected. So z1 So y + 10z = 99+10 × 1 = 109


Question 60.
Let G be an undirected complete graph, on n vertices, where n > 2. Then, the number of different Hamiltonian cycles in G is equal to
(a) n!
(b) (n – 1)!
(c) 1
(d) \(\frac{(n-1) !}{2}\)

Answer/Explanation

Answer:
(c,d)

Explanation:
• When vertices are labeled.
In a complete graph, we can traverse the n vertices in any order and return to the starting vertex and form a Hamiltonian cycle. The number of such cycles will be n\ However since circular rotations will have to ignore. Since for example K4 with vertices {1, 2, 3, 4}, the cycle 1-2-3-4 is same as 2-3-4-1 is same as 3-4-1-2 etc. we now get only (n – 1)! distinct Hamiltonian cycles. Further, the cycles 1-2-3-4 and 1-4-3-2 are also the same (clockwise and anticlockwise).
So ignoring this orientation also we finally get \(\frac { (n – 1)! }{ 2 }\) distinct Hamiltonian cycles which is option (d).

• When vertices are unlabelled.
All the Hamiltonian cycles are formed which is isomorphic to each other. So only 1 Hamiltonian cycle will be the answer in this case. So both options (c) and (d) are correct.


Question 61.
Graph G is obtained by adding vertex s toK3, 4 and making s adjacent to every vertex of K3, 4. The minimum number of colors required to edge- color G is ______.

Answer/Explanation

Explanation:

Computer Science Graph Theory Questions and Answers chapter 4 img 37

7 edges are touching at S each of which needs to be colored by a different color. So 7 colors minimum are required. All other vertices have less than 7 edges touching. So 7 colors only are required for edge coloring.


Question 62.
In an undirected connected planar graph G, there are eight vertices and five faces. The number of edges in G is _________.

Answer/Explanation

Explanation:
In a connected planar graph
r = e – n + 2
Here, n = 8, r = 5
∴ 5 = e – 8 + 2
e = 11


Question 63.
Let G = (V, E) be an undirected unweighted connected graph. The diameter of G is defined as diam(G) = Computer Science Graph Theory Questions and Answers chapter 4 img 38 {the length of the shortest path between u and v}
Let M be the adjacency matrix of G. Define graph G2 on the same set of vertices with adjacency matrix N, where

Computer Science Graph Theory Questions and Answers chapter 4 img 43

Which one of the following statements is true?

(a) [“diam(G) / 2] < diam(G2) < diam(G)
(b) diam(G2) ≤ [diam(G) / 2]
(c) diam(G) < diam(G2) ≤ 2 diam(G)
(d) diam(G2) = diam(G)

Answer/Explanation

Answer:
(b) diam(G2) ≤ [diam(G) / 2]

Explanation:

Computer Science Graph Theory Questions and Answers chapter 4 img 39

Means G2 will have not only all the edges in G but also will have edges connecting vertices in G which have a path of length 2, since M2 will have all edges between u and v if there is a path of length 2 between shown in G.

option (a) [diam(G)/2] < diam(G2) < diam(G) Let G be the graph shown below with dia(G) = 2

Computer Science Graph Theory Questions and Answers chapter 4 img 40

Since (a,c) has a path of length 2 in G, G2 will have an edge connecting a and c. Now diameter of G2 = 1
This violates option (a) condition that dia(G2)> dia(G)/2 So option (a) false.

option (b) diam(G2) ≤ [diam (G)/2] consider graph below with dia(G) = 3

Computer Science Graph Theory Questions and Answers chapter 4 img 41

Now G2 will connect all paths of length 2 with edges and will be

Computer Science Graph Theory Questions and Answers chapter 4 img 42

Now dia(G2) = 2
But dia(G) = 3
dia (G2) = 2 ≤ [dia(G)/2]
2 ≤ [1.5]
2 ≤ 2 satisfied.

option (b) is correct.

Option (c) diam(G) < diam (G2) ≤ 2 diam (G) Taking previous option example where dia (G) = 3 and dia (G2) = 2

3 ≤ 2 ≤ 6

Is false.
So option (c) is false.

Option(d) diam (G2) = diam (G)
Taking previous example where dia(G) = 3 and dia (G2) = 2
2 = 3 is false.
So option (d) is false.
So correct option is an option (b).


Set Theory and Algebra Questions and Answers | Computer Science Quiz

Computer Science Set Theory and Algebra MCQ Quiz Questions and Answers PDF Download

Computer Science Set Theory and Algebra Questions and Answers

Question 1.
State whether the following statements are TRUE or FALSE:
The union of two equivalence relations is also an equivalence relation.

Answer/Explanation

Explanation:
A relation is said to be equivalence relation is

  • Reflexive
  • Symmetric, and
  • Transitive

The union of two reflexive relations and two symmetric relations are reflexive and symmetric respectively. However, the union of two transitive relations need not be transitive. Therefore, the union of two equivalence relations need not be an equivalence relation.
Example:
Let R1 and R2 on set A = {1, 2, 3}
R1 = {(1, 1), (2, 2,), (3, 3) (1, 2), (2, 1)} is an equivalence relation
R2 = {(1, 1),(2, 2), (3, 3), (2, 3), (3, 2)} is an equivalence relation
R1 ∪ R2 = {(1, 1), (2, 2), (3, 3,), (1, 2), (2, 1), (2, 3), (3,2)} is not an equivalence relation, because (1, 2) & (2, 3) needs (1, 3) element to be in transitive relation.


Question 2.
(a) How many binary relations are there on a set A with n elements?
(b) How many one—to—one functions are there from a set A with n elements onto itself.

Answer/Explanation

Explanation: (a) Set A contains n elements. Every subset of A × A is a binary relation on set A.
∴ Number of binary relations on a set A with n elements 2
(b) Number of one-to-one functions from a set A with m-elements to a set B with n – elements are nPm So the number of one-to-one functions from a set A with n-elements to itself is nPn = n!.


Question 3.
The complement(s) of the element ‘a’ in the lattice shown in the figure is (are)

 

Computer Science Set Theory and Algebra Questions and Answers chapter 2 img 1

Answer/Explanation

Explanation: The complement of an element x is x’ iff LUB of x and x’ is 1 (greatest element) and GLB of x and x’ is 0 (least element).
∴ The complement of the element ‘a’ in the lattice = {b, c, d, e}.


Question 4.
The transitive closure of the relation {(1, 2) (2, 3) (3, 4) (5, 4)} on the set A = {1, 2, 3, 4, 5} is _______.

Answer/Explanation

Explanation:
The relation has (1, 2) (2, 3) then add (1, 3) to the relation. Since relation have (2, 3) (3,4) then add (2, 4) to relation.
So the resultant relation is = {(1, 2), (2, 3), (3, 4), (5, 4), (1, 3), (2, 4)} Now the resultant relation have (1,2) (2, 4) then add (1, 4) to the relation
∴ {(1,2), (2,3), (3,4), (5,4), (1,3), (2,4), (1,4)}
So the transitive closure of the relation is = {(1,2), (2,3), (3,4), (5,4), (1,3), (2,4), (1,4)}


Question 5.
Let S be an infinite set and S1, S2, … Sn sets such that S1 ∪ S2 ∪ ……. ∪ Sn = S. Then
(a) At least one of the sets Si is a finite set
(b) Not more than one of the sets Si can be finite
(c) At least one of sets Si is infinite
(d) Not more than one of the sets Si is an infinite set.

Answer/Explanation

Answer: (c) At least one of sets S; is infinite
Explanation:
S = S1 ∪ S2 ∪ S3 ∪ … ∪ Sn.
For S to be an infinite set, at least one of sets Si must be infinite, since if all Si were finite, then S will also be finite.


Computer Science Set Theory and Algebra Questions and Answers

Question 6.
Let A be a finite set of size n. The number of elements in the power set of A × A is
(a) 22ⁿ
(b) 2
(c) 2n
(d) 2n

Answer/Explanation

Answer: (b) 2
Explanation:
Number of elements in A × A = n2
∴ A number of elements in the power set of A × A = 2.


Question 7.
Some group (G, o) is known to be abelian. Then, which one of the following is true for G?
(a) g = g-1 for every g∈ G.
(b) g = g2 for every g ∈ G
(c) (goh)2 = g2 o h2 for every g, h ∈ G.
(d) G is of finite order

Answer/Explanation

Answer: (c) (goh)2 = g2 o h2 for every g, h ∈ G.
Explanation:
(goh)2 = (goh)o(goh)
Since group is abelian so it is commutative as well as associative.
= go (hog)h
= go (goh) oh
= (gog) o(hh) = g2 o h2
So (goh)2 = g2 o h2 for every g, h∈ G


Question 8.
Let R be asymmetric and transitive relation on a set A. Then
(a) R is reflexive and hence an equivalence relation
(b) R is reflexive and hence a partial order
(c) R is reflexive and hence not an equivalence relation
(d) None of the above

Answer/Explanation

Answer: (d) None of the above
Explanation:
A relation that is symmetric and transitive, need not be reflexive relation.

  • R = { }; on the set A = {a, b}. The relation R is symmetric and transitive but not reflexive.
  • R = {(a, a), (b, b)}; on the set A = {a, b}. The relation R is symmetric, transitive and also reflexive.

∴ A relation is transitive and symmetric relation but need not be reflexive relation.


Question 9.
The number of elements in the power set P(S) of the set S ={(Φ), 1, (2, 3)} is:
(a) 2
(b) 4
(c) 8
(d) None of these

Answer/Explanation

Answer: (c) 8
Explanation:
If a set has n elements then its powers set has 2n elements.
Given set S = {(Φ), 1, (2, 3)}
Number of elements in S = 3
∴ The number of elements in powerset (S)
= 23 = 8.


Question 10.
Let A be the set of all nonsingular matrices over real numbers and let * be the matrix multiplication operator. Then
(a) A is closed under * but <A, *> is not a semigroup.
(b) <A, *> is a semigroup but not a monoid.
(c) <A, *> is a monoid but not a group.
(d) <A, *> is a group but not an abelian group

Answer/Explanation

Answer: (d) <A, *> is a group but not an abelian group
Explanation:

  • Closure Property: Multiplication of two non-singular matrices is also a non-singular matrix. Matrix multiplication over non-singular matrices follows closure properties.
  • Associative Property: Multi-plication over any set of matrices is associative. (AB)C = A(BC) Where A, B, and C are non-singular matrices
  • Identity Element: Identity matrix I am the identity element for matrix multiplication over matrices and I is non-singular.
  • Inverse Element: For every non-singular matrix its inverse exists. So, for non¬singular matrices, inverse elements exist.
  • Commutative: Matrix multiplication is not commutative
    AB ≠ BA
    Where A, B are non-singular matrices. Matrices multiplication is not commutative. So <A, *> is a group but not an abelian group

Computer Science Set Theory and Algebra Questions and Answers

Question 11.
Let A and B set and let Ac and Bc denote the complements of the sets A and B. The set (A – B) ∪ (B – A) ∪ (A n B) is equal to
(a) A ∪ B
(b) Ac ∪ Bc
(c) A ∩ B
(d) Ac ∩ Bc

Answer/Explanation

Answer: (a) A ∪ B
Explanation:
(A – B) ∪ (B – A) ∪ (A ∩ B)
Representing the above set using the Venn diagram as follows.

Computer Science Set Theory and Algebra Questions and Answers chapter 2 img 10

 

∴ By Venn diagram,
(A – B) ∪ (B – A) ∪ (A ∩ B) = A ∪ B


Question 12.
Let X = {2, 3, 6,12, 24}. Let ≤ be the partial order defined by x ≤ y if x divides y. The number of edges in the Hasse diagram of (X, ≤) is
(a) 3
(b) 4
(c) 9
(d) None of these

Answer/Explanation

Answer: (b) 4
Explanation:
x = {2, 3, 6, 12, 24}
The Hasse diagram of (x, ≤) is

Computer Science Set Theory and Algebra Questions and Answers chapter 2 img 11

 

Therefore, the number of edges in the Hasse diagram = 4


Question 13.
Suppose X and Y are sets and |x| and |Y| are their respective cardinalities. It is given that there are exactly 97 functions from X to Y. From this one can conclude that
(a) |X| = 1, |Y| =97
(b) IXj =97, |Y| = 1
(c) j X | = 97, | Y | = 97
(d) None of the above

Answer/Explanation

Answer: (a) |X| = 1, |Y| =97
Explanation:
X and Y are set. The cardinalities of X and Y are |X| and |Y| respectively.
The number of functions from X to Y = (|Y|)|X| Given that number of functions from X to Y = 97
∴ 97 = (|Y|)|X|
So above implies that |X| = 1 and |Y| = 97


Question 14.
Which of the following statements is false?
(a) The set of rational numbers is an abelian group under addition
(b) The set of integers in an abelian group under addition
(c) The set of rational numbers form an abelian group under multiplication
(d) The set of real numbers excluding zero in an abelian group under multiplication

Answer/Explanation

Answer: (c) The set of rational numbers form an abelian group under multiplication
Explanation:
0 is also a rational number and for 0, the inverse doesn’t exist under multiplication. Therefore, the set of rational numbers doesn’t form an abelian group under multiplication.


Computer Science Set Theory and Algebra Questions and Answers

Question 15.
Let R denote the set of real numbers. Let f:R x R → R x R be a bijective function defined by f(x, y) = (x + y, x – y). The inverse function of f is given by
(a) f-1(x,y) = \(\left(\frac{1}{x+y}, \frac{1}{x-y}\right)\)
(b) f-1(x,y) = (x – y, x + y)
(c) f-1(x,y) = \(\left(\frac{x+y}{2}, \frac{x-y}{2}\right)\)
(d) f-1(x,y) = (2(x – y), 2(x + y))

Answer/Explanation

Answer: (c) f-1(x,y) = \(\left(\frac{x+y}{2}, \frac{x-y}{2}\right)\)
Explanation:
f(x, y) = ((x + y), (x — y))
So let z1 = x+ y ……(i)
z2=x—y …(ii)
f(x, y) = (z1, z2)
So f-1(z1, z2) = (x, y)
Adding (i) and (ii)
z1 + z2 = 2x
X = \(\frac{\mathrm{z}_{1}+\mathrm{z}_{2}}{2}\)
Subtracting (i) and (ii)
z1 – z2 = 2y
y = \(\mathrm{y}=\frac{\mathrm{z}_{1}-\mathrm{z}_{2}}{2}\)
So the inverse function of F is given by
f-1(z1 , z2) = (x,y) = \(\left(\frac{\mathrm{z}_{1}+\mathrm{z}_{2}}{2}, \frac{\mathrm{z}_{1}-\mathrm{z}_{2}}{2}\right)\)
Since z1 and z2 are just dummy variables so replacing z1 and z2 by x and y respectively
f-1(x,y) = \(\left(\frac{x+y}{2}, \frac{x-y}{2}\right)\)

Alternate Method:

Given f(x, y) = ((x + y), (x — y))
Take some random ordered pair say (2, 3) f(2, 3) ((2 + 3), (2 — 3)) = (5, —1)
Now the correct inverse must map (5. —1) back to(2,3).
Trying the options one by one we find that only option (e) maps (5, -1) to (2, 3).


Question 16.
Let R be a non-empty relation on a collection of sets defined by ARB if and only if A ∩ B =Φ. Then, (pick the true statement)
(a) R is reflexive and transitive
(b) R is symmetric and not transitive
(c) R is an equivalence relation
(d) R is not reflexive and not symmetric

Answer/Explanation

Answer: (b) R is symmetric and not transitive
Explanation:
(i) Reflexive
A ∩ A = A ≠ Φ
So; (A, A) doesn’t belong to relation R.
∴ Relation R is not reflexive.

(ii) Symmetric
If A ∩ B = Φ then B ∩ A Φ is also true
∴ relation R is a symmetric relation.

(iii) Transitive
If A ∩ B = Φ and B ∩ C = Φ. it need not be true that A ∩ C = Φ.
For example:
A = {1, 2}, B = {3, 4}, C = {1, 5, 6}
A ∩ B = Φ and B ∩ C = Φ but
A ∩ C = {1} ≠ Ø
∴ Relation R is not transitive relation.


Question 17.
Which one of the following is false?
(a) The set of all bijective functions on a finite set forms a group under function composition.
(b) The set {1, 2, …, p – 1} forms a group under multiplication mod p where p is a prime number.
(c) The set of all strings over a finite alphabet Σ forms a group under concatenation.
(d) A subset s ≠ Φ of G is a subgroup of the group <G, *> if and only if for any pair of elements a, b ∈ s, a * b-1∈ s.

Answer/Explanation

Answer: (c) The set of all strings over a finite alphabet Σ forms a group under concatenation.
Explanation:
In option (c). the set of all strings over a finite alphabet Σ doesn’t form a group under concatenation because the inverse of a string doesn’t exist with respect to concatenation.


Computer Science Set Theory and Algebra Questions and Answers

Question 18.
The number of equivalence relations on the set {1, 2, 3, 4} is
(a) 15
(b) 16
(c) 24
(d) 4

Answer/Explanation

Answer: (a) 15
Explanation:
Corresponding to every partition of the set 1, 2, 3, 4, there exists a unique equivalence relation. So we count every type of unordered partition of the set of 4 elements into one block, two-block, three-block, and four block partitions. as shown below:

Computer Science Set Theory and Algebra Questions and Answers chapter 2 img 12

 

Total 1+7+6+1=15
So the number of equivalence relations on the set {1, 2, 3. 4} is 15.


Question 19.
Suppose A is a finite set with n elements. The number of elements in the Largest equivalence relation of A is
(a) n
(b) n2
(c) 1
(d) n + 1

Answer/Explanation

Answer: (b) n2
Explanation:
A is a finite set with n elements. The largest equivalence relation of A is the cross. product A × A and the number of elements in the cross product A × A is n2.


Question 20.
Let R1 and R2 be two equivalence relations on a set. Consider the following assertions:
(i) R1 ∪ R2 is an equivalence relation
(ii) R1 ∩ R2 is an equivalence relation
Which of the following is correct?
(a) both assertions are true
(b) assertion (i) is true but assertion (ii) is not true
(c) assertion (ii) is true but assertion (i) is not true
(d) neither (i) nor (ii) is true

Answer/Explanation

Answer: (c) assertion (ii) is true but assertion (i) is not true
Explanation:
A relation is said to be an equivalence relation if the relation is
(i) Reflexive
(ii) Symmetric
(iii) Transitive
Reflexive and symmetric properties are both closed under ∪ & ∩.
Transitive property is closed under n but not u. So equivalence relations are closed under ∩ hut not ∪.
Therefore R1 ∩ R2 is an equivalence relation but R1 ∪ R2 is not necessarily an equivalence relation.


Computer Science Set Theory and Algebra Questions and Answers

Question 21.
The number of functions from an m element set to an n element set is
(a) m + n
(b) mn
(c) nm
(d) m * n

Answer/Explanation

Answer: (c) nm
Explanation:
The number of functions from an m element set to an n clement set is nm.


Question 22.
The binary relation R = {(1, 1), (2, 1), (2, 2), (2, 3), (2, 4), (3, 1), (3, 2), (3, 3), (3, 4)} on the set A = {1, 2, 3, 4} is
(a) Reflexive, symmetric and transitive
(b) Neither reflexive, nor irreflexive but transitive
(c) Irreflexive, symmetric and transitive
(d) Irreflexive and antisymmetric

Answer/Explanation

Answer: (b) Neither reflexive nor irreflexive but transitive
Explanation:
The relation R doesn’t contain (4, 4), so R is not reflexive relation. Since relation R contains (1, 1), (2, 2), and (3, 3). Therefore, relation R is also not irreflexive.
That R is transitive, can be checked by systematically checking for all (a. b) and (b, c) in R, whether (a, e) also exists in R. So option (b) is correct.


Question 23.
Suppose A = {a, b, c, d} and Π1 is the following partition of A
Π1 = {{a, b, c}, {d}}
(a) List the ordered pairs of the equivalence relations induced by Π1
(b) Draw the graph of the above equivalence relation

Answer/Explanation

Answer: Given partition of A is
π1 = {(a, b, c), (d)}
(a) The ordered pairs of the equivalence relations induced by π1 is
R = (a, b, c) × (a, b, c) ∪ (d) × (d)
R = {(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c), (d, d)}
(b) The digraph of the above equivalence relation is as follows:

Computer Science Set Theory and Algebra Questions and Answers chapter 2 img 13


Question 24.
Let (A, *) be a semigroup. Furthermore, for every a and b in A, if a ≠ b, then a * b ≠ b * a.
(a) Show that for every an in A a * a = a
(b) Show that for every a, b in A a * b * a = a
(c) Show that for every a, b, c in A a * b * c = a * c

Answer/Explanation

Answer:
Explanation:
Given a ≠ b ⇒ a * b ≠ b * a The contrapositive version of this is a*b = b*a ⇒ a = b
(a) Now since (A, *) is given to be a semigroup, * is associative
i. e. a * (a * a) = (a * a) * a
Hence a = a * a
(b) (a * b * a) * a = a * b * (a * a) = a * b * a
⇒ a*(a*b*a) = (a*a)*b*a = a * b * a
as a * a = a [proved in part a]
So (a * b * a) * a = a * (a * b * a)
Hence a * b * a = a
(c) (a * b * c) * (a * c) = a * b * (c * a * c) = a * b * c
(a * c) * (a * b * c) = (a * c * a) * b * c = a * b * c
So (a *b * c) * (a * c) = (a * c) * (a * b * c)
Hence a*b*c = a*c


Computer Science Set Theory and Algebra Questions and Answers

Question 25.
The number of binary relations on a set with n elements is
(a) n2
(b) 2n
(c) 2ⁿ²
(d) None of these

Answer/Explanation

Answer: (c) 2ⁿ²
Explanation:
The maximum number of elements in a binary relation on a set A with n elements = Number of elements in A × A = n2
Each element has two choices, either to appear on a binary relation or doesn’t appear on a binary relation.
∴ The number of binary relations = 2.


Question 26.
(a) Mr. X claims the following:
If a relation R is both symmetric and transitive, then R is reflexive. For this, Mr. X offers the following proof. “From xRy, using symmetry we get yRx. Now because R is transitive, xRy and yRx together imply xRx. Therefore, R is reflexive.” Briefly point out the flaw in Mr. X’s proof.
(b) Give an example of a relation R which is symmetric and transitive but not reflexive.

Answer/Explanation

Explanation:
(a) According to Mr. X if xRy is in relation then yRx is also in relation because of symmetricity. Now because R is transitive, xRy and yRx implies xRx.
The flaw in Mr. X claim is that if xRy is present then only it implies yRx and hence xRx. However, if xRy is not present then according to symmetricity yRx is also not present. So xRx need not be present in relation. So it need not be reflexive.
For Example, Empty relation Φ is both symmetric and transitive. However, Φ is not reflexive relation.
(b) Examples of relations that are symmetric and transitive but not reflexive.
(i) Empty relation Φ is symmetric and transitive but not reflexive.
(ii) Relation R = {(a, b), (b, a), (a, a), (b, b)} over A = {a, b, c} is both symmetric and transitive but not reflexive.


Question 27.
A relation R is defined on the set of integers as xRy iff (x + y) is even. Which of the following statements is true?
(a) R is not an equivalence relation
(b) R is an equivalence relation having 1 equivalence class
(c) R is an equivalence relation having 2 equivalence classes
(d) R is an equivalence relation having 3 equivalence classes

Answer/Explanation

Answer: (c) R is an equivalence relation having 2 equivalence classes
Explanation:
A relation R is defined as xRy iff (x + y) is even over a set of integers.
(x + y) is even iff
(i) both x and y are even
(ii) both x and y are odd
Therefore, relation R is equivalence relation because relation is
(i) Reflexive
x + x = 2x = even
So (x, x) belongs to R. So relation is reflexive.
(ii) Symmetric
If x + y = even then y + x is also even So relation is symmetric.
(iii) Transitive
If x + y = even and y + z = even
Then x + y + y + z = even + even
⇒ x + z + 2y = even
⇒ x + z = even – 2y
⇒ x + z = even
∴ Relation R is transitive.
So relation R is an equivalence relation which divides the set of integer into two equivalence classes: One is of all even and other is of odd integer.

Equivalence classes of R are
[0] = { ….. -6, -4, -2, 0, 2, 4, 6, …}
[1] = { ….. -7, -5, -3, -1, 1, 3, 5, 7, …}


Question 28.
Let P(S) denote the power set of a set S. Which of the following is always true?
(a) P(P(S)) = P(S)
(b) P(S) ∩ P(P(S)) = {Ø}
(c) P(S) ∩ S = P(S)
(d) S ∉ P(S)

Answer/Explanation

Answer: (b) P(S) ∩ P(P(S)) = {Ø}
Explanation:
Φ always present in any powerset of a set and Φ is the only common element between P(S) and P(P(S))
∴ P(S) ∩ P(P(S)) = {Φ}


Question 29.
Consider the following relations
R1(a, b) iff (a + b) is even over the set of integers
R2(a, b) iff (a + b) is odd over the set of integers
R3(a, b) iff a.b > 0 over the set of non-zero rational numbers.
R4 (a, b) iff | a – b | ≤ 2 over the set of natural numbers
Which of the following statements is correct?
(a) R1 and R2 are equivalence relations, R3 and R4 are not
(b) R1 and R3 are equivalence relations, R2 and R4 are not
(c) R1 and R4 are equivalence relations, R2 and R3 are not
(d) R1, R2 R3, and R4 are all equivalence relations

Answer/Explanation

Answer: (b) R1 and R3 are equivalence relations, R2 and R4 are not
Explanation:
(I) Relation R1(a, b) iff (a + b) is even over the set of integers.
(i) a + a = 2a which is even So (a, a) belongs to R1
∴ R1 is reflexive relation

(ii) If (a + b) is even, then (b + a) is also even
∴ R1 is symmetric relation

(iii) If (a + b) and (b + c) are even then a + c = (a + b) + (b + c) – 2b = even + even — even = even
∴ R1 is transitive relation.
Since R1 is reflexive, symmetric and transitive so R1 is an equivalence relation.

(II) RR2(a, b) iff (a +b) is odd over set of integers,
(i) a + a = 2a which is not odd So (a, a) doesn’t belong to R2
∴ R2 is not reflexive relation Since R2 is not reflexive, it is not an equivalence relation.

(III) R3(a, b) iff a . b > 0 over set of non-zero relational numbers.
(i) a. a. > 0 for every non-zero rational number.
∴ R3 is reflexive relation.
(ii) If a.b > 0 then b.a > 0
∴ R3 is symmetric relation.
(iii) a.b > 0 and b.c > 0 ⇒ All a,b,c are positive or all a,b,c are negative.
So a.c > 0
∴ R3 is transitive relation.
So R3 is an equivalence relation.

(IV) R4 (a, b) iff |a – b| ≤ 2 over the set of natural number
(i) |a – a| ≤ 2
0 ≤ 2
∴ R4 is reflexive relation.

(ii) If |a — b| ≤ 2 then also |b – a| ≤ 2 ∴ R4 is symmetric relation
(iii) If |a — b| ≤ 2 and |b — c| ≤ 2 then it is not necessary that |a — c| ≤ 2
Ex. |3 – 5| ≤ 2 and |5 — 7| ≤ 2 but |3 —7| ≤ 2
∴ R4 is not transitive.
Since R4 is reflexive and symmetric not transitive, so R4 is not an equivalence relation.


Question 30.
Consider the following statements:
S1: There exist infinite sets A, B, C such that A ∩ (B ∩ C) is finite.
S2: There exist two irrational numbers x and y such that (x + y) is rational.
Which of the following is true about S1 and S2?
(a) Only S1 is correct
(b) Only S2 is correct
(c) Both S1 and S2 are correct
(d) None of S1 and S2 is correct

Answer/Explanation

Answer: (c) Both S1 and S2 are correct
Explanation:
S1: Let A = set of integers
B = set of odd integers
C = set of even integers
A ∩ (B ∩ C) = Φ and Φ is finite set.
Therefore, S1 is true.
S2: Let two irrational number x and y are respectively \((1+\sqrt{2})\) and \((1-\sqrt{2})\).
So x + y= 1 + \(\sqrt{2}\) +1 – \(\sqrt{2}\)
= 2 which is rational number Therefore, S2 is true. Since both S1 and S2 are true, option (c) is true.


Computer Science Set Theory and Algebra Questions and Answers

Question 31.
Let f: A → B be a function and let E and F be subsets of A. Consider the following statements about images.
S1:f(E ∪ F)=  f(E) ∪ f(F)
S2: f(E ∩ F) = f(E) ∩ f(F)
(a) Only S1 is correct
(b) Only S2 is correct
(c) Both S1 and S2 are correct
(d) None of S1 and S2 is correct

Answer/Explanation

Answer: (a) Only S1 is correct
Explanation:
Given a function f: x → y and subsets E and F of A then we have f(E ∪ F) = f(E) ∪ f(F) and f(E ∩ F) ⊆ f(E) ∩ f(F)
Therefore S1 is correct and S2 is false.


Question 32.
The binary relation S = f(empty set) on set A = {1, 2, 3} is
(a) Neither reflexive nor symmetric
(b) Symmetric and reflexive
(c) Transitive and reflexive
(d) Transitive and symmetric

Answer/Explanation

Answer: (d) Transitive and symmetric
Explanation:
The empty relation on any set is always transitive and symmetric but not reflexive.


Question 33.
Consider the set Σ* of all strings over the alphabet Σ = {0,1}. Σ* with the concatenation operator for strings
(a) does not form a group
(b) forms a non-commutative group
(c) does not have a right identity element
(d) forms a group if the empty string is removed from Σ*

Answer/Explanation

Answer: (a) does not form a group
Explanation:
Σ = {0, 1}
Σ* = {0,1}*
= {ε, 0, 1, 01, 10, 11, 000, …}
So (Σ*, •) is an algebraic system, where • (concatenation) is a binary operation.
So (Σ*, •) is a group if and only if the following conditions are satisfied.
1. • (Concatenation) is a closed operation.
2. • is an associative operation.
3. There is an identity.
4. Every element of Σ* has an inverse

Condition 1: * is a closed operation because for any ω1,∈ Σ* and ω2 ∈ Σ*, ω1 . ω2∈ Σ*
Condition 2: For any string x, y, z ∈ Σ*, x . (y . z) = (x . y) . z
So it is associative for example let
x = 01, y = 11, z = 00 then L.H.S. = x . (y.z)
= 01(1100) = 01(1100) = 011100 R.H.S. = (x.y).z
= (0111)00 = (0111)00 = 011100
Condition 3: The Identity is e or empty string because for any string ω ∈ Σ*,
εω = ωε = ω
Now, since ε ∈ Σ*, identity exists.
Condition 4: There is no inverse exist for Σ* because any string ω ∈ Σ*, there is no string ω-1 such that ω . ω-1 = ε = ω-1 ω.
So Σ* with the concatenation operator for strings doesn’t form a group but it does form a monoid.


Question 34.
Let (S, ≤) be a partial order with two minimal elements a and b, and a maximum element c. Let P: S →{True, False} be a predicate defined on S. Suppose that P(a) = True, P(b) = False and P(x) ⇒ P(y) for all x, y e S satisfying x ≤ y, where ⇒ stands for logical implication. Which of the following statements CANNOT be true?
(a) P(x) = True for all x ∈ S such that x ≠ b
(b) P(x) = False for all x ∈ S such that x ≠ a and x ≠ c
(c) P(x) = False for all x ∈ S such that b ≤ x such that x ≠ c
(d) P(x) = False for all x ∈ S such that a ≤ x and b ≤ x

Answer/Explanation

Answer: (d) P(x) = False for all x ∈ S such that a ≤ x and b ≤ x
Explanation:
If a ≤ x, since p(x) ⇒ p(y) whenever x ≤ y ∴ p(a) ⇒ p(x)
Now since p(a) = True, p(x) = cannot be false. ∴ (d) cannot be true.


Computer Science Set Theory and Algebra Questions and Answers

Question 35.
Consider the set {a, b, c} with binary operators + and x defined as follows :

 

Computer Science Set Theory and Algebra Questions and Answers chapter 2 img 2

For example, a + c = c, c + a = a, c x b = c and b x c = a.
Given the following set of equations:
(a x x) + (a x y) = c
(b x x) + (c x y) = c
The number of solution (s) (i.e., pair (s) (x, y) that satisfies the equations) is
(a) 0
(b) 1
(c) 2
(d) 3

Answer/Explanation

Answer: (c) 2
Explanation:
The possible solution pairs are (a, a), (a, b), (a, e), (b, a), (b, b), (b, c), (c, a,), (c, b) and (e, c). Substitute them one by one in both equations and see which of them satisfies both the equations.
The given equations are:
(a × x)+(a × y) = C ……(i)
(b × x)+(c × y) = C ……(ii)
Substitute first (x. y) = (a, a)
LHS of equation (i) becomes (a × a) + (a × a) = a +a = b
Now RHS of equation (i) = e
Therefore LHS ≠ RHS. This means that (a, a) is not a solution pair. Similarly, try each of the remaining seven possible solution pairs. It will be found that only two pairs (b, c) and (c, b) will satisfy both equations (i) & (ii) simultaneously. Therefore choice (c) is correct.


Question 36.
Consider the binary relation:
S = {(x, y) | y = x + 1 and x, y e {0, 1, 2, ….}}
The reflexive transitive closure of S is
(a) {(x, y) | y > x and x, y ∈ {0, 1, 2, ….}}
(b) {(x, y) | y ≥ x and x,y ∈ {0, 1, 2, …..}}
(c) {(x, y) | y < x and x,y ∈ {0, 1, 2, ….}}
(d) {(x, y) | y ≤ x and x, y ∈ {0, 1, 2, ….}}

Answer/Explanation

Answer: (b) {(x, y) | y ≥ x and x,y ∈ {0, 1, 2, …..}}
Explanation:
S = {(x, y) | y = x + 1, and x, y ∈ (0, 1, 2, …}} = {(0, 1), (1, 2), (2, 3), (3, 4), …}
Now let T1 be the reflexive closure of S.
T1 = {(0, 0), (1, 1), (2, 2), (3, 3)…} ∪ {(0, 1), (1, 2), (2, 3), (3, 4)…}
= {(0, 0), (0, 1), (1, 1), (1, 2), (2, 2), (2, 3), (3, 3), (3, 4) …}

Let T2 be the transitive closure of S.
(0, 1), (1, 2) ∈ S ⇒ (0, 2) ∈ T2
(0, 2), (2, 3) ∈ S ⇒ (0, 3) ∈ T2
(0, 3), (3, 4) ∈ S ⇒ (0, 4) ∈ T2
and so on…..
Also (1, 2), (2, 3) ∈ S ⇒ (1, 3) ∈ T2
(1, 3), (3, 4) ∈ S ⇒ (1, 4) ∈ T2
(1, 4), (4, 5) ∈ S ⇒ (1, 5) ∈ T2
and so on….
∴ T2 = {(0, 1), (0, 2), (0, 3), …, (1, 2), (1, 3), (1, 4), …}

Now the reflexive, transitive closure of S will be T3 = T1 ∪ T2 = {(0, 0),(0, 1), (0, 2),…, (1,1), (1, 2), (1, 3),…,(2, 2) (2, 3), (2, 4),…}.
Option (b) is correct.


Question 37.
The number of different nxn symmetric matrices with each element being either 0 or 1 is: (Note : power (2, x) is same as 2x)
(a) power(2, n)
(b) power(2, n2)
(c) power(2, (n2 + n)/2)
(d) power (2, (n2 – n)/2)

Answer/Explanation

Answer: (c) power(2, (n2 + n)/2)
Explanation:
In a symmetric matrix, the lower triangle must be the mirror image of the upper triangle using the diagonal as a mirror. Diagonal elements may be anything. Therefore, when we are counting symmetric matrices we count how many ways are there to fill the upper triangle and diagonal elements. Since the first row has n elements, second (n -1) elements, third row (n – 2) elements, and so on up to the last row, one element.
Total number of elements in diagonal + upper triangle
= n + (n – 1) + (n – 2) + … + 1 = n(n + 1)/2
Now, each one of these elements can be either 0 or 1. So total number of ways we can fill these elements is
\(2 \frac{n(n+1)}{2}\) = power (2, (n2 + n)/2)
Since there is no choice for lower triangle elements the answer is power (2, (n2 + n)/2) which is choice (c).


Question 38.
In a class of 200 students, 125 students have taken Programming Language course, 85 students have taken Data Structures course, 65 students have taken Computer Organization course; 50 students have taken both Programming Language and Data Structures, 35 students have taken both Data Structures and Computer Organization; 30 students have taken both Data Structures and Computer Organization, 15 students have taken all the three courses. How many students have not taken any of the three courses?
(a) 15
(b) 20
(c) 25
(d) 30

Answer/Explanation

Answer: (c) 25
Explanation:

Computer Science Set Theory and Algebra Questions and Answers chapter 2 img 14

According to inclusion – exclusion formula:
| PL ∪ DS ∪ CO | = | PL | + | DS | + | CO | – | PL ∩ DS|- |PL – CO|-|DS ∩ CO| + |PL ∩ DS ∩ CO| PL = students who have taken programming. DS = Students who have taken Data structures. CO = Students who have taken Computer Organization.
So, the number of students who have taken atleast 1 of the 3 courses is given by:
= 125 + 85 + 65- 50- 35- 30 + 15 = 175
Therefore, the number of students who have not taken any of the 3 courses is = Total students – students taking at least 1 course = 200 – 175 = 25


Computer Science Set Theory and Algebra Questions and Answers

Question 39.
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 x in A is related to an element y in B (under R1) if x + y is divisible by 3.
(ii) An element x in B is related to an element y in C (under R2) if x + y 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), (7, 3)}
(b) R1R2={1, 2), (1, 3), (3, 2), (5, 2), (7, 3)}
(c) R1R2={1, 2), (3, 2), (3, 4), (5, 4), (7, 2)}
(d) R1R2={(3, 2), (3, 4), (5, 1), (5, 3), (7, 1)}

Answer/Explanation

Answer: (c) R1R2={1, 2), (3, 2), (3, 4), (5, 4), (7, 2)}
Explanation:
R1 = {(An element x in A, An element y in B) if x + y divisible by 3}
R1 = {(1, 2), (1, 8), (3, 6), (5, 4), (7, 2), (7, 8)}
R2 = {(An element x in B, An element y in C) if x + y is even but not divisible by 3}
R2 = {(2, 2), (4, 4), (6, 2), (6, 4), (8, 2)}
So, R1 o R2 = {(1, 2), (3, 2), (3, 4), (5, 4), (7, 2)}.


Question 40.
The following is the incomplete operation table of a 4-element group.

 

Computer Science Set Theory and Algebra Questions and Answers chapter 2 img 3

The last row of the table is
(a) c a e b
(b) c b a e
(c) c b e a
(d) c e a b

Answer/Explanation

Answer: (d) c e a b
Explanation:
Step 1:
By looking at the row for e, we see that it is a copy of the column headers. So e must be the identity element. Since right identity and left identity elements must both be the same. The column corresponding to e must be a copy of the row headers. We can now say that the operation table is:

Computer Science Set Theory and Algebra Questions and Answers chapter 2 img 15

 

Step 2:
From the table above we see that a*c = e
∴ c*a must also be = e (if a is the inverse of c, then c is the inverse of a)
Now the operation table looks like

Computer Science Set Theory and Algebra Questions and Answers chapter 2 img 16

 

Step 3:
The blank in the second column must he c (since in a Cayley table, every row and every column is a unique permutation of the row and column headers).
Now the operation table looks like

Computer Science Set Theory and Algebra Questions and Answers chapter 2 img 17

 

Step 4:
Now the blanks in the third row can be filled as a, e or e, a. Let us try each one in turn. If we fill a, e in the third row the operation table will look like

Computer Science Set Theory and Algebra Questions and Answers chapter 2 img 18

 

Now the blank in the fourth row and third column must be filled by e. However, this is not possible since e is already entered in the fourth row and second column. Therefore filling a, e in third-row blanks is wrong. So let us try filling the third-row blanks with e, a Now the operation table looks like

Computer Science Set Theory and Algebra Questions and Answers chapter 2 img 19

 

Now the blanks in the fourth row have to be filled with a, b The final operation table looks like

Computer Science Set Theory and Algebra Questions and Answers chapter 2 img 20

 

which is consistent with all the rules of a Cayley Table. The last row of this table is c, e, a, b Therefore the correct answer is (d).


Question 41.
The inclusion of which of the following sets into S = {{1, 2}, {1,2,3}, {1, 3, 5}, {1, 2, 4}, {1, 2, 3, 4, 5}} is necessary and sufficient to make S a complete lattice under the partial order defined by set containment?
(A) {1}
(b) {1}, {2, 3}
(c) {1}, {1, 3}
(d) {1}, (1, 3}, {1, 2, 3, 4}, {1, 2, 3, 5}

Answer/Explanation

Answer: (A) {1}
Explanation:
The hasse diagram of the given post is:

Computer Science Set Theory and Algebra Questions and Answers chapter 2 img 21

 

In a complete lattice L, every nonempty subset of L has both LUB and GLB. Now it is necessary to add {1} since GLB of {1,2} and {1, 3, 5} is {1}. The hasse diagram now becomes:

Computer Science Set Theory and Algebra Questions and Answers chapter 2 img 22

 

Now the above hasse diagram represents a complete lattice since every nonempty subset has both LUB and GLB. Therefore adding {1} is not only necessary but it is also sufficient to make the given lattice a complete lattice. Therefore the correct choice is (a).


Question 42.
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 these

Answer/Explanation

Answer: (a) X = Y
Explanation:
X = (A-B) – C
= (A ∩ B’) – C
= (A ∩ B’) ∩ C’
= AB’C’
Y= (A-C)-(B-C)
= (A ∩ C) – (B ∩ C’)
= (AC’) – (BC’)
= (AC’) ∩ (BC’)’
= (AC’) ∩ (B’ + C)
= (AC’) . (B’ + C)
= AC’B’ + AC’C
= AC’B’ (Since C’C = 0)
= AB’C’ (commutative property)
∴ X =Y


Computer Science Set Theory and Algebra Questions and Answers

Question 43.
The following is the Hasse diagram of the poset [{a, b, c, d,e}, ≤]

 

Computer Science Set Theory and Algebra Questions and Answers chapter 2 img 4

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/Explanation

Answer:(b) a lattice but not a distributive lattice
Explanation:

Computer Science Set Theory and Algebra Questions and Answers chapter 2 img 23

 

The poset [{a, b, c, d, e}, ≤ ] is a lattice (since every pair of elements has LUB and GLB) but it is not a distributive lattice. Because distributive lattice satisfies the following conditions. For any x, y, z,
x ∧ (y v z) — (x ∧ y) v (x ∧ z)
x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z)
Where ∧ and ∨ are meet and join operations but for given poset [{a, b, c, d, e} ≤]
b ∧ (c ∨ d) = b ∧ a = b
(b ∧ c) ∨ (b ∧ d) = e ∨ e = e
So it is not distributive. (Also, element b has 2 complements c and d, which is not possible in a distributive lattice, since, in a distributive lattice, complement if it exists, is always unique).


Question 44.
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/Explanation

Answer: (c) 4 and 13
Explanation:
The set S = {1, 2, 4, 7, 8, 11, 13, 14} is a group under multiplication modulo 15.
The identity element for this group is e = 1 since,
∀x ∈ S, 1 . x mod 15 = x
Now let the inverse of 4 be 4-1.
Now (4 . 4-1) mod 15 = e = 1
Since (4 . 4) mod 15=1
∴ 4-1 = 4 (This inverse is unique)
Similarly let the inverse of 7 be 7-1
(7 . 7-1) mod 15=1
putting each element of set as 7-1 by trial and error we get
(7 . 13) mod 15 = 91 mod 15=1
∴ 7-1 = 13
So, 4-1 and 7-1 are respectively 4 and 13. The correct choice is (c).


Question 45.
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/Explanation

Answer: (c) R ∩ S is an equivalence relation
Explanation:
R ∩ S is an equivalence relation as can be seen from proof given below.
Let ∀x ∈ A (x, x) ∈ R and (x, x) ∈ S (since R and S are reflexive)
∴ (x, x) ∈ R n S also ∴ R ∩ S is reflexive.
Now, (x, y) ∈ R ∩ S
⇒ (x, y) ∈ R and (x, y) ∈ S
⇒ (y, x) ∈ R and (y, x) ∈ S
(Since R and S are symmetric)
⇒ (y,x) ∈ R ∩ S
∴ (x, y) ∈ R ∩ S
⇒ (y, x) ∈ R ∩ S
R ∩ S is therefore symmetric Now consider
(x, y) and (y, z) ∈ R ∩ S ⇒ (x, y) and (y, z) ∈ R and (x, y) and (y, z) ∈ S ⇒ (x, z) ∈ R and (x, z) ∈ S
(Since R and S are transitive)
⇒ (x, z) ∈ R ∩ S
∴ R ∩ S is transitive also. Since R ∩ S is reflexive, symmetric, and transitive.
∴ R ∩ S is an equivalence relation.
Note: A similar argument cannot be made from R ∪ S.


Question 46.
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 not be onto
(d) both f and g need not be onto

Answer/Explanation

Answer: (b) f should be onto but g need not be onto
Explanation:
Consider the arrow diagram shown below:

Computer Science Set Theory and Algebra Questions and Answers chapter 2 img 24

 

h(a) = f . g(a) = α
h(b) = f . g(b) = β
Here f is onto but g is not onto, yet h is onto. As can be seen from the diagram if f is not onto, h cannot be onto.
∴ f should be onto, but g need not be onto.
∴ The answer is (b).


Computer Science Set Theory and Algebra Questions and Answers

Question 47.
Consider the set H of all 3 × 3 matrices of the type

Computer Science Set Theory and Algebra Questions and Answers chapter 2 img 25

 

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/Explanation

Answer: (a) a group
Explanation:
(i) The set H is closed since the multiplication of upper triangular matrices will result only in the upper triangular matrix.
(ii) Matrix multiplication is associative, i.e.
A * (B * C) = (A * B) * C.
(iii) Identity element is

Computer Science Set Theory and Algebra Questions and Answers chapter 2 img 26

 

and this belongs to H as I is an upper triangular as well as a lower triangular matrix.

(iv) If A ∈ H, then | A | = abc. Since it is given that abc ≠ 0, this means that |A | ≠ 0 i.e. every matrix belonging to H is non-singular and has a unique inverse.
∴ the set H along with matrix multiplication is a group.


Question 48.
Let f be a function from a set A to a set B, g a function from B to C, and h a function from A to C, such that h(a) = g(f(a)) for all an ∈ A. Which of the following statements is always true for all such functions f and g?
(a) g is onto ⇒ h is onto
(b) h is onto ⇒ f is onto
(c) h is onto ⇒ g is onto
(d) h is onto ⇒ f and g are onto

Answer/Explanation

Answer: (c) h is onto ⇒ g is onto
Explanation:
Given, h = g(f(x)) = g.f
Consider the following arrow diagram:

Computer Science Set Theory and Algebra Questions and Answers chapter 2 img 27

 

From the above diagram it is clear that g is not onto ⇒ h = g.f is also not onto, since the co-domain of g is the same as the co-domain of g.f. The contrapositive version of the above implication is h is onto ⇒ g is onto which also has to be true since direct = contrapositive. So option (c) is true.


Question 49.
Let A be a set with n elements. Let C be a collection of distinct subsets of A such that for any two subsets S1 and S2 in C, either S1 ⊂ S2 or S2 ⊂ S1 What is the maximum cardinality of C?
(a) n
(b) n+1
(c) 2n-1 +1
(d) n!

Answer/Explanation

Answer: (b) n+1
Explanation:
The way C is defined in the question contains only comparable subsets of A. i.e. the set C is the set of all comparable subsets of set A. Such a set is called a chain. Consider an example with set A = {1, 2} Subsets are Φ, {1}, {2} and {1, 2} Maximum cardinality of collection of distinct subsets is {Φ, {1} and {1, 2}} i.e. 3. So with n elements, the maximum cardinality is n + 1.


Computer Science Set Theory and Algebra Questions and Answers

Question 50.
For the set N of natural numbers and a binary operation f: N × N → N, an element z ∈ N is called an identity for f, if f(a, z) = a = f(z, a), for all an e N. Which of the following binary operations have an identity?
I. f(x, y) = x + y – 3
II. f(x, y) = max(x, y)
III. f(x, y) = xy
(a) I and II only
(b) II and III only
(c) I and III only
(d) None of these

Answer/Explanation

Answer: (d) None of these
Explanation:
I. f(x) = x + y – 3
x + a – 3 = x = a + x – 3
so a = 3
Now 3 is unique, and 3 ∈ N So I has identity.
II: f(x) = max(x, y)
max(x, a) = x = max(a, x)
In N, the only value of a which will satisfy the above equation is a = 1.
Since 3 is unique, and 3 ∈ N So II has an identity.

III. f(x) = xy
xa = x = ax
Now xa = x ⇒ a = 1, but x= ax has no solution for a in the set N.
So III has no identity.
So only I and II have an identity.


Question 51.
Let, X, Y, Z be sets of sizes x, y, and z respectively. Let W = X × Y and E be the set of all subsets of W. The number of functions from Z to E is
(a) z
(b) 2 × 2xy
(c) 2z
(d) 2xyz

Answer/Explanation

Answer: (d) 2xyz
Explanation:
Given | X | = x, | Y | = y and | Z | = z W = X × Y
So | W| = xy
| E | = 2|W| =2xy
So the number of functions for Z to E = | E | |z|
= (2xy)z = 2xyz


Question 52.
The set {1, 2, 3, 5, 7, 8, 9} under multiplication modulo 10 is not a group. Given below are four possible 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/Explanation

Answer: (c) 3 does not have an inverse
Explanation:
Let A = {1, 2, 3, 5, 7, 8, 9}
Construct the table for any x, y ∈ A such that x * y = (x.y) mod 10

Computer Science Set Theory and Algebra Questions and Answers chapter 2 img 28

 

We know that 0 ∉ A. So it is not closed. Therefore, (a) is true.
The identity element = 1
∴ (2 . 2-1) mod 10 = 1
From the table, we see that 2-1does not exist. Since, (3 . 7) mod 10 = 1
∴ 7 is the inverse of 3 and 7 ∈ A.
(c) is false.
(d) is true since 8 does not have an inverse.


Question 53.
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
(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/Explanation

Answer: (a) Neither a Partial Order nor an Equivalence Relation
Explanation:
(x, y) R (u, v) iff x < u and y > v
(x, x) (x, x) since x / x and x / x
So R is not reflexive,
∴ R is neither a partial order, nor an equivalence relation.


Question 54.
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/Explanation

Answer: (c) X = Y
Explanation:
Consider the following Venn diagram for X = (E ∩ F) – (F ∩ G)

Computer Science Set Theory and Algebra Questions and Answers chapter 2 img 29

Y = (E -(E ∩ G)) – (F – F)

Computer Science Set Theory and Algebra Questions and Answers chapter 2 img 30

So, X = Y
or alternatively the solution can be obtained from boolean algebra as follows:
X = (E ∩ F) – (F ∩ G)
= EF – FG
= EF ∩ (FG)’
= EF . (F’ + G’)
= EFF’ + EFG’
= EFG’
Similarly, Y = (E -(E ∩ G)) – (E – F)
= (E – EG) – (E . F’)
= E . (EG)’ – EF’
= E . (E’ + G’) – EF’
= EG’ – EF’
= EG’ . (EF’)’
= EG’ . (E’ + F)
= EE’ G’ + EFG’
= EFG’
Therefore X = Y


Computer Science Set Theory and Algebra Questions and Answers

Question 55.
Let S = {1, 2, 3,…, m}, m > 3. Let X1, X2,…, 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 contains the element i. That is f(i) = | {j | i∈ Xj} |.
Then \(\sum_{i=1}^{m}\) (i) is
(a) 3m
(b) 3n
(c) 2m +1
(d) 2n + 1

Answer/Explanation

Answer: (b) 3n
Explanation:
The problem can be solved by considering the cases m = 4 and m = 5 etc.
Let, m = 4
S = {1, 2, 3, 4}
n = number of 3 element subsets
= 4C3 = 4C1 = 4
n = 4
The 4 subsets are {1, 2, 3}, {1, 2, 4}, {1, 3, 4} and {2, 3, 4}
f(1) = number of subsets having 1 as an element = 3
f(2) = number of subsets having 2 as an element = 3
f(3) = 3 and f(4) = 3
∴ \(\sum_{i=1}^{4} f(i)\) = 3 + 3 + 3 + 3=12

Both choice (a) and choice (b) are matching the answer since
3m = 3n = 12
Now let us try m = 5
S = {1, 2, 3, 4, 5}
n = number of 3 element subsets = 5C3 = 10
∴ n = 10
The 10 subsets are {1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 3, 4}, {1, 3, 5}, {1, 4, 5}, {2, 3, 4}, {2, 3, 5}, {2, 4, 5}, {3, 4, 5}
f(1) = f(2) = f(3) = f(4) = f(5) = 6
\(\sum_{i=1}^{5} f(i)\) = 6 + 6 + 6 + 6 + 6 = 30

Clearly 3m = 3 × 5 = 15{is not matching Σf(i)} But
3n = 3 × 10 = 30 {is matching Σf(i) = 30}
∴ 3 n is the only correct answer.
The correct choice is (b).
The problem can also be solved in a more general way as follows:

\(\sum_{i=1}^{m} f(i)\) = f(1) + f(2) + ……+ f(m)
Since, f(1) = f(2) =…….= f(m) = (m-1)C2
= \(\frac{\mathrm{m} \times(\mathrm{m}-1) \times(\mathrm{m}-2)}{2}\)
= \(\frac{3 \times \mathrm{m} \times(\mathrm{m}-1) \times(\mathrm{m}-2)}{1 \times 2 \times 3}\)
= 3 × mC3
Since n = Number of there elements subsets of a set of m elements = mC3
Therefore, \(\sum_{i=1}^{m} f(i)\) = 3 × mC3 = 3n


Question 56.
Let P, Q, and R be set to let △ denote the symmetric difference operator defined as P △ Q = (P ∪ Q) — (P ∩ Q). Using Venn diagrams, determine which of the following is/are TRUE?
I. P △ (Q ∩ R) = (P △ Q) ∩ (P △ R)
II. P ∩ (Q △ R) = (P ∩ Q) △ (P ∩ R)
(a) I only
(b) II only
(c) Neither I nor II
(d) Both I and II

Answer/Explanation

Answer: (b) II only
Explanation:
P △ Q = PQ’ + P’Q
where △ is symmetric difference between P and Q.
I. LHS = P △ Q ∩ R = P△(QR) = P(QR)’ + P'(QR) = P(Q’ + R’) + P’QR
RHS = (P △ Q) ∩ (P △ R) = (PQ’ + P’Q) (PR’ + P’R) = PQ’R’ + P’QR
LHS ≠ RHS So statement I is false.

II. LHS = P ∩ Q △ R = P(QR’ + Q’R)
= PQR’ + PQ’R
RHS = (P ∩ Q) △ (P ∩ R) = PQ △ PR = PQ(PR)’ + (PQ)’ PR = PQ(P’ + R’) + (P’+Q’)PR = PQR’ + PQ’R
LHS = RHS
So statement II is true.


Question 57.
What is the cardinality of the set of integers X defined below? X = {n| 1 ≤ n ≤ 123, n is not divisible by 2, 3 or 5}
(a) 28
(b) 33
(c) 37
(d) 44

Answer/Explanation

Answer: (b) 33
Explanation:
We know that, number of elements divisible by number ‘x’ in set of integer (from 1 to X) = \(\frac{X}{x}\)
So, according to inclusion exclusion formula:
n(2 or 3 or 5) = n(2) + n(3) + n(5) – n(2,3) – n(2,5) – n(3,5) – n (2,3,5))
No’s divisible by 2 in X = \(\left[\frac{123}{2}\right\rfloor\) = 61
No’s divisible by 3 in X = \(\left[\frac{123}{3}\right\rfloor\) = 41
No’s divisible by 5 in X = \(\left[\frac{123}{5}\right\rfloor\) = 24
No’s divisible by 2 and 3 = \(\left.\mid \frac{123}{2 \times 3}\right\rfloor\) = \(\left[\frac{123}{6}\right\rfloor\) = 20
No’s divisible by 3 and 5 = \(\left.\mid \frac{123}{3 \times 5}\right\rfloor\) = \(\left[\frac{123}{15}\right\rfloor\) = 8
No’s divisible by 2 and 5 = \(\)
No’s divisible by 2 and 3 and 5
The problem can be solved by considering the cases m = 4 and m = 5 etc.
= \(\left[\frac{123}{2 \times 3 \times 5}\right\rfloor\) = \(\left[\frac{123}{30}\right\rfloor\) = 4
So, n(2 or 3 or 5) = 61 + 41 +24 — 20 — 8-12 + 4 = 90
n(2 or 3 or 5) = Total number – n(2 or 3 or 5) = 123-90 = 33


Computer Science Set Theory and Algebra Questions and Answers

Question 58.
Let S be a set of n elements. The number of ordered pairs in the largest and the smallest equivalence relations on S is
(a) n and n
(b) n2 and n
(c) n2 and 0
(d) n and 1

Answer/Explanation

Answer: (b) n2 and n
Explanation:
Let S be a set of n elements say {1, 2, 3,…, n}. Now the smallest equivalence relation on S must contain all the reflexive elements {(1, 1), (2, 2), (3, 3),…, (n, n)} and its cardinality is therefore n. The largest equivalence relation on S is S × S, which has a cardinality of n × n = n2.
∴ The largest and smallest equivalence relations on S have cardinalities of n2 and n respectively. The correct choice is (b).


Question 59.
Consider the set S = {a, b, c, d}. Consider the following 4 partitions π12, π3, π4 on
S: π1 = \(\{\overline{a b c d}\}\) , π2 = \(\{\overline{a b}, \overline{c d}\}\) , π3 = \(\{\overline{a b c}, \bar{d}\}\) , π4 = \(\{\bar{a}, \bar{b}, \bar{c}, \bar{d}\}\)
Let ≺ be the partial order on the set of partitions S’ = (π12, π3, π4) defined as follows: πi≺ πj if and only if πi refines πj The poset diagram for (S’, ≺) is

 

Computer Science Set Theory and Algebra Questions and Answers chapter 2 img 5

Answer/Explanation

Answer: (c)
Explanation:
A partition P1 is called a refinement of the partition P2 if every set in P1, is a subset of one of the sets in P2.
π4 is a refinement of π23, and π1
π2 and n3 are refinements of π1
π2 and π3 are not comparable since neither is a refinement of the other.
So the poset diagram for (S’, <) would

Computer Science Set Theory and Algebra Questions and Answers chapter 2 img 31

 

Which is choice (c).


Question 60.
A partial order P is defined on the set of natural numbers as follows. Here x/y denotes integer division.
(i) (0, 0) ∈P.
(ii) (a, b) ∈P if and only if a %10 ≤ b %10 and (a/10, b/10) ∈P.
Consider the following ordered pairs:
(i) (101, 22)
(ii) (22, 101)
(iii) (145, 265)
(iv)(0, 153)
Which of these ordered pairs of natural numbers are contained in P?
(a) (i) and (iii)
(b) (ii) and (iv)
(c) (i) and (iv)
(d) (iii) and (iv)

Answer/Explanation

Answer: (d) (iii) and (iv)
Explanation:
In this problem
a % b means the mod function (i.e. residue when a is divided by b).
a/b means integer division (i.e. quotient when a is divided by b)
(i) (101,22):
101% 10 ≤ 22% 10 ⇒ 1 ≤ 2 which is true. (101/10, 22/10) = (10, 2) ∈ P need to check IS (10, 2) ∈ P?
10% 10 ≤ 2% 10 ⇒ 0 ≤ 2 which is True.
Then (10/10, 2/10) = (1, 0) fails since 1 < 0.
∴ (101, 22) ∉ P.

(ii) (22, 101)
22% 10 ≤ 101% 10 ⇒ 2 ≤ 1 is False.
∴ (22, 101)∉ P

(iii) (145, 265)
145% 10 ≤ 265% 10 ⇒ 5 ≤ 5 is true and (145/10, 265/10) = (14, 26) e P has to be checked.
Now consider (14, 26).
14% 10 ≤ 26% 10 ⇒ 4 ≤ 6 is true and (14/10, 26/10) = (1, 2) ∈ P has to be checked. Now consider (1, 2)
1% 10 ≤ 2% 10 ⇒ 1 ≤ 2 is true and (1/10, 2/10) = (0, 0) ∈ P which is given to be true. Therefore (145, 265) ∈ P.

(iv) (0, 153):
0% 10 ≤ 153% 10 ⇒ 0 ≤ 3 is true.
Then (0/10, 153/10) = (0, 15) should be in P. (0, 15):
0% 10 ≤ 15% 10 ⇒ 0 ≤ 5 is true.
Then (0/10, 15/10) = (0, 1) should be in P. (0, 1):
0% 10 ≤ 1% 10 ⇒ 0 ≤ 1 is true.
Then (0/10, 1/10) = (0, 0) should be in P. It is given that (0, 0) ∈ P Therefore (0, 153) ∈ P.
So (iii) and (iv) are contained in P.


Question 61.
If P, Q, R are subsets of the universal set
U, then (P∩Q∩R) ∪ (Pc ∩ Q ∩ R) ∪ Qc ∪ Rc is
(a) Qc ∪ Rc
(b) P ∪ Qc ∪ Rc
(c) Pc ∪ Qc ∪ Rc
(d) U

Answer/Explanation

Answer: (d) U
Explanation:
The given set theory expression can be converted into equivalent boolean algebra expression as follows:
(p∩q∩r) ∪ (pc ∩ q ∩ r) ∪ qc ∪ rc
= p.q.r + p’.q.r + q’ + r’
= qr (p + p’) + q’ + r’
= qr + q’ + r’
= (q + q’) . (r + q’) + r’
= r + q’ + r’
= r + r’ + q’
= 1 + q’
= 1 = U


Computer Science Set Theory and Algebra Questions and Answers

Question 62.
Consider the following Hasse diagrams.

 

Computer Science Set Theory and Algebra Questions and Answers chapter 2 img 6

Which all of the above represent a lattice?
(a) (i) and (iv) only
(b) (ii) and (iii) only
(c) (iii) only
(d) (i), (ii) and (iv) only

Answer/Explanation

Answer: (a) (i) and (iv) only
Explanation:
In lattice, every pair in the Hasse diagram must have Least Upper Bound (LUB) and Greatest Lower Bound (GLB). In figure

Computer Science Set Theory and Algebra Questions and Answers chapter 2 img 32

 

For element d, e LUB (d, e) = {b, c} but LUB must be unique i.e. only 1 element present in LUB. Same for GLB (b, c) = {d, e} Hence not lattice.

Computer Science Set Theory and Algebra Questions and Answers chapter 2 img 33

 

GLB (b, d) = {c, e} but GLB must be unique i.e. only 1 element present in GLB. Hence not lattice. So, (ii) and (iii) are not lattice


Question 63.
Which one of the following is NOT necessarily a property of a Group?
(a) Commutativity
(b) Associativity
(c) Existence of inverse for every element
(d) Existence of identity

Answer/Explanation

Answer: (a) Commutativity
Explanation:
Group properties are closure, associativity existence of identity, and existence of inverse for every element. Commutativity is not required for a mathematical structure to become a group.


Question 64.
Consider the binary relation: R = {(x, y), (x, z), (z, x), (z, y)} on the set {x, y, z}. Which one of the following is TRUE?
(a) R is symmetric but NOT antisymmetric
(b) R is NOT symmetric but antisymmetric
(c) R is both symmetric and antisymmetric
(d) R is neither symmetric nor antisymmetric

Answer/Explanation

Answer: (d) R is neither symmetric nor antisymmetric
Explanation:
Given, R {(x, y), (x, z), (z, x), (z, y)) on set {x, y, z}, here (x, y) ∈ R and (y, x) ∉ R.
∴ R is not symmetric
Also(x, z)ER and(z, x) ∈ R.
∴ R is not an autism metric.
R is neither symmetric nor anti-symmetric.


Question 65.
The composition table of a cyclic group is shown below:

 

Computer Science Set Theory and Algebra Questions and Answers chapter 2 img 7

Which one of the following choices is correct?
(a) a, b are generators
(b) b, c are generators
(c) c, d are generators
(d) d, a are generators

Answer/Explanation

Answer: (c) c, d are generators
Explanation:
If an element is a generator, all elements must be obtained as powers of that element.
Try a, b, c, d one by one to see which are the generators.
a = a
a2 = a.a = a
a3 = a.a2 = a.a = a and so on.
∴ a is not the generator,
b = b
b2 = b.b = a
b3 = b.b2 = b.a = b
b4 = b.b3 = b.b = a and so on

∴ b is not the generator c = c
c2 c.c = b
c3 = c.c2 = c.b = d
c4 = c.c3 = c.d = a
Since all of a, b, c, d have been generated as powers of c

∴ c is a generator of this group.
Similarly,
d = d
d2 = d.d = b
d3 = d.d2 d.b = c
d4 = d.d3 = d.c a
∴ d is the other generator.


Computer Science Set Theory and Algebra Questions and Answers

Question 66.
What is the possible number of reflexive relations on a set of 5 elements?
(a) 210
(b) 215
(c) 220
(d) 225

Answer/Explanation

Answer: (c) 220
Explanation:
A number of reflexive relations on a set with n elements = 2n² – n.
Here n = 5. So, answer is 25² – 5 = 220.


Question 67.
Consider the set S = {1, ω, ω2}, where ω and ω2 are cube roots of unity. If * denotes the multiplication operation, the structure {S, *} forms
(a) a group
(b) a ring
(c) an integral domain
(d) a field

Answer/Explanation

Answer: (a) a group
Explanation:
The structure ({n, nth roots of unity}, ×) always forms a group. When n = 3 we get the set ({1, w, w2}, ×) which must also form a group.
or
The fact that ({1, w, w2}, × ) forms a group can also be seen by the fact that it satisfies the four group properties.

Computer Science Set Theory and Algebra Questions and Answers chapter 2 img 34

 

From the above operation table, we can see that the given operation is closed, on the given set.
2. Associative: “*” is an associative operation.
3. Identity: From the operation table, we can see that the identity element, is “1”.
4. Inverse: From the operation table, we can see that the inverse of 1 is 1, the inverse of w is w2 and the inverse of w2 is w.
So, ({1, w, w2}, *) is a group.
To be a ring, integral domain, or field, we need two binary operations to be specified, whereas here we have only one operation given. So, choice (a) is correct.


Question 68.
How many onto (or surjective) functions are there from an n-element (n ≥ 2) set to a 2-element set?
(a) 2n
(b) 2n – 1
(c) 2n– 2
(d) 2(2n-2)

Answer/Explanation

Answer: (c) 2n– 2
Explanation:
Let n = 2. There are only 2 onto functions as shown below:

Computer Science Set Theory and Algebra Questions and Answers chapter 2 img 35

 

For, n = 2
Option (a) 2n = 22 = 4
Option (b) 2n – 1 = 22 – 1 = 3
Option (c) 2n — 2 = 22 — 2 = 2
Option (d) 2(2n — 2) = 2(22 – 2) = 4
So only option (c) gives correct answer.
Alternate method:
The number of onto functions from a set A with m elements to set B with n elements where n < m is given by
nm – nC1(n- 1)m+ nC2(n —2)m … + nCn- 1 1m
Here, m = n = 2
So number of onto functions = 2n2C1 1m = 2n – 2
which is choice (c).


Question 69.
A binary operation ⊕ on a set of integers is defined as x ⊕ y = x2 + y2. Which one of the following statements is TRUE about ⊕?
(a) Commutative but not associative
(b) Both commutative and associative
(c) Associative but not commutative
(d) Neither commutative nor associative

Answer/Explanation

Answer: (a) Commutative but not associative
Explanation:
x ⊕ y = x2 + y2
y ⊕ x = y2 + x2
As ‘+’ sign in commutative so x2 + y2 is equal to y2 + x2 so x ⊕ y is commutative.
Now check associativity
x ⊕ (y ⊕ z) = x ⊕ (y2 + z2)
= x2 + (y2 + z2)2
= x2 + y4 + z4 + 2y2z2
(x ⊕ y) ⊕ z = (x2 + y2) ⊕ z
= (x2 + y2)2 + z2
= x4 + y4 + 2x2y2 + z2
x ⊕ (y ⊕ z) t- (x ⊕ y) ⊕ z
So not associative Option (a) is correct.


Computer Science Set Theory and Algebra Questions and Answers

Question 70.
Let S denote the set of all functions f: {0, 1}4 → {0,1}. Denote by N the number of functions from S to the set {0, 1}. The value of log2 log2N is ______.

Answer/Explanation

Explanation:
f : {0, 1}4 → {0,1} ⇒ S is the set of all functions from a 16 element set to a 2 element set.
| S | =216
N = Number of functions from S to 2 element set {0, 1} = 2216 ]
N = 22
∴ log log N = log log 22’6 = log2216 = 16


Question 71.
Consider the following relation on subsets of the set S of integers between 1 and 2014. For two distinct subsets U and U of S we say U Consider the following two statements:
S1: There is a subset of S that is larger than every other subset.
S2: There is a subset of S that is smaller than every other subset.
Which one of the following is CORRECT?
(a) Both S1 and S2 are true
(b) S1 is true and S2 is false
(c) S2 is true and S1 is false
(d) Neither S1 nor S2 is true

Answer/Explanation

Answer: (a) Both S1 and S2 are true
Explanation:
Given the following details:
S = {1,2,3,4,. ..2014}
U < V if the minimum element in the symmetric difference of the two sets is in U.
S1: There is a subset of S that is larger than every other subset.
S2: There is a subset of S that is smaller than every other subset.
S1 is true since Φ (which is a subset of S) is larger than every other subset.
i.e. ∀u v < Φ is true since the minimum element in v △ Φ = v, is in v.
(Note: v △ Φ = uΦ + v’Φ = v)
S2 is also true since S (which is a subset of S) is smaller than every other subset, i.e. ∀u S < v is true since the minimum element in S △ v = v’, is in <S.
(Note: S △ v = Sv’ + S’v = lv’ + Ov =v’)
∴ Both S1 and S2 are correct.


Question 72.
Let X and Y be finite sets and f: X → Y is a function. Which one of the following statements is TRUE?
(a) For any subsets A and B of X, | f(A ∪ B)| = |f(A)| + |f(B)|
(b) For any subsets A and B of X, |f(A ∪ B) = |f(A)| + |f(B)|
(c) For any subsets A and B of X, |f(A ∩ B)| = min{|f(A)|,|f(B)|}
(d) For any subsets S and Tof Y, f-1(S ∩ T) = f -1(S) ∩ f-1(T)

Answer/Explanation

Answer: (d) For any subsets S and Tof Y, f-1(S ∩ T) = f -1(S) ∩ f-1(T)
Explanation:
Example:

Computer Science Set Theory and Algebra Questions and Answers chapter 2 img 36

 

Let A = {1, 2}, B = {3, 4}
(a) |f (A ∪ B)| = |f(A) |+ |f(B)|
⇒ 3 = 2 + 2 is false

(b) f (A ∩ B) = f (A) ∩ f (B)
⇒ Φ = {a} is false

(c) |f(A ∩ B)| =min{|f(A)|, |f(B)|}
⇒ 0 = min (2, 2) = 2 is false

(d) Let S = {a, b}, T- {a, c}
f-1 (S ∩ T)=f-1(S)∩ f-1(T)
⇒ {1, 3} = {1, 2, 3} n {1, 3, 4}
⇒ {1, 3} = {1, 3} is true


Question 73.
Let G be a group with 15 elements. Let L be a subgroup of G. It is known that L ≠ G and that the size of L is at least 4. The size of L is _____.

Answer/Explanation

Explanation:
Order of subgroup divides the order of group (Lagrange’s theorem). So the order of L has to be 1, 3, 5, or 15. As it is given that the subgroup has at least 4 elements and it is not equal to the given group, therefore the order of the subgroup can’t be 1, 3, or 15. Hence it is 5.


Question 74.
Consider the set of all functions f : {0,1, …, 2014} → {0,1, …,2014} such that f(f(i)) = i, for all 0≤i≤ 2014. Consider the following statements:
P: For each such function it must be the case that for every i, f(i) = i.
Q: For each such function it must be the case that for some i, f(i) = i.
R: Each such function must be onto.
Which one of the following is CORRECT?
(a) P, Q, and R are true
(b) Only Q and R are true
(c) Only P and Q are true
(d) Only R is true

Answer/Explanation

Answer: (b) Only Q and R are true
Explanation:
Since it is given that ∀i f(f(i)) = i
It means f . f = I i.e. f = f’-1 That is f is a symmetric function.
Statement P means that every symmetric function is an identity function which is false since there are many symmetric functions other than the identity function.

Example: {(0,1), (1,0), (2, 3), (3,2),…(2012,2013),(2013, 2012), (2014, 2014)} is a symmetric function but not the identity function.

Statement Q means that in every such symmetric function at least one element is mapped to itself and this is true since there is an odd number of elements in the set {0, 1, 2, … 2014}.

Statement R means that every symmetric function is onto which is true since it is impossible to make an into function symmetric. See the below diagram for an into function shown with only 3 elements:

Computer Science Set Theory and Algebra Questions and Answers chapter 2 img 37

 

In the above function note that (2, 1) exists in the function but not (1,2) and so it is not symmetric.


Question 75.
There are two elements x,y in a group (G, *) such that every element in the group can be written as a product of some number of x’s and y’s in some order. It is known that x*x = y*y = x*y*x*y = y*x*y*x = e where e is the identity element. The maximum number of elements in such a group is______.

Answer/Explanation

Explanation:
(i) e is identity element
(ii) x*x = e, so x = x-1.
(iii) y*y = e, so y = y-1.
(iv) (x*y)*(x*y) = e, so x*y = (x*y)-1 and (y*x)*(y*x) = e, so y*x = (y*x)-1.
Now (x*y)*(y*x) = x*(y*y)*x = x*e*x = x*x = e
So, (x*y)-1. = (y*x)
From (i) and (ii) we get x*y* = y*x
There are only 4 distinct elements possible in this group
1. e
2. x
3. y
4. xy
All other combinations are equal to one of these four as can be seen below:
yx = xy (already proved)
xxx = xe = x
xyy = xe = x
xxy = ey = y
xyx = xxy = y
and so on…….
So the group is G = {e, x, y, x*y
⇒ |G| = 4


Computer Science Set Theory and Algebra Questions and Answers

Question 76.
If g(x) =1 -x and h(x) = \(\frac{x}{x-1}\) , then \(\frac{g(h(x))}{h(g(x))}\) is
(a) \(\frac{h(x)}{g(x)}\)
(b) \(\frac{-1}{x}\)
(c)\(\frac{g(x)}{h(x)}\)
(d) \(\frac{x}{(1-x)^{2}}\)

Answer/Explanation

Answer: (a) \(\frac{h(x)}{g(x)}\)
Explanation:
g(x) = 1 – x, h(x) = \(\frac{x}{x-1}\)
\(\frac{g(h(x))}{h(g(x))}\) = \(\frac{g\left(\frac{x}{x-1}\right)}{h(1-x)}\) = \(\frac{1-\frac{x}{x-1}}{\frac{1-x}{1-x-1}}\) = \(\frac{x-1-x}{\frac{x-1}{\frac{1-x}{-x}}}\) = \(\frac{\frac{-1}{x-1}}{\frac{1-x}{-x}}\) = \(\frac{x}{(x-1)(1-x)}\) = \(\frac{-x}{(1-x)^{2}}\)
\(\frac{h(x)}{g(x)}\) = \(\frac{x}{\frac{x-1}{1-x}}\) = \(\frac{x}{(1-x)(x-1)}\) = \(\frac{-x}{(1-x)^{2}}\)
∴ \(\frac{g(h(x))}{h(g(x))}\) = \(\frac{h(x)}{g(x)}\)


Question 77.
For a set A, the power set of A is denoted by 2A. If A = {5, {6}, {7}}, which of the following options are True?
1. Ø ∈ 2A
2. Ø ⊆ 2A
3. {5,{6}} ∈ 2A
4. {5,{6}} ⊆ 2A
(a) 1 and 3 only
(b) 2 and 3 only
(c) 1, 2 and 3 only
(d) 1, 2 and 4 only

Answer/Explanation

Answer: (c) 1, 2, and 3 only
Explanation:
A = {5, {6}, {7}}
1. Φ ∈ 2A is true. Any power set contains an empty set.
2. Φ ⊆ 2A is true. Empty set is subset of any set.
3. {5, {6}}e 2A is true, power set of A contain {5, {6}} as a 2 element subset of A.
4. {5, {6}} ⊆ 2A is false. Power set of A not contain 5 and {6} as elements.
So {5, {6}} can not be subset of 2A.


Question 78.
Suppose L = {p,q, r, s, t} is a lattice represented by the following Hasse diagram:

Computer Science Set Theory and Algebra Questions and Answers chapter 2 img 38

For any xy ∈ L, not necessarily distinct, x ∨ y and x ∧ y are join and meet of x, y respectively. Let L<sup>3</sup> = {(x,y,z): x, y, z ∈ L} be the set of all ordered triplets of the elements of L. Let pr be the probability that an element (x,y,z) e L<sup>3</sup> chosen equiprobably satisfies x ∨ (y ∧ Z) = (x ∨ y) ∧ (x ∨ z). Then
(a) P<sub>r</sub> = 0
(b) p<sub>r</sub> = 1
(c) 0<p<sub>r</sub>≤\(\frac { 1 }{ 5 }\)
(d) \(\frac { 1 }{ 5 }\) < p<sub>r</sub> < 1

Answer/Explanation

Answer: (d) \(\frac { 1 }{ 5 }\) < p<sub>r</sub> < 1
Explanation:
L has 5 elements
L3 has all ordered triplets of elements of L
⇒ L3 contain 5 × 5 × 5 = 53 = 125 elements.

Gate Questions on Set Theory and Algebra chapter 2 img 38

If q, r, s are chosen, then only it will violate the distributive property. Number of ways to choose q, r, s in any triplet order = 3! = 3 × 2 × 1 = 6.
∴ p(satisfying distributive property)
= 1 – p(violate the distributive property)
= 1 – \(\frac{6}{5^{3}}\) = 0.952 which is between \(\frac{1}{5}\) and 1.


Question 79.
Let R be the relation on the set of positive integers such that aRb if and only if a and b are distinct and have a common divisor other than 1. Which one of the following statements about R is True?
(a) R is symmetric and reflexive but not transitive
(b) R is reflexive but not symmetric and not transitive
(c) R is transitive but not reflexive and not symmetric
(d) R is symmetric but not reflexive and not transitive

Answer/Explanation

Answer: (d) R is symmetric but not reflexive and not transitive
Explanation:
aRb iff a and b are distinct a and b have a common divisor other than 1.
(i) R is not reflexive since a and b are distinct i.e, (a, a) ∉ R
(ii) R is symmetric If a and b are distinct and have a common divisor other than 1, then b and a also are distinct and have a common divisor other than 1.
(iii) R is not transitive
If (a, b) ∈ R and (b, c) ∈ R then (a, c) need not be in R.
Example: (2, 6) ∈ R and (6, 2) ∈ R, but (2, 2) ∉ R
∴ R is symmetric but not reflexive and not transitive.


Question 80.
The cardinality of the power set of {0, 1,2…, 10} is _____.

Answer/Explanation

Explanation:
Let X = {0, 1,2,…..10}
|X| = 1
|P(X)| = 211 = 2048


Computer Science Set Theory and Algebra Questions and Answers

Question 81.
The number of onto functions (surjective functions) from set X = {1,2,3,4} to set Y = {a, b, c} is _____.

Answer/Explanation

Explanation:

Computer Science Set Theory and Algebra Questions and Answers chapter 2 img 39

 

The number of onto functions from A → B where | A | = m and | B | = n is given by the formula
nm – nC1(n – 1)m + nC2(n – 2)m +…
+ (-1)n – 1 nCn – 11m

Here, m = 4 and n = 3
Substituting in above formula we get, 343C1(3 – 1)4 + 3C2 (3 – 2)4 = 81 – 48 + 3 = 36


Question 82.
Let X and Y denote the sets containing 2 and 20 distinct objects respectively and F denote the set of all possible functions defined from X and Y. Let f be randomly chosen from F. The probability of f being one-to-one is _______.

Answer/Explanation

Explanation:

Computer Science Set Theory and Algebra Questions and Answers chapter 2 img 40

 

Total possible functions = 202 = 400
Number of one-to-one functions = 20P2 = 20 × 19
∴ Required probability = \(\frac{20 \times 19}{20 \times 20}\) = 0.95


Question 83.
Let # be a binary operator defined as X # Y = X’ + Y’ where X and Y are Boolean variables. Consider the following two statements:
S1:(P # Q) # R = P # (Q # R)
S2:Q # R = R # Q
Which of the following is/are true for the Boolean variables P, Q, and R?
(a) Only S1 is True
(b) Only S2 is True
(c) Both S1 and S2 are True
(d) Neither S1 nor S2 is True

Answer/Explanation

Answer: (b) Only S2 is True
Explanation:
X # Y = X’ + Y’
This is the NAND operation. NAND is known to be commutative but not associative. So, only S2 is true.


Question 84.
Suppose U is the power set of the set S = {1,2,3,4,5,6}. For any Te U, let | T| denote the number of elements in T and T’ denote the complement of T. For any T, R ∈ U, let T \ R be the set of all elements in T which are not in R. Which one of the following is true?
(a) ∀X ∈ U(|X| = |X’|)
(b) ∃X ∈ U ∃Y ∈U(|X|= 5, |Y|=5 and X ∩ Y = 0)
(c) ∀X ∈ U ∀Y ∈U(|X |=2,| Y|=3 and Y\F = 0)
(d) ∀X ∈U ∀ Y ∈U(X\Y =Y’\X’)

Answer/Explanation

Answer: (d) ∀X ∈U ∀ Y ∈U(X\Y =Y’\X’)
Explanation:
S = {1, 2, 3, 4, 5, 6}
U is the power set of S ⇒ U = P(S)
U ={{ } {1}, {2}, …{1, 2}, {1, 3}, …{1, 2, 3}, … {1, 2, 3, 4}, …{1, 2, 3, 4, 5} …{1, 2, 3, 4, 5, 6}}
| U |= 26 = 64 elements.
T ∈ U ⇒ T’ ∈ U
R ∈U, T\R=T – R

(a)∀X ∈ U(| X | = | X’ |) means that every subset of S has same size as its complement. Clearly this is False.
(For example, {1} ∈ U, and complement of {1} = {2, 3, 4, 5, 6})
(b)∃X ∈ U∃Y ∈ U(|X|=5,|Y|=5 and X ∩ Y = Φ) means that there are two 5 element subsets of S which have nothing in common. This is clearly False.
Since any two 5 element subsets will have atleast 4 elements in common.
(c) ∀X ∈ U ∀ Y ∈ U(|X| = 2,|y|=3 and X\Y = Φ) means that every 2 element subset X and every 3 element subset Y will have X – Y = Φ i.e., X ⊆ Y.
This is clearly False as can be seen from the example X= {1,2}, Y = {3,4,5} where X’^Y.
(d) ∀X ∈ U ∀T ∈ U(X \Y = Y’\X’) means that for any two subsets X and Y, X\ Y = Y \ X’ i.e. X – Y = Y’ – X’.
This is clearly True since by boolean algebra LHS = X – Y = XY’.
RHS =Y’ -X’ = Y’Xand therefore LHS = RHS.


Computer Science Set Theory and Algebra Questions and Answers

Question 85.
Let R be a relation on the set of ordered pairs of positive integers such that ((p, q), (r, s)) ∈ R if and only if p – s = q — r. Which one of the following is true about R?
(a) Both reflexive and symmetric
(b) Reflexive but not symmetric
(c) Not reflexive but symmetric
(d) Neither reflexive nor symmetric

Answer/Explanation

Answer: (c) Not reflexive but symmetric
Explanation:
R = {(p, q), (r, s) I p – s = q – r}
(i) Check reflexive property
∀(p, q) ∈ Z+ × Z+ ((p, q), (p, q)) ∈ R
is true iff p – q = q – p which is false. So relation R is not reflexive.
(ii) Check symmetry property
If ((p, q), (r, .s’))∈ R then ((r, s), (p, q)) ∈ R
((p, q), (r, s)) ∈ R ⇒ p – s = q – r
((r, s), (p, q)) ∈ R ⇒ r – q = s – p
If p – s = q – r is true, then r — q = s – p is also true by rearranging the equation.
∴ R is symmetric.


Question 86.
A function f : N++ → N+, defined on the set of positive integers N+, satisfies the following properties:
f(n) – f(nl2) if n is even
f(n) = f(n + 5) if n is odd
Let R = {i | ∃ j : f (j) = i} be the set of distinct values that/takes. The maximum possible size of R is _______.

Answer/Explanation

Explanation:
f(n) = f\(\left(\frac{n}{2}\right)\) if n is even
f(n) = f{n + 5) if n is odd
f : N+ → N+
Now f(2) = f\(\left(\frac{2}{2}\right)\) = f(1)
f(3) = f(3 + 5) = f(8) = f\(\left(\frac{8}{2}\right)\) = f(4) = f\(\left(\frac{4}{2}\right)\) = f(2) = (1)
So, f(1) = f(2) = f(3) = f(4) = f(8)
Now let us find f(5) = f(5 +5) = f(10) = f\(\left(\frac{10}{2}\right)\)
= f(5) so f(5) = f(10)
Now let us find f(9)
f(9) = f(9 +5) = f(14) = f\(\left(\frac{14}{2}\right)\) = f(7)
= f(7 + 5) = f(12) = f\(\left(\frac{12}{2}\right)\) = f(6)
= f\(\left(\frac{6}{2}\right)\) = f(3)
So f(9) = f(7) = f(6) = f(3) = f(1) = f(2) = f(4) = f(8)
For n > 10, the function will be equal to one of f(1), f(2)….f(10)
So the maximum no. of distinct values / takes is only 2.
First is f(1) = f(2) = f(3) = f(4) = f(8) = f(9) = f(7) = f(6)
Second is f(5) = f(10)
All other n values will give only one of these two values.


Question 87.
A binary relation R on N × N is defined as follows: (a, b) R (c, d) if a ≤ c or b ≤ d. Consider the following propositions:
P: R is reflexive
Q: R is transitive
Which one of the following statements is TRUE?
(a) Both P and Q are true
(b) P is true and Q are false
(c) P is false and Q are true
(d) Both P and Q are false

Answer/Explanation

Answer: (b) P is true and Q are false
Explanation:
(a, b) R (c, d) if a ≤ c or b ≤ d
P : R is reflexive
Q : R is transitive
Since, (a, b) R (a, b) ⇒ a ≤ a or b ≤ b ⇒ t or t
Which is always True, R is reflexive. Now let us check transitive property
Let(a,b) R (c, d) ⇒ a ≤ c or b ≤ d
and(c, d) R {e, f) ⇒ c ≤ e or d ≤ f
Now let us take a situation
a ≤ c (True) or b ≤ d ( false)
and c ≤ e (False) or d ≤ f (True)
Now we can get neither a ≤ e nor b ≤ f So, (a, b) R (c, d) and (c, d) R (e, f) ≠ (a, b) R (e, f). So clearly R is not transitive.
So Pis true and Q is false. Choice (b) is correct.


Question 88.
Consider a set U of 23 different compounds in a Chemistry lab. There is a subset S of U of 9 compounds, each of which reacts with exactly 3 compounds of U. Consider the following statements:
I. Each compound in U \ S reacts with an odd number of compounds.
II. At least one compound in U \S reacts with an odd number of compounds.
Ell. Each compound in U\S reacts with an even number of compounds
Which one of the above statements is ALWAYS TRUE?
(a) Only I
(b) Only II
(c) Only III
(d) None of these

Answer/Explanation

Answer: (b) Only II
Explanation:
This is actually a graph theory Question. Let the components be represented by vertices and if component x reacts with component y then let there be an undirected edge between x and y.Now, 9 of the 23 vertices will have 3 degrees each.
Note: U \ S means U — S, which is the remaining 23 – 9 = 14 vertices.
By Handshaking theorem,
9 × 3 + degree of 14 vertices = 2e = Even. i.e., 27 + degree of 14 vertices = 2e = Even. So, the total degree of 14 vertices must be odd.
Statement I means that the degree of each of the 14 vertices is odd, which means that the total degree of 14 vertices will be even (since even number of odd numbers is always even). But we need the total degree of 14 vertices to be odd so, statement I is false.
Statement III means that everyone of the 14 vertices has even degree, which guarantees that the total degree of 14 vertices will be even. So, statement III is false. Since statement II is the negation of statement III, it must be true.


Question 89.
Consider the set X = {a, b, c, d, ej under the partial ordering:
R = {(a, a), (a, b), (a, c), (a, d), (a, e), (b, b), (b, c), (b, e), (c, c), (c, e), (d, d), (d, e), (e, e)}.
The Hasse diagram of the partial order (X, R) is shown below:

Computer Science Set Theory and Algebra Questions and Answers chapter 2 img 9

The minimum number of ordered pairs that need to be added to R to make (X, R) a lattice is ______.

Answer/Explanation

Explanation:
Since the given hasse diagram is already a lattice, three is no need to add any ordered pair. So the answer is 0.


Computer Science Set Theory and Algebra Questions and Answers

Question 90.
The number of integers between 1 and 500 (both inclusive) that are divisible by 3 or 5 or 7 is ______.

Answer/Explanation

Explanation:
Let A → -5- by 3
B → ÷ by 5
C →÷ by 7
n(A ∪ B ∪ C) = n(A)+n(B) + n(C) – n(A ∩ B) – n(A ∩ C) – n(B ∩ C) + n(A ∩ B ∩ C)
= \(\left[\frac{500}{3}\right\rfloor\) + \(\left[\frac{500}{5}\right\rfloor\) + \(\left[\frac{500}{7}\right\rfloor\) – \(\left[\frac{500}{15}\right\rfloor\) – \(\left[\frac{500}{21}\right\rfloor\) – \(\left[\frac{500}{35}\right\rfloor\) + \(\left[\frac{500}{105}\right\rfloor\) = 166 + 100 + 71 – 33 – 23 – 14 + 4 = 271


Question 91.
Let G be a finite group on 84 elements. The size of the largest possible proper subgroup of G is _______.

Answer/Explanation

Explanation:
Given | G | =84
By Lagrang’s theorem any subgroup size is a divisior of 84.
But a proper subgroup cannot have same size as group.
So largest divisor of 84, other than 84 is 42. So, largest proper subgroup can have in size of 42.


Question 92.
Let N be the set of natural numbers. Consider the following sets:
P. Set of Rational numbers (positive and negative).
Q. Set of functions from {0, 1} to N.
R. Set of functions from N to {0, 1}.
S. Set of finite subsets of N.
Which of the sets above is countable?
(a) Q and S only
(b) P and S only
(c) P and R only
(d) P, Q, and S only

Answer/Explanation

Answer: (d) P, Q, and S only

Explanation:
P: Set of rational number → countable
Q: Set of functions from {0, 1} to N → N

Computer Science Set Theory and Algebra Questions and Answers chapter 2 img 41

 

0 can be assigned in N ways
1 can be assigned in N ways
There are N × N functions, the cross product of countable set in countable.
R: Set of functions from N to {0,1}

Computer Science Set Theory and Algebra Questions and Answers chapter 2 img 42

 

Each of these boxes can be assigned to 0 or 1 so each such function is a binary number with an infinite number of bits.
Example: 0000 is the binary number corresponding to 0 is assigned to all boxes and so on. Since each such binary number represents a subset of N (the set of natural numbers) by characteristic function method, therefore, the set of such function is the same as the power set of N which is uncountable due to Cantor’s theorem, which says that power set of a countably infinite set is always uncountably infinite.
S: Set of finite subsets of N → countably infinite since we are counting only finite subsets. So P, Q, and S are countable.


Question 93.
Let G be an arbitrary group. Consider the following relations on G:
R1: ∀a, b ∈ G, a R1 b if and only if ∃g ∈ G such that a = g-1 bg
R2: ∀a, b ∈ G, a R2 b if and only if a = b-1
Which of the above is/are equivalence relation/ relations?
(a) R1 and R2
(b) R1 only
(c) R2 only
(d) Neither R1 nor R2

Answer/Explanation

Answer: (b) R1 only
Explanation:
R1: ∀a, b ∈ G,a R1 b if and only if ∃g∈ G such that a = g-1bg
Reflexive: a = g-1ag can be satisfied by putting g = e, identity “e” always exists in a group.
So reflexive
Symmetric: aRb ⇒ a = g-1ag for some g
⇒ b = gag-1 = (g-1)-1 ag-1 g-1 always exists for every g ∈ G.
So symmetric
Transitive: aRb and bRc ⇒ a = g1-1bg1 and b = g2-1 cg2 for some g1g2 ∈ G.
Now a=g1-1g2-1cg2g1(g2g1)-1 cg2g1
g1 ∈ G and g2 ∈ G ⇒ g2g1 ∈ G since group is closed so aRb and aRb ⇒ aRc hence transitive
Clearly R1 is equivalence relation.
R2 is not equivalenced it need not even be reflexive, since aR2 a => a = a-1 ∀a which not be true in a group.
R1 is equivalence relation is the correct answer.


Question 94.
Let R be the set of all binary relations on the set {1, 2, 3}. Suppose a relation is chosen from R at random. The probability that the chosen relation is reflexive (round off to 3 decimal places) is _____.

Answer/Explanation

Explanation:
A = {1, 2, 3}
n = |A| = 3
Number of relations on A = 2 = 2 = 29
Number of reflexive relations on A
= 2n² – n  = 23² – 3 = 26


Question 95.
Let G be a group of 35 elements. Then the largest possible size of a subgroup of G other than G itself is _______.

Answer/Explanation

Explanation:
Size of group = O(G) = 35
Lagrange’s theorem says if H is a subgroup of G
then O(H) | 0(G).
So 0(H) can be 1, 5, 7 or 35.
So largest subgroup size other than G itself is 7.


Computer Science Set Theory and Algebra Questions and Answers

Question 96.
A relation R is said to be circular if aRb and bRc together imply cRa.
Which of the following options is/are correct?
(a) If a relation S is reflexive and circular, then S is an equivalence relation.
(b) If a relation S is circular and symmetric, then S is an equivalence relation.
(c) If a relation S is transitive and circular, then S is an equivalence relation.
(d) If a relation S is reflexive and symmetric, then S is an equivalence relation.

Answer/Explanation

Answer: (a) If a relation S is reflexive and circular, then S is an equivalence relation.
Explanation:
Let S be reflexive and circular,
Let us checking symmetry:
Symmetry:
Let xSy
Now since S is reflexive ySy true.
So xSy and ySy is true
Now by circular property we get, ySx
So xSy => ySx
So S is symmetric.
Transitive:
Let xSy and ySz
Now by circular property we get zSx and by symmetry property proved above, we get
zSx => xSz
So xSy and ySz => xSz
So S is transitive.
So S is reflexive, symmetric and transitive and hence an equivalence relation.
So option (a) is true.
Option (b): Let S be circular and symmetric. Let S be defined on set {1, 2, 3}
Now empty relation is circular and symmetric but not reflexive. So S need not be an equivalence relation.
So option (b) is false.
Option (c): Let S be transitive and circular. Let S be defined on the set {1, 2, 3}
Now empty relation again satisfies transitive and circular but is not reflexive. So S need not be an equivalence relation.
So option (c) is false.
Option (d): Reflexive and symmetric need not be transitive for example on {1, 2, 3}.
S = {(L 1), (2, 2), (3, 3), (1, 2), (2, 1), (2, 3), (3, 2)}
is reflexive and symmetric. But it is not transitive because (1, 2) and (2, 3) belong to S but (1, 3) does not.
So option (d) is false.


Question 97.
Let G be a group of order 6, and Hbe a subgroup of G such that 1 < | H | <6. Which one of the following options is correct?
(a) Both G and H are always cyclic.
(b) G is always cyclic, but H may not be cyclic.
(c) G may not be cyclic, but H is always cyclic.
(d) Both G and H may not be cyclic.

Answer/Explanation

Answer: (c) G may not be cyclic, but H is always cyclic.
Explanation:
|G| = 6
H is subgroup, so by Lagrange’s theorem
| H | = 1, 2, 3 or 6 (Divisor’s of 6) Now it is given that 1 < | H | <6 or | H | = 2 or 3
Since 2 and 3 are both prime and since every group of prime order is cyclic, H is surely cyclic. But order of | G | =6 which is not prime. So G may or may not be cyclic. So G may not be cyclic, but H is always cyclic. Option (c) is correct.


Question 98.
Consider the following sets, where n ≥ 2:
S1: Set of all n × n matrices with entries from the set {a, b, c}
S2: Set of all functions from the set {0,1, 2, n2 – 1} to the set {0, 1, 2}
Which of the following choice(s) is/are correct?
(a) There exists a surjection from S1 to S2.
(b) There does not exist a bijection from S1 to S2.
(c) There does not exist an injection from S1 to s2.
(d) There exists a bijection from S1 to S2.

Answer/Explanation

Answer:
(a) There exists a surjection from S1 to S2.
(d) There exists a bijection from S1 to S2.
Explanation:
| S1 | = 3n
Since each of the n2 entries in n × n matrix can be fills in 3 ways.
|S2| = 3n2
Since | {0, 1, 2} | =3 and | {0, 1, 2, n2 — 1} | = n2)
Now the theorem says A bijection fA → B exists iff |A| = |B|.
Here |S1| = |S2|
So, there has to be a bijection from S1 to S2. So, option (d) is correct. If bijection exists surely surjection also exists. So, option (a) is also correct. Option (b) and (c) are incorrect.


Question 99.
Let S be a set consisting of 10 elements. The number of tuples of the form (A, B) such that A and B are subsets of S and A ⊆ B is _______.

Answer/Explanation

Explanation:
The Venn diagram for this is

Computer Science Set Theory and Algebra Questions and Answers chapter 2 img 43

 

Now every element x in S has only 3 options. It can be x ∈ A or x ∈ B – A or x ∈ S — B. So the number of ways to choose A and B such that A ⊆ B ⊆ S is 310.


Computer Science Set Theory and Algebra Questions and Answers

Question 100.
For two n-dimensional real vectors P and Q, the operation s(P, Q) is defined as follows:
s(P, Q) = \(\sum_{i=1}^{n}\)(P[i].Q[i])

Let L be a set of 10-dimensional non-zero real vectors such that for every pair of distinct vectors P, Q ∈ L, s(P, Q) = 0. What is the maximum cardinality possible for the set L?
(a) 10
(b) 9
(c) 100
(d) 11

Answer/Explanation

Answer: (a) 10
Explanation:
L is the set of 10-dimensional orthogonal vectors.
So cardinality of L ≤ 10.
i.e., Maximum cardinality of L = 10.
So, option (a) is correct.


Mathematical Logic Questions and Answers | Computer Science Quiz

Computer Science Mathematical Logic MCQ Quiz Questions and Answers PDF Download

Computer Science Mathematical Logic Questions and Answers

Question 1.
Indicate which of the following well-formed formula are valid:
(a) ((P⇒Q) ∧ (Q ⇒ R)) ⇒ (P ⇒ R)
(b) (P ⇒ Q) ⇒(¬ P ⇒ ¬ Q)
(c) (P∧(¬P V¬ Q)) ⇒ Q
(d) ((P ⇒ R) ∨ (Q ⇒ R)) ⇒ ((P ∨ Q)) ⇒ R)

Answer/Explanation

Answer: (a) ((P ⇒ Q) ∧ (Q ⇒ R)) ⇒ (P ⇒ R)
Explanation:
Option (a) is well known valid formula (tautology) because it is a rule of inference called a hypothetical syllogism. By applying Boolean algebra and simplifying, we can show that (b), (c), and (d) are invalid.
For example,
Choice (b) ≡(P ⇒ Q) ⇒ (¬P ⇒ ¬Q)
≡(P ⇒ Q) ⇒ (P ⇒Q’)
≡(P’ + Q) ⇒ (P + Q’)
≡(P’ + Q)’ + (P+Q’)
≡PQ’ + P+Q’
≡P+ Q’
≠1
So, invalid.


Question 2.
Which of the following predicate calculus statements is/are valid
(a) (∀x) P(x)∨ (∀x) Q(x) → (∀x) {P(x) ∨ Q(x)}
(b) (∃x) P(x) ∧ (∃x) Q(x) → (∃x) {P(x) ∧ Q(X)}
(c) (∃x) {P(x) ∨ Q(x)} → (∀x) P(x) ∨ (∀x) Q(x)
(d) (∃x) {P(x) ∨ Q(x)} → ∃x P(x) ∨ ∀x Q(x)

Answer/Explanation

Answer: (a) (∀x) P(x)∨ (∀x) Q(x) → (∀x) {P(x) ∨ Q(x)}
Explanation:
According to distributive properties
∀x (P(x) ∧ Q(x)) ↔ ∀xP(x) ∧ ∀xQ(x)
(∀xP(x) ∨∀xQ(x)) → ∀x(P(x) ∨ Q(x))
∃x (P(x) ∨ Q(x)) ↔ ∃xP(x)∨∃xQ(x)
∃x(P(x) ∧Q(X)) → ∃xP(x) ∧∃xQ(X)
So option (a) is valid.


Question 3.
Which of the following is/are tautology:
(a) (a ∨ b) → (b ∧ c)
(b) (a ∧ b) → (b ∨ c)
(c) (a ∨ b) → (b → c)
(d) (a → b) → (b → c)

Answer/Explanation

Answer: (b) (a ∧ b) → (b ∨ c)
Explanation:
(a) (a ∨ b) → (b ∧ c)
≡ (a + b)’ + bc
≡ a’b’+ bc
Therefore, ((a ∨ b) → (b ∧ C)) is contingency and not tautology.
(b) (a ∧ b) → (b ∨ c)
≡ ab → b + c
≡ (ab)’ + b + c
≡a’ + b’ + b + c
≡a’ + 1 + c
≡1
So ((a ∧b) → (b ∨c)) is tautology.
(c) (a ∨ b) → (b → c)
≡ (a + b) → (b’ + c)
≡(a +b)’ +b’ + c
≡a’b’ + b’ + c
≡b’ + c
So ((a ∨b) → (b → c)) is contingency but not a tautology.
(d) (a → b) → (b → c)
≡(a’ + b) → (b’ + c )
≡(a’ + b)’ + b’ + c
≡ ab’ + b’ + c
≡b’ + c
Therefore, ((a → b) → (b → c)) is contingency but not tautology.


Computer Science Mathematical Logic Questions and Answers

Question 4.
The proposition p ∧ (~p ∨ q) is
(a) A tautology
(b) ⇔ (p ∧ q)
(c) ⇔ (p ∨ q)
(d) A Contradiction

Answer/Explanation

Answer: (b) ⇔ (p ∧ q)
Explanation:
The proposition p ∧ (~p ∨ q)
≡p(p’ + q) ≡pq
≡p ∧ q


Question 5.
Let p and q be propositions. Using only the truth table decide whether p ⇔ q does not imply p →¬ q is true or false.

Answer/Explanation

Answer: TRUE
Explanation:

p q P ↔ q P → ~ q (p ↔ q) → (p → ~ q)
T T T F F
T F F T T
F T T T T
F F F T T

From the truth table, (p ↔ q) → (p → ~q) is not a tautology, hence it is true that p ↔ q doesn’t imply p →¬q.


Question 6.
If the proposition ¬ p ⇒ q is true, then the truth value of the proposition ¬ p ∨ (p ⇒ q), where ¬ is negation, ‘∨’ is inclusive or and ‘⇒’ is the implication, is
(a) True
(b) Multiple valued
(c) False
(d) Cannot be determined

Answer/Explanation

Answer: (d) Cannot be determined
Explanation:

P q ¬ p → q
0 0 0
0 1 1
1 0 1
1 1 1

Now since ¬p → q is given true, We reduce the truth table as follows.

p q ¬ p → q
0 1 1
1 0 1
1 1 1

In the reduced truth table we need to find the true value of ¬p ∨(p → q) ≡p’ +(p → q) ≡p’ + p’ +q ≡p’ + q
The truth value of p’ + q in the reduced truth table is given below.

P q P’ + q
0 1 1
1 0 0
1 1 1

Since in the reduced truth table also, the given expression is sometimes true and sometimes false, therefore the truth value of proposition ¬p ∨(p → q) can not be determined.


Question 7.
Which one of the following is false? Read ∧ as AND, ∨ as OR, ~ as NOT, → as one-way implication, and ↔ as two-way implication.
(a) ((x → y) ∧ x) → y
(b) ((~ x → y) ∧ (~ x → ~ y) ) → x
(c) (x → (x ∨ y))
(d) ((x ∨ y)↔(~ x → ~ y))

Answer/Explanation

Answer: (d) ((x ∨ y)↔(~ x → ~ y))
Explanation:
(d) ((x ∨y) ↔ (~x →~y))
= (x ∨ y) ↔ (~(~x ) ∨~y)
= (x ∨ y) ↔ (~x ∨~y)
= ((x ∨ y) ∧ (~x ∨~y)) ∨(~(x ∨y) ∧~(x ∨~y))
= ((x ∨(y ∧ ~y)) ∨(( ~x ∧ ~y) ∧ (~x ∧ y))
= (x ∨ F) ∨ ((~x ∧ ~y) ∧(~x ∧ y))
= x ∨ (~x ∧(y ∧~y)) = x ∨(~x ∧F)
= x ∨ F = x


Computer Science Mathematical Logic Questions and Answers

Question 8.
Let a, b, c, d be propositions. Assume that the equivalence a ↔ (b ∨ ¬ b) and b ↔ c hold. Then the truth-value of the formula (a ∧ b) → (a ∧ c) ∨ d is always
(a) True
(b) False
(c) Same as the truth-value of b
(d) Same as the truth-value of d

Answer/Explanation

Answer: (a) True
Explanation:
. a ↔ (b ∨¬b)
a ↔ True
So a is true, i.e. a = 1
. b ↔ c holds. So b = c
Now the given expression is
(a ∧ b) → ((a ∧ c) ∨d) ≡(a . b) → ((a . c) + d)
putting a=1 in above expression We get
1 . b →((1 . c) +d)
≡ b → c + d
≡ b’ + c + d
Now putting b=c in above expression We get
≡c’ + c + d ≡1 + d ≡1
So the expression is always true.


Question 9.
What is the converse of the following assertion? I stay only if you go
(a) I stay if you go
(b) If I stay then you go
(c) If you do not go then I do not stay
(d) If I do not stay then you go

Answer/Explanation

Answer: (a) I stay if you go
Explanation:
Let p: I stay
q: you go
I stay only if you go
p → q
The converse of p → q is q → p
Now convert the answers one-by-one into boolean form. Only option (a) i.e. “I stay if you go” converts to q → p.


Question 10.
Consider two well-formed formulas in propositional logic:
F1: P ⇒ ¬ P
F2: (P ⇒ ¬ P) v ( ¬ P ⇒P)
Which of the following statements is correct?
(a) F1 is satisfiable, F2 is valid
(b) F1 is unsatisfiable, F2 is satisfiable
(c) F1 is unsatisfiable, F2 is valid
(d) F1 and F2 are both satisfiable

Answer/Explanation

Answer: (a) F1 is satisfiable, F2 is valid
Explanation:
F1: P → ~P ≡ p → p’ ≡ p’ + p’ ≡p’
So F1 is contingency. Hence, F1 is satisfiable but not valid.
F2: (P → ~P) ∨ (~P → P)
≡ (p → p’) + (p’ → p)
≡ (p’+p’) + (p + p)
≡ p’ + p ≡ 1
So F2 is tautology and therefore valid.


Question 11.
“If X then Y unless Z” is represented by which of the following formulas in propositional logic? (“¬”) is negation, “ ∧” is the conjunction, and “→” is the implication)
(a) (X ∧¬ Z) → Y
(b) (X ∧ Y) → ¬ Z
(c) X → (Y ∧ ¬ Z)
(d) (X → Y) ∧ ¬ Z

Answer/Explanation

Answer: (a) (X ∧¬ Z) → Y
Explanation:
If X then Y unless Z is represented by
X →Y unless Z ≡ (X → Y) + Z
≡ X’ + Y + Z
Now convert the answers one-by-one into boolean form only choice (a) converts to X’+ Y+ Z as can be seen below:
(X∧~Z) →Y ≡ XZ’ → Y
≡ (XZ’)’ + y
= X’+ Y+Z


Computer Science Mathematical Logic Questions and Answers

Question 12.
Which of the following is a valid first order formula? (Here α and β are first order formulae with x as their only free variable)
(a) ((∀x) [α] ⇒ (∀x)[β]) ⇒ (∀x) [α ⇒ β]
(b) (∀x) [α] ⇒ (∃x) [α ∧ β]
(c) (∀x) [α v β ] ⇒ (∃x) [α] ⇒ (∀x) [α]
(d) (∀x) [α ⇒ β ] ⇒ ((∀x) [α] ⇒ (∀x) [β])

Answer/Explanation

Answer: (d) (∀x) [α ⇒ β ] ⇒ ((∀x) [α] ⇒ (∀x) [β])
Explanation:
(∀x) [α ⇒ β] ⇒ ((∀x) [α] ⇒ ∀(x) [[β]) is a logical equivalence and therefore, a valid first order formula.


Question 13.
Consider the following formula α and its two interpretations I1 and I2.
α : (∀x) [Px ⇔ (∀y) [Qxy ⇔ ¬ Qyy]] ⇒ (∀x)[¬ Px]
I1 : Domain: the set of natural numbers
Px ≡ ‘x is a prime number ‘
Qxy ≡’y divides x’
I2: Same as I1 except that Px = ‘x is a composite number.’
Which of the following statements is true?
(a) I1 satisfies α, I2 does not
(b) I2 satisfies α, I1 does not
(c) Neither I2 nor I1 satisfies α
(d) Both I1 and I2 satisfy α

Answer/Explanation

Answer: (d) Both I1 and I2 satisfy α
Explanation:
Qxy ≡ “y divides y” is always true
∴Qxy ⇔ ¬ Qxy is the same as Qxy ⇔False
Now α becomes
(∀x)[P(x)⇔(∀y)(Qxy⇔false)]
⇒ (∀x) [¬ P(x)]
Now consider I1: P(x) = “x is a prime number”. α becomes
(∀x x is a prime number if and only if ∀y (y does not divide x)) ⇒ (∀x) x is not prime. which means that x is a prime number if and only if no number divides x implies that no number is prime. Since x always divides x, the above sentence is true.

Now consider I2: P(x) = “x is a composite number”. Now α becomes

(∀x x is a composite number if and only if ∀y (y does not divide x)) ⇒ (∀x) x is not composite. This means that x is a composite number if and only if no number divides x implies that no number is composite.
Since x always divides x, the above sentence is true.
∴ Both I1 and I2 satisfy α.


Question 14.
The following resolution rule is used in logic programming: Derive clause (P ∨ Q) from clauses (P ∨ R), (Q ∨ ¬ R) Which of the following statements related to this rule is FALSE?
(a) (P ∨ R)∧(Q ∨ ¬ R) ⇒ (P ∨ Q) is logically valid
(b) (P ∨ Q) ⇒ (P ∨ R) ∧ (Q ∨¬ R) is logically valid
(c) (P ∨ Q) is satisfiable if and only if (P ∨ R) ∧ (Q ∨ ¬ R) is satisfiable
(d) (P ∨ Q) ⇒ FALSE if and only if both P and Q are unsatisfiable

Answer/Explanation

Answer: (b) (P ∨ Q) ⇒ (P ∨ R) ∧ (Q ∨¬ R) is logically valid
Explanation:
Derive clause P ∨ Q from clauses P ∨ R, Q ∨¬R means that (P ∨ R) ∧ (Q ∨ ¬R) ⇒ P ∨ Q
.’. (a) is true
Since x ⇒ y does not imply that y ⇒ x
.’. P ∨ Q ⇒ (P ∨ R) ∧ (Q ∨¬R)
.’. may or may not be true.
Hence (b) is false.


Question 15.
Identify the correct translation into the logical notation of the following assertion. Some boys in the class are taller than all the girls
Note: Taller (x, y) is true if x is taller than y.
(a) (∃x) (boy(x) → (∀y) (girl(y) ∧ taller (x, y)))
(b) (∃x) (boy(x) ∧ (∀y) (girl(y) ∧ taller (x, y)))
(c) (∃x) (boy(x) → (∀y) (girl(y) → taller (x, y)))
(d) (∃x) (boy(x) ∧ (∀y) (girl(y) → taller (x, y)))

Answer/Explanation

Answer: (d) (∃x) (boy(x) ∧ (∀y) (girl(y) → taller (x, y)))
Explanation:
The statement is “some boys in the class are taller than all the girls”. so the notation for the given statement is (∃x) (boy(x) ∧(∀y) (girl(y) → taller (x,y)))


Question 16.
Let an (x, y), b(x, y,), and c(x, y) be three statements with variables x and y chosen from some universe. Consider the following statement:
(∃x)(∀y)[(a(x,y) ∧ b(x,y)) ∧ ¬ c(x,y)]
Which one of the following is its equivalent?
(a) (∀x)(∃y)[(a(x,y) ∨ b(x,y)) ∧ ¬ c(x,y)]
(b) (∃x)(∀y)[(a(x,y) ∨ b(x,y)) ∧ ¬ c(x,y)]
(c) ¬(∀x)(∃y)[(a(x,y) ∧ b(x,y)) → c(x,y)]
(d) ¬ (∀x)(∃y)[(a(x,y) ∨ b(x,y)) → c(x,y)]

Answer/Explanation

Answer: (c) ¬(∀x)(∃y)[(a(x,y) ∧ b(x,y)) → c(x,y)]
Explanation:
Choice (c) is
¬(∀x)(∃y)[(a(x,y) ∧ b(x,y)) → c(x,y)]
= ¬(∀x)(∃y)[a ∧ b → c]
= ¬(∀x)(∃y)[(ab)’ + c]
= ∃x ∀y[(ab)’ + c]’
= ∃x ∀y [abc’] = ∃x ∀y [a ∧ b ∧ ¬C] which is same as the given expression. (∃x)(∀y)[(a(x,y) ∧ b(x,y)) ∧ ¬c(x,y)]


Computer Science Mathematical Logic Questions and Answers

Question 17.
Let p, q, r, and s be four primitive statements. Consider the following arguments:
P: [(¬ p ∨ q) ∧ (r → s) ∧ (p ∨ r)] → (¬ s → q)
Q: [(¬ p ∧ q) ∧ [q → (p → r)]] → ¬ r
R: [[(q ∧ r) → p] ∧ (¬q ∨ p)] → r
S: [p ∧ (p → r) ∧ (q ∨ ¬ r)] → q
Which of the above arguments are valid?
(a) P and Q only
(b) P and R only
(c) P and S only
(d) P, Q, R, and S

Answer/Explanation

Answer: (c) P and S only
Explanation:
p: [(¬p ∨q) ∧(r → s) ∧(p ∨r)] →q
≡p(p’ +r)(q + r’) →q
≡pr(q +r’) →q
≡prq →q
≡(prq)’ + q
≡p’ + r’ + q’ + q
≡p’ + r’ + 1
≡1
Therefore S is valid.
Q and R can be similarly simplified in boolean algebra to show that is both not equivalent to 1.


Question 18.
The following propositional statement is
(P →(Q ∨ R)) → ((P ∧ Q) → R)
(a) Satisfiable but not valid
(b) Valid
(c) A contradiction
(d) None of the above

Answer/Explanation

Answer: (a) Satisfiable but not valid
Explanation:
(p → (Q ∨R)) → ((P ∧Q) → R)
≡(P → Q + R) → (PQ → R)
≡[P’ + Q + R] → [(PQ)’ + R]
≡[P’ + Q + R] → [P’ + Q’ + R]
≡(P’ + Q + R)’ + P’ + Q’ + R
≡P Q’ R’ + P’ + Q’ + R
≡Q’ + Q’ P R’ + P’ + R
≡Q’ + P’ + R (by absorption law)
which is a contingency (i.e. satisfiable but not valid).


Question 19.
Let P, Q, and R be three atomic propositional assertions. Let X denote (P ∨ Q) → R and Y denote (P → R) ∨ (Q → R). Which one of the following is a tautology?
(a) X ≡ Y
(b) X → Y
(c) Y → X
(d) ¬ Y →X

Answer/Explanation

Answer: (b) X → Y
Explanation:
X: (P ∨ Q) → R
Y: (P → R) ∨(Q → R)
X: P + Q → R ≡(P + Q)’ + R ≡P’ Q’ + R
Y: (P’ + R) + (Q’ +R) ≡P’ + Q’ + R
Clearly X ≠ Y
Consider X → Y
≡(P’Q’ +R) →(P’ + Q’ + R)
≡(P’Q’+R)’ + P’ + Q’ + R
≡(P’Q’)’ . R’ + P’ + Q’ + R
≡(P + Q) . R’ + P’ + Q’ + R
≡ PR’ + QR’ + P’ + Q’ + R
≡ (PR’ + R) + (QR’ + Q’) + P’
≡(P + R) (R’ + R) + (Q + Q’) × (R’ +Q’) + P’
≡(P + R) + (R’ + Q’) + P’
≡P + P’ + R + R’ + Q’
≡1 + 1 + Q’
≡ 1
∴X → Y is a tautology.


Computer Science Mathematical Logic Questions and Answers

Question 20.
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/Explanation

Answer: (b)∀(x) [teacher (x) → ∃ (y) [student (y) ∧ likes (y, x)]]
Explanation:
Every teacher is liked by some student: then the logical expression is ∀(x) [teacher(x) → ∃(y) [student (y) ∧ likes (y, x)]] Where likes (y, x) means y likes x, such that y represent the student and x represents the teacher.


Question 21.
Let P(x) and Q(x) be arbitrary predicates. Which of the following statements is always TRUE?
(a) (∀x(P(x) ∨ Q(x))) ⇒ ((∀xP(x)) ∨ (∀xQ(x)))
(b) (∀x(P(x) ⇒ Q(x))) ⇒ ((∀xP(x)) ⇒ (∀xQ(x)))
(c) (∀x(P(x) ⇒ (∀xQ(x)))) ⇒ (∀x(P(x) ⇒ Q(x)))
(d) ((∀x(P(x)) ⇔ (∀xQ(x))) ⇒ (∀x(P(x) ⇔ Q(x)))

Answer/Explanation

Answer: (b) (∀x(P(x) ⇒ Q(x))) ⇒ ((∀xP(x)) ⇒ (∀xQ(x)))
Explanation
Consider choice (b)
(∀x(P(x) ⇒ Q(x))) ⇒ ((∀xP(x)) ⇒ (∀xQ(x))) Let the LHS of this implication be true This means that
P1 → Q1
p2 → Q2

.
.
.
Pn → Qn
Now we need to check if the RHS is also true. The RHS is ((∀xP(x)) ⇒ (∀xQ(x)))
To check this let us take the LHS of this as true i.e. take∀xP(x) to be true. This means that (P1 P2,…Pn ) is taken to be true. Now P1 along with P1 → Q1 will imply that is true. Similarly
P2 along with P2 → Q2, will imply that Q2 is true. And so on…
Therefore (Q1, Q2,……Qn) all true.
i.e. ∀x Q(x) is true. Therefore statement (b) is a valid predicate statement.


Question 22.
Consider the following first-order logic formula in which R is a binary relation symbol.
∀x ∀y ( R(x,y) ⇒ R(y, x))
The formula is
(a) Satisfiable and valid
(b) Satisfiable and so is its negation
(c) Unsatisfiable but its negation is valid
(d) Satisfiable but its negation is unsatisfiable

Answer/Explanation

Answer: (b) Satisfiable and so is its negation
Explanation:
Since a relation may or may not be symmetric, the given predicate is satisfiable but not valid. So (a) is clearly false.
Whenever a predicate is satisfiable its negation also is satisfiable. So option (b) is the correct answer.


Question 23.
Which one of the first-order predicate calculus statements given below correctly expresses 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)) → {(attacks (x) → (hungry (x) ∨ Threatened (x))}]
(d) ∀x [(tiger (x) ∨ lion (x)) → {(hungry (x) ∨ threatened (x)) → attacks (x)}]

Answer/Explanation

Answer: (d) ∀x [(tiger (x) ∨ lion (x)) → {(hungry (x) ∨ threatened (x)) → attacks (x)}]
Explanation:
The given statement should be read as “If an animal is a tiger or a lion, then (if the animal is hungry or threatened, then it
will attack). Therefore the correct translation is ∀x [(tiger (x) ∨ lion (x)) → {(hungry (x) ∨ threatened (x)) → attacks (x)}] which is choice (d).


Computer Science Mathematical Logic Questions and Answers

Question 24.
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/Explanation

Answer: (d) Both P1 and P2 are not tautologies
Explanation:
P1: ((A ∧ B) → c) ≡ ((A → c) ∧ (B → c))
LHS :
(A ∧ B) → C
≡ AB → C
≡ (A B)’ + C
≡ A’ + B’ + C
RHS:
(A → C) ∧ (B → C)
≡ (A’+ C) (B’ + C)
≡ A’B’ + C
Clearly, LHS ≠ RHS
P1 is not a tautology
P2: ((A ∨ B → C)) ≡ ((A → C) ∨(B → C))
LHS ≡ (A + B → C)
≡ (A + B)’+C
≡ A’B’ + C
RHS = (A → C) ∨ (B → C)
≡ (A’+ C) + (B’ + C)
≡ A’+ B’ + C
Clearly, LHS ≠ RHS ⇒ P2 is also not a tautology. Therefore, both P1 and P2 are not tautologies. The correct choice is (d).


Question 25.
A logical binary relation ⊙ is defined as follows:

A B A ⊙ B
True True True
True False True
False True False
False False True

Let ~ be the unary negation (NOT) operator, with higher precedence, than ⊙. Which one of the following is equivalent to A ∧ B?
(a) (~ A ⊙ B)
(b) ~ (A ⊙ ~ B)
(c) ~ (~ A ⊙ ~ B)
(d) ~ (~ A ⊙ B)

Answer/Explanation

Answer: (d) ~ (~ A ⊙ B)
Explanation:
By using min terms we can define
A⊙B = AB + AB’ + A’B’
= A + A’B’
= (A + A’) . (A + B’) = A + B’
(a) ~ A⊙B = A’⊙ B = A’ + B’
(b) ~ (A ⊙ ~B) = (A ⊙ B’)’ =(A + (B’)’)’
= (A + B)’ = A’B’
(c) ~ (~A ⊙ ~B) = (A’ ⊙ B’)’ = (A’ + (B’)’)’
= (A’ + B)’ = AB’
(d) ~ (~A ⊙ B) = (A’ ⊙ B)’ = (A’ + B’)’
= A . B = A ∧ B
∴ Only, choice (d) = A ∧ B
Note: This problem can also be done by constructing a truth table for each choice and comparing it with the truth table for A ∧ B.


Question 26.
Let Graph (x) be a predicate that denotes that x is a graph. Let Connected (x) be a predicate that denotes that x is connected. Which of the following first-order logic sentences DOES NOT represent the statement; “Not every graph is connected”?
(a) ¬∀x (Graph(x) ⇒ Connected (x))
(b) ∃x (Graph(x) ∧¬ Connected (x))
(c) ¬∀x (¬ Graph(x) ∨ Connected (x))
(d) ∀x (Graph(x) ⇒ ¬ Connected (x))

Answer/Explanation

Answer: (d) ∀x (Graph(x) ⇒ ¬ Connected (x))
Answer:
Explanation:
The statement “Not every graph is connected” is the same as “There exists some graph which is not connected” which is the same as
∃x {graph (x) ∧ ¬ connected (x)}
Which is choice (b)
By boolean algebra, we can see that options (a) and (c) are the same as (b). Only option (d) is not the same as (b).
In fact option (d) means that “all graphs are not connected”.
Alternate solution:
We can translate the given statement “NOT (every graph is connected)” as ¬(∀x graph (x) → connected (x))
≡∃x¬(graph (x) →connected (x))
≡ ∃x¬(¬graph (x) ∨connected (x))
≡ ∃x (graph (x) ∧ ¬ connected (x))
By boolean algebra, we can see that options (a) and (c) are the same as (b). Only option (d) is not the same as (b).
In fact option (d) means that “all graphs are not connected”.


Computer Science Mathematical Logic Questions and Answers

Question 27.
Which of the following is TRUE about formulae in Conjunctive Normal Form?
(a) For any formula, there is a truth assignment for which at least half the clauses evaluate to true.
(b) For any formula, there is a truth assignment for a which all the clauses evaluate to true.
(c) There is a formula such that for each truth assignment at most one-fourth of the clauses evaluate to true.
(d) None of the above

Answer/Explanation

Answer: (a) For any formula, there is a truth assignment for which at least half the clauses evaluate to true.
Explanation:
In conjunction normal form, for any particular assignment of truth values, all except one clause, will always evaluate to true. So, the proportion of clauses which evaluate to true to the total

number of clauses is equal to \(\frac{2^{n}-1}{2^{n}}\)
Now putting n = 1, 2, . . . . ., We get \(\frac{1}{2}\) , \(\frac{3}{4}\) , \(\frac{7}{8}\) ….
All of these proportions are ≥ \(\frac{1}{2}\) and so choice (a) at least half of the clauses evaluate to true, is the correct answer.


Question 28.
Which one of these first-order logic formulae is valid?
(a) ∀x(P(x) ⇒ Q(x)) ⇒ ((∀xP(x)) ⇒ (∀xQ(x)))
(b) ∃x(P(x) ∨ Q(x)) ⇒ ((∃xP(x)) ⇒ (∃xQ(x)))
(c) ∃x(P(x) ∧ Q(X)) ⇔ ((∃xP(x)) ∧ (∃xQ(x)))
(d) ∀x∃y P(x, y) ⇒ ∃y∀xP(x, y)

Answer/Explanation

Answer: (a) ∀x(P(x) ⇒ Q(x)) ⇒ ((∀xP(x)) ⇒ (∀xQ(x)))
Explanation:
Option (a) is a standard one-way distributive property of predicates.


Question 29.
Let fsa and pda be two predicates such that fsa(x) means x is a finite state automaton and pda(y) means, that y is a pushdown automaton. Let equivalent be another predicate such that equivalent (a, b) means a and b are equivalent. Which of the following first-order logic statement represents the following:
Each finite state automaton has an equivalent pushdown automaton.
(a) ∀x (fsa(x) ⇒ ∃y (pda(y) ∧ equivalent (x, y)))
(b) ~∀y(∃x fsa(x) ⇒ pda(y) ∧ equivalent (x, y))
(c) ∀x ∃y (fsa(x) ∧ pda(y) ∧ equivalent (x, y))
(d) ∀x ∃y (fsa{y) ∧ pda(x) ∧ equivalent (x, y))

Answer/Explanation

Answer: (a) ∀x (fsa(x) ⇒ ∃y (pda(y) ∧ equivalent (x, y)))
Explanation:
“For x which is a fsa, there exists a y which is a pda and which is equivalent to x.” ∀x (fsa(x) ⇒ ∃y (pda(y) ∧ equivalent (x, y))) is the logical representation.


Question 30.
Which of the following first order formulae is logically valid? Here a(x) is a first order formula
(a) [β → (∃x,α(x))] → [∀x, β → α(x)]
(b) [∃x, β → α(x)] → [β → (∀x, α(x))]
(c) [(∃x, α(x)) → β] → [∀x,α(x) → β]
(d) [(∀x,α(x)) → β] → [∀x, α(x) → β]

Answer/Explanation

Answer: (c) [(∃x, α(x)) → β] → [∀x,α(x) → β]
Explanation:
Option (c) is [(∃x, α(x)) → β] → [∀x,α(x) → β] Let us check the validity of this predicate. Let the LHS of this predicate be true.
This means that some α → β.
Let a5 → β
Now we will check if the RHS is true. The RHS is [∀x,α(x) → β] to check this implication let us take ∀x,α(x)to be true.
This means that all the a are true. It means that a5 is also true.
But α5 → β. Therefore β is true.
So the RHS [∀x,α(x) → β] is true.
Whenever the LHS [(∃x, α(x)) → β] is true. So option (c) is valid.


Computer Science Mathematical Logic Questions and Answers

Question 31.
Which of the following is the negation of [(∀x,α → (∃y, β → (∀u,∃v,y))]
(a) [∃x,α → (∀y,β → (∃u,∀u, Y))]
(b) [∃x,α →(∀y,β → (∃u,∀u, ¬ Y))]
(c) [∀x,¬α → (∃y,¬β →(∀u,∃u ¬Y))]
(d) [∀x,α ∧ (∃y, β ∧ (∃U, ∀U, ¬Y))]

Answer/Explanation

Answer: (d) [∀x,α ∧ (∃y, β ∧ (∃U, ∀U, ¬Y))]
Explanation:
The given predicate is
[∀x, α → (∃y,β → (∀u, ∃u, y))]
The negation is of this predicate is
¬[∀x, α → (∃y,β → ∀u, ∃u, y)]
¬[∀x, α →(∀y, ¬β ∨∀u, ∃u, y)]
¬[∃x, ¬α ∨(∀y, ¬β ∨∀u, ∃u, y)]
[∀x, α ∧ (∃y, β ∧(∃y, β ∧ (∃u, ∀u, ¬y))]
which is an option (d).


Question 32.
P and Q are two propositions, which of the following logical expressions are equivalent?
1. P ∨ ~Q
2. ~ (~P ∧ Q )
3. (P ∧ Q) ∨ (P ∧ ~Q) ∨ (~P ∧ ~ Q)
4. (P ∧ Q) ∨ (P ∧ ~Q) ∨ (~P ∧ Q)
(a) Only 1 and 2
(b) Only 1, 2 and 3
(c) Only 1, 2 and 4
(d) All of these

Answer/Explanation

Answer: (b) Only 1, 2 and 3
Explanation:
1. P ∨ ~Q ≡ P + Q’
2. ~(~P ∧ Q) ≡ (P’Q)’ ≡P+Q’
3. (P ∧ Q) ∨ (P ∧ ~Q) ∨ (~P ∧ ~Q)
≡ PQ + PQ’ + P’Q’
≡ P(Q + Q’) + P’Q’
≡ P + P’Q’
≡ (P + P’) (P + Q’)
≡ P + Q’
4. (P ∧ Q) ∨ (P ∧ ~Q) ∨ (~P ∧ Q)
≡ PQ + PQ’ + P’Q
≡ P(Q + Q’) + P’Q
≡ P + P’Q
≡ (P + P’) (P + Q) = P + Q
Clearly (i), (ii) and (iii) are equivalent. Correct choice is (b).


Question 33.
Which one of the following is the most appropriate logical formula to represent the statement: “Gold and silver ornaments are precious”
The following notations are used:
G(x): x is a gold ornament
S(x): x is a silver ornament
P(x): x is precious
(a) ∀x(P(x) → (G(x) ∧ S(x)))
(b) ∀x(G(x) ∧ (S(x) → P(x)))
(c) ∃x((G(x) ∧ S(x)) → P(x))
(d) ∀x ((G(x) ∨ S(x)) → P(x))

Answer/Explanation

Answer: (d) ∀x ((G(x) ∨ S(x)) → P(x))
Explanation:
The correct translation of “Gold and silver ornaments are precious” is choice (d)
∀x((G(x) ∨ S(x)) → P(x))
which is read as “if an ornament is a gold or silver, then it is precious”. Now since a given ornament cannot be both gold and silver at the same time.
Choice (b) ∀x ((G(x) ∧ S(X)) → P(x)) is incorrect.


Question 34.
The binary operation □ is defined as follows:
Table
Which one of the following is equivalent to P ∨ Q?
(a) ¬Q □ ¬ P
(b) P □ ¬ Q
(c) ¬P □ Q
(d) ¬ P □ ¬ Q

Answer/Explanation

Answer: (b) P □ ¬ Q
Explanation:
The given table can be converted into a boolean function by adding minterms corresponding to true rows.
Gate Questions on Mathematical Logic chapter 1 img 1
Since there is only one false in the above truth table, we can represent the function P □ Q more efficiently, in conjunctive normal form. Translates P □ Q = P + Q’ (the max-term corresponding to the third row, where the function is false).
Now, we can easily translate the choices into boolean algebra as follows:
Choice (a) ¬Q □ ¬P ≡ Q’ □ P’ ≡ Q’ + P
Choice (b) P □ ¬Q ≡ P □ Q’ ≡ P + Q
Choice (c) ¬P □ Q ≡ P’ □ Q ≡ P’ + Q’
Choice (d) ¬P □ ¬Q ≡ P’ □ Q’ ≡ P’ + Q
As we can clearly see only choice (b) P □ ¬ Q is equivalent to P + Q.


Question 35.
Consider the following well-formed formulae:
I.¬∀x (P(x))
II. ¬∃x (P(x))
III.¬∃x (¬P(x))
IV. ∃x (¬P(x))
Which of the above are equivalent?
(a) I and III
(b) I and IV
(c) II and III
(d) II and IV

Answer/Explanation

Answer: (b) I and IV
Explanation:
I ¬∀xP(x) ≡ ∃x¬P(x)
and IV ∃x ¬P(x)
Clearly, choices I and IV are equivalent.
II ¬∃xP(x) ≡ ∀x ¬P(x)
and III ¬∃x[¬P(x)] ≡ ∀xP(x)
Clearly, II and III are not equivalent to each other or to I and IV.


Computer Science Mathematical Logic Questions and Answers

Question 36.
Suppose the predicate F(x, y, t) is used to represent the statement that person x can fool person y at time t. Which one of the statements below expresses best the meaning of the formula ∀x∃y∃t (¬F(x, y, t))?
(a) Everyone can fool some person at some time
(b) No one can fool everyone all the time
(c) Everyone cannot fool some person all the time
(d) No one can fool some person at some time

Answer/Explanation

Answer: (b) No one can fool everyone all the time
Explanation:
∀x ∃y ∃t ¬ F(x, y, t)
≡ ¬{∃x ∀y ∀t F(x, y, t)}
≡ it is not true that (someone can fool all people at all times)
≡ no one can fool everyone all the time


Question 37.
Which one of the following options is CORRECT given three positive integers x, y, and z, and a predicate
P (x) = ¬ (x = 1) ∧ ∀y (∃z (x = y * z) ⇒ (y = x) ∨ (y = 1)
(a) P(x) being true means that x is a prime number
(b) P(x) being true means that x is a number other than 1
(c) P(x) is always true irrespective of the value of x
(d) P(x) being true means that x has exactly two factors other than 1 and x

Answer/Explanation

Answer: (a) P(x) being true means that x is a prime number
Explanation:
If P(x) is true, then
x ≠ 1 and also
x is broken into two factors, only if, one of the factors is x itself and the other factor is 1, which is exactly the definition of a prime number.
So P(x) is true means x is a prime number.


Question 38.
Consider the following logical inferences.
I1: If it rains then the cricket match will not be played.
The cricket match was played.
Inference: There was no rain.
I2: If it rains then the cricket match will not be played.
It did not rain.
Inference: The cricket match was played.
Which of the following is TRUE?
(a) Both I1 and I2 are correct inferences
(b) I1 is correct but I2 is not a correct inference
(c) I1 is not correct but I2 is a correct inference
(d) Both I1 and I2 are not correct inferences

Answer/Explanation

Answer: (b) I1 is correct but I2 is not a correct inference
Explanation:
Let p: It rains
q: cricket match will not be played.
I1: p ⇒ q
∴ \(\underline{\sim q}{\sim p}\)
Clearly I1 is correct since it is in the form of modus Tollens (rule of contrapositive)

I2: p ⇒ q
∴ \(\underline{\sim q}{\sim p}\)
which corresponds [p ⇒ q ∧~p] ⇒ ~ q
≡ [(p’ + q) p’] ⇒ q’
≡ [p’ + qp’] ⇒ q’
≡p’ ⇒ q’
≡(p’)’ + q’ ≡p + q’
which is not a tautology. So I2 is incorrect inference.


Question 39.
What is the correct translation of the following statement into mathematical logic?
“Some real numbers are rational”
(a) ∃x (real (x) ∨ rational (x))
(b) ∀x (real (x) → rational (x))
(c) ∃x (real (x) ∧ rational (x))
(d) ∃x (rational (x) → real (x))

Answer/Explanation

Answer: (c) ∃x (real (x) ∧ rational (x))
Explanation:
Some real numbers are rational ≡∃x [real (x) ∧rational (x)]


Computer Science Mathematical Logic Questions and Answers

Question 40.
What is the logical translation of the following statements?
“None of my friends are perfect”
(a) ∃x (F(x) ∧ ¬ P(x))
(b) ∃x (¬ F(x) ∧ Fix))
(c) ∃x (¬ F(x) ∧ ¬P(x))
(d) ¬∃x (F(x) ∧ P(x))

Answer/Explanation

Answer: (d) ¬∃x (F(x) ∧ P(x))
Explanation:
None of my friends are perfect i.e., all of my friends are not perfect
∀x((F(x) → ¬ P(x))
∀x(¬ F(x) ∨¬ P(x))
¬ ∃x (F(x) ∧ P(x))
Alternatively
∃x (F(x) ∧ P(x)) gives
there exist some of my friends who are perfect, ¬∃x (F(x) ∧ P(x))
there does not exist any friend who is perfect i.e., none of my friends are perfect. So (d) is the correct option.


Question 41.
Which one of the following is NOT logically equivalent to ¬∃x(∀y(α) ∧ ∀z(β))
(a) ∀x(∃z(¬β) → ∀y(α))
(b) ∀x(∀z(β) → ∃y(¬ α))
(c) ∀x(∀y(α) → ∃z(¬β))
(d) ∀x(∃y(¬ α)∨ ∃z(¬β))

Answer/Explanation

Answer: (a) ∀x(∃z(¬β) → ∀y(α))
Explanation:
Let, ∀y(α) = p, ∀z(β) = Q
then, ∃y(¬α) = ¬p and ∃z (¬β) = ¬Q
Given, ¬∃x(∀y(α) ∧∀z(β))
= ¬∃x(P ∧ Q) = ¬∀x (¬P ∨¬Q)
= ∀x (P →¬Q)
(a) ∀x(∃z(¬β) → ∀y(α)) = ∀x (¬Q → P)
(b) ∀x(∀z(β) → ∃y(¬α)) = ∀x (Q → ¬ P)
= ∀x (P →¬Q)
(c) ∀x (∀x(α) → ∃z (¬β)) = ∀x (P → ¬ Q)
(d) ∀x (∃y(¬α) ∨ ∃z (¬β)) = ∀x (¬ P ∨ ¬ Q)
= ∀x (P → ¬ Q)
∴ Only (a) is not logocally equivalent to ∀x(P → ¬ Q).


Question 42.
Consider the statement:
“Not all that glitters is gold”
Predicate glitters(x) is true if x glitters and predicate gold(x) is true if x is gold. Which one of the following logical formulae represents the above statement?
(a) ∀x: glitters(x) ⇒ ¬gold(x)
(b) ∀x : gold(x) ⇒ glitters(x)
(c) ∃x : gold(x) ∧¬glitters(x)
(d) ∃x: glitters(x) ∧¬gold(x)

Answer/Explanation

Answer: (d) ∃x: glitters(x) ∧¬gold(x)
Explanation:
(a) ∀x glitters (x) ⇒¬gold (x) All glitters are not gold
(b) ∀x gold(x) ⇒ glitters(x) All golds are glitters
(c) ∃x gold(x) ∧ ¬ glitters(x) There exist gold which is not glitter i.e. not all golds are glitters.
(d) ∃x glitters(x) ∧ ¬ gold(x) Not all that glitters is gold i.e., there exist some which glitters and which is not gold.


Question 43.
Which one of the following propositional logic formulas is TRUE when exactly two of p, q, and r are TRUE?
(a) ((p ↔ q) ∧ r) ∨ (p ∧ q ∧ ~ r)
(b) (~ (p ↔ q) ∧ r) ∨ (p ∧ q ∧ ~ r)
(c) ((p → q) ∧ r) ∨ (p ∧ q ∧ ~ r)
(d) (~ (p ↔ q) ∧ r) ∧ (p ∧ q ∧ ~ r)

Answer/Explanation

Answer: (b) (~ (p ↔ q) ∧ r) ∨ (p ∧ q ∧ ~ r)
Explanation:
Option (b) is (~(p ↔ q) ∧ r) ∨ (p ∧ q ∧ ~r)
≡((p ⊕ q)r) + pqr’ ≡(pq’ + p’q)r + pqr’
≡pq’r + p’qr + pqr’ ≡pqr’ + pq’r + pq’r
This is exactly the mm-term form of a logical formula which is true when exactly two variables are true (only p, q true or only p, r true or the only q, r true).


Question 44.
Which one of the following Boolean expressions is NOT a tautology?
(a) ((a → b) ∧ (b → c)) → (a → c)
(b) (a ↔ c) → (~b → (a ∧ c))
(c) (a ∧ b ∧ c) → (c ∨ a)
(d) a →(b → a)

Answer/Explanation

Answer: (b) (a ↔ c) → (~b → (a ∧ c))
Explanation:
(a ↔ c) → (~ b → (a ∧c))
≡ (a ↔ c )’ + (b’ → ac)
≡(a ⊕ c)’ + (b’ → ac)
≡ac’ + a’c + b + ac
≡a(c’ + c) + a’c + b
≡a + a’c + b ≡a + c + b
which is not a tautology.


Question 45.
Consider the following statements:
P: Good mobile phones are not cheap
Q: Cheap mobile phones are not good
L: P implies Q
M: Q implies P
N: P is equivalent to Q
Which one of the following about L, M, and N is CORRECT?
(a) Only L is TRUE
(b) Only M is TRUE
(c) Only N is TRUE
(d) L, M, and N are TRUE.

Answer/Explanation

Answer: (d) L, M, and N are TRUE.
Explanation:
g: mobile is good
C: mobile is cheap
P: Good mobile phones are not cheap
g → c’ ≅ (g’ + c’)
Q: Cheap mobile phones are not good
c → g’ ≅ (c’ + g’)
:. Both P and Q are equivalent.
L: P → Q
M: Q → P
N: P ≡ Q
Since both P and Q are equivalent, all three of L. M, N are true. So the correct option is (d).


Computer Science Mathematical Logic Questions and Answers

Question 46.
The CORRECT formula for the sentence, “not all rainy days are cold” is
(a) ∀d(Rainy (d)∧~Cold (d))
(b) ∀d (~Rainy (d) → Cold (d))
(c) ∃d (~Rainy (d) → Cold (d))
(d) ∃d (Rainy (d)∧ ~ Cold (d))

Answer/Explanation

Answer: (d) ∃d (Rainy (d)∧ ~ Cold (d))
Explanation:
Not (all rainy days are cold):
~ (∀d (Rainy (d) → Cold (d)))
≡~ (∀d (~ Rainy (d) ∨ Cold (d)))
≡ ∃d (Rainy (d)∧ ~ Cold (d))
Alternate Method:
Not all rainy days are cold is same as some rainy days are not cold which is the same as ∃d (Rainy (d)∧ ~ Cold (d))


Question 47.
Which one of the following is Not equivalent to p ↔ q?
(a) (¬p ∨ q) ∧ (p ∨¬ q)
(b) (¬p ∨ q) ∧ (q → p)
(c) (¬p ∧ q) ∨ (p ∧ ¬q)
(d) (¬p ∧¬q) ∨ (p ∧ q)

Answer/Explanation

Answer: (c) (¬p ∧ q) ∨ (p ∧ ¬q)
Explanation:
Here, option (a) and (b) can be reduced to (p → q) ∧ (q → p) and hence = p ↔ q
Option (d) is p’q’ + pq ≡ p ↔ q.
Option (c) is p’q + pq’ = p ⊕ q which is not equivalent to p ↔ q.


Question 48.
The binary operator ≠ is defined by the following truth table.
Table
Which one of the following is true about the binary operator ≠ ?
(a) Both commutative and associative
(b) Commutative but not associative
(c) Not commutative but associative
(d) Neither commutative nor associative

Answer/Explanation

Answer: (a) Both commutative and associative
Explanation:
The given truth table corresponds to p’q + pq’ = P ⊕ q. ⊕ is known to be both commutative and associative.


Question 49.
Consider the following two statements:
S1: If a candidate is known to be corrupt, then he will not be elected.
S2: If a candidate is kind, he will be elected. Which one of the following statements follows from S1 and S2 as per sound inference rules of logic?
(a) If a person is known to be corrupt, he is kind
(b) If a person is not known to be corrupt, he is not kind
(c) If a person is kind, he is not known to be corrupt
(d) If a person is not kind, he is not known to be corrupt

Answer/Explanation

Answer: (c) If a person is kind, he is not known to be corrupt
Explanation:
C: Person is corrupt
K: Person is kind.
E : Person is elected
S1 : C → \(\bar{E}\)
S2: K → E
S2 ↔ \(\bar{E}\) → \(\bar{K}\)
So from S1 and S2:(C → \(\bar{E}\)) ∧ (\(\bar{E}\) → \(\bar{K}\)) ≅ C → \(\bar{K}\) We can conclude C → \(\bar{K}\) which is same as K → \(\bar{C}\), which is same as option (c).


Question 50.
Which one of the following well-formed formulae is a tautology?
(a) ∀x ∃y R(x, y) ↔ ∃y ∀x R(x, y)
(b) (∀x [∃y R(x, y) → S(x, y)]) → ∀x ∃y S(x, y)
(c) [∀x ∃y (P(x, y) → R(x, y))] ↔ [∀x ∃y (¬P(x, y) ∨R(x, y))]
(d) ∀x ∀y P(x, y) → ∀x ∀y P(y, x)

Answer/Explanation

Answer: (c) [∀x ∃y (P(x, y) → R(x, y))] ↔ [∀x ∃y (¬P(x, y) ∨ R(x, y))]
Explanation:
Since P → R ≡¬P ∨R, and both the sides are the same (∀x∃y) Option (e) is clearly a tautology.


Computer Science Mathematical Logic Questions and Answers

Question 51.
In a room, there are only two types of people, namely, Type 1 and Type 2. Type 1 people always tell the truth and Type 2 people always lie. You give a fair coin to a person in that room, without knowing which type he is from and tell him to toss it and hide the result from you till you ask for it. Upon asking, the person replies the following:
“The result of the toss is head if and only if I am telling the truth.”
Which of the following options is correct?
(a) The result is head
(b) The result is tail
(c) If the person is of Type 2, then the result is tail
(d) If the person is of Type 1, then the result is tail

Answer/Explanation

Answer: (a) The result is head
Explanation:
Type 1 always tells truth.
Type 2 always tells lies.
The statement is “toss is head if and only if I am telling the truth”.
There are two cases possible.
Case-1: Let the person be type 1.
Case-2: Let the person be type 2.
In each case, we shall prove that result is head.
Case-1: Let the person be type 1. Type 1 always tells truth.
So the statement “toss is head if and only if I am telling the truth” is true.
So toss head ⇔ telling truth. Since type 1 is telling truth so toss head is also true. So in case, 1 the result is that the toss is head.
Case-2: Let the person be type 2. Type 2 always tells lies.
So the statement “toss is head if and only if I am telling the truth” is false.
So toss head ⇔ telling truth is false. So toss head ⊕ telling truth. So toss head and telling truth to have opposite truth values. Now, since type 2 telling truth is false, so toss head has to have the opposite truth value which is true.
So toss head is true. So in case 2 also, the result is head.
So in both cases, we have proved that the result is head.
So option (a) is correct.


Question 52.
Let p, q, r, s represent the following propositions.
p : x∈ {8, 9, 10, 11, 12}
q : x is a composite number
r : x is a perfect square
s : x is a prime number
The integer x ≥ 2 which satisfies ¬((p ⇒ q) ∧ (¬r ∨ ¬is)) is ______.

Answer/Explanation

Explanation: We wish to make
¬ ((p ⇒ q) ∧ (¬r ∨ ¬s)) = 1
⇒ (p ⇒ q) ∧ (¬r ∨ ¬s) = 0
⇒ (p ⇒ q) = 0
or ¬r ∨ ¬s = 0

Now (1) is satisfies only when p 1 and q = 0.
Equation (2) ¬r ∨ ¬s = 0, iff r ∧ s = 1
i.e. r 1 and s= 1
i.e. x is a perfect square and x is a prime number. Which is not possible so condition (2) cannot be satisfied by any x. So condition (1) must be satisfies which is p = 1 and q = 0 i.e. x e {8, 9, 10, 11, 12,) and x is not a composite. Now the only value of x which satisfies this is x = 11. So correct answer is x = 11.


Question 53.
Consider the following expressions:
(i) False
(ii) Q
(iii) True
(iv) P ∨ Q
(v) ¬Q ∨ P
The number of expressions given above that is logically implied by P∧(P ⇒ Q) is ______.

Answer/Explanation

Solution:
p∧(p ⇒ q) = p(p’ + q) =pq
Take (i) false
pq ⇒ false ≡ pq ⇒ 0
≡ (pq)’ + 0
≡ p’ + q’ + 0
≡ not valid

Take (ii)
pq ⇒ q = (pq)’ + q
≡ (pq)’ + q
≡ p’ + 1 = 1
≡ valid

Take (iii)
pq ⇒ true ≡ pq ⇒ 1
≡ (pq)’ + 1 ≡ 1
≡ valid

Take (iv)
pq ⇒ p + q ≡ (pq)’ + p + q
≡ P’ + q’ + P + q
≡ 1 + 1
≡ 1
≡ valid

Take (v)
pq ⇒ q’ + p ≡ (pq)’ + q’ + p
≡ p’ + q’ + q’ + p
≡ 1
≡ valid

So the number of expressions that are logically implied by p ∧ (p ⇒ q) is 4.


Question 54.
Which one of the following well-formed formulae in predicate calculus is NOT valid?
(a) (∀x p(x) ⇒ ∀xq(x)) ⇒ (∃x¬p(x) ∨ ∀xq(x))
(b) (∃xp(x) ∨∃xg(x)) ⇒ ∃x(p(x) ∨q(x))
(c) ∃x (p(x) ∧ q(x)) ⇒ (∃x p(x) ∧ ∃xq(x))
(d) ∀x (p(x) ∨ q(x)) ⇒ (∀x p(x) ∨ ∀xq(x))

Answer/Explanation

Answer: (d) ∀x (p(x) ∨ q(x)) ⇒ (∀x p(x) ∨ ∀xq(x))

Explanation:
∀x is only one way distribution over “∨” so let us check (d)
(d) ∀x (p(x) ∨ q(x)) ⇒ (∀x p(x) ∨ ∀xq(x))
Let LHS be true, so we have,
P1 ∨ q1 (true)
p2 ∨ q2 (true)
p3 ∨ q3 (true)
.
.
.

Now take p1 is true, q1 is false and p2 is false, q2 is true.
Now LHS is true, but RHS, ∀x p(x) is false (since p2 is false) and ∀x q(x) is also false (since q1 is false)
So, LHS ≠ RHS.


Computer Science Mathematical Logic Questions and Answers

Question 55.
Consider the first-order logic sentence F : ∀x(∃yR(x,y)). Assuming non-empty logical domains, which of the sentences below are implied by F?
I. ∃y(∃x R(x,y))
II. ∃y(∀x R(x,y))
III. ∀y(∃x R(x,y))
IV. ¬∃x(∀y ¬R(x,y))
(a) IV only
(b) I and IV only
(c) II only
(d) II and III only

Answer/Explanation

Answer: (b) I and IV only
Explanation:
I. ∀x ∃y R(x,y) →∃y (∃x R(x,y)) is true, since ∃y (∃x R(x,y))
II. ∀x ∃y R(x,y) →∃y (∀x R(x,y)) is false Since ∃y when it is outside is stronger than when it is inside.
III. ∀x ∃y R(x,y) → ∀y ∃x R(x,y) is false Since R(x, y) may not be symmetric in x and y.
IV. ∀x ∃y R(x,y) →¬ (∃x ∀y ¬R(x,y)) is true since ¬ (∃x ∀y ¬R(x,y)) ≡∀x ∃y R (x,y)
So, IV will reduce to ∀x ∃y R(x,y) → ∀x ∃y R(x,y) which is trivially true.
So the correct answer is I and IV only which is an option (b).


Question 56.
The statement (¬p) ⇒ (¬q) is logically equivalent to which of the statements below?
I. P ⇒ q
II. q ⇒ p
III. (¬q) ∨ p
IV. (¬p) ∨ q
(a) I only
(b) I and IV only
(c) II only
(d) II and III only

Answer/Explanation

Answer: (d) II and III only
Explanation:
Statement p’ ⇒ q’ ≡p + q’
I. p → q ≡p’ + q
II. q → p ≡ q’ + p
III. (¬q ∨ p) ≡ q’ + p.
IV. (¬p ∨ q) ≡p’ + q
So, clearly, the given statement is the same as II and III only.



Question 57.
Let p, q and r be propositions and the expression (p → q)→r be a contradiction. Then, the expression (r→p)→q is
(a) A tautology
(b) A contradiction
(c) Always TRUE when p is FALSE
(d) Always TRUE when q is TRUE

Answer/Explanation

Answer:
(d) Always TRUE when q is TRUE
Explanation:
(p → q) → r = 0
i.e., (p’ + q)’ + r = 0
i.e., pq’ + r = 0
This is possible only if pq’ = 0 and r = 0 Now, pq’ = 0 iff p = 0 or q’ = 0
So, final solution is r = 0 and (p = 0 or q’ = 0) Now let us see
(r → p) → q
≡(r’ + p)’ + q ≡ rp’ + q but we have previously shown that r – 0 So, rp’ = 0
So, (r → p) → q ≡ rp’ + q ≡ 0 + q ≡ q
So, the truth value of (r → p) → q is the same as that of q. So It is true whenever q is true.
So option (d) is correct.
Note: Since we have shown that (p 0 (or) q’ = 0) is true,
Option (c) is false because when p is false i.e.,
when p = 0, q is free to be O or 1.


Question 58.
Let p, q, r denote the statements “It is raining”, “It is cold”, and “It is pleasant”, respectively. Then the statement “It is not raining and it is pleasant, and it is not pleasant only if it is raining and it is cold” is represented by
(a) (¬ p ∧ r) ∧ (¬r → (p ∧ q))
(b) (¬ p ∧ r) ∧ ((p ∧ q) → ¬r)
(c) (¬ p ∧ r) ∨ ((p ∧ q) → ¬r)
(d) (¬ p ∧ r) ∨ (r → (P ∧ q))

Answer/Explanation

Answer:
(a) (¬ p ∧ r) ∧ (¬r → (p ∧ q))
Explanation:
p : “It is raining”,
q : “It is cold”, and
r : “It is pleasant”
So the correct representation of “It is not raining and it is pleasant, and it is not pleasant only if it is raining and it is cold” is
(¬p ∧ r) ∧ (¬r only if p ∧q)≡(¬p ∧ r) ∧ (¬r → (p ∧ q))


Question 59.
Consider the first order predicate formula φ:∀x[∀z z|x ⇒∃w (w >x) ∧(∀z z | w ⇒ (( w = z) ∨ (z = 1)))]
Here ‘a | b’ denotes that ‘a divides b’, where a and b are integers. Consider the following sets:
S1:{1, 2, 3, …, 100}
S2: Set of all positive integers
S3: Set of all integers
Which of the above sets satisfy φ?
(a) S1 and S3
(b) S2 and S3
(c) S1 S2 and S3
(d) S1 and S2

Answer/Explanation

Answer:
(b) S2 and S3
Explanation:
∀x[∀z|x ⇒ ((z = x) ∨ (z = 1)) ⇒ ∃w (w > x) ∧(∀z z | w ⇒((w = z) ∨(z = 1))) ]
The predicate φ simply says that if z is a prime number in the set then there exists another prime number in the set which is larger. Clearly, φ is true in S2 and S3 since in a set of all integers as well as all positive integers, there is a prime number greater than any given prime number.
However, in S1 : {1, 2, 3 100} φ is false since for prime number 97 ∈ S1 there exists no prime number in the set which is greater.


Question 60.
Which one of the following predicate formulae is NOT logically valid?
Note that W is a predicate formula without any free occurrence of x.
(a) ∃x(p(x) ∧ W) ≡ ∃x p (x) ∧ W
(b) ∀x(p(x) → W) ≡ ∀xp(x) → W
(c) ∃x(p(x) → W) ≡ ∀xp(x) → W
(d) ∀x(p(x) ∨ W) ≡ ∀x p(x) ∨ W

Answer/Explanation

Answer: (b) ∀x(p(x) → W) ≡ ∀xp(x) → W
Explanation:
∀x (p(x) → W) ⇒ (∀x p(x)) → W is true.
But (∀x p(x)) → W ⇒ ∀x (p(x) → W) is false. Since if LHS is true then (P1 ∧ P2 ∧ P3 … ∧Pn ) → W will be true and RHS will be false since P1 W, itself will be false since only P1 true cannot make W true (we need all the P1, P2 … Pn to be true to make W true)
So LHS ⇒ RHS is true and RHS ⇒ LHS is false so LHS ≠ RHS.
So option (b) is invalid.
Note that option (c) is true because by Boolean algebra,
LHS = ∃x (p(x) → W) ≡ ∃x (~p(x) ∨ W) ≡ ∃x (~p(x)) ∨ W
RHS = ∀x p(x) → W ≡ ~(∀x p(x)) ∨ W ≡ ∃x ~p(x) ∨ W
So LHS = RHS.


Computer Science Mathematical Logic Questions and Answers

Question 61.
Let p and q be two propositions. Consider the following two formulae in propositional logic.
S1: (¬ p ∧ (p ∨ q)) → p
S2: q → ( ¬ p ∧ (p ∨ q))
Which one of the following choices is correct?
(a) Neither S1 nor S2 is a tautology.
(b) Both S1 and S2 are tautologies.
(c) S1 is a tautology but S2 is not a tautology.
(d) S1 is not a tautology S2 is a tautology.

Answer/Explanation

Answer: (c) S1 is a tautology but S2 is not a tautology.
Explanation:
S1: (¬p ∧(p ∨q)) →p
S2: q → (¬p ∧(p ∨q))
S1 : [p’ (p + q)] →p
≡(p’p + p’q) →q
≡p’q →q
≡(p’q)’ + q
≡p + q’ + q
≡p + 1
≡1 (tautology)

S2: q → (p’ (p + q))
≡ q → (p’p + p’q)
≡ q → p’q
≡ q’ + p’q
≡ (q’ + p’) (q’ + q)
≡q’ + p’ (contigency) (not a tautology) So, option (c) S1 is a tautology and S2 is not a tautology is correct.


Question 62.
Choose the correct choice(s) regarding the following propositional logic assertion S:
S : ((p ∧ Q) →R) → ( (P ∧Q) →(Q → R))
(a) S is a tautology.
(b) S is neither a tautology nor a contradiction.
(c) The antecedent of S is logically equivalent to the consequent of S.
(d) S is a contradiction.

Answer/Explanation

Answer: (a) S is a tautology.(c) The antecedent of S is logically equivalent to the consequent of S.
Explanation:
S : ((P ∧ Q) → R) → ((P ∧ Q) → (Q → R))
≡ (pq → r) → (pq → (q → r))
≡ [(pq)’ + r] [(pq)’ + (q’ + r)]
≡ [(pq)’ + r]’ + [(pq)’ + q’ + r]
≡ [pq . r’] + [p’ + q’ + q’ + r]
≡ pqr’ + p’ + q’ + r
≡ (p + P’)(qr’ + p’) + q’ + r
≡ qr’ + p’ + q’ + r
≡ (q + q’)(r’ + q’) + p’ + r
≡ r’+ q’ + p’ + r = r’ + r + q’ + p’
≡ 1+ q’ + p’ = 1 (Tautology)
So, S is a tautology.
So, option (a) is true.
Option (b) and (d) are false.
Option (c) antecedent of S is
pq → r ≡ (pq)’ + r
≡ p’ + q’ + r
The consequent of S is pq → (q → r)
≡ (pq)’ + q’ + r
≡ p’ + q’ + q’ + r
≡ p’ + q’ + r
So,Antecedent of S ≡ Consequent of S So, option (c) is also true.