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

There are 5 propositional variables $p,q,r,s,u$, so the table has $2^{5}=32$ rows. Write the formula as $I \to u$, where $I = (p \to q) \to (r \to s)$ depends only on $p,q,r,s$.

Step 1 — count the 1's of the inner part $I$ (over its 16 rows). An implication $A \to B$ is false only when $A$ is true and $B$ is false. So $I=(p\to q)\to(r\to s)$ is false exactly when $p \to q$ is true and $r \to s$ is false.

• $p \to q$ is true in $3$ of the $4$ $(p,q)$-combinations.
• $r \to s$ is false in exactly $1$ of the $4$ $(r,s)$-combinations (namely $r=1,\,s=0$).

Hence $I$ is false in $3 \times 1 = 3$ rows, so it is true in $16-3 = 13$ rows and false in $3$ rows.

Step 2 — bring in $u$ via $I \to u$ (over all 32 rows). Split on the value of $u$:

When $u=0$ the formula equals $\lnot I$, which is true on exactly the $3$ rows where $I$ is false.

Total 1's $= 16 + 3 = \mathbf{19}$.

Pitfall: Read the bracketing carefully — here $u$ is the consequent ($I \to u$), not the antecedent. The mirror formula $u \to I$ would have $16 + 13 = 29$ ones, which is not an option. Putting $u$ on the wrong side is the trap.