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

A subformula is any formula that appears as a node in the formation (parse) tree of the given formula. We count the distinct subformulas (each atomic letter is counted once).

The formula is

$((p \to \neg q) \lor ((p \land r) \to s)) \to \neg r.$

Atomic subformulas (4):

$p,\quad q,\quad r,\quad s.$

Compound subformulas, built bottom-up (7):

1. $\neg q$
2. $p \to \neg q$
3. $p \land r$
4. $(p \land r) \to s$
5. $(p \to \neg q) \lor ((p \land r) \to s)$
6. $\neg r$
7. $((p \to \neg q) \lor ((p \land r) \to s)) \to \neg r$ (the whole formula)

Total: $4 + 7 = 11$ subformulas, so the answer is option 3.

Exam trick: Count distinct subformulas, not parse-tree nodes. Here $p$ and $r$ each occur twice, but each distinct atomic letter is counted only once. A quick check: the number of compound subformulas equals the number of logical connectives ($\neg,\neg,\to,\land,\to,\lor,\to$ = 7), and adding the distinct atoms ($p,q,r,s$ = 4) gives $11$.