Theory and Practice of Truth Trees

 
 The tree method is a way of testing whether a set of wffs is consistent or inconsistent. In simple terms, it is a scheme to hunt for a truth table row that will make all of the wffs in the set true together, without having to construct a whole truth table and then check by inspection. The way this scheme works is first, to set out, in a vertical list, the wffs given in the set we are testing. For example, if we are testing the following set of wffs for consistency: (A & B), (C v D)

we begin our tree by constructing the root. We put the wffs we're testing for consistency one below another at the up-side-down root:

Remember, we are trying to find a row of the truth table that will make all of these wffs true. What we need are rules for breaking down these complex wffs into sentence letters, and their negations, in such a way that these atoms will tell us exactly those rows of the truth table which make the given non-atomic wff true. The truth tree rules do just that.

Using those rules, we apply them to each wff until we've applied them to all:

Notice how some of these rules involve branching (that's why they are called "trees"!) A branch represents, in effect "or". So in the rule for the disjunction, we have the following information: the rows in which (C v D) is true are either the rows in which C is true or the rows in which D is true. The branching picture captures exactly those rows of the truth table which make (C v D) true. When the rule calls for you to put A and B one below the other (the rules in which there is no branching) this represents "and". So in the rule for conjunction we have the following information: the rows in which (A & B) is true are the rows in which both A and B are true. And this is exactly what the truth table tells us.

As you may have noticed, the rules tell us what it takes for a wff with a given main operator to be true. But our truth tables also tell us the conditions under which a given wff is false. And this is just what our rules do. So, you can see that, taken together, the rules for any connective give us a complete picture of the truth table for that connective.

What do we do with the truth-tree when we've applied all the rules? That's our next topic.

B. Using the tree method to determine consistency

To get started we need some definitions:

By given wffs we mean the wffs we are testing, the ones we set down vertically at the top of the tree.

A path starts at the top of the tree and continues to a tip. Notice that every path contains the given wffs. Remember also that a path represents a try at finding a row of the truth table which makes all the wffs in the path true.

A path is closed iff it contains two wffs, one of which is the negation of the other. Note that these wffs need not be atoms. To indicate that a path is closed, write an "X" under its tip.

A path which is not closed is an open path.

The meaning of a closed path is this: this try is a failure. Why? Well, clearly there is no row of the truth table that can make all the wffs in the path true, because there is no row in which a wff and its negation are both true. That would be a contradiction, right?

A wff gets checked only after you have supplied the appropriate rule to it. (That is, once you have applied the appropriate rule to a wff, put a check make next to it.)

IMPORTANT: The appropriate rule is the one that corresponds to the main connective of the wff. The meaning of a checked wff is this: the truth conditions of this wff are not represented by other wffs lower down in the tree.

A path is finished in either of two cases:

1. It is closed;

2. It is not closed but every non-atomic wff is checked. The only unchecked wffs are sentence letters and their negations, that is, the atoms. This indicates that all the necessary rules have been applied, that the truth conditions of all the complex wffs have been reduced to the truth conditions of the remaining atoms.

The meaning of a finished open path is that there is definitely a row of the truth table in which all the wffs in the path, including the given ones, are all true. And we can specify this row by applying the following recipe to the finished open path:

1. If a sentence letter is in the path, give that letter the truth value T.

2. If a negation of a sentence letter is in the path, give that letter the value F.

3. If neither the sentence letter nor its negation is in the path, give it whatever value you choose.

The result of these assignments is a row of the truth table in which all the wffs in that path are true. An entire tree is said to be finished iff each of its paths is finished. Taking a group of wffs and considering a finished tree for them:

The set is inconsistent iff every path is closed.

The set is consistent iff at least one finished path is open.

VERY IMPORTANT: When applying a tree-rule to a wff, you must set down the results of applying that rule on every open path that passes through that wff.

Testing for consistency with the truth-tree method: An Example