# 8.1: Proving Validity with Truth Trees

You know, from the exercises of chapter 4, that you can use truth tables to check the validity of any argument of sentence logic. But such truth table checks for validity are extremely tedious. If you read chapters 5, 6, and 7, you also know how to establish validity by using derivations. Many logicians like this natural deduction technique because (for those with a taste for logic) derivations are challenging and fun, and because derivations express and make precise informal modes of deductive reasoning.

In this and the next chapter I will present a third means for determining the validity of sentence logic arguments-the truth tree method. This method is more nearly mechanical than is natural deduction. This fact makes truth trees less fun, because they provide less of a challenge, but also less aggravating, because they are easier to do. Truth trees also have the advantage of making the content of sentence logic sentences dear, in a way which helps in proving general facts about systems of logic, as you will see if you study part II of Volume II.

As a basis for the truth tree method we need to remember two fundamental facts from sections 4-1 and 4-2. We know that an argument is valid if and only if every possible case which makes all its premises true makes its conclusion true. And we know that this comes to the same thing 114 Truth Trees fm Sentence Logic Fundamentals 8-1. Proving Validity with Truth Trees 115 as an argument having no counterexamples, that is, no cases which make the premises true and the conclusion false.

The truth tree method proceeds by looking for counterexamples in.an organized way. The method has been cleverly designed so that it is guaranteed to turn up at least one counterexample to an argument if there are any counterexamples. If the method finds a counterexample, we know the argument is invalid. If the method runs to completion without turning up a counterexample, we know there are no counterexamples, so we know that the argument is valid. Finally, the method considers whole blocks of possible cases together, so in most cases it works much more efficiently than truth tables.

We will introduce the truth tree method with a specific example:

AvB
~BvC
AvC

We are trying to find a counterexample to this argument. That is, we are looking for an assignment of truth values to sentence letters which makes the premises true and the conclusion false. Now, if we try to make some sentences true and another sentence false, things are going to get very confusing. It would be much more straightforward if we could follow a procedure which tried to make all of the sentences considered true.

Can we do that and still be looking for a counterexample to our argument? Yes - if we replace the conclusion of the argument with its negation. So we begin the truth tree method for looking for a counterexample by listing the premises of the argument and the negation of the conclusion:

1 AvB P(Premise)
2 ~BvC P (Premise)
3 ~(AvC) ~C (Negation of the Conclusion)

Our method now proceeds by trying to make lines 1, 2, and 3 true. "Make true" just means finding an assignment of truth values to sentence letters for which the sentences are true. If we succeed, we will have a case in which the argument's premises, lines 1 and 2, are true. And this same case will be one in which the conclusion is false, because the negation of the conclusion, line 3, will be true. So if we can make lines 1, 2, and 3 true, we will have our counterexample.

Note that I have numbered the lines, and written some information off to the right of each line which tells you why the line got put there. You should always number and annotate your lines in this way so that we can talk about them easily.

Now to work. Let's begin by making line 1 true. We see that there are two alternative ways of making 'AvB' true. First, we can make it true just by making 'A' true. If we make 'A' true, we have made 'AvB' true, whatever eventually happens to the truth value of 'B'. But the same is true of 'B'. If we make 'B' true, 'AvB' will be true whatever eventually happens to the truth value of 'A'. So making 'A' true is a first and making 'B' true is a second, alternative way of making 'AvB' true. We need the truth tree method to be guaranteed to find a way of making all initial lines true if there is a way. So we must be sure to write down all ways in which a line might be true, and if there are alternative ways, we must list them independently.
We mark this fact by extending the tree as follows: We have split the original path into two paths or branches. Each branch will represent one way of making true all the sentences which appear along it. The left branch will make line 1 true by making 'A' true. The right branch will make line 1 true by making 'B' true. Since the paths have branched, they represent alternative ways of making line 1 true. What happens along one path will have no effect on what happens along the other path below the point at which they branch.

I have added some notation to the tree. The '1, v' at the right of line 4 means that I got line 4 from line 1 by working on a disjunction. I have checked line 1 to remind myself that I have now done everything which needs doing to make it true. I won't have to work on that line anymore.

Now let's work on line 2. I have to make it true, and I will do this exactly as I did for line 1. I will make each of the two disjuncts true; that is, I will make '~B' true and I will independently make 'C' true along a separate branch. But I have to "add on" the ways of making line 2 true to each of the ways of making line 1 true. Remember, we are looking for some way of making all the original lines true together. So I must first write each of the alternative ways of making line 2 true as an extension of the first (left branch) way of making line 1 true. That is, I must extend the left branch with two new branches each of which represents one of the two ways of making line 2 true. So the left branch will itself split and look like this: The same reasoning obviously applies to the right branch. I must add on both of the ways of making line 2 true to the second (right branch) way of making line 1 true. We represent this by splitting the right branch so it looks like this: Putting these pieces together, after working on line 2, the tree looks like this: Each branch represents one of the ways of making line 1 true combined with one of the ways of making line 2 true. The leftmost, or first, branch makes line 1 true by making 'A' true and makes line 2 true by making '-B' true. The second branch makes line 1 true by making 'A' true and makes line 2 true by making 'C' true. (Do you see how we combine the alternative ways of making the first two lines true?)

The third branch makes line 1 true by making 'B' true and makes line 2 true by making '~B' true. Whoops! Surely something has gone wrong! Surely we can't make line 1 true by making 'B' true and at the same time make line 2 true by making '~B' true. If we were to make '~B' true, this would be to make 'B' false, and we just said that along the third branch 'B' would be made true to make line 1 true. We can't make 'B' both true and false. What is going on?

What has happened is that the third branch represents an inconsistent way of making lines 1 and 2 true. Focus on the fact that each branch represents one of the four ways of trying to make lines 1 and 2 true together. It turns out that the third of these ways won't work. One way of making line 1 true is by making 'B' true. One way of making line 2 true is by making '~B' true. But we can't combine these ways of making the two lines true into one way of making the lines true at the same time, because doing this would require making 'B' both true and false. We ' mark this fact by writing an 'x' at the bottom of the branch on which both 'B' and '~B' appear. The 'x' tells us that we cannot consistently make true all of the sentences which appear along the branch. We say that the branch is Closed. We never have to work on a closed branch again:

We say that a branch is Closed when a sentence, X, and its negation, ~X, both appear on the branch. We mark a branch as closed by writing an ' X ' at the bottom of the branch. Do not write anything further on a branch once it has been marked as closed.

The sentence X may be an atomic sentence, such as 'A', or a compound sentence, such as 'Bv~(C&~A)'. Also note that the sentence and its negation which cause a branch to close must both appear as entire sentences at points along a branch. If one or both appear as part of some larger compounds, that does not count. To illustrate this point, look at the tree drawn up to line 4, as presented on page 115. On the right-hand branch you see 'B' as the entire sentence at the end of the branch, and '~B' as part of a compound on line 2. The branch does not close at this point because there is no conflict between line 2 and the right branch at line 4. It is perfectly possible for 'B' and '~BvC' both to be true.

It is the fact that branches can close which gives the truth tree method its simplifying power. Here is how simplification occurs. We still have to make line 3 true, and we have to combine the ways of making line 3 true with the ways of making lines 1 and 2 true. But we can forget about one of these ways of (trying to) make lines 1 and 2 true because it turned out to be inconsistent. This corresponds to ruling out certain lines of the truth table before we have completely worked them out. Because a truth tree avoids working out what corresponds to some of the lines of the corresponding truth table, truth trees often save work.

Note how I annotated the tree in the last step: I put '2, v' to the right of line 5 to indicate that I got line 5 from line 2 by working on a disjunction. And I checked line 2 to remind myself that I have done everything needed to make line 2 true. I won't need to worry about line 2 anymore.

Let's complete the tree by working on line 3. What has to be done to make line 3 true? Line 3 is the negation of a disjunction. The negation of a disjunction is true just in case the disjunction itself is false. So, to make '~(AvC)' true, I have to make 'AvC' false. How do I make 'AvC' false? According to the truth table definition of 'v', I can do this only by making both 'A' false and 'C' false. So the result of making line 3 true will not be a branch of two alternative ways of making a sentence true. There is only one way to make line 3 true: a stack which first makes 'A' false and then makes 'C' false. But to keep things clearly organized I only write down true sentences. So what I have to write is a stack which makes '~A' true and makes '~C' true.:

~A
~C

By making '~A' true followed by '~C' true, I have made 'A' and 'C' both false, which makes 'AvC' false, in the only way that this can be done. Finally, making 'AvC' false makes '~(AvC)' true, which was what we wanted to accomplish.

Where do I write this stack? I must combine the results of making line 3 true with all the ways I already have for making lines I and 2 true. At first thought, this would seem to indicate that I should write my '~A', '~C' stack at the bottom of every branch. This is almost right. But I won't have to write the results of working on line 3 at the bottom of the closed (third) branch. Remember that the closed branch represents a way of trying to make previous sentences true that can't work because it is inconsistent. So I only have to write my stack at the bottom of every Open Branch, that is, every branch which does not have an 'x' at its bottom:

A branch which is not closed is Open.

Adding the stack to the open branches gives a tree that looks like this: The '3, ~v' means that I got the lines from line 3 by working on a negated disjunction. I also checked line 3.

We have one more thing to do to this tree. Note that now the first, second, and fourth branches all have the problem that the third branch had. To make all the sentences along the first branch true, I would have to make 'A' true and '~A' true. That is, I would have to make 'A' both true and false. I can't do that, so I put an 'x' at the bottom of the first branch. I do exactly the same to tk second branch for exactly the same reason. The fourth branch has both 'C' and '~C', so I must close it with an ' x ' also. The final tree looks like this: Here is the final result: All branches have closed. That means that every possible way of trying to make all the initial sentences true results in a conflict. Each way of trying to assign truth values to sentence letters requires that some sentence be made both true and false, and the rules of the game do not permit that. We agreed in chapter 1 that in a given problem a sentence letter would be true or false, but not both. Since there is no way of making all initial sentences true, there is no way of making the argument's premises true and its conclusion false. That is, there is no counterexample to the argument. So the argument is valid.