Introduction to Logic

Answer Page

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