<<

. 48
( 107 .)



>>

to discover a large number of quanti¬ed sentences that are logical truths.
Consider the following tautology:

(A ’ B) ’ (¬B ’ ¬A)



Section 10.1
260 / The Logic of Quantifiers


If we replace A and B by any quanti¬ed sentences of fol, the result is still
a tautology. For example, we might replace A by ∃y (P(y) ∨ R(y)) and B by
∀x (P(x) § Q(x)). The result is the following rather complex sentence, which
we dub “Phred” (pronounced “Fred”):
(∃y (P(y) ∨ R(y)) ’ ∀x (P(x) § Q(x))) ’
(¬∀x (P(x) § Q(x)) ’ ¬∃y (P(y) ∨ R(y)))
If we just came across Phred, it would be hard to know what it even meant.
But since it is a substitution instance of a tautology, we know that it is in fact
a logical truth. In a similar way, we could make many other substitutions, in
this and other tautologies, to discover many complex logical truths.
There is a small di¬culty with this method of identifying the tautologies
of fol. A given sentence can typically be obtained by substitution from many
di¬erent sentences, some tautologies, some not. Phred, for example, can be
obtained from all of the following (and many others) by means of substitution:
A
A’B
(A ’ B) ’ C
A ’ (B ’ C)
(A ’ B) ’ (C ’ D)
(A ’ B) ’ (¬B ’ C)
(A ’ B) ’ (¬B ’ ¬A)
For instance, we can obtain Phred from the fourth of these by substituting as
follows:
—¦ Replace A by (∃y (P(y) ∨ R(y)) ’ ∀x (P(x) § Q(x)))

—¦ Replace B by ¬∀x (P(x) § Q(x))

—¦ Replace C by ¬∃y (P(y) ∨ R(y)).
But of the seven candidates for substitution, only the last, (A ’ B) ’
(¬B ’ ¬A), is a tautology. If a sentence can be obtained from so many dif-
ferent formulas by substitution, how do we know which one to look at to see
if it is a tautology?
Here is a simple method for solving this problem: The basic idea is that
for purposes of testing whether a sentence is a tautology, we must treat any
quanti¬ed constituent of the sentence as if it is atomic. We don™t look “inside”
quanti¬ed parts of the sentence. But we do pay attention to all of the truth-
functional connectives that are not in the scope of a quanti¬er. We™ll describe



Chapter 10
Tautologies and quantification / 261



a procedure for replacing the quanti¬ed and atomic constituents of a sentence
with letters, A, B, C, . . . , so that the result displays all and only the truth-
functional connectives that aren™t inside quanti¬ed pieces of the sentence.
The result of applying this procedure is called the truth-functional form of truth-functional form
the original sentence.
The procedure has two main steps. The ¬rst annotates the sentence by
labeling the constituents that we must treat as atomic, either because they
are quanti¬ed or because they really are atomic. Applied to Phred, it yields
the following result:

(∃y (P(y) ∨ R(y)) ’ ∀x (P(x) § Q(x)) ) ’
A B
(¬∀x (P(x) § Q(x)) ’ ¬∃y (P(y) ∨ R(y)) )
B A

The second step replaces the underlined constituents with the sentence letters
used to label them:

(A ’ B) ’ (¬B ’ ¬A)

We state the procedure as a little algorithm, a series of step-by-step in-
structions for ¬nding the truth-functional form of an arbitrary sentence S of
fol.
Truth-functional form algorithm: Start at the beginning of sentence S and truth-functional
form algorithm
proceed to the right. When you come to a quanti¬er or an atomic sentence,
begin to underline that portion of the sentence. If you encountered a quanti¬er,
underline the quanti¬er and the entire formula that it is applied to. (This will
either be the atomic w¬ that immediately follows the quanti¬er or, if there are
parentheses, the formula enclosed by the parentheses.) If you encountered an
atomic sentence, just underline the atomic sentence. When you come to the
end of your underline, assign the underlined constituent a sentence letter (A,
B, C, . . . ). If an identical constituent already appears earlier in the sentence,
use the same sentence letter as before; otherwise, assign the ¬rst sentence
letter not yet used as a label. Once you™ve labeled the constituent, continue
from that point. Finally, when you come to the end of the sentence, replace
each underlined constituent with the sentence letter that labels it. The result
is the truth-functional form of S.
Let™s see how we would apply this algorithm to another sentence. See if you
understand each of the following steps, which begin with a quanti¬ed sentence
of fol, and end with that sentence™s truth-functional form. Pay particular
attention to steps 4 and 5. In step 4, do you understand why the label A
is used again? In step 5, do you understand why ∀y Small(y) gets labeled C
rather than B?



Section 10.1
262 / The Logic of Quantifiers


1. ¬(Tet(d) § ∀x Small(x)) ’ (¬Tet(d) ∨ ¬∀y Small(y))

2. ¬(Tet(d) § ∀x Small(x)) ’ (¬Tet(d) ∨ ¬∀y Small(y))
A

3. ¬(Tet(d) § ∀x Small(x) ) ’ (¬Tet(d) ∨ ¬∀y Small(y))
A B

4. ¬(Tet(d) § ∀x Small(x) ) ’ (¬Tet(d) ∨ ¬∀y Small(y))
A B A

5. ¬(Tet(d) § ∀x Small(x) ) ’ (¬Tet(d) ∨ ¬∀y Small(y) )
A B A C

6. ¬(A § B) ’ (¬A ∨ ¬C)

We are now in a position to say exactly which sentences of the quanti¬ed
language are tautologies.
De¬nition A quanti¬ed sentence of fol is said to be a tautology if and only
tautologies of fol
if its truth-functional form is a tautology.
Here is a table displaying six ¬rst-order sentences and their truth-functional
forms. Notice that although four of the sentences in the left column are log-
ically true, only the ¬rst two are tautologies, as shown by their t.f. forms in
the right column.
FO sentence t.f. form
∀x Cube(x) ∨ ¬∀x Cube(x) A ∨ ¬A
(∃y Tet(y) § ∀z Small(z)) ’ ∀z Small(z) (A § B) ’ B
∀x Cube(x) ∨ ∃y Tet(y) A∨B
∀x Cube(x) ’ Cube(a) A’B
∀x (Cube(x) ∨ ¬Cube(x)) A
∀x (Cube(x) ’ Small(x)) ∨ ∃x Dodec(x) A∨B

A useful feature of the truth-functional form algorithm is that it can be
applied to arguments as easily as it can be applied to sentences. All you do is
continue the procedure until you come to the end of the argument, rather than
stopping at the end of the ¬rst sentence. For example, applied to argument 3
on page 258, we ¬rst get the labeled argument:

∃x (Cube(x) ’ Small(x))
A
∃x Cube(x)
B


∃x Small(x)
C

and then the truth-functional form:



Chapter 10
Tautologies and quantification / 263



A
B
C

This shows that argument 3 is not an instance of ’ Elim. But when we apply
the algorithm to a deceptively similar argument:

∃x Cube(x) ’ ∃x Small(x)
A B
∃x Cube(x)
A


∃x Small(x)
B

we see that this argument is indeed an instance of modus ponens:

A’B
A
B

The Taut Con procedure of Fitch uses the truth-functional form algo-
rithm so you can use it to check whether a quanti¬ed sentence is a tautology,
or whether it is a tautological consequence of other sentences.
The truth-functional form algorithm allows us to apply all of the concepts
of propositional logic to sentences and arguments containing quanti¬ers. But
we have also encountered several examples of logical truths that are not tau-
tologies, and logically valid arguments that are not tautologically valid. In the
next section we look at these.




Section 10.1
264 / The Logic of Quantifiers



Remember

1. Use the truth-functional form algorithm to determine the truth-
functional form of a sentence or argument containing quanti¬ers.

2. The truth-functional form of a sentence shows how the sentence is
built up from atomic and quanti¬ed sentences using truth-functional
connectives.

3. A quanti¬ed sentence is a tautology if and only if its truth-functional
form is a tautology.

4. Every tautology is a logical truth, but among quanti¬ed sentences
there are many logical truths that are not tautologies.

5. Similarly, there are many logically valid arguments of fol that are not
tautologically valid.




Exercises


10.1 For each of the following, use the truth-functional form algorithm to annotate the sentence and
 determine its form. Then classify the sentence as (a) a tautology, (b) a logical truth but not
a tautology, or (c) not a logical truth. (If your answer is (a), feel free to use the Taut Con
routine in Fitch to check your answer.)
1. ∀x (x = x)
2. ∃x Cube(x) ’ Cube(a)
3. Cube(a) ’ ∃x Cube(x)
4. ∀x (Cube(x) § Small(x)) ’ ∀x (Small(x) § Cube(x))
5. ∀v (Cube(v) ” Small(v)) ” ¬¬∀v (Cube(v) ” Small(v))
6. ∀x Cube(x) ’ ¬∃x ¬Cube(x)
7. [∀z (Cube(z) ’ Large(z)) § Cube(b)] ’ Large(b)
8. ∃x Cube(x) ’ (∃x Cube(x) ∨ ∃y Dodec(y))
9. (∃x Cube(x) ∨ ∃y Dodec(y)) ’ ∃x Cube(x)
10. [(∀u Cube(u) ’ ∀u Small(u)) § ¬∀u Small(u)] ’ ¬∀u Cube(u)




Chapter 10
Tautologies and quantification / 265



Turn in your answers by ¬lling in a table of the following form:
Annotated sentence Truth-functional form a/b/c
1.
.
.
.

In the following six exercises, use the truth-functional form algorithm to annotate the argument. Then
write out its truth-functional form. Finally, assess whether the argument is (a) tautologically valid, (b)
logically but not tautologically valid, or (c) invalid. Feel free to check your answers with Taut Con.
(Exercises 10.6 and 10.7 are, by the way, particularly relevant to the proof of the Completeness Theorem
for F given in Chapter 19.)

10.2 Cube(a) § Cube(b)
 Small(a) § Large(b)
∃x (Cube(x) § Small(x)) § ∃x (Cube(x) § Large(x))

10.3 ∀x Cube(x) ’ ∃y Small(y)
 ¬∃y Small(y)
∃x ¬Cube(x)

<<

. 48
( 107 .)



>>