سوال ۹۱ کنکور ارشد علوم کامپیوتر ۱۴۰۴

Push the negation inward step by step, using the quantifier-negation rules $\neg \forall x\, \Phi \equiv \exists x\, \neg\Phi$ and $\neg \exists y\, \Psi \equiv \forall y\, \neg\Psi$:

$\neg \forall x\, \exists y\, P(x,y) \equiv \exists x\, \neg \exists y\, P(x,y) \equiv \exists x\, \forall y\, \neg P(x,y).$

So the canonical form is $\exists x\, \forall y\, \neg P(x,y)$. Now reduce each candidate to a fully pushed-in form and compare.

(a) $\exists x\, \neg \forall y\, P(x,y) \equiv \exists x\, \exists y\, \neg P(x,y)$. The inner quantifier is $\exists y$, not $\forall y$ — not equivalent.

(b) $\exists x\, \exists y\, \neg P(x,y)$. Same as (a); inner quantifier is $\exists y$ — not equivalent.

(c) $\exists x\, \neg \exists y\, P(x,y) \equiv \exists x\, \forall y\, \neg P(x,y)$. Matches the canonical form — equivalent $\checkmark$.

(d) $\exists x\, \forall y\, \neg P(x,y)$. Already the canonical form — equivalent $\checkmark$.

Exactly two propositions, (c) and (d), are logically equivalent to the original. The answer is option 2.

Pitfall: Negating a $\forall$ flips it to $\exists$ and negating an $\exists$ flips it to $\forall$. Choices (a) and (b) keep an existential inner quantifier, which is the negation of the original's pattern, so they are equivalent to each other but not to $\exists x\, \forall y\, \neg P$.