Exercises: Rules of Inference

These run from mechanical warm-ups to full derivations, code, modeling, and a few that ask you to conjecture first and prove second. Difficulty markers: ⭐ foundational, ⭐⭐ intermediate, ⭐⭐⭐ challenging. Worked solutions to the dagger (†) and odd-numbered problems live in _scratch/answers/ch03.md — wrestle with each problem before you peek, because the whole skill of this chapter is finding the step, not reading it.

Throughout, write arguments in the premises-over-line form from §3.1 and cite a named rule on every derivation line, exactly as §3.5 does.

Part A — Warm-ups (⭐)

3.1 † For the argument with premises $p \rightarrow q$ and $\neg q$ and conclusion $\neg p$, name the single rule that justifies it, and write the conditional whose tautology-hood (Ch. 1) would confirm its validity.

3.2 Classify each as modus ponens, modus tollens, affirming the consequent, or denying the antecedent, and say whether it is valid: (a) $r \rightarrow s$; $r$; $\therefore s$. (b) $r \rightarrow s$; $\neg r$; $\therefore \neg s$. (c) $r \rightarrow s$; $s$; $\therefore r$. (d) $r \rightarrow s$; $\neg s$; $\therefore \neg r$.

3.3 † State which rule takes you from the given premises to the conclusion: (a) $a \land b \ \Rightarrow\ a$. (b) $a,\ b \ \Rightarrow\ a \land b$. (c) $a \ \Rightarrow\ a \lor b$. (d) $a \lor b,\ \neg a \ \Rightarrow\ b$. (e) $a \rightarrow b,\ b \rightarrow c \ \Rightarrow\ a \rightarrow c$.

3.4 Translate the cache argument from §3.1 ("If the cache is stale, the test fails; the test failed; so the cache is stale") into symbols with $p,q$, then circle the row of its truth table that proves it invalid. (You do not need to recopy the whole table — just identify the counterexample row.)

3.5 † Fill in the side condition each quantifier rule requires: (a) Universal instantiation: from $\forall x\,P(x)$ conclude $P(c)$ where $c$ is __. (b) Existential instantiation: from $\exists x\,P(x)$ conclude $P(c)$ where $c$ is _. (c) Universal generalization: from $P(c)$ conclude $\forall x\,P(x)$ where $c$ is ___.

3.6 Is the argument "All integers are even; $7$ is an integer; therefore $7$ is even" valid, sound, both, or neither? Justify in one sentence each for validity and soundness.

Part B — Prove it (⭐⭐)

Give a numbered derivation. Each line is a premise or follows from earlier lines by one named rule (§3.5 format).

3.7 † (Scaffolded — fill the missing step.) From the premises $p \rightarrow q$, $\ q \rightarrow r$, and $\ p$, derive $r$. Complete the blanks:

(Then redo it in two lines using hypothetical syllogism first — which derivation is shorter, and does shorter mean "more valid"?)

3.8 Derive $\neg p$ from the premises $p \rightarrow (q \land r)$, $\ \neg r$, and $\ s$. (One premise is a red herring — say which, and recall from Ch. 1 that $\neg(q \land r) \equiv \neg q \lor \neg r$.)

3.9 † Derive $u$ from the four premises $p$, $\ p \rightarrow (q \lor r)$, $\ \neg q$, and $\ r \rightarrow u$. State your backward strategy in one sentence before the derivation, as §3.5 models.

3.10 Derive $t$ from $p \lor q$, $\ p \rightarrow s$, $\ q \rightarrow t$, and $\ \neg s$. (Hint: rule out $p$ first.)

3.11 † Prove the quantified "Socrates"-style argument formally. Premises: $\forall x\,(C(x) \rightarrow R(x))$ ("every cat is a registered pet") and $C(\text{milo})$. Conclusion: $R(\text{milo})$. Cite the quantifier rule and the propositional rule you use, in order.

3.12 Show that resolution generalizes disjunctive syllogism: starting from the resolution pattern $p \lor q,\ \neg p \lor r \ \Rightarrow\ q \lor r$, explain (in two or three sentences, no full proof needed) what to substitute for $r$ so that the rule collapses exactly to "$p \lor q,\ \neg p \vdash q$."

Part C — Implement it (⭐⭐)

Write Python in the book's style. Do not run it — hand-trace and include an # Expected output: comment, matching §3.2. Reuse the chapter's is_valid, implies, forall, and exists where natural.

3.13 † Using the chapter's is_valid(premises, conclusion, names) (Project Checkpoint), write the three to five lines that test whether denying the antecedent ($p \rightarrow q,\ \neg p \vdash \neg q$) is valid. State the boolean output you expect and, in one sentence, the assignment that produces it.

3.14 Write a function is_fallacy(premises, conclusion, names) that returns True exactly when the argument is invalid (i.e., when is_valid returns False). Then call it on affirming the consequent and on modus ponens, and give the two-value expected output.

3.15 † Over the finite domain range(1, 11), use the chapter's forall/exists helpers to show the EI pitfall numerically: define P = lambda x: x % 2 == 0 ("even") and Q = lambda x: x % 2 == 1 ("odd"). Print exists(domain, P), exists(domain, Q), and exists(domain, lambda x: P(x) and Q(x)). Explain in one sentence why the third value shows you may not instantiate two existentials with the same name.

3.16 Write chain(implications, start, goal) that, given a list of pairs [(p,q), (q,r), ...] encoding $p \rightarrow q$, $q \rightarrow r$, …, returns True if hypothetical syllogism chains start all the way to goal. (This is transitivity of implication as a graph reachability check — foreshadowing Ch. 27.) Give expected output for a small chain you write by hand.

Part D — Find the error (⭐⭐)

Each argument or "derivation" below is flawed. State precisely which line or move fails and why, and say whether the failure is invalidity (bad form) or unsoundness (a false premise) — the distinction from §3.3.

3.17 † A teammate writes: "If there is a deadlock, the request times out. The request timed out. Therefore there is a deadlock — restart the database." Name the fallacy, give a concrete counterexample (another cause of a timeout), and classify the failure.

3.18 A "derivation" claims:

What is wrong with line 3? Name the rule that was actually needed to reach a valid conclusion from lines 1–2, and say what that valid conclusion would be (if any).

3.19 † A proof of "$\forall x\,P(x)$" reads: "Let $c = 0$. We show $P(0)$ holds: [correct argument for $0$]. Since $c$ was chosen, by universal generalization $\forall x\,P(x)$." Identify the broken side condition and state what the argument actually proves.

3.20 From "$\exists x\,\text{Passed}(x)$" and "$\exists x\,\text{Failed}(x)$" a student instantiates both with the same fresh name $c$, gets $\text{Passed}(c) \land \text{Failed}(c)$, and concludes $\exists x\,(\text{Passed}(x) \land \text{Failed}(x))$ — "some single student both passed and failed." Name the violated condition and give the everyday counterexample.

3.21 † A reviewer argues: "All inputs that crash the parser are malformed. This input is malformed. Therefore it will crash the parser — reject it." Is this invalid or merely unsound? Name the fallacy and give the counterexample.

Part E — Model it (⭐⭐⭐)

Translate a real situation into the discrete-math objects of this chapter (propositions, an argument form, a derivation), then reason about it.

3.22 † (Model it — access control.) A file server enforces: "If a user is an owner, they may write. If a user may write, they may read." You observe that user u cannot read a file. Introduce propositional variables for "u is an owner," "u may write," "u may read," write the two rules as implications, and derive what you can validly conclude about u's ownership. Name every rule used.

3.23 (Model it — feature flags.) A deploy script encodes: "Roll out the new UI or keep the old UI" ($n \lor o$); "If we roll out the new UI, run the migration" ($n \rightarrow m$); "We did not run the migration" ($\neg m$). Model this and derive whether the old UI is kept. Identify the rules.

3.24 † (Model it — type checking, ties to §3.6.) A toy type checker has the rule "if e1 : int and e2 : int then e1 + e2 : int." Given the premises x : int and y : int, write the one-step derivation that types x + y, and state which inference rule the horizontal bar of a typing rule corresponds to.

Part F — Conjecture and test (⭐⭐⭐)

Use code on many cases to form (or break) a conjecture, then prove or disprove it. Computation proposes; a proof disposes (theme four).

3.25 † (Conjecture, then prove or refute.) A colleague conjectures a "rule": "from $p \rightarrow q$ and $p \lor r$, conclude $q \lor r$." Using is_valid (write the call by hand, hand-derive the boolean), decide whether the conjecture holds. If it is valid, give a short derivation or name the rule it matches; if it is invalid, exhibit the counterexample assignment.

3.26 (Conjecture, then prove or refute.) Test whether "from $p \rightarrow q$ and $q \rightarrow p$ and $p \lor q$, conclude $p \land q$" is valid by reasoning about its truth table (you may sketch the relevant rows by hand). Prove it valid with a derivation, or refute it with a counterexample row.

3.27 † (Conjecture about chains.) Conjecture: "any chain of $n$ implications $p_1 \rightarrow p_2,\ p_2 \rightarrow p_3,\ \dots,\ p_{n-1} \rightarrow p_n$ entails $p_1 \rightarrow p_n$." Verify it for $n = 2, 3, 4$ (the $n=2$ case is one rule; describe how you'd check $n=3,4$ with is_valid), then explain which single rule, applied repeatedly, proves the general claim — and which proof technique from the next chapters would make "for all $n$" rigorous.

Part G — Interleaved (mixing earlier chapters)

Keeping Chapters 1–2 sharp is the point here.

3.28 † (Ch. 1 + 3.) Validity says a certain conditional is a tautology. Write the conditional for modus tollens ($p \rightarrow q,\ \neg q \vdash \neg p$) and verify it is a tautology by building its four-row truth table by hand.

3.29 (Ch. 1 + 3.) Using only logical equivalences from Chapter 1 (not a truth table), show that the argument form for disjunctive syllogism is valid: rewrite $p \lor q$ using implication ($p \lor q \equiv \neg p \rightarrow q$) and finish with a rule from this chapter.

3.30 † (Ch. 2 + 3.) Use Chapter 2's quantifier-negation equivalence to rewrite $\neg \forall x\,(P(x) \rightarrow Q(x))$ as an existential statement, then explain why a single witness (one $c$ with $P(c)$ true and $Q(c)$ false) suffices to refute the universal — connecting "counterexample" (Ch. 2) to "the consequent could be true another way" (this chapter).

3.31 (Ch. 2 + 3.) The Socrates derivation used universal instantiation followed by modus ponens. For the domain range(1, 6), predicate $E(x)$ = "$x$ is even" and $D(x)$ = "$x$ is divisible by 2," write (by hand) what forall(domain, lambda x: implies(E(x), D(x))) evaluates to, then state the instantiation at $c = 4$ and the propositional rule that finishes "therefore $D(4)$."

3.32 † (Ch. 1 + 2 + 3 — synthesis.) Consider: "Every prime greater than 2 is odd. There exists a prime greater than 2. Therefore there exists an odd number." Write the two premises with quantifiers, give the derivation (which quantifier rules and which propositional rule, in order), and state whether the argument is valid, sound, both, or neither.

Solutions to † and odd-numbered exercises are in _scratch/answers/ch03.md. For each derivation, the rubric rewards: the correct rule named on every line, justifications that cite only earlier lines, correct handling of quantifier side conditions, and — for "find the error" — naming whether the defect is invalidity or unsoundness.