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

Picture the universe as the six points $b_1,\ldots,b_6$ in a line. The relation $O_1$ is the successor edge $b_i \to b_{i+1}$ (for $1 \le i \le 5$), and $O_2$ is the skip-one edge $b_i \to b_{i+2}$ (for $1 \le i \le 4$). Key fact: the first coordinate of every $O_2$ pair is one of $b_1,b_2,b_3,b_4$ only — so $b_5$ and $b_6$ have no outgoing $O_2$ edge.

Checking $\alpha$

$\alpha : \forall x\,(F_2(x) \to \exists y\,\exists z\,(O_1(x,y) \wedge O_2(x,z)))$

$\alpha$ ranges over $x$ with $F_2(x)$, i.e. $x \in \{b_2, b_5\}$. For each such $x$ we need both an outgoing $O_1$ edge and an outgoing $O_2$ edge.

At $x = b_5$ the implication's body fails: $b_5$ has an $O_1$-successor $b_6$ but no $O_2$-successor (the largest first coordinate in $O_2$ is $b_4$). Hence $\alpha$ is false: $I \not\models \alpha$.

Checking $\beta$

$\beta : \forall x\,(F_1(x) \to \exists y\,\exists z\,(O_1(y,x) \wedge O_2(x,z)))$

$\beta$ ranges over $x$ with $F_1(x)$, i.e. only $x = b_6$. We need an incoming $O_1$ edge $O_1(y,b_6)$ and an outgoing $O_2$ edge $O_2(b_6,z)$.

The incoming-$O_1$ part holds ($b_5 \to b_6$), but $b_6$ has no outgoing $O_2$ edge, so the conjunction is false at $b_6$. Hence $\beta$ is false as written: $I \not\models \beta$.

Conclusion

Both sentences fail, so $I \not\models \alpha$ and $I \not\models \beta$ — option 4.

Pitfall: The official answer key marks option 1 ($I \not\models \alpha,\ I \models \beta$). That holds only if $\beta$'s second conjunct were the incoming edge $O_2(z,x)$ — then $b_6$ has both an $O_1$-predecessor $b_5$ and an $O_2$-predecessor $b_4$, making $\beta$ true. $\beta$ flips $O_1(x,y)$ to $O_1(y,x)$ to test predecessors, and the intended dual is to also flip $O_2$; but the printed formula keeps $O_2(x,z)$, and $b_6$ has no $O_2$-successor. As literally printed the answer is option 4 (key appears to be a typo carrying $O_2(x,z)$ where $O_2(z,x)$ was intended).

Note on the answer key / question: as literally printed, $\beta$'s second conjunct is $O_2(x,z)$; under faithful transcription $\beta$ fails at the last element (no outgoing $O_2$ edge), giving option 4. The official key's answer (option 1) requires the dual form $O_2(z,x)$ — the printed $O_2(x,z)$ appears to be a typo. Answer per the printed formula: option 4.