GATE IT 2005 | Question: 36

Question

Let $P(x)$ and $Q(x)$ be arbitrary predicates. Which of the following statements is always TRUE?

• A. $\left(\left(\forall x \left(P\left(x\right) \vee Q\left(x\right)\right)\right)\right) \implies \left(\left(\forall x P\left(x\right)\right) \vee \left(\forall xQ\left(x\right)\right)\right)$
• B. $\left(\forall x \left(P\left(x\right) \implies Q\left(x\right)\right)\right) \implies \left(\left(\forall x P\left(x\right)\right) \implies \left(\forall xQ\left(x\right)\right)\right)$
• C. $\left(\forall x\left(P\left(x\right) \right) \implies \forall x \left( Q\left(x\right)\right)\right) \implies \left(\forall x \left( P\left(x\right) \implies Q\left(x\right)\right)\right)$
• D. $\left(\forall x \left( P\left(x\right)\right) \Leftrightarrow \left(\forall x \left( Q\left(x\right)\right)\right) \right) \implies \left(\forall x  \left (P\left(x\right) \Leftrightarrow Q\left(x\right)\right)\right)$

Comments

https://youtu.be/P910Ue-gDG8?t=1160

---

In the go book ,In option D of this question there is a mistake in Brackets in option D

---

Satish sir’s box method also works for this

Answer 1

For brevity, $P(x)$ is written as $P_x$ and the connectives are interchanged with +, *, ‘

Let the domain be $\{1, 2\}$

Option A:

$\forall x (P_x + Q_x) \rightarrow \forall x P_x + \forall x Q_x$

$=\{(P_1 + Q_1)(P_2 + Q_2)\} \rightarrow P_1P_2 + Q_1Q_2 = P_1’Q_1’ + P_2’Q_2’ + P_1P_2 + Q_1Q_2 =$ a contingency

 

Option B: (Ans)

$\forall x (P_x \rightarrow Q_x) \rightarrow (\forall x P_x \rightarrow \forall x Q_x)$

$= (P_1’+ Q_1)(P_2’+ Q_2) \rightarrow (P_1P_2 \rightarrow Q_1Q_2) = P_1Q_1’ + P_2Q_2’ + (P_1’ + P_2’) + Q_1Q_2$

$= P_1’ + Q_1’ + P_2’ + Q_2’ + Q_1Q_2 = P_1’ + P_2’ + (Q_1Q_2)’ + Q_1Q_2 = 1 = $ valid

 

Option C:

$(\forall x P_x \rightarrow \forall x Q_x) \rightarrow \forall x (P_x \rightarrow Q_x)$

$= (P_1P_2 \rightarrow Q_1Q_2) \rightarrow  (P_1’+ Q_1)(P_2’+ Q_2) = (P_1P_2)(Q_1Q_2)’ + (P_1’+ Q_1)(P_2’+ Q_2) =$ contingency

 

Option D:

$(\forall x P_x \leftrightarrow \forall x Q_x )\rightarrow \forall x (P_x \leftrightarrow Q_x)$

$=(P_1P_2 \leftrightarrow Q_1Q_2) \rightarrow (P_1 \leftrightarrow Q_1)(P_2 \leftrightarrow Q_2)$

$=(P_1P_2Q_1Q_2 + (P_1P_2)’(Q_1Q_2)’) \rightarrow (P_1Q_1 + P_1’Q_1’)(P_2Q_2 + P_2’Q_2’)$

$=(P_1P_2Q_1Q_2)’(P_1P_2 + Q_1Q_2) + (P_1Q_1 + P_1’Q_1’)(P_2Q_2 + P_2’Q_2’) = $ contingency

 

NOTE:

For Options (A.), (C.) and (D.) put $P_1,P_2,Q_1,Q_2 = 1, 0, 0, 1$ to prove contingency

Comments

Required Information:

FOL conversion to Propositional Form

$\forall xP(x) \equiv \{P(x_1) \land P(x_2) \land … \}, x_i \in \text{domain(}x)$

i.e., the conjunction of all propositions

$\exists xP(x) \equiv \{P(x_1) \lor P(x_2) \lor … \}, x_i \in \text{domain(}x)$

i.e., the disjunction of all propositions

Answer 2

For the better explanation check this one

https://www.youtube.com/watch?v=xR2YzdGzf9k

Answer 3

Generally, these type of questions can be solved by using two statements and checking the validity of each and every option.
Here, let the statements be P and Q where,
P : Student is a girl
Q : Student is smart

Option B says that, IF for all student x : If x is a girl then the student is smart THEN IF the whole class comprises of girls then the whole class comprises of smart students.

Answer 4

First of all define the domain of x. Then assign some practically feasible attribute defination for P and Q.

Let x is the set of persons (i.e x is a person) and, P and Q respectively be GOES TO GYM and TAKES PROTEIN. Then we can have

(a) [For every person either it goes to gym or takes protein] ---> [Every person goes to gym or Every person takes protein].

(b) [For every person if it goes to gym then it takes protein]--->[If every person goes to gym then every person takes protein]

(c)[If every person goes to gym then every person takes protein]--->[For every person if it goes to gym then it takes protein]

(d)[If and only if every person goes to gym then every person takes protein]--->[Every person if and only if it goes to gym then it takes protein].

NOW BASED ON YOUR INTUITION YOU CAN CLEARLY LEFT (A), (C) (D) AND CHOOSE (B).

PS: It's my very first answer here on GATE OVERFLOW. :):)