Note: The material presented below is Chapter 11 of Howard Pospesel, Introduction to Logic: Propositional Logic (3rd ed.), rewritten as an introduction to one-sided truth trees.

¹The method is also known as the "semantic tableau" test. It was conceived independently by E. W. Beth and Jaakko Hintikka in the 1950's. Several truth-tree formats have been developed. The one employed in this chapter was devised by Richard Jeffrey.

A truth tree is a vertical list of wffs that may branch into further vertical lists of wffs. Here is a simple example:

P  Q  
P  
-Q
/  \
-P  Q
*   *

This tree has two "branches." The left branch is the list consisting of the top three wffs and '-P'. The right branch, of course, consists of the first three wffs and 'Q'.

The idea behind truth trees is to unpack the contents of wffs by decomposing or analyzing them into smaller and smaller parts until you reach capital letters and their negations. We'll need nine decomposition rules. These rules are based on the five principles displayed on page 152 in the text. Let's start by considering these four rules:

A & B  
A
B

A v B  
/  \
A   B

A  B  
/  \
-A  B

A  B  
/  \
A   -A
B   -B

We "check" a wff to show that it has been decomposed. The & Rule is very like the &O Rule (from Chapter Three). The v Rule represents disjunction by dividing a branch into two sub-branches. The Rule relies on this equivalence:

A  B  =  -A v B;

and the Rule on this one:

A  B  =  (A & B) v (-A & -B).

I'll illustrate the use of the first two rules with this tree (in which 'C & (D v -E)' and 'F & G' are assumed as truths):

     1  C & (D v -E)
     2     F & G
              ---
     3         C          from line 1 by &
     4     D v -E       from line 1 by &
     5         F          from line 2 by &
     6         G          from line 2 by &
              / \
     7       D  -E        from line 4 by v

(The columns on the left and the right are instructional devices and not part of the tree diagram.) Let's draw a short horizontal line beneath the initial assumptions to separate them from the wffs that are derived from them. Several comments on tree construction: (1) The main connective in the wff on a given line determines what rule is to be applied to that wff. It would be a mistake to apply the v Rule to the wff on line one since the wedge is not the main connective in that wff. (2) Each wff added to a branch is written below the wffs already on that branch. Wffs on different branches may be written on the same horizontal line. (3) You save yourself work by postponing branching as long as possible. If I had not followed that plan, the tree would look like this (with ten wffs instead of eight):

C & (D v -E)  
F & G  
C
D v -E  
/  \
D   -E
F    F
G    G

(4) Note that when a wff is decomposed after the tree has branched beneath it, the decomposition move must be made on each of the (open) branches below.

This tree shows the use of the third and fourth rules:

H  -I
J  K  
/       \
J        -J
K        -K
/  \      /  \
-H   -I   -H   -I

(I shorten the tree slightly by decomposing the biconditional formula first.)

Here are the five remaining rules (and the equivalences they rely on):

-(A & B)  
/  \
-A   -B

-(A v B)  
-A
-B

-(A  B)  
A
-B

-(A  B)  
/  \
A   -A
-B   B

--A  
A

The tree below illustrates the application of three of these additional rules:

     1   -(L & M)
     2   -(N v -O)
              ---
     3        -N              from line 2 by -v
     4      --O             from line 2 by -v
     5         O              from line 4 by --
             /   \
     6      -L   -M           from line 1 by -&

I attend to line 2 (and then line 4) before line 1 so as to postpone branching as long as possible.

11.2
Testing Arguments

The truth-tree test of validity is simple in concept, but to explain it I need to provide a few definitions:

A "closed" branch is a branch on which some wff and its negation both appear. (We will mark closed branches with an asterisk at the tip.)

An "open" branch is a branch that isn't closed.

A "closed" tree is a tree all of whose branches are closed.

An "open" tree is a tree some of whose branches are open.

An open branch (of a completed truth tree) reveals an assignment of truth-values to the capitals occurring on that branch that is consistent with the initial assumptions. Consider this tree, for example:

A v B  
-(A  B)  
A
-B
/  \
A   B
    *

The open left branch shows that the assignment of truth to A and falsity to B is compatible with the initial assumption that 'A v B' and '-(A B)' are both true.

Every assignment of truth-values to all the capitals that is consistent with the initial assumptions will be represented by some open branch (and possibly more than one). And that means that if all the branches on a truth tree are closed, that is, if the tree itself closes, then no assignment of truth-values to all the capital letters is consistent with the initial assumptions. That provides the key to the truth-tree test for validity. Recall that a sequent is valid iff it is impossible for its premises to be true while its conclusion is false. So we set the test up by listing as initial assumptions the premise wffs and the negation of the conclusion wff. The sequent is valid iff the tree closes.

I'll illustrate by testing four arguments (sequents). A newspaper columnist writes:

Mas states that "it is not true there have not been public hearings" on the proposed transfer of Radio Marti to Miami. . . . The fact is that there were no congressional hearings prior to lawmakers' sudden approval of the move last month.²

²Christopher Marquis, "'Truth-Telling' and Jorge Mas," Miami Herald (January 15, 1996), p. 13A.

There have been no HEARINGS. Hence the claim [made by Mas] that it is not true that there have not been hearings is itself not true.

H ---H

-H
----H  
--H
*

The tree has only one branch and that branch is closed because both '-H' and its negation '--H' appear. The fact that the tree is closed shows the sequent to be valid. The premise cannot be true at the same time that the conclusion is false.

The second argument undergirds a joke that I will tell in a stripped-down version. The philosopher Réné Descartes is sitting in a bar when the bartender announces that it is closing time. When he asks Descartes whether he wants one for the road, Descartes answers, "I think not," and promptly vanishes. (Look, it's a philosopher's joke; it doesn't have to be that funny.)

Of course, the joke capitalizes on Descartes' famous cogito ergo sum argument ("I think; therefore I am"). The argument behind the joke, then, goes like this:

If Descartes THINKS, then he EXISTS. But he thinks not [i.e., doesn't think]. So, he doesn't exist.

T E, -T -E

T  E  
-T
--E  
E
/  \
-T  E

The tree is open; this shows that the sequent is invalid. The tree even tells you the invalidating assignment of truth-values. If T is false and E true, then the premises of the argument are true and the conclusion false.

In the animated musical "Aladdin," the hero sings, "Gotta eat to live, gotta steal to eat," suggesting this argument:

My EATING is necessary for my continuing to LIVE. I eat only if I STEAL. Thus, stealing is necessary for my survival.

L E, E S L S

The tree:

L  E  
E  S  
-(L  S)  
L
-S
/  \
-L   E
  *  /  \
    -E   S
     *   *

Every branch closes, so the sequent (and argument) is valid (which we knew anyway, since it is a chain argument).

The last example concerns an argument suggested by the "Sally Forth" comic strip displayed on page 179 of the text.

If Mom got her hair CUT and I don't say anything, I'm in trouble. But if she didn't get it cut and I do SAY something, I'm in just as much trouble. Therefore, I'm in trouble.

(C & -S) T, (-C & S) T T

³Because it considers only two of four possible states of affairs. If Mom got her hair cut and Dad says something, for example, then he is not necessarily in trouble.

(C & -S)  T  
(-C & S)  T  
-T
/           \
 -(C & -S)         T        
/          \        *       
-C        --S                 
S     
/     \      /      \                 
-(-C&S)  T -(-C&S)   T                    
/    \   *   /    \    *                  
--C   -S   --C   -S                       
*            C     *                       

Two of the branches remain open, establishing the invalidity of the sequent.

Answers to some pertinent questions about the truth-tree test: (1) Q: When is a truth tree complete? A: When every compound wff (aside from the negation of a capital letter) has been decomposed or when every branch of the tree has closed. Note that these are independent conditions. (2) Q: Is it ever safe to stop constructing a tree before it is complete? A: Yes. If all the compound wffs (aside from negations of capital letters) on one branch have been decomposed and that branch remains open, then construction can stop. The tree will be open; no further construction will change that fact. (3) Q: Aside from postponing branching, does it matter in what order you decompose wffs? A: Sometimes you can simplify a tree by the order in which you decompose wffs, as these trees for the same sequent illustrate:

P  Q  
R  Q  
R
-P
/     \
-P      Q
/ \     / \
-R  Q   -R  Q
*       *    

P  Q  
R  Q  
R
-P
/    \
-R     Q
 *     / \
      -P   Q

Compare the truth-tree and full-truth-table techniques. In one respect the two methods are mirror images of each other. In full truth tables you do truth-value calculations beginning with the smallest wff components. In truth trees you are in effect calculating truth-values in the opposite direction. Think about a truth table and a truth tree for a given set of wffs. Every row on the truth table on which the initial wffs are all true correlates with at least one open tree branch (and every open branch correlates with at least one such row). A truth table on which there is no row where the initial wffs have the indicated truth-values corresponds to a truth tree on which every branch closes.

The truth-tree and brief-truth-table methods also have something in common. In both techniques you assume the premises of a sequent to be true and the conclusion to be false, and then determine whether a contradiction follows from this assumption.

EXERCISES

1. Complete the following truth trees. Remember to place a check mark by each decomposed wff, and to mark each closed branch with an asterisk. Identify each tree as "open" or "closed."

(a)

A  B
-(B  A)


/ \

*(b)

-(C & D)
-(C v D)


/ \

(c)

-E v -F
--(E & -F)



/ \

(d)

G  H
-(H  G)
/      \


/   \    /   \

Exercises 2 through 14 are provided on pages 182 through 184 of the text.