Propositional Logic · step 13 of 13

Soundness & completeness

Two different relations sit at the heart of logic. Γ ⊢ A is syntactic: there is a proof of A from Γ in your chosen system. Γ ⊨ A is semantic: every model of Γ satisfies A. Soundness says ⊢ implies ⊨ (the system never proves anything false); completeness says ⊨ implies ⊢ (the system can prove everything true). Propositional logic enjoys both, so the two relations coincide.

Practise soundness & completeness free → All Propositional Logic subtopics

✓ Unlimited questions · marked criterion by criterion · no card needed

Method: how to approach it

The order below is what examiners expect to see, and each step carries its own marks.

Keep the direction straightSoundness: if you can prove it, it is true. Completeness: if it is true, you can prove it. Mixing the arrows is the classic exam slip.
Prove soundness by induction on the proofShow each axiom is valid and each rule preserves validity. Then every derivable formula is valid, by induction on derivation length.
Read completeness through consistencyThe standard route is: every consistent set has a model. Contrapositive of that gives completeness, which is why the Lindenbaum construction appears in every textbook proof.
Apply the equivalenceOnce both hold you may switch freely: refute a proof claim with a counter-model, or establish a semantic claim with a derivation.

Worked example

A proposed rule lets you infer p from p ∨ q. Is the resulting system still sound?

Soundness requires the rule to preserve validity: whenever the premise is true, the conclusion must be true.
Take the valuation p = F, q = T.
The premise p ∨ q evaluates to T, but the conclusion p evaluates to F.
So the rule can lead from a true premise to a false conclusion.

Answer. No — the system is unsound. The rule permits deriving p from p ∨ q, but p ∨ q ⊭ p.

Where marks get dropped

These are the specific errors that cost credit on soundness & completeness questions — QED's rubric penalises each of them separately.

Stating completeness as "every formula is provable or refutable". That is a different property; completeness is about provability of the semantically valid formulas.
Assuming soundness is trivial. It is a theorem about every rule in the system — adding one bad rule, as above, destroys it.
Carrying propositional intuitions to every system. Predicate logic is also sound and complete (Gödel), but arithmetic is not — Gödel’s incompleteness theorem is a statement about a much richer language.

Practise this until it is automatic

Unlimited fresh questions

QED generates new soundness & completeness problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.

Marked like an examiner

Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.

Answer in real notation

A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.

Saved to your library

Every question you generate is kept and re-takeable as a timed exam, and your Propositional Logic mastery is tracked so you know when this is exam-ready.

Soundness & completeness — frequently asked questions

Which is worse, an unsound or an incomplete system?

Unsound, by a wide margin. An incomplete system merely fails to prove some truths; an unsound one proves falsehoods, which makes every conclusion untrustworthy.

Does completeness mean I can decide any formula?

For propositional logic yes — it is decidable, and truth tables give an algorithm. Completeness alone does not imply decidability: first-order logic is complete but only semi-decidable.

How does this relate to Gödel’s incompleteness theorem?

They concern different things. Gödel’s completeness theorem is about first-order logic as a whole; the incompleteness theorems are about specific axiom systems for arithmetic being unable to prove all arithmetic truths.

The rest of Propositional Logic

Connectives, truth tables, equivalences and normal forms. Each subtopic below has its own method, worked example and mark-losing traps.

Ready to make soundness & completeness exam-proof?

Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.

Start practising free →