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

An inference $\Gamma \models \varphi$ is valid iff every truth assignment that makes all premises in $\Gamma$ true also makes $\varphi$ true. To refute one, find a single row where the premises hold but the conclusion fails.

Inference 1 — $\{\neg p,\, p \vee q\} \models q$ (valid). This is the disjunctive syllogism. If $\neg p$ is true then $p$ is false, so $p \vee q$ can only be true when $q$ is true. There is no assignment making both premises true and $q$ false, so the entailment holds.

Inference 2 — $\{p \vee q,\, \neg q \vee r\} \models p \vee r$ (valid). This is exactly the resolution rule on the literal $q$. Try to refute it: a counterexample needs $p \vee r$ false, i.e. $p = F$ and $r = F$.

• $p = F$ forces $q = T$ to keep $p \vee q$ true.
• $r = F$ forces $\neg q = T$, i.e. $q = F$, to keep $\neg q \vee r$ true.

These demand $q = T$ and $q = F$ simultaneously — impossible. No counterexample exists, so the entailment is valid.

Inference 3 — $\{p \to q,\, s \to t\} \models (p \vee s) \to (q \wedge t)$ (invalid). Look for a refuting row. Take $p = T,\ q = T,\ s = F,\ t = F.$ Then both premises hold: $p \to q = T \to T = T$ and $s \to t = F \to F = T$. But the conclusion fails: $p \vee s = T \vee F = T,\qquad q \wedge t = T \wedge F = F,$ so $(p \vee s) \to (q \wedge t) = T \to F = F$. Premises true, conclusion false $\Rightarrow$ not valid.

Valid inferences: numbers 1 and 2 only $\Rightarrow$ exactly 2 valid inferences, matching option 2.

Exam trick: To kill a conditional conclusion $A \to B$, you only need one assignment with $A$ true and $B$ false. Here splitting the work between the two independent implication-premises ($p\to q$ via the $p$-branch, $s\to t$ via the $s$-branch) lets $q\wedge t$ collapse even though both premises stay true.