Skip to content
Tutorials Center
My learning

Topics

Lesson 29 of 37 · Formal Systems and Completeness

Soundness and Completeness of Propositional Logic

Connect proof and truth: see why propositional proofs are sound and complete, build a semantic tableau prover, and test it against truth tables and Hilbert axioms in Python.

Two notions of correctness meet in this lesson. Semantic consequence Γ ⊨ φ says every valuation that makes all of Γ true makes φ true. Syntactic derivability Γ ⊢ φ says there is a formal proof of φ from Γ in some calculus (see formal systems). One is about truth, the other about symbol pushing, yet for propositional logic they coincide:

  • Soundness: Γ ⊢ φ implies Γ ⊨ φ. Proofs never lead you astray.
  • Completeness: Γ ⊨ φ implies Γ ⊢ φ. Everything true by logic alone can be proved.

Completeness for propositional logic was shown by Post (1921); for first-order logic by Gödel in 1929 (the completeness theorem, not to be confused with his incompleteness theorems, which come in the next lesson).

Why soundness holds

Soundness is proved by induction on the length of the proof. Every axiom is a tautology, so it is true under every valuation. Modus ponens preserves truth: if A and A → B are both true under a valuation, then B must be true. So if each earlier line is true (under a valuation that satisfies the hypotheses), the next line is too. We can't prove soundness by testing, but we can test instances of it, which is a good sanity check for any calculus you design.

Python Every consequence of the Hilbert axioms is a tautology

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.

Completeness through semantic tableaux

A semantic tableau is a proof-search method that is easy to implement and is complete by construction. To test whether φ is valid, try to build a model where φ is false. Start with ¬φ and keep breaking formulas into simpler parts:

  • A ∧ B: both A and B go on the same branch.
  • A ∨ B: split into two branches, one with A, one with B.
  • A → B: split into ¬A and B.
  • ¬(A ∧ B), ¬(A ∨ B), ¬(A → B), ¬¬A: use De Morgan and the laws of implication.

A branch closes when it contains both p and ¬p. If every branch closes, there is no countermodel, so φ is valid; if some branch stays open with only literals, read off a countermodel from it. Because the search always ends in one of these two ways, the procedure is both sound and complete, and it decides propositional validity.

flowchart TB
    R["not (p or q) -> p"] --> A["p or q, not p"]
    A --> B1["p, not p: closed"]
    A --> B2["q, not p: open"]

Testing the formula (p ∨ q) → p: the open branch gives the countermodel p = false, q = true.

Python A tableau prover agrees with truth tables

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.

From consistency to a model

The standard completeness proof (Henkin / Lindenbaum) runs the other way round: if Γ is consistent (it proves no contradiction), then Γ has a model. Extend Γ to a maximal consistent set by adding, one formula at a time, either φ or ¬φ, whichever keeps it consistent. Then define a valuation by "p is true iff p is in the set" and check by induction that it makes every formula in the set true. Contrapositive: if Γ ⊨ φ, then Γ ∪ {¬φ} has no model, hence it is inconsistent, hence Γ ⊢ φ.

A pleasant by-product is the compactness theorem: if every finite subset of Γ has a model, so does Γ. Proofs are finite, so a contradiction derived from Γ already comes from a finite part. Compactness lets logicians build exotic models and powers many results in SAT and verification.

Python Entailment and a finite unsatisfiable core

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.

Completeness does not say you can prove statements that are merely true in one model. It speaks only about what is true in all models, i.e. valid. For example, in the model of the natural numbers some statements are true but not provable from the first-order axioms of arithmetic. That gap is Gödel's incompleteness.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. Soundness of a proof system means

    Soundness: ⊢ φ implies ⊨ φ, so the system never proves anything false.
  2. 2. How does a semantic tableau test whether φ is valid?

    If every branch from ¬φ closes there is no countermodel, so φ is valid; an open branch gives a countermodel.
  3. 3. What does the compactness theorem state?

    Compactness says a set has a model exactly when every finite subset has one.
  4. 4. In a Henkin-style completeness proof, what is built from a consistent set?

    Extending to a maximal consistent set and reading off the valuation produces a model, so consistency implies satisfiability.

Summary

  • Soundness (⊢ implies ⊨) is proved by induction on proof length: axioms are tautologies and modus ponens preserves truth.
  • Completeness (⊨ implies ⊢) holds for propositional logic and for first-order logic (Gödel 1929).
  • A semantic tableau is a complete, terminating procedure that decides propositional validity.
  • Consistent sets have models; compactness follows because proofs are finite.

Next: Gödel's Incompleteness and Computability