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)