سوال ۹۷ کنکور ارشد علوم کامپیوتر ۱۳۹۸

Check each claimed equivalence by comparing the exact conditions under which the two sides are false. Two formulas are logically equivalent iff they fail on the same models.

Option 1 (correct).

$\exists x\,P(x) \to \forall y\,P(y) \;\equiv\; \forall x\,\forall y\,(P(x) \to P(y))$

The right side $\forall x\,\forall y\,(P(x)\to P(y))$ is false exactly when there exist $x,y$ with $P(x)$ true and $P(y)$ false — i.e. $P$ holds for some element but not all:

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

The left side $\exists x\,P(x) \to \forall y\,P(y)$ is false exactly when its antecedent is true and its consequent is false:

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

The two failure conditions are identical, so the equivalence holds. Intuitively, both say: if any element satisfies $P$, then every element does (so $P$ is either everywhere-false or everywhere-true).

Option 2 (wrong). The left side is $\forall x\,P(x) \to \forall y\,P(y)$. Since the antecedent and consequent are the same sentence $\forall P$, this is of the form $A \to A$, a tautology (always true). But the right side $\forall x\forall y(P(x)\to P(y))$ is false whenever $P$ is mixed (true on some elements, false on others), e.g. domain $\{a,b\}$ with $P(a)$ true, $P(b)$ false. A tautology cannot equal a non-tautology.

Option 3 (wrong). Swapping $\forall$ and $\exists$ is not sound. Only one direction holds:

$\exists y\,\forall x\,Q(x,y) \;\Rightarrow\; \forall x\,\exists y\,Q(x,y),$

but not the converse. Counterexample: domain $\mathbb{Z}$, $Q(x,y):\; x < y$. Then $\forall x\,\exists y\,(x<y)$ is true (take $y=x+1$), yet $\exists y\,\forall x\,(x<y)$ is false (no single $y$ exceeds every $x$).

Option 4 (wrong). The existential quantifier does not distribute over conjunction. The left side needs a single witness $y$ satisfying both $R$ and $S$; the right side allows different witnesses. Counterexample: domain $\{a,b\}$ with $R(a)$ true, $S(a)$ false, $R(b)$ false, $S(b)$ true. Then $\exists y\,R(y)$ and $\exists y\,S(y)$ are both true, but no $y$ satisfies $R(y)\wedge S(y)$, so the left side is false.

Only Option 1 is a genuine equivalence.

Exam trick: To compare quantified formulas fast, push the negation inside and compare the falsifying conditions. Remember that $\forall$ distributes over $\wedge$ and $\exists$ over $\vee$, but $\exists$ does not distribute over $\wedge$ and adjacent $\forall\exists$ generally cannot be swapped (only $\exists\forall \Rightarrow \forall\exists$).