Skip to content
Tutorials Center
My learning

Topics

Lesson 28 of 37 ยท Formal Systems and Completeness

Formal Systems and Proof Calculi

Learn what a formal system is, how axioms and inference rules produce theorems, and write a Hilbert-style proof checker for propositional logic in Python.

So far you have proved facts in prose and tested statements with truth tables. A formal system (or proof calculus) makes proof itself a mechanical game of symbols. It has three ingredients:

  1. A language: which strings are formulas.
  2. Axioms: formulas accepted without proof.
  3. Inference rules: patterns that turn formulas you already have into new ones.

A proof is a finite list of formulas where each line is an axiom, a hypothesis, or follows from earlier lines by a rule. A theorem is the last line of a proof from no hypotheses, written โŠข ฯ†. Because proofs are finite and each step is mechanically checkable, a computer can verify any proof. Finding proofs is harder; checking them is easy.

Contrast this with semantic truth: โŠจ ฯ† ("ฯ† is valid") means ฯ† is true under every interpretation, which you checked with truth tables. Whether โŠข and โŠจ coincide is the subject of soundness and completeness.

A Hilbert-style system

A Hilbert system uses many axioms and few rules. For formulas built from โ†’ and ยฌ, a standard choice has three axiom schemas (any formulas may replace A, B, C) and one rule:

  • A1: A โ†’ (B โ†’ A)
  • A2: (A โ†’ (B โ†’ C)) โ†’ ((A โ†’ B) โ†’ (A โ†’ C))
  • A3: (ยฌB โ†’ ยฌA) โ†’ (A โ†’ B)
  • Modus ponens (MP): from A and A โ†’ B, infer B.

Even this tiny system proves every tautology built from โ†’ and ยฌ. But proofs can be surprisingly roundabout. The simplest-looking theorem, p โ†’ p, takes five lines:

  1. (p โ†’ ((p โ†’ p) โ†’ p)) โ†’ ((p โ†’ (p โ†’ p)) โ†’ (p โ†’ p)) by A2
  2. p โ†’ ((p โ†’ p) โ†’ p) by A1
  3. (p โ†’ (p โ†’ p)) โ†’ (p โ†’ p) by MP from 2, 1
  4. p โ†’ (p โ†’ p) by A1
  5. p โ†’ p by MP from 4, 3
flowchart TB
    A2["A2 instance"] --> L3["line 3 (MP)"]
    A1a["A1 instance: line 2"] --> L3
    L3 --> L5["line 5: p -> p (MP)"]
    A1b["A1 instance: line 4"] --> L5

The dependency structure of the five-line proof of p โ†’ p.

A proof checker

Represent formulas as nested tuples: a variable is a string, ("not", A) is negation and ("imp", A, B) is implication. The checker must test whether a line is an instance of an axiom schema, which is pattern matching with substitution.

Python A Hilbert-system 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.

The checker prints one line per step and ok or BAD for each. Change one line, for example replace the second "axiom" by "hyp", and watch the checker reject the proof.

Natural deduction and sequent calculus

Hilbert proofs are easy to check but painful to write. Natural deduction has no axioms and instead gives each connective an introduction and an elimination rule, mirroring how mathematicians argue. For implication, introduction says: assume A, derive B, then conclude A โ†’ B and discharge the assumption. Elimination is modus ponens. For conjunction: from A and B infer A โˆง B (intro); from A โˆง B infer A or B (elim).

Gentzen's sequent calculus works with sequents ฮ“ โŠข ฮ” ("from assumptions ฮ“, one of ฮ” follows"). Its cut-elimination theorem says every proof can be rewritten without the detour of the cut rule, which gives the subformula property and underlies automated proving, including the resolution prover you build at the end.

Python Derived rules: using the deduction theorem

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.

Pick the calculus that fits your job: Hilbert systems for metatheory (few rules to analyze), natural deduction for human readability, sequents for proof theory, and resolution or tableaux for automation. They all prove the same propositional theorems.

Properties we ask of a system

  • Soundness: every theorem is valid (โŠข ฯ† implies โŠจ ฯ†). A system that proves false statements is useless.
  • Completeness: every valid formula is a theorem (โŠจ ฯ† implies โŠข ฯ†).
  • Consistency: the system does not prove both ฯ† and ยฌฯ†.
  • Decidability: an algorithm decides whether ฯ† is a theorem. Propositional logic is decidable (truth tables); first-order logic is not.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What three ingredients make up a formal system?

    A formal system fixes which strings are formulas, which formulas are axioms and how new formulas follow from old ones.
  2. 2. What does modus ponens do?

    Given A and A โ†’ B, modus ponens concludes B.
  3. 3. Why is a Hilbert-style proof easy to check by computer?

    Checking just means pattern matching each line, which is a finite mechanical task.
  4. 4. Which is the meaning of soundness?

    Soundness: โŠข ฯ† implies โŠจ ฯ†. The converse direction is completeness.

Summary

  • A formal system consists of a language, axioms and inference rules; proofs are finite, mechanically checkable lists.
  • A Hilbert system uses axiom schemas A1 to A3 and modus ponens; even p โ†’ p takes five lines.
  • Natural deduction and sequent calculi trade axioms for intro/elim rules, which are easier to use and analyze.
  • We judge systems by soundness, completeness, consistency and decidability.

Next: Soundness and Completeness of Propositional Logic