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

Key idea. $\alpha \Rightarrow \beta$ ($\alpha$ entails $\beta$) means $\alpha \to \beta$ is a tautology: every model of $\alpha$ is a model of $\beta$. If $\alpha$ and $\beta$ are logically equivalent, then entailment holds in both directions.

Simplify each formula using $x \to y \equiv \neg x \lor y$.

$\alpha \equiv \neg p \to (q \to r) \equiv \neg(\neg p) \lor (\neg q \lor r) \equiv p \lor \neg q \lor r$

$\beta \equiv q \to (p \lor r) \equiv \neg q \lor (p \lor r) \equiv p \lor \neg q \lor r$

Both reduce to the same clause $p \lor \neg q \lor r$, so $\alpha \equiv \beta$.

Truth-table confirmation. A disjunction $p \lor \neg q \lor r$ is false in exactly one row: $p = F,\ q = T,\ r = F$. So $\alpha$ and $\beta$ are false on precisely the same single assignment and true on all other $7$ assignments — they agree everywhere.

Since the two formulas have identical truth tables, $\alpha \to \beta$ and $\beta \to \alpha$ are both tautologies. Hence:

$\alpha \Rightarrow \beta \quad \text{and} \quad \beta \Rightarrow \alpha.$

This is option 1.

Exam trick: Convert implications to disjunctions ($x \to y \equiv \neg x \lor y$) and collapse nested conditionals; if both formulas flatten to the same clause they are equivalent, so entailment automatically holds both ways — no full $8$-row table needed.