Difficulty: Intermediate | Prerequisites: Chapter 8 (basic truth tree construction) and Section 9-1 (applying rules to complex sentences)
Truth trees are introduced in most courses as a way to test argument validity. This section shows that the same method, with small adjustments to what you place on the first line, can answer four other fundamental questions in sentence logic: Is a sentence a contradiction? Is it a logical truth? Are two sentences logically equivalent? Is a set of sentences consistent? Mastering these applications rounds out your toolkit for the course.
Truth trees can do more than test argument validity. By changing what you place on the first line, you can test whether a sentence is a contradiction (place the sentence itself), whether it is a logical truth (place its negation), whether two sentences are logically equivalent (test their biconditional for logical truth), and whether a set of sentences is consistent (list them all as initial sentences). Every test comes down to the same question: do all paths close, or does an open path remain?
Contradiction
A sentence that is false under every possible assignment of truth values to its sentence letters. In simple terms, there is no way to make it true. On a truth tree, if you place the sentence as the first line and all paths close, it is a contradiction.
Logical truth (tautology)
A sentence that is true under every possible assignment of truth values to its sentence letters. In simple terms, it is true no matter what. A sentence is a logical truth if and only if its negation is a contradiction.
Counterexample (to a contradiction)
A truth-value assignment that makes the sentence true. If such an assignment exists, the sentence is not a contradiction. On a truth tree, any open path provides this counterexample.
Counterexample (to a logical truth)
A truth-value assignment that makes the sentence false. If such an assignment exists, the sentence is not a logical truth. On a truth tree testing the negation, any open path gives this counterexample.
Logical equivalence
Two sentences are logically equivalent if and only if they have the same truth value in every possible case. In simple terms, they always agree. You test this by checking whether their biconditional (X≡Y) is a logical truth.
Consistency
A set of sentences is consistent if and only if there is at least one assignment of truth values that makes all of them true simultaneously. Think of it as: can these sentences all be true together?
Inconsistency
A set of sentences is inconsistent if there is no truth-value assignment that makes them all true at once. On a truth tree, if all paths close when the sentences are listed as initial lines, the set is inconsistent.
Model
An assignment of truth values to sentence letters that makes all the sentences in a set true. An open branch on a truth tree provides a model and proves the set is consistent.
Finite set (of sentences)
A set containing a definite, limited number of sentences. The truth tree test for consistency applies directly to finite sets. For infinite sets, you cannot form the conjunction of all members (since all sentences must be finite in length), which is why the set-based definition of consistency (C2) is more general than the single-sentence definition (C1).
Procedure: Make the sentence the first (and only) line of a truth tree.
If all paths close: the sentence is a contradiction. There is no way to make it true.
If any path remains open: the sentence is not a contradiction. The open path gives a counterexample (a case where the sentence is true).
Worked example: test ~(AvB)&(~A\u2283B).
Line 1: ~(AvB)&(~A\u2283B) – this is a conjunction, so stack both conjuncts.
Line 2: ~(AvB) – from line 1, rule &.
Line 3: ~A\u2283B – from line 1, rule &.
Line 4: ~A – from line 2, rule ~v.
Line 5: ~B – from line 2, rule ~v.
Line 6: branches from line 3 (rule \u2283): left leg ~~A, right leg B.
Left leg: ~~A becomes A (rule ~~), which contradicts ~A on line 4. Path closes (×).
Right leg: B contradicts ~B on line 5. Path closes (×).
All paths closed. The sentence is a contradiction.
Procedure: Take the negation of the sentence and test that negation for contradiction.
If the negation is a contradiction (all paths close): the original sentence is a logical truth.
If the negation is not a contradiction (some path stays open): the original sentence is not a logical truth. The open path gives a counterexample (a case where the original sentence is false).
Why this works: a sentence is true in all cases if and only if its negation is false in all cases, which means its negation is a contradiction.
Worked example: test whether (Av~A)v(A&~A) is a logical truth.
Negate it: ~[(Av~A)v(A&~A)].
Line 1: ~[(Av~A)v(A&~A)] – negated disjunction, so stack.
Line 2: ~(Av~A) – from line 1, rule ~v.
Line 3: ~(A&~A) – from line 1, rule ~v.
Line 4: ~A – from line 2, rule ~v.
Line 5: ~~A – from line 2, rule ~v. This gives A, which contradicts ~A. Path closes (×).
All paths closed. The negation is a contradiction, so the original is a logical truth.
Worked example: test whether (A&B)v~A is a logical truth.
Negate it: ~[(A&B)v~A].
Line 1: ~[(A&B)v~A] – negated disjunction, so stack.
Line 2: ~(A&B) – from line 1, rule ~v.
Line 3: ~~A – from line 1, rule ~v. This gives A (rule ~~).
Line 4: from ~(A&B), rule ~&: branches into ~A (contradicts A, closes) and ~B.
Right leg with ~B and A remains open. Counterexample: A true, B false (A&~B).
The sentence is not a logical truth.
Procedure: Form the biconditional X\u2261Y. Test whether it is a logical truth (negate it and test for contradiction).
If X\u2261Y is a logical truth (negation closes): X and Y are logically equivalent.
If X\u2261Y is not a logical truth (negation has an open path): X and Y are not logically equivalent. The counterexample is a case where one is true and the other false.
Why this works: a biconditional is true exactly when both sides agree. If it is a logical truth, the two sides agree in every case.
Worked example: show ~(A&B) is logically equivalent to ~Av~B (De Morgan's rule).
Form the biconditional: ~(A&B)\u2261(~Av~B).
Negate it: [(A&B)\u2261(~Av~B)].
Apply negated biconditional rule (~\u2261): branches into two stacks.
Left stack: ~(A&B) and ~(~Av~B). Right stack: ~~(A&B) and (~Av~B).
Both branches close after further decomposition. The biconditional is a logical truth, so the sentences are logically equivalent.
Procedure: List all the sentences in the set as the initial lines of a truth tree (as though they were all premises).
If all paths close: the set is inconsistent. There is no assignment of truth values making all sentences true together.
If any path remains open: the set is consistent. The open path provides a model (a truth-value assignment making all the sentences true).
Connection to validity: an argument is valid if and only if the set comprising its premises and the negation of its conclusion is inconsistent. Validity testing is a special case of consistency testing.
Students sometimes test for logical truth by placing the sentence itself on the tree and checking whether all branches remain open. This does not work. A simple sentence letter like "A" would pass that test (nothing to decompose, branch stays open), but "A" is not a logical truth. The correct test negates the sentence first.
Students sometimes confuse the direction of the test. For contradictions, you place the sentence itself and look for all paths to close. For logical truths, you place the negation and look for all paths to close. Mixing these up gives the wrong answer.
When testing logical equivalence, students sometimes test each sentence separately for logical truth. That tells you nothing about equivalence. The correct test forms the biconditional of the two sentences and tests that for logical truth.
Students sometimes assume that a consistent set of sentences must all be individually true. Consistency only requires that there exists at least one truth-value assignment making them all true together. Individual sentences in the set may be false under other assignments.
⚠️ Exercise 9-3 asks you to test sentences for logical truth. Remember: negate first, then build the tree. State clearly whether the sentence is a logical truth and give counterexamples if it is not.
⚠️ Exercise 9-4 asks you to test for contradictions. Place the sentence directly on the tree. State clearly whether it is a contradiction and give counterexamples if it is not.
⚠️ Exercise 9-6 asks you to test pairs of sentences for logical equivalence. You may use either the biconditional test or the closely related test from Exercise 9-5 (comparing logical equivalence to the logical truth of X≡Y). Know both approaches.
⚠️ The relationship between validity and consistency (Exercise 9-7g) is a classic exam topic: an argument is valid if and only if the set of its premises together with the negation of its conclusion is inconsistent.
⚠️ When giving counterexamples to a sentence being a logical truth, note that the counterexample makes the original sentence false (it makes the negation true). Students frequently state it backwards.
True or false: To test a sentence for being a logical truth, place it on the first line of a truth tree and see if all branches stay open.
Fill in the blank: A sentence is a logical truth if and only if its ______ is a contradiction.
True or false: If you place a sentence on the first line of a tree and all paths close, the sentence is a logical truth.
Fill in the blank: A set of sentences is consistent if the truth tree has at least one ______ path.
True or false: An argument is valid if and only if the set of its premises plus the negation of its conclusion is consistent.
Answers: 1. False (you must negate it first). 2. negation. 3. False (it is a contradiction). 4. open. 5. False (the set must be inconsistent for the argument to be valid).
Q: Is the sentence (A&B)&(~Av~B) a contradiction? Describe the test.
A: Place (A&B)&(~Av~B) as the first line of a tree. Decompose the conjunction to get A&B and ~Av~B. Then A and B from the conjunction, and branch on the disjunction: ~A on one leg (contradicts A, closes), ~B on the other (contradicts B, closes). All paths close. Yes, it is a contradiction.
Q: Is the sentence (FvG)&(~Fv~G) a contradiction?
A: Place it on the tree. Decompose: FvG and ~Fv~G. Branch on FvG: F on one leg, G on the other. On each leg, branch on ~Fv~G. At least one path will remain open (for example, F true and ~G true). It is not a contradiction. Counterexample: F true, G false.
Q: Describe how to test whether A\u2283~A and ~A are logically equivalent.
A: Form the biconditional (A\u2283~A)\u2261~A. Negate it: ~[(A\u2283~A)\u2261~A]. Build the tree. If all paths close, the sentences are logically equivalent. If any path stays open, they are not, and the open path gives a case where one is true and the other false.
Q: You are given the set {PvS, P\u2283S}. Is this set consistent?
A: List PvS and P\u2283S as the initial lines. Branch on PvS: P on one leg, S on the other. On each, branch on P\u2283S: ~P or S. At least one path stays open (for example, S true). The set is consistent. Model: S true (P can be either).
Q: Explain the connection between argument validity and set consistency.
A: An argument is valid if and only if the set made up of all its premises together with the negation of its conclusion is inconsistent. If that set has a model (is consistent), the model is a counterexample to the argument's validity.
This material connects to Section 9-1 (applying rules to complex sentences), since the four tests here all require fluent decomposition of compound sentences. It also ties to truth tables from earlier chapters: every test truth trees perform can also be done with a truth table, but trees are generally faster because they stop as soon as all paths close or an open path is found.
The concept of consistency becomes central in Volume II, Part II of the text, where it underpins the metatheory of logic. The distinction between finite and infinite sets of sentences (Exercise 9-7) foreshadows that material.
Truth trees, semantic tableaux, contradiction, tautology, logical truth, logically true, logical equivalence, logically equivalent, consistency, inconsistency, model, satisfiable, unsatisfiable, counterexample, De Morgan's rules, sentence logic, propositional logic, PHIL 101, Chapter 9, truth tree applications, validity, argument testing, finite set, infinite set