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

We must check the two quantifier-introduction steps against the side conditions of natural deduction for first-order logic.

The existential-introduction step ($\exists\mathrm{I}$)

$\frac{A(x)}{\exists x\,A(x)}$

The rule $\exists\mathrm{I}$ says: from $\varphi(t)$ for any term $t$, infer $\exists x\,\varphi(x)$. Here the term is simply the variable $x$ itself, so from $A(x)$ we obtain $\exists x\,A(x)$. There is no eigenvariable side condition on $\exists\mathrm{I}$ — it is always sound to existentially generalize. So this step is used correctly.

The body of the derivation

With $\exists x\,A(x)$ in hand and the premise $\exists x\,A(x)\to\forall x\,B(x)$, modus ponens ($\to\!\mathrm{E}$) gives $\forall x\,B(x)$. Universal elimination ($\forall\mathrm{E}$) then gives $B(x)$. The assumption $A(x)$ was used to reach $B(x)$, so $\to\!\mathrm{I}$ discharges it, yielding $A(x)\to B(x)$.

The universal-introduction step ($\forall\mathrm{I}$)

$\frac{A(x)\to B(x)}{\forall x\,(A(x)\to B(x))}$

The rule $\forall\mathrm{I}$ carries the eigenvariable condition: to generalize on $x$, the variable $x$ must not occur free in any undischarged assumption on which $A(x)\to B(x)$ depends.

At this point, what does $A(x)\to B(x)$ depend on?

• The assumption $A(x)$ — already discharged by the preceding $\to\!\mathrm{I}$, so it no longer counts.
• The premise $\exists x\,A(x)\to\forall x\,B(x)$ — here every occurrence of $x$ is bound by a quantifier, so $x$ is not free in it.

Hence $x$ is free in no undischarged assumption, the eigenvariable condition is satisfied, and the $\forall\mathrm{I}$ step is used correctly.

Conclusion

Both quantifier rules respect their side conditions, so both are used correctly — option 1.

Exam trick: The whole trap is timing. $\forall\mathrm{I}$ on $x$ is illegal only while an undischarged assumption mentions $x$ free. Because $A(x)$ is discharged by $\to\!\mathrm{I}$ one step earlier, and $x$ is bound in the remaining premise, the generalization is clean.