GATE IT 2008 | Question: 22

Question

Which of the following is the negation of $[∀ x, α → (∃y, β → (∀ u, ∃v, y))]$

• A. $[∃ x, α → (∀y, β → (∃u, ∀ v, y))]$
• B. $[∃ x, α → (∀y, β → (∃u, ∀ v, ¬y))]$
• C. $[∀ x, ¬α → (∃y, ¬β → (∀u, ∃ v, ¬y))]$
• D. $[∃ x, α \wedge (∀y, β \wedge (∃u, ∀ v, ¬y))]$

Comments

https://youtu.be/s41PLmHGf08?list=PLIPZ2_p3RNHidhFvyKH4U_VE1rFAyvG8U&t=4607

---

@Arjun plz check this ..Am I right ? because most of the comment are confusing Here I am considering comma as bracket .

$$\forall x \left[ \alpha \rightarrow \left( \exists y \left( \beta \rightarrow \left( \forall u \left( \exists v (y) \right) \right) \right) \right) \right]$$

$$  Now  -take -negation $$

$$\neg \Big( \forall x \left[ \alpha \rightarrow \left( \exists y \left( \beta \rightarrow \left( \forall u \exists v (y) \right) \right) \right) \right] \Big)$$

$$\exists x \,\,\,\mathbf{\neg} \left[ \alpha \rightarrow \left( \exists y \left( \beta \rightarrow \left( \forall u \exists v (y) \right) \right) \right) \right]$$

$$\exists x \left[ \alpha \wedge \mathbf{\neg} \left( \exists y \left( \beta \rightarrow \left( \forall u \exists v (y) \right) \right) \right) \right]$$

$$\exists x \left[ \alpha \wedge \left( \forall y \,\,\,\mathbf{\neg} \left( \beta \rightarrow \left( \forall u \exists v (y) \right) \right) \right) \right]$$

$$\exists x \left[ \alpha \wedge \left( \forall y \left( \beta \wedge \mathbf{\neg} \left( \forall u \exists v (y) \right) \right) \right) \right]$$

$$\exists x \left[ \alpha \wedge \left( \forall y \left( \beta \wedge \left( \exists u \forall v (\neg y) \right) \right) \right) \right]$$

$$[\exists x, \alpha \wedge (\forall y, \beta \wedge (\exists u, \forall v, \neg y))]$$

 

 

---

Option  D is correct

Answer 1

$[∀ x, α → (∃y, β → (∀ u, ∃v, y))] \equiv [∀ x, ¬α \vee  (∃y, ¬β v (∀ u, ∃v, y))]$

Now, doing complement gives (complement of $∀$ is $∃$ and vice versa while propagating negation inwards as $∀x (P) \equiv ¬∃x (¬P)$ and $∃x (P) \equiv ¬∀x (¬P))$

$[∃ x, α \wedge (∀y, β \wedge (∃ u, ∀ v, ¬y))]$

(D) choice

Comments

@Pranavpurkar Yeah, now I am not getting it. Probably before I didn’t consider negation of arrow (→) to be important. But if we don’t negate implication then the predicate will be wrong!

---

Isn’t this the correct answer? And what do these commas mean here?

---

got it

Answer 2

dont solve full its just waste of time 

follow my rule and save your time

 

Answer 3

It's very important to notice how the commas are being used here.....

Comma between Quantifier and Predicate ends up getting seperated as a bracket which is a key thing to know....