The truth-tree method
A tree tests one thing directly: whether a finite set is truth-functionally consistent. Section 3.6 already showed that every other property reduces to consistency, so that is enough.
How it works
List the set members (SM). Then repeatedly pick a sentence that isn't a literal (an atom or the negation of an atom), decompose it by the rule for its form, and check it off. Each rule writes down what must be true for the sentence to be true. Group 1 sentences have one way to be true and get non-branching rules; Group 2 sentences have several and get branching rules.
Results go on every open branch that runs through the decomposed sentence, and nowhere else. Each line of the tree cites exactly one earlier line and one rule.
Reading the result
- A branch is closed when it contains contradictory literals, like C and ~ C. Mark it × and stop working on it.
- A completed open branch is open and every sentence on it is a literal or checked off. Mark it o.
- A finite set is consistent if and only if it has a tree with at least one completed open branch; inconsistent if and only if it has a closed tree.
- Read an assignment off a completed open branch: letters that appear make true, negated letters false, and absent letters can be either.
The order of decomposition is up to you. Different completed trees for the same set always give the same verdict.
Guidelines for concise trees
- Stop when the tree answers the question being asked.
- Decompose sentences that don't branch first.
- Next, prefer decompositions that close one or more branches.
- Otherwise, decompose the more complex sentence first.
Complex sentences decomposed late have to be copied onto many branches. The builder below follows these guidelines when it suggests a move.
The nine decomposition rules
Group 1 · non-branching
Group 2 · branching
Using trees to test other properties
Each test builds a tree for a carefully chosen set, using the results of section 3.6.
One subtlety: to show a sentence is truth-functionally indeterminate you need two trees, one for {P} and one for {~ P}, and neither may close.
The section's exercises also add rules for new connectives (such as the Sheffer stroke), a good test of whether you understand where the rules come from: each one records what must be true for the sentence to be true.
Which tree to build
| Question | Build a tree for | Yes if |
|---|---|---|
| Γ consistent? | Γ | an open branch completes |
| P TF-false? | {P} | tree closes |
| P TF-true? | {~ P} | tree closes |
| P indeterminate? | {P} and {~ P} | neither closes |
| P, Q equivalent? | {~ (P ≡ Q)} | tree closes |
| Γ ⊨ P? | Γ ∪ {~ P} | tree closes |
| Argument valid? | premises + ~ conclusion | tree closes |
Truth-tree builder
Choose a question and type the sentences, one per line. Build the tree yourself by clicking the sentence to decompose next, or let the builder finish it using the book's guidelines.
Practice sets for Chapter 4
Discussion questions
- The rule for disjunctions puts P on one branch and Q on the other, with no ~ Q next to P. Why isn't anything lost?
- Why may we stop working on a branch as soon as it closes, even with undecomposed sentences on it?
- A closed tree for Γ ∪ {~ P} shows Γ ⊨ P. Explain why in your own words, without mentioning trees.
- When is a truth-table quicker than a tree, and when is a tree quicker? Try a set with six sentence letters.
- Write decomposition rules for "neither P nor Q" treated as a new connective, and for its negation.
Questions for our session
Saved in this browser only.