Symbolic LogicNatural Deduction: Rules of Inference

What a Formal Proof Is

A proof is a numbered list of lines; each is a premise or follows from earlier lines by a rule, written beside it with the line numbers it uses.

Not started Jump to practice

Truth tables decide validity, but they grow fast: an argument with six letters needs 64 rows, and predicate logic, later in the course, cannot be handled by tables at all. A proof takes another road. Instead of checking every situation, it shows the conclusion follows by small steps, each one an instance of a form you already know is valid (Valid and Invalid Argument Forms).

Key idea

A formal proof is a numbered list of lines. The first lines are the premises. Every later line follows from earlier lines by a rule, and the rule and the line numbers it uses are written beside it, like "MP 1, 3". The proof is finished when its last line is the conclusion.

Why it works

Each rule is a valid argument form. If the premises are true, a line made from true lines by a valid form must be true too, so truth passes down the proof line by line all the way to the conclusion. That is why a correct proof guarantees validity without a single truth table, and why every line must name the rule that justifies it: an unjustified line could break the chain.
Step through a short proof. The bar separates the premises from the derived lines.

Reading a proof

  • Line numbers run down the left. The premises come first, marked Pr, with a bar under them.
  • The conclusion is shown beside the last premise after "∴".
  • Each derived line has a justification at the right: a rule name and the numbers of the lines it uses.
  • Any earlier line may be used, and used more than once.

Worked examples

Worked example: Read a justification

Line 5 of a proof says $r$ with "MP 2, 4". What does that tell you?
  1. MP is modus ponens: from $p \to q$ and $p$, infer $q$.
  2. Lines 2 and 4 are the conditional and its antecedent.
  3. Line 5 is the consequent of line 2.

Answer: Line 5 was made by modus ponens from lines 2 and 4.

Worked example: Is it a proof?

Premises: $p \to q$, $p$, $s$. A writer derives $q$ by MP from lines 1 and 2 and stops. The conclusion is $q$. Is that a proof, even though line 3 was never used?
  1. Every derived line is justified, and the last line is the conclusion.
  2. Nothing requires every premise to be used.

Answer: Yes, it is a complete proof.

Worked example: Two proofs of one argument

The proof above uses MP twice. Could it use another route?
  1. Hypothetical syllogism on lines 1 and 2 gives $p \to r$.
  2. Then MP with line 3 gives $r$.

Answer: Yes: a different proof, equally correct. Proofs are not unique.

Common mistake

Thinking a proof must use every premise, or must be the shortest one. A proof is any chain of correctly justified lines that ends in the conclusion. Extra premises do no harm, and a long correct proof is still a proof. What does matter is that every line has a rule that really fits it.

In the next lessons you will learn the eight rules of inference one or two at a time, starting with modus ponens and modus tollens. Each comes with a pattern to match against whole lines.

Practice

Pass with 3 right answers, the last 2 in a row. Each right answer earns 1 XP.

Loading practice…

Builds on

Leads to

Sources and further reading

  • Patrick J. Hurley and Lori Watson, A Concise Introduction to Logic, 13th ed., section 7.1, Rules of Implication I
  • forall x: Calgary, an open introduction to formal logic (P. D. Magnus, Tim Button and others; Open Logic Project), chapter on the very idea of natural deduction
@teddyrookbook GitHub