Rules of Inference

Why This Matters

Rules of inference are the engine of formal proof. They're what allow you to move from premises to conclusions with absolute certainty. In Formal Logic II, you're tested on your ability to recognize which rule applies in a given situation, construct valid proof sequences, and understand why each inference preserves truth.

Don't just memorize the symbolic forms. Know what logical work each rule performs. Some rules let you break apart compound statements, others let you build them up, and still others let you chain reasoning across multiple conditionals. Understanding these functional categories will help you spot the right tool for each step in a proof and avoid common errors on exams.

---

Conditional Elimination Rules

These rules extract conclusions from conditional (if-then) statements. Conditionals make promises about what follows from what, and these rules let you cash in on those promises.

Modus Ponens

• Affirms the antecedent to derive the consequent: $P \rightarrow Q$, $P$, therefore $Q$
• This is direct forward reasoning. If you know the "if" part is true, the "then" part must follow.
• The most commonly used rule in proofs. When you see a conditional and its antecedent as separate premises, apply this immediately.

Modus Tollens

• Denies the consequent to reject the antecedent: $P \rightarrow Q$, $\neg Q$, therefore $\neg P$
• This is backward reasoning from a failed prediction: if the effect didn't happen, the cause didn't either.
• Essential for indirect proofs and disproving hypotheses. Look for this when you have a negated statement matching a consequent.

---

Conditional Chaining Rules

These rules connect multiple conditionals to extend your reasoning across a chain of implications. Think of them as building bridges between statements that don't directly connect.

Hypothetical Syllogism

• Chains two conditionals into one: if $P \rightarrow Q$ and $Q \rightarrow R$, then $P \rightarrow R$
• This is the transitivity of implication. The consequent of one conditional becomes the antecedent of the next, and you skip the middle term.
• Look for shared middle terms in your premises. When $Q$ appears as both a consequent and an antecedent, you can link the chain. This rule can be applied repeatedly to build longer chains (e.g., adding $R \rightarrow S$ to get $P \rightarrow S$).

Constructive Dilemma

• Combines two conditionals with a disjunction: $(P \rightarrow Q)$, $(R \rightarrow S)$, $P \lor R$, therefore $Q \lor S$
• This is parallel conditional reasoning. Whichever disjunct is true triggers its corresponding conditional, so at least one consequent must hold.
• Useful for case analysis when you know one of two things must be true but not which. The disjunctive structure carries through to the conclusion.

Destructive Dilemma

• The mirror image of Constructive Dilemma, using negations: $(P \rightarrow Q)$, $(R \rightarrow S)$, $\neg Q \lor \neg S$, therefore $\neg P \lor \neg R$
• When at least one consequent fails, at least one corresponding antecedent must be rejected. This applies Modus Tollens across parallel conditionals.
• Powerful for ruling out options when predictions fail.

---

Disjunction Rules

These rules work with "or" statements, either building them or breaking them down. Disjunctions assert that at least one option holds.

Disjunctive Syllogism

• Eliminates one disjunct to affirm the other: $P \lor Q$, $\neg P$, therefore $Q$
• Pure process of elimination. If you know "P or Q" and P is false, Q must be true. This works symmetrically: $P \lor Q$, $\neg Q$, therefore $P$.
• High-frequency exam rule. Whenever you can negate one side of a disjunction, apply this to simplify.

Addition

• Introduces a disjunction from a single statement: $P$, therefore $P \lor Q$
• This weakens your information by adding possibilities. It seems counterintuitive, but it's logically valid since "or" only requires one true disjunct. You can introduce any $Q$ you want.
• A strategic proof tool for setting up Disjunctive Syllogism or Constructive Dilemma later. If a proof seems stuck, check whether adding a disjunct now creates the structure you need for a future step.

---

Conjunction Rules

These rules handle "and" statements, combining or separating conjuncts. Conjunctions assert that both parts hold.

Conjunction

• Combines two statements into one compound: $P$, $Q$, therefore $P \land Q$
• Both premises must be independently established first. You can't conjoin something you haven't already derived.
• Often the final step in proofs requiring compound conclusions. Gather your pieces, then conjoin them.

Simplification

• Extracts one conjunct from a conjunction: $P \land Q$, therefore $P$ (or therefore $Q$)
• Breaks apart compound information to isolate what you need for the next step.
• Apply early in proofs when premises contain conjunctions. Extract the components you'll use separately rather than carrying the whole conjunction forward.

---

Resolution

This rule generalizes Disjunctive Syllogism and is used extensively in automated theorem proving and logic programming.

Resolution

• Resolves complementary literals across two disjunctions: $P \lor Q$, $\neg P \lor R$, therefore $Q \lor R$
• The $P$ and $\neg P$ "resolve away," and the remaining disjuncts combine. The complementary pair must contain exactly one positive and one negative occurrence of the same proposition.
• This is the foundation of resolution refutation in AI and automated reasoning, where all statements are converted to clausal (disjunctive) form and repeatedly resolved until a contradiction is found or no new clauses can be derived.

---

Quick Reference Table

---

Self-Check Questions

1. Modus Tollens and Disjunctive Syllogism both work by denying or eliminating to reach a conclusion. What's the key structural difference between them? (Hint: what kind of statement does each one operate on?)

2. You have the premises $A \rightarrow B$, $B \rightarrow C$, and $A$. Which two rules would you apply, and in what order, to derive $C$?

3. Addition "weakens" information while Simplification "strengthens" it. Why is that the case, and when would you strategically use each in a proof?

4. Given $(P \rightarrow Q)$ and $(R \rightarrow S)$ as premises, what additional premise would you need to apply Constructive Dilemma versus Destructive Dilemma?

5. A proof requires you to derive $\neg A \lor \neg B$ from conditional premises. Which rule of inference should you look to apply, and what form must your premises take?