Natural Deduction: Proving Arguments Step by Step

In 1935, mathematician Gerhard Gentzen invented natural deduction to mirror how humans actually reason — not by applying one massive axiom system, but by building conclusions step by step from smaller, simpler pieces. Today, every field from computer science to courtroom law uses similar step-by-step proof structures. Learning natural deduction teaches you to see the skeleton inside any argument.

What You'll Learn

- What natural deduction is and how it differs from axiomatic proof systems - The four core inference rules: Modus Ponens, And-Introduction, And-Elimination, and Conditional Proof - How to write a numbered, step-by-step formal proof - Where natural deduction appears in computer science, law, and medicine

What Is Natural Deduction?

Natural deduction is a proof system in formal logic where you derive a conclusion from premises by applying a small set of inference rules. Unlike axiomatic systems — where you start with dozens of fixed axioms and derive everything from them — natural deduction starts with assumptions and eliminates them as the proof progresses. The key insight: every logical connective (AND, OR, NOT, IF-THEN) has exactly two types of rules: - Introduction rules: how to BUILD or create that connective in a proof - Elimination rules: how to USE or deconstruct a connective that is already present This introduction/elimination pairing makes natural deduction feel balanced and symmetric, which is exactly why Gentzen considered it elegant and why logicians still use it today.

The Four Core Inference Rules

Here are the rules you will use most frequently: Modus Ponens (written as arrow-Elimination, or ->E): If you have the premise 'P -> Q' (if P then Q) AND you have P, you can immediately conclude Q. Example: 'If it rains, the ground gets wet' plus 'It is raining' gives you 'The ground is wet.' And-Introduction (written as AND-I): If you have P established on its own and Q established on its own, you may combine them to conclude 'P AND Q.' And-Elimination (written as AND-E): If you have 'P AND Q' already established, you can extract P by itself, or Q by itself — whichever one you need for the next step. Conditional Proof (written as ->I): Temporarily assume P. If from that assumption you can derive Q, you may conclude 'P -> Q' and discharge (cancel) the temporary assumption. This is how you prove if-then statements from scratch.

What Does It Mean to Discharge an Assumption?

Natural deduction lets you make temporary assumptions that you later discharge — that is, cancel — once you are done with them. When you use Conditional Proof, you assume P, derive Q, write 'P -> Q,' and then mark that assumption as cancelled. From that point forward, 'P -> Q' stands on its own without requiring P to remain active. This mirrors everyday reasoning: IF we assume X is true, THEN Y would follow — therefore X implies Y.

A Complete Step-by-Step Proof

Goal: From the premises 'P -> Q' and 'Q -> R,' prove 'P -> R.' Line 1: P -> Q (given as premise) Line 2: Q -> R (given as premise) Line 3: [Assume P] — temporary assumption, marked with brackets Line 4: Q — derived from lines 1 and 3 by Modus Ponens (we have P -> Q and we assumed P, so Q follows) Line 5: R — derived from lines 2 and 4 by Modus Ponens (we have Q -> R and Q from line 4, so R follows) Line 6: P -> R — by Conditional Proof: we assumed P at line 3, derived R at line 5, so P -> R; the assumption at line 3 is now discharged This proof establishes what logicians call the transitivity of implication, also known as the hypothetical syllogism: if P leads to Q, and Q leads to R, then P leads directly to R.

Why Natural Deduction Matters Beyond Logic Class

Natural deduction is not an abstract exercise — it appears in fields you may already care about: Computer science: Type-checking in functional programming languages like Haskell directly follows the introduction/elimination structure of natural deduction. Every well-typed program IS a valid proof. This deep connection is called the Curry-Howard correspondence. Legal reasoning: Lawyers argue by citing a rule (if the defendant did X, then liability follows under statute Y), establishing the facts (X occurred), and concluding (therefore liability follows). That structure is Modus Ponens applied to law. Medical diagnosis: A physician reasons 'If the patient has condition A, we expect symptom B. The patient has symptom B, combined with lab result C...' — a chain of elimination and deduction steps. When you write any structured argument and check each step for validity, you are practicing informal natural deduction.

Match each inference rule to the correct description of what it does.

Terms

Modus Ponens (->E)

And-Introduction (AND-I)

And-Elimination (AND-E)

Conditional Proof (->I)

Definitions

Assume P, derive Q, conclude 'If P then Q,' then discharge P

Extract P alone, or Q alone, from 'P and Q'

Given 'If P then Q' and P, conclude Q directly

Combine separate P and Q into 'P and Q'

Drag terms onto their definitions, or click a term then click a definition to match.

Flashcards — click each card to reveal the answer

❓

You have the premises 'A -> B' and 'A.' Which inference rule lets you immediately conclude 'B'?

❓

In a Conditional Proof, what happens to your assumption after you write the final 'P -> Q' conclusion?

🎯

Write a Natural Deduction Proof From Scratch

Write a numbered proof for the following argument. For each line, write the statement AND the rule and line numbers that justify it. Premises given: (1) M -> N (2) N -> O (3) M Goal: Prove O. Once you have the basic proof, try the bonus challenge: prove 'M -> O' WITHOUT using line (3) as a premise. Instead, use Conditional Proof: assume M, derive O, conclude M -> O, and discharge the assumption. Write one sentence comparing the two proofs — which one is more general and why?

Want to keep learning?

Start Learning Free