1. (a) is a wff (and a sentence); its outer parentheses have been omitted, which is permissible. (b) is also a wff; the variable y in the second conjunct is free, so it is not a sentence, however. (c) might look strange, because the quantifier containing x does not bind any other occurrences of the x variable. This makes it a “vacuous” quantifier, but that does not disqualify it from being a wff. (d) is not a wff, since ∃b is not a quantifier: a quantifier must contain a variable, and b is a constant, not a variable.

2. (a) is a sentence, since all of its variables are bound. (b) is not a sentence, since its second occurrence of x is free; don’t be fooled by the x quantifier at the front, for its scope stops after Cube(x). Watch out for those parentheses as scope indicators! (c) is a sentence, since it’s a wff and contains no free variables. Don’t think that b is free variable; it’s a constant.

3. You should apply the truth-functional form algorithm (p. 261) before answering this kind of question. The negation sign at the beginning applies only to the antecedent ∃x Tet(x). That alone tells you that the form begins ¬A →. The scope of the universal quantifier ∀y extends all the way to the end of the sentence. That means that the consequent of the truth-functional form has no sentences embedded within it. So the form is ¬A → B, so (c) is the right answer.

4. In order to have A ∧ (B ∨ ¬A) as its truth-functional form, a sentence must be a disjunction whose left disjunct has no truth-functional complexity. The right disjunct must be a conjunction, whose left conjunct has no truth-functional complexity, and whose right conjunct is the negation of the left disjunct of the entire sentence. In answering this question, you should apply the truth-functional form algorithm to each of the possible answers, and see whether you end up with the form you were given in the question. (a) is incorrect; if you chose it, you were probably fooled by apparent complexity of ∀y (Small(y) ∧ ¬Cube(y)). But all the truth-functional complexity here is at the level of wffs that are not sentences. From the point of view of Boole, this sentences counts as if it were atomic. (c) is also incorrect; if you chose it, you must have thought that ∀y Small(y) could not be substituted for B. But ∀y Small(y) is not truth-functionally complex, so it has the truth-functional form B. (d) is also incorrect. The negation signs in front of Tet(x) are operating at the level of wffs that are not sentences, so they do not enter into the truth-functional form of the sentence. Once you block them out, it should be obvious that (d) is of the form in question. The correct answer is (b). ¬Tet(d) is not of the form A; it is of the form ¬A. Similarly, Tet(d) is not of the form ¬A; anything of that form must begin with a negation sign. Remember, you can’t ignore the negations signs, or think that they “cancel out.” Truth-functional form is a purely syntactical matter.

5. (a) is a vacuously true universal generalization Since nothing is both a tetrahedron and a cube, the wff in the antecedent of (a) comes out false of everything. So the entire conditional wff in (a) is (vacuously) true of everything, which makes (a) vacuously true. (b) is also vacuously true, but it is not a universal generalization; it begins with an existential quantifier. (c) is not even true. In fact, it is false in every Tarski world. If you thought (c) was vacuously true, it was probably because you know that in a Tarski world, no two blocks can be in the same column and same row simultaneously, because that would put them in the same square, which is impossible. But that does not make the antecedent wff in (c) false of everything; it can be satisfied, so long as the same value is taken for both x and y. For all such cases, of course, Larger(x, y) will always come out false (since nothing is larger than itself).

6. If a deductive system for FOL is sound, that means that it is not possible to use it to deduce a conclusion that is not an FO-consequence of its premises. Hence if R is not sound, you can use it to deduce such a conclusion.

7. If a deductive system for FOL is complete, that means that every FO-valid sentence can be proved in that system. Hence if R is not complete, that means that there is some FO-valid sentence that cannot be proved using R.

8. This sentence falls into area 2; it is FO-valid, but not a tautology. It is not a tautology because its truth-functional form is A → ¬B. It is clearly a logical truth, however; it says that if there are non-cubes, then not everything is a cube. But it is also FO-valid, and you can see that it is by applying some equivalence principles from Chapter 10: DeMorgan’s Laws for Quantifiers and Replacing Bound Variables. Applying these principles to the consequent will produce a sentence identical to the antecedent.

9. This sentence falls into area 1; it is a tautology. Its truth-functional form is A → (A ∨ B).

10. This example is tricky. The sentence might seem to say that there are two objects that do not adjoin one another, and this would seem to be falsifiable. Yet if you put this sentence into a Tarski sentence file and evaluate it in a world containing exactly two blocks with those blocks adjoining one another, you will see that the sentence still comes out true. (Try it!) If this surprises you, try playing the game with Tarski, and commit to false. You will lose, and notice why: Tarski will pick the same block to be the value of both variables. Since no block adjoins itself, there will always be an x and a y such that x and y do not adjoin; just make x and y the same block. So (10) does not belong in area 5, since it is true in every Tarski world. But it does not belong in area 4, since it is not just in all Tarski worlds that it comes out true. (10) is a logical consequence (indeed, an FO-consequence) of the claim that nothing adjoins itself. But it is a logical truth that nothing adjoins itself. So we must push (10) closer to the center; it belongs at least in area 3. Does it belong further inside, say in area 2? No. For the claim it depends on (that nothing adjoins itself) is only a logical truth, not an FO validity. To see that, try the replacement method. For example, replace Adjoins(x, y) with SameRow(x, y) and you will be able to come up with a counterexample. So (10) belongs in area 3; it is a logical truth, but not FO-valid.

11. Once you get this sentence translated, it should be pretty easy to classify. What it says is that if every cube is large, then no cube adjoins any block. This cannot be falsified in a Tarski world, since no large block is capable of adjoining any other block. But outside of Tarski worlds, this sentence is falsifiable. It is not part of the meanings of adjoins and large that a large object cannot adjoin another object. (Imagine yourself sitting next to Shaquille O’Neal!) So (11) belongs in area 4; it is a TW necessity, but not a logical truth.

12. This sentence is certainly not a tautology, since it is not a truth-functional compound. It is an existential generalization, so it cannot be a tautology. It might not appear to be logically true at all, so you might guess that it belongs in area 5, but this would be a mistake. For (12) is FO-valid, and belongs in area 2. In fact, it is an instance of something we proved in 13.51 (“The Drinking Theorem”). That is why it does not belong in area 3 (logical truth, but not FO-valid). The necessity of (12) does not depend at all on the meaning of the predicate Cube. It depends solely on the meanings of the quantifiers and connectives. Notice that (12) is an existentially generalized conditional, and we know that such sentences seldom come out false. Some of them (like this one) never do.

13. (a) is a tautology; its truth-functional form is (A ∧ B) → B. (b) is the correct answer; its truth-functional form is (A ∧ B) → C, so it is not a tautology. But it is FO-valid; the consequent, Tet(b), is an FO-consequence of the second conjunct of the antecedent, ∀y Tet(y), and therefore is an FO-consequence of the entire antecedent. And when C is an FO-consequence of B, the sentence B → C is an FO-validity. (c) is not a tautology, but it is not FO-valid, either. (Check it out in Tarski’s world.) It must be carefully distinguished from (d), which is a tautology. (Look carefully at the placement of the parentheses.) (d) says “If everything is a tetrahedron, then everything is a tetrahedron,” a tautology. (c) says “If anything is a tetrahedron, then everything is a tetrahedron,” which comes out false in any world containing at least one tetrahedron and at least one non-tetrahedron.

14. (a) is a logical truth, but it is also FO-valid, since its truth is determined by the meanings of the connective → and the identity sign (=). (b) is not FO-valid, but it is not a logical truth, either. What (b) says, in effect, that there cannot be a pair of objects one of which is a tetrahedron and the other not a tetrahedron. This is clearly false in any world that contains, say, a tetrahedron and a cube. (b) must be carefully distinguished from (c), which is FO-valid. What (c) says is that if everything is a tetrahedron, then everything is a tetrahedron. Interestingly, (c) is not a tautology (unlike 13(d)), since the antecedent and consequent are different sentences (one contains x in the quantifier, the other contains y). Replace the consequent of (c) with ∀x Tet(x) and you get 13(d), which is a tautology. (d) is the correct answer to question 14. It is a logical truth that objects are the same size if one of them is neither larger nor smaller than the other, but this depends on the meanings of the predicates Larger, Smaller, and SameSize, and not just on the connectives and quantifiers. (e) says that if objects adjoin one another, then neither of them is large. This is TW-necessary (true in every Tarski world) but not a logical truth. In other (non-Tarski) worlds, it is possible for a large object to adjoin another object.

15. (a) is a logical truth; if something is between two objects, it cannot be identical to either of them. (b) is also a logical truth; if something is a cube, it is neither a tetrahedron nor a dodecahedron. (c) is the converse of (b), and it says that if something is neither a tetrahedron nor a dodecahedron, it is a cube. This is TW-necessary, but not a logical truth. In non-Tarski worlds, there are other shapes than the three in Tarski worlds. (d) says that only large things are larger than objects that differ from one another in size. This is true in every Tarski world, for of the two different size blocks that are both smaller than some other block, one must be medium, and to be larger than a medium block requires being large. But it is not a logical truth, since outside of Tarski worlds there are more gradations of size, and so one can have 3 objects that differ in size but all of which are small. So the correct answer is (e); both (c) and (d) are TW-necessary (true in every Tarski world) but not logically true.

16. (a) is wrong, since Larger is transitive (if x is larger than y and y is larger than z, then x is larger than z). (c) is wrong for the same reason: SameCol is transitive. (d) is also wrong, since the identity relation is transitive. The correct answer is (b), since it is not true that if x adjoins y and y adjoins z, then x adjoins z. To see this clearly, just let x = z. In that case, x cannot adjoin z, since nothing can adjoin itself.

17. SameRow is symmetric, since if x is in the same row as y, then y is in the same row as x. Similarly, Adjoins is symmetic, as is the relation that is the product of these two: being both in the same row as and adjoining. And everyone should remember the symmetry law about identity from algebra: if x = y, then y = x. So these are all symmetric relations, and the correct answer is (d).

18. (a) is wrong, since nothing is larger than itself. (c) and (d) are also wrong, since nothing adjoins itself and nothing is in front of itself. (e) is also wrong, since nothing is either larger or smaller than itself. The correct answer is (b): everything is in the same row as itself.

19. (b) is wrong, for although Adjoins is irreflexive, it is not asymmetric. (It is, in fact, symmetric, which is not the same thing as being not asymmetric.) (c) is also wrong, for although non-identity is irreflexive (nothing is distinct from itself), it is symmetric: if x is distinct from y, then y is distinct from x. (d) is wrong for different reasons. First, this relation is reflexive: everything is either larger than or the same size as itself. (This follows from the fact that everything is the same size as itself.) Second, this relation is neither symmetric nor asymmetric. It is not symmetric: let x be large cube and y a medium cube. Then x is either larger than or the same size as y (since it is larger), but y is not either larger or the same size as x. Nor is it asymmetric: let x and y both be large cubes. Then x is either larger than or the same size as y (since it is the same size), but it is not the case that y is neither larger nor the same size as x (since it is the same size). The correct answer is (a). Larger is irreflexive (since nothing is larger than itself), and also asymmetric, since if x is larger than y, it follows that y is not larger than x.

20. ∀x (Cube(x) → ¬Small(x)) translates into English as No cubes are small. This is equivalent to Nothing small is a cube, so (a) is equivalent to (20). So is (b), which says There does not exist a small cube. (c) is wrong; it says If everything is a cube, then nothing is small. (d) is also wrong; it says If everything is a cube, then not everything is small. So the correct answer is (e); both (a) and (b) are equivalent to the sentence in question 20.

21. All three sentences are equivalent to ¬∀x∃y∃z (Cube(x) → Between(x, y, z)). You can see this as you proceed through the sentences. To get from 21 to (a), just replace ¬∀x with ∃x ¬. To get from (a) to (b), just replace ¬∃y∃z with ∀y∀z ¬. To get from (b) to (c), just replace ¬(Cube(x) → Between(x, y, z)) with (Cube(x) ∧ ¬Between(x, y, z)). You can confirm the equivalence between (17) and (c) by translating each of them naturally into English. (17) goes naturally into Not every cube is between a pair of blocks. (c) says There is a cube that is not between a pair of blocks. These two certainly sound equivalent, don’t they? (It is a bit harder to come up with a natural translation of (b) into English that mirrors the truth-functional structure of the embedded wff; it’s probably best not to try to do this.)

22. (a) is not an equivalent pair; imagine a world with one small cube and one large tetrahedron. In that world, everything is either a cube or a large block, but it is not true that either everything is a cube or everything is large. It is false that everything is a cube, and false that everything is large, and so the disjunction of these two universal generalizations is false. (b) is also not an equivalent pair. Here, imagine a world with a large cube and a small tetrahedron. The sentence on the left is false (no cube is small) but the sentence on the right is true (there is a cube and there is a tetrahedron. Nor is (c) an equivalent pair. Imagine a world with a small tetrahedron and a large cube. Then the sentence on the left is false, since its antecedent is true (something is small) and its consequent is false (there are no dodecahedra). But the sentence on the right is true; the witness, in this case, is the large cube, which satisfies if x is small, then x is a dodecahedron. Finally, (d) is not an equivalent pair. The same world that was a counterexample to (c) works here, as well. It is not true that every small block is a dodecahedron, because of the small tetrahedron. So the sentence on the right is false. But the one on the left is true, since it is a conditional with a false antecedent (not everything is small). The correct answer, therefore, is (e); none of these is an equivalent pair of sentences.

23. (a) is an equivalent pair. Since there is no free occurrence of x in the conjunct Tet(b), we may move the internal quantifier in ∃x Cube(x) to the outside and give it the entire conjunction as its scope. The same is true for (d). Since there is no free occurrence of y in the disjunct Tet(b), we may move the internal quantifier in ∀y Cube(y) to the outside and give it the entire disjunction as its scope. (c) may look like the culprit, but it is not. Since there is no free occurrence of x in the consequent Dodec(c), we may move the internal quantifier ∃x from the antecedent ∃x Tet(x) to the outside, giving it the entire conditional as its scope, provided that we change the quantifier from existential to universal. The correct answer is (b). A counterexample to this equivalence claim would be any world containing both a tetrahedron and a non-tetrahedron in which c is not a dodecahedron. For example, suppose c is a tetrahedron and there is also a cube. Then the sentence on the left is false, since it has a true antecedent (there is a tetrahedron) and a false consequent (c is not a dodecahedron). But the sentence on the right it true; the witness is the cube, which satisfies the wff if x is a tetrahedron, then c is a dodecahedron.

24. (a) is FO-valid, and so is (b). When a string of quantifiers is of the same quantity (all universal or all existential) the order in which they occur does not affect the truth-value of the sentence. So the antecedent and consequent of (a) are actually equivalent to one another, as are those of (b). (d) is FO-valid because the consequent is a logical consequence of the antecedent (although the two are not equivalent). (c) is the correct answer. The antecedent says Everything is in the same column as something which is actually a TW-necessity, since everything is in the same column as itself. But the consequent says There is something that is in the same column as everything, and this comes out false in any world in which there are two or more objects not in the same column. In general, ∃y∀x implies ∀x∃y, but ∀x∃y does not imply ∃y∀x.

25. (a) is incorrect. It says Every tetrahedron adjoins a cube, which allows for the possibility that blocks of other shapes also adjoin cubes; and that is ruled out by our sentence. (c) is also incorrect. It says All and only tetrahedra adjoin cubes, which is too strong. Our sentence does not say that all tetrahedra adjoin cubes, but that nothing other than a tetrahedron adjoins cubes. (d) says Whatever adjoins every cube is a tetrahedron, which leaves open the possibility that some dodecahedron, say, adjoins a cube, but does not adjoin every cube. But that possibility is denied by our sentence. The correct answer is (b). One way of putting (b) into English is Whatever adjoins a cube is a tetrahedron. You can see how the only gets into the translation if you remember how to translate → as only if. It might go like this: A block adjoins a cube only if that block is a tetrahedron. From there it is a short step to Only tetrahedra adjoin cubes, the sentence we started out with.

26. Nothing is a dodecahedron unless it is small says, in effect, that there does not exist a non-small dodecahedron. This immediately confirms (c) as a correct translation, and rules it out as an answer to our question. Another way of putting this is to say All dodecahedra are small, which is what (a) says; so that is also a correct translation. (b) and (e) are obviously both equivalent to (a), so they are correct translations. The correct answer is (d). What (d) says is Nothing is either a dodecahedron or small. This is clearly a mistaken translation, for it follows from (d) that there are no dodecahedra and there is nothing small, which says something quite different from what our English sentence says. So (d) is the one incorrect translation here.

27. What (a) says is that for every person, there is a person he or she does not admire. But that leaves open the possibility that some people do admire some people, so (a) cannot be correct. (b) says that there is no person such that there is some person he or she does not admire; in other words, it says that everyone admires everyone! This is surely as incorrect as you could be. (c) says that it is true of each person that he or she admires no one, so (c) is a correct translation. But so is (d), which says that no matter what pair of people (not necessarily distinct) that you pick, the first does not admire the second. The correct answer is therefore (e); both (c) and (d) are correct translations.

28. Our FOL sentence contains no existential quantifiers, so it does not commit itself to the existence of any tetrahedra. That rules out (a), (c), and (d). This is clearly an at most sentence. But is it at most two or at most three? The rule of thumb here is that there must be one more variable in the FOL sentence than the number mentioned in the English sentence: to say at most n you need n+1 variables. That rules out (e). So the correct answer is (b).

29. (a) cannot be right, because (a) would be true even if there were no cubes at all. (If there are no cubes, there are no counterexamples to the claim All cubes are …. (d) is objectionable for the same reason. (b) is a correct translation; it says that some cube, x, is larger than everything that is both a cube and distinct from x. How many such x could there be? There could not be two cubes each of which is larger than all cubes other than itself, for each of them would have to be larger than the other, which is impossible. So there must be one largest cube, which is what (c) says. Hence (b) and (c) are both correct translations, so the answer to the question is (e).

Return to Final Exam Theory Quiz.

Return to PHIL 120A Home Page

Copyright © 2006, S. Marc Cohen