8-2. TRUTH TREES WITH MULTIPLE QUANTIFIERS
The sentence is a logical truth. In the last chapter I tried to keep the basics in the limelight by avoiding the complication of multiple quantifiers. Multiple quantifiers involve no new rules. But they do illustrate some circumstances which you have not yet seen.
Suppose I asked you to determine whether '(3x)[Lxa 3 (Vy)Lya]' is a logical truth. To determine this, we must look for a counterexample to its being a logical truth, that is, an interpretation in which it is false. So we - make the negation of the sentence we are testing the first line of a tree. Here are the first six lines: J1 -(3x)[Lxa 3 WyILyal -S a 2 pix)-[Lxa 3 Wy)Lya] 1, -3 J3 -[Laa 3 Wy)Lyal 2, V 4 Laa 3, -> J5 -(Vy)Lya 3, -3 6 (3~)-Lya 5, -V We begin with the negation of the sentence to be tested. Line 2 applies the rule for a negated quantifier, and line 3 instantiates the resulting universally quantified sentence with the one name on the branch. Lines 4, 5, and 6 are straightforward, first applying the rule -3 to line 3 and then the rule -V to line 5. But now the rules we have been using all along are going to force on us something we have not seen before. Applying the rule 3 to line 6 forces us to introduce a new name, say, 'b', giving '-Lba' as line 7. This has repercussions for line 2. When we worked on line 2 we instantiated it for all the names we had on that branch at that time. But when we worked on line 6 we got a new name, 'b'. For the universally quantified line 2 to be true in the interpretation we are building, it must be true for all the names in the interpretation, and we now have a name which we did not have when we worked on line 2 the first time. So we must return to line 2 and instantiate it again with the new name, 'b'. This gives line 8. Here, with the final two easy steps, is the way the whole tree looks:
The sentence is a logical truth.
We do not need to work on line 10 because line 7 is the negation of line 9, and the branch thus closes. Indeed, I could have omitted line 10. There was no way for us to avoid going back and working on line 2 a second time. There was no way in which we could have worked on the
130 More on Truth Trees for Predicate Logic 8-3. Three Shortc& 13 1
existentially quantified sentence of line 6 before working on line 2 the first time. The sentence of line 6 came from inside line 2. Thus we could get line 6 only by instantiating line 2 first. You should always be on the watch for this circumstance. In multiple quantified sentences it is always possible that an existentially quantified sentence will turn up from inside some larger sentence. The existential quantifier will then produce a new name which will force us to go back and instantiate all our universally quantified sentences with the new name. This is why we never check a universally quantified sentence.
Here is another example. We will test the following argument for validity: Everyone loves someone. (V~Y~Y Anyone who loves someone (Vx)[(3y)Lxy 3 Lxxl loves themself. Wx)Lxx Everyone loves themselves. (Vx)(3y)Lxy (Vx)[(3y)Lxy 3 Lxxl -(Vx)Lxx (3x)-Lxx -Laa (3y)Lay Lab (3y)Lay 3 Laa A -(3y)Lay Laa (Vy)-Lay x -Lab X Valid P P - C 3, -v 4, 3 1, v 6, 3, New name 2, v
Getting this tree to come out as short as I did requires some care in choosing at each stage what to do next. For example, 1 got line 8 by instantiating the universally quantified line 2 with just the name 'a'. The rule V requires me to instantiate a universally quantified sentence with all the names on the branch. But it does not tell me when I have to do this. I am free to do my instantiating of a universally quantified sentence in any order I like, and if I can get all branches to close before I have used all available names, so much the better. In the same way, the rule V requires that I return to instantiate lines 1 and 2 with the new name 'b', which arose on line 7. But the rule doesn't tell me when I have to do that. With a combination of luck and skill in deciding what to do first, I can get all branches to close before returning to line 1 or line 2 to instantiate with 'b'. In this circumstance I can get away without using 'b' in these sentences.
However, in any problem, if I instantiate with fewer than all the names and I have failed to close all the branches, then I must return and put - the names not yet used into all universally quantified sentences which appear on open branches.