In this section we are going to see how to apply the truth tree method to test predicate logic sentences for some familiar properties. This will be little more than a review of what you learned for sentence logic. The ideas are all the same. All we have to do is to switch to talking about interpretations where before we talked about lines of a truth table.
Let's start with logical contradiction. In sentence logic we say that a sentence is a contradiction if and only if it is false in all possible cases, where by "possible cases" we mean assignments of truth values to sentence letters-in other words, lines of the sentence's truth table. Recharaaerizing the idea of a possible case as an interpretation, we have
A dosed predicate logic sentence is a CmrtradicCion if and only if it is false in all of its interpretations.
The truth tree test for being a contradiction also carries over directly from sentence logic. The truth tree method is guaranteed to lind an interpretation in which the initial sentence or sentences on the tree 'are true, if there is such an interpretation. Consequently
To test a sentence, X, for being a contradiction make X the first he of a truth tree. If there is an interpretation which makes X true, the tree method will find such an interpretation, which will provide a counterexample to X being a contradiction. If all branches close, there is no interpretation in which X is true. In this case, X is false in all of its interpretations; that is, X is a contradiction.
Here is a very simple example. We test '(3x)(Bx & -Bx)' to see whether it is a contradiction:
J1 (3x)(Bx & -Bx) S (The sentence being tested) 42 (Ba & -Ba) 1, 3, New name 3 Ba 2, 4 - Ba 2, X
The sentence is a contradiction.
The idea of a logical truth carries over from sentence logic in exactly the same way. In sentence logic a sentence is a logical truth if it is true for all possible cases, understood as all truth value assignments. Now, taking possible cases to be interpretations, we say
A closed predicate logic sentence is a Logccal Truth if and only if it is true in all of its interpretations.
To determine whether a sentence is a logical truth, we must, just as we do in sentence logic, look for a counterexample-that is, a case in which the sentence is false. Consequently To test a predicate logic sentence, X, for being a logical truth, make -X the first line of a tree. If there is an interpretation which makes -X true, the tree method will find such an interpretation. In such an interpretation, X is false, so that such an interpretation provides a counterexample to X being a logical truth. If all branches close, there is no interpretation in which -X is true, and so no interpretation in which X is false. In this event, X is true in all of its interpretations; that is, X is a logical truth. Again, let's illustrate with a simple example: Test '(3x)Bx v (3x)-Bx' to see if it is a logical truth: -[(gx)~x v (~x)-Bx] -S (The negation of the sentence being tested) J 2 -(3x)Bx 1, -v 43 -(ax)-Bx 1, -v a4 (Vx)-Bx 2, -3 a5 Wx)--Bx 3, -3 6 - Ba 4, v 7 --Ba 5, v X The sentence is a logical truth. The tree shows that there are no interpretations in which line 1 is true. Consequently, there are no interpretations in which the original sentence (the one which we negated to get line 1) is false. So this original sentence is a logical truth. Notice that I had to introduce a name when I worked on line 4. Line 4 is a universally quantified sentence, and having no name at that point I h'ad to introduce one to start my try at an interpretation. Line 5 is another universally quantified sentence, and when I worked on it, I already had the name 'a'. So I instantiated line 5'with 'a'. At no place on this tree did the new name requirement of the rule 3 apply. This is because at no place on the tree is the entire sentence an existentially quantified sentence. In particular, the sentences of lines 2 and 3 are negated existentially quantified sentences, not existentially quantified sentences, so the rule 3 and the new name requirement do not apply to them. It's time to talk about logical equivalence. We already discussed this subject in section 3-4, which you may want to review at this point. For completeness, let's restate the definition: Two closed predicate logic sentences are Logically Equivalent if and only if in each of their interpretations the two sentences are either both true or both false. Do you remember how we tested for logical equivalence of sentence logic sentences? Once again, everything works the same way in predicate logic. Two closed predicate logic sentences have the same truth value in one of their interpretations if and only if their biconditional is true in the interpretation. So the two sentences will agree in truth value in all of their interpretations if and only if their biconditional is true in all of their interpretations-that is, if and only if their biconditional is a logical truth. So to test for logical equivalence we just test for the logical truth of the biconditional: To determine whether the closed predicate logic sentences, X and Y, are logically equivalent, test their biconditional, X=Y, for logical truth. That is, make -(X=Y) the first line of a tree. If all branches close, -(X=Y) is a logical truth, so that X and Y are logically equivalent. If there is an open branch, X and Y are not logically equivalent. An open branch will be an interpretation in which one of the two sentences is true and the other false, so that such an open branch provides a counterexample to X and Y being logically equivalent.
Here is another way in which you can test two sentences, X and Y, for logical equivalence. Consider the argument "X. Therefore Y." with X as premise and Y as conclusion. If this argument is invalid, there is a counterexample, an interpretation in which X is true and Y is false. Thus if "X. Therefore Y." is invalid, X and Y are not logically equivalent, and a counterexample to the argument is also a counterexample which shows X and Y not to be logically equivalent. The same goes for the argument "Y. Therefore X.", this time taking the second sentence, Y, as premise and the first sentence, X, as conclusion. If this argument is invalid there is a counterexample, that is, an interpretation in which Y is true and X is false, and hence again a counterexample to X and Y being logically equivalent.
Now, what happens if both the arguments "X. Therefore Y." and "Y. Therefore X." are valid? In this event every interpretation in which X is ' true is an interpretation in which Y is true (the validity of "X. Therefore Y."), and every interpretation in which Y is true is an interpretation in which X is true (the validity of "Y. Therefore X."). But that is just another way of saying that in each interpretation X and Y have the same truth value. If whenever X is true Y is true and whenever Y is true X is true, we can't have a situation (an interpretation) in which one is true and the other is false. Thus, if "X. Therefore Y." and "Y. Therefore X." are both valid, X and Y are logically equivalent:
To determine whether the closed predicate logic sentences, X and Y, are logically equivalent, test the two arguments "X. Therefore Y." and "Y. Therefore X." for validity. If either argument is invalid, X and Y are not logically equivalent. A counterexample to either argument is a counterexample to the logical equivalence of X and Y. If both arguments are valid, X and Y are logically equivalent.
In fact, the two tests for logical equivalence really come to the same thing. To see this, suppose we start out to determine whether X and Y are logically equivalent by using the first test. We begin a tree with -(X=Y) and apply the rule -=: A 2 X-X I,-= 3 -Y Y I,-=
Now notice that the left-hand branch, with X followed by -Y, is just the way we start a tree which tests the validity of the argument "X. Therefore Y.". And, except for the order of -X and Y, the right-hand branch looks just like the tree which we would use to test the validity of the argument "Y. Therefore X.". So far as the right-hand branch goes, this order makes no difference. Because we are free to work on the lines in any order, what follows on the right-hand branch is going to look the same whether we start it with -X followed by Y or Y follow by -X.
In sum, lines 2 and 3 in our tree are just the beginning of trees which test the validity of "X. Therefore Y." and "Y. Therefore X.". Thus the completed tree will contain the trees which test the arguments "X. Therefore Y." and "Y. Therefore X.". And, conversely, if we do the two trees which test the arguments "X. Therefore Y." and "Y. Therefore X." we will have done all the work which appears in the tree we started above, the tree which tests X=Y for logical truth. So the two ways of determining whether X and Y are logically equivalent really involve the same work.
If you did all of exercise 7-4 you have already tested 11 pairs of sentences for logical equivalence! In each of these pairs you tested two arguments, of the form "X. Therefore Y." and "Y. Therefore X.". Using our new test for logical equivalence, you can use your work to determine in each of these problems whether or not the pair of sentences is logically equivalent.
Truth trees also apply to test sets of sentences for consistency. Recall from section 9-2 in volume I that a set of sentence logic sentences is consistent if and only if there is at least one case which makes all of the sentences in the set true. Interpreting cases as interpretations, we have
A Model of a set of one or more predicate logic sentences is an interpretation in which all of the sentences in the set are true.
A set of one or more predicate logic sentences is consistent just in case it has at least one model, that is, an interpretation in which all of the sentences in the set are true.
To test a finite set of predicate logic sentences for consistency, make the sentence or sentences in the set the initial sentences of a tree. If the tree closes, there is no interpretation which makes all of the sentences true together (no model) and the set is inconsistent. An open branch gives a model and shows the set to be consistent.
Every truth tree test of an argument is also a test of the consistency of the argument's premises with the negation of the argument's conclusion. An argument is valid if and only if its premises are inconsistent with the negation of the argument's conclusion. In other words, an argument is invalid if and only if its premises are consistent with the negation of its conclusion. Thus one can view the truth tree test for argument validity as a special application of the truth tree test for consistency of sets of sentences. (If you have any trouble understanding this paragraph, review exercise 9-7 in volume I. Everything in that exercise applies to predicate logic in exactly the same way as it does to sentence logic.)
8-1. Test the following sentences to determine which are logical truths, which are contradictions, and which are neither. Show your work and state your conclusion about the sentence. Whenever you find a counterexample to a sentence being a logical truth or a contradiction, give the counterexample and state explicitly what it is a counterexample to. (Vx)Dx v (3x)-Dx b)(Vx)Kx & (3x)-Kx (Vx)Nx v (Vx)-Nx d)(Vx)Jx & (Vx)-Jx (3x)Bx v (3x)-Bx f )(3x)Px & (3x)-Px [(Vx)Gx v (Vx)Hx] & -(Vx)(Gx v Hx) (Vx)(Kx v Jx) 3 [(3x)-Kx 3 (3x)Jxl [(Vx)Mx 3 (Vx)-Nx] & (3x)(-Mx & Nx) [(3x)Hx 3 (Vx)(Ox 3 Nx)] 3 [(3x)(Hx & Ox) > (Vx)Nx] (3x)[-Sx & (Gx v Kx)] v [(Vx)Gx 3 (Vx)(Sx v Kx)] [(Vx)Fx v (Vx)Gx] = [(3x)-Fx & -(Vx)Gx]
8-2. Use the truth tree method to test the following sets of sentences for consistency. In each case, state your conclusion about the set of sentences, and if the set of sentences is consistent, give a model. a) (3x)Px. (3x)-Px b) (Vx)Px, (Vx)-Px c) (Vx)Px, (3x)-Px d) (Vx)-Fx, (Vx)Sx, (3x)[(-Fx 3 Sx) 3 Fx] e) (3x)Gx & (3x)Qx, -(3x)(Gx & Qx) f) (Vx)(Gx v Qx), -[(Vx)Gx v (Vx)Qx] g) (3x)Ux v Dx), (Vx)Ux 3 -Hx), (Vx)(Dx 3 Hx), (Vx)Ux = (Dx v Hx)]
8-3. Explain the connections among consistency, logical truth, and logical contradiction.
8-4. By examining your results from exercise 7-4(a) through (k), determine which pairs of sentences are logically equivalent and which are not. This is more than an exercise in mechanically applying the test for logical equivalence. For each pair of sentences, see if you can understand intuitively why the pair is or is not logically equivalent. See if you can spot any regularities. 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: -(3x)ILxa 3 (Vy)Lyal Wx)-[Lxa 3 (Vy)Lyal -[Laa 3 (Vy)Lya] Laa -(Vy)Lya (3~)-Lya -Lba -[Lba 3 (Vy)Lya] Lba -(Vy)Lya X -S 1, -3 2, v 3, -3 3, -3 5, -v 6, 3, New name 2, v 8, -3 8, -3