Skip to content
Tutorials Center
My learning

Topics

Lesson 8 of 37 ยท 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