Skip to content

Lesson 8 · Propositional Logic

Propositional Proofs with Natural Deduction

Learn natural deduction for propositional logic: introduction and elimination rules, discharging assumptions, worked proofs, and a Python proof checker you can run.

Truth tables decide validity by checking every row. A proof system takes a different route: it starts from premises and applies small, mechanical inference rules until the conclusion appears. Proofs matter because they scale beyond propositional logic (where truth tables stop working) and because a proof is a certificate anyone can check. Natural deduction is the proof style closest to how people actually argue.

The idea: introduction and elimination

For each connective there are two kinds of rules:

  • an introduction rule that tells you how to build a statement using the connective;
  • an elimination rule that tells you how to use such a statement.

We write Γ ⊢ φ to mean "from the assumptions Γ, φ can be derived".

Connective Introduction Elimination
∧ From φ and ψ infer φ ∧ ψ From φ ∧ ψ infer φ (or ψ)
∨ From φ infer φ ∨ ψ (or ψ ∨ φ) From φ ∨ ψ, a proof of χ from φ, and a proof of χ from ψ, infer χ
→ If assuming φ lets you prove ψ, infer φ → ψ (discharging φ) From φ → ψ and φ infer ψ (modus ponens)
¬ If assuming φ leads to ⊥, infer ¬φ From φ and ¬φ infer ⊥
⊥ n/a From ⊥ infer anything (ex falso quodlibet)

Two extras complete classical logic: double negation elimination (from ¬¬φ infer φ) or equivalently proof by contradiction (if assuming ¬φ leads to ⊥, infer φ). Without it you get intuitionistic logic, where p ∨ ¬p is not provable.

A worked proof

Prove p → q, q → r ⊢ p → r (hypothetical syllogism).

  1. p → q (premise)
  2. q → r (premise)
  3. p (assumption, to be discharged)
  4. q (modus ponens on 1, 3)
  5. r (modus ponens on 2, 4)
  6. p → r (→-introduction, discharging assumption 3)

The shape to remember: to prove an implication, assume the hypothesis and prove the conclusion. This is exactly how you prove "if n is even then n² is even" in a math course.

flowchart TD
    A["p → q"] --> D["q (→E)"]
    C["assume p"] --> D
    D --> E["r (→E)"]
    B["q → r"] --> E
    E --> F["p → r (→I, discharge p)"]

Proof tree for the hypothetical syllogism.

A second proof: proof by cases

Prove p ∨ q, p → r, q → r ⊢ r.

  1. p ∨ q (premise)
  2. p → r (premise)
  3. q → r (premise)
  4. Case 1: assume p. Then r by modus ponens (2).
  5. Case 2: assume q. Then r by modus ponens (3).
  6. r (∨-elimination on 1, with cases 4 and 5)

Cases are the logical form of "either this holds or that holds; either way we are done".

Soundness and completeness

Natural deduction for propositional logic is sound (every provable formula is a tautology, so you cannot prove false things) and complete (every tautology is provable). So Γ ⊢ φ exactly when Γ ⊨ φ, where ⊨ means "every assignment satisfying Γ satisfies φ". Chapter 7 treats those meta-theorems seriously. For now: proofs and truth tables agree.

A tiny proof checker

The program below checks a linear proof (a numbered list of lines), where each line is either a premise or follows from earlier lines by modus ponens, conjunction introduction or conjunction elimination. Formulas are nested tuples. It is deliberately small: the aim is to see that proof checking is a simple mechanical procedure even though proof finding can be hard.

Python A mini proof checker

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Try changing the last line's references to [3, 5]; the checker will reject the proof because the line it cites is not the antecedent. That rejection is the whole value of formal proofs: you do not have to trust the author.

Finding proofs automatically

Proof search can be automated by backward reasoning: to prove a goal, find a rule whose conclusion matches it and make its premises new goals. Our second TryIt does this for Horn rules (if-then facts), searching backward from a goal.

Python Backward chaining: proving a goal from rules

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Tips for writing natural-deduction proofs

  • Look at the main connective of the goal. For A → B, assume A. For A ∧ B, prove both. For A ∨ B, prove one side.
  • Look at the premises: split conjunctions, use modus ponens on implications, do case analysis on disjunctions.
  • If you are stuck, assume the negation of the goal and aim for a contradiction.
  • Always close or discharge every assumption you open.

Common mistakes

  • Using an assumption after the sub-proof that discharged it has ended.
  • Using ∨-introduction backwards: from p ∨ q you cannot conclude p.
  • Confusing ⊢ (derivability, syntax) with ⊨ (truth, semantics).
  • Citing a rule without checking that the cited lines have the required shape.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. How do you prove an implication A → B in natural deduction?

    That is the →-introduction rule: assume the hypothesis, derive the conclusion, discharge.
  2. 2. Which rule is modus ponens?

    From A → B and A, infer B: that eliminates the arrow.
  3. 3. What does soundness of a proof system mean?

    Soundness guarantees that derivations preserve truth; completeness is the converse.
  4. 4. Which proof principle gives classical but not intuitionistic logic?

    Intuitionistic logic rejects deriving φ from ¬¬φ, so excluded middle is not provable there.

Summary

  • Natural deduction has introduction and elimination rules for each connective.
  • To prove A → B, assume A and derive B; to use A ∨ B, argue by cases.
  • Propositional natural deduction is sound and complete: ⊢ and ⊨ coincide.
  • Checking a proof is easy and mechanical; finding one can be hard.
  • Backward chaining shows how goals reduce to subgoals.

Next: SAT and Resolution