Propositional Logic · step 8 of 13

Semantic tableaux & truth trees

A semantic tableau is a systematic search for a valuation that satisfies a set of formulas. You decompose formulas by rules: conjunctive (α) formulas extend the current branch, disjunctive (β) formulas split it into two. A branch closes when it contains both a formula and its negation. If every branch closes the set is unsatisfiable; any branch that stays open and is fully decomposed hands you a model directly.

Practise semantic tableaux & truth trees 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.

Set up the rootTo test validity of Γ ⊨ A, put all of Γ and the NEGATION of A at the root. The argument is valid exactly when the resulting tree closes.
Classify each formula α or βA ∧ B, ¬(A ∨ B) and ¬(A → B) are non-branching. A ∨ B, A → B and ¬(A ∧ B) branch. Biconditionals branch into two two-formula branches.
Do non-branching rules firstExhausting α-formulas before splitting keeps the tree dramatically smaller and often closes branches before they multiply.
Close, or read off a modelMark a branch closed (×) when it holds X and ¬X. From an open, saturated branch, read every literal on it — that assignment is a counter-model.

Worked example

Use a tableau to test whether p → q, ¬q ⊨ ¬p.

Root: p → q, ¬q, and the negated conclusion ¬¬p.
Decompose ¬¬p to get p.
Branch on p → q: left branch gets ¬p, right branch gets q.
Left branch contains p and ¬p — closed. Right branch contains q and ¬q — closed.

Answer. Every branch closes, so the argument is valid. (This is modus tollens.)

Where marks get dropped

These are the specific errors that cost credit on semantic tableaux & truth trees questions — QED's rubric penalises each of them separately.

Forgetting to negate the conclusion. A tableau tests satisfiability, so validity is checked by refuting the negation — putting the conclusion in unnegated tests something else entirely.
Closing a branch on a non-atomic clash without saying so. It is legitimate to close on X and ¬X for any formula X, but be explicit about which two lines clash.
Declaring a branch open before it is saturated. Every non-literal on the branch must have been decomposed first.

Practise this until it is automatic

Unlimited fresh questions

QED generates new semantic tableaux & truth trees 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.

Semantic tableaux & truth trees — frequently asked questions

How do tableaux compare with truth tables?

They usually do far less work, because a closed branch rules out many valuations at once. For a formula with four variables a tableau often closes in six lines where the table needs sixteen rows.

What does an open branch tell me?

It gives an explicit satisfying valuation: read the literals along the branch and assign each variable accordingly. Any variable not mentioned can take either value.

Which formulas branch?

The ones with a disjunctive character: A ∨ B, A → B, ¬(A ∧ B), and both directions of a biconditional. Conjunctive ones — A ∧ B, ¬(A ∨ B), ¬(A → B) — extend the branch without splitting.

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 semantic tableaux & truth trees 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 →