Common Inference Rules

Why This Matters

Inference rules are the engine of formal proof—they're the legal moves that let you transform premises into conclusions. When you're constructing proofs in Proof Theory, you're not inventing arguments from scratch; you're applying these rules systematically to derive new truths from established ones. Understanding why each rule is valid (not just that it's valid) is what separates students who can follow proofs from those who can build them.

You're being tested on more than memorization here. Exams will ask you to identify which rule justifies a particular step, construct proofs using multiple rules in sequence, and recognize when a rule has been misapplied. The key is understanding the logical structure each rule exploits: Does it work with conditionals? Disjunctions? Conjunctions? Does it eliminate information or introduce it? Don't just memorize the schemas—know what type of reasoning each rule captures and when to reach for it.

---

Rules for Conditional Reasoning

Conditionals ($P \rightarrow Q$) are the workhorses of logical arguments. These rules let you use conditionals to derive new information, either by affirming the antecedent, denying the consequent, or chaining implications together.

Modus Ponens

• The foundational "forward" rule—if you have $P \rightarrow Q$ and you establish $P$, you can conclude $Q$
• Direction matters: you must affirm the antecedent (the "if" part), not the consequent—affirming the consequent is a formal fallacy
• Most frequently used rule in natural deduction proofs; often the final step when discharging assumptions

Modus Tollens

• The "backward" conditional rule—if $P \rightarrow Q$ holds and $\neg Q$ is true, then $\neg P$ must follow
• Contrapositive reasoning: this rule exploits the logical equivalence between $P \rightarrow Q$ and $\neg Q \rightarrow \neg P$
• Key for indirect proofs: when you can't prove something directly, showing its consequent fails lets you deny the antecedent

Hypothetical Syllogism

• Chain rule for conditionals—from $P \rightarrow Q$ and $Q \rightarrow R$, derive $P \rightarrow R$
• Transitivity of implication: lets you connect distant premises through intermediate steps
• Proof strategy essential: when your goal is a conditional and you have a "middle term," look for this rule

---

Rules for Disjunctive Reasoning

Disjunctions ($P \lor Q$) represent alternatives. These rules let you either eliminate options to reach a conclusion or combine disjunctions with conditionals for more complex reasoning.

Disjunctive Syllogism

• Elimination by denial—from $P \lor Q$ and $\neg P$, conclude $Q$
• Process of elimination: when you know "one or the other" and can rule one out, the other must hold
• Works symmetrically: you can also derive $P$ from $P \lor Q$ and $\neg Q$

Constructive Dilemma

• Disjunction-conditional combo—from $P \lor Q$, $P \rightarrow R$, and $Q \rightarrow S$, derive $R \lor S$
• "Either way" reasoning: whichever disjunct is true, something follows—you just get a disjunction of the consequents
• Powerful for case analysis: when you can't determine which alternative holds but know what each implies

Destructive Dilemma

• Contrapositive version of Constructive Dilemma—from $\neg R \lor \neg S$, $P \rightarrow R$, and $Q \rightarrow S$, derive $\neg P \lor \neg Q$
• Backward disjunctive reasoning: if at least one consequent fails, at least one antecedent must fail
• Less common but testable: recognize it as Constructive Dilemma's "mirror image" using contraposition

---

Rules for Conjunction Manipulation

Conjunctions ($P \land Q$) package multiple truths together. These rules let you build conjunctions from separate truths or extract components from existing ones.

Conjunction (Introduction)

• Combining truths—from $P$ and $Q$ separately, derive $P \land Q$
• Both premises required: you cannot introduce a conjunction unless both conjuncts are independently established
• Often a penultimate step: when your goal is to prove "A and B," prove each separately, then combine

Simplification (Elimination)

• Extracting components—from $P \land Q$, derive $P$ (or derive $Q$)
• Information reduction: you're discarding part of what you know to isolate what you need
• Two applications possible: a single conjunction gives you access to either conjunct independently

---

Rules for Introducing and Eliminating Logical Structure

These rules let you add logical structure (sometimes in ways that seem too easy) or remove redundant structure to simplify expressions.

Addition (Disjunction Introduction)

• Weakening by disjunction—from $P$, derive $P \lor Q$ for any $Q$
• Counterintuitive but valid: you can introduce any claim as an alternative because "P or anything" is weaker than "P" alone
• Strategic use: often needed to set up Disjunctive Syllogism or Constructive Dilemma later in a proof

Double Negation

• Negation cancellation—from $\neg\neg P$, derive $P$ (and vice versa in classical logic)
• Classical logic principle: this rule is not valid in intuitionistic logic, making it a key distinguishing feature
• Proof cleanup: often used to simplify expressions after indirect proof steps introduce extra negations

---

Quick Reference Table

---

Self-Check Questions

1. Both Modus Ponens and Modus Tollens work with conditionals—what distinguishes which part of the conditional each rule targets, and why does this matter for proof direction?

2. You have the premises $A \lor B$, $A \rightarrow C$, and $B \rightarrow C$. Which rule lets you conclude $C \lor C$ (equivalently, $C$), and how does this differ from Disjunctive Syllogism?

3. Compare Addition and Conjunction Introduction: one seems to "give you something for free" while the other requires work. Explain why Addition is still a valid inference despite appearing to create information.

4. In a proof, you've derived $\neg\neg(P \rightarrow Q)$. What rule do you apply to simplify this, and why might this rule be controversial in non-classical logical systems?

5. Construct a short proof outline using Hypothetical Syllogism and Modus Ponens together: given $P \rightarrow Q$, $Q \rightarrow R$, and $P$, show how to derive $R$ in two different ways.