Proof: Suppose that the sentence a = b § Cube(a) is true. Then

a = b and Cube(a) are both true. Using the indiscernibility of identi-

cals (Identity Elimination), we know that Cube(b) is true, and hence

that a = b § Cube(b) is true. So the truth of a = b § Cube(a) logically

implies the truth of a = b § Cube(b).

The reverse holds as well. For suppose that a = b § Cube(b) is true.

Then by symmetry of identity, we also know b = a. From this and

Cube(b) we can conclude Cube(a), and hence that a = b § Cube(a)

Section 4.2

108 / The Logic of Boolean Connectives

is true. So the truth of a = b § Cube(b) implies the truth of a = b §

Cube(a).

Thus a = b § Cube(a) is true if and only if a = b § Cube(b) is true.

This proof shows that these two sentences have the same truth values in

any possible circumstance. For if one were true and the other false, this would

contradict the conclusion of one of the two parts of the proof. But consider

what happens when we construct a joint truth table for these sentences. Three

number of rows in

joint table atomic sentences appear in the pair of sentences, so the joint table will look

like this. (Notice that the ordinary truth table for either of the sentences alone

would have only four rows, but that the joint table must have eight. Do you

understand why?)

a=b Cube(a) Cube(b) a = b § Cube(a) a = b § Cube(b)

T T

t t t

T F

t t f

F T

t f t

F F

t f f

F F

f t t

F F

f t f

F F

f f t

F F

f f f

This table shows that the two sentences are not tautologically equivalent,

since it assigns the sentences di¬erent values in the second and third rows.

Look closely at those two rows to see what™s going on. Notice that in both

of these rows, a = b is assigned T while Cube(a) and Cube(b) are assigned

di¬erent truth values. Of course, we know that neither of these rows corre-

sponds to a logically possible circumstance, since if a and b are identical, the

truth values of Cube(a) and Cube(b) must be the same. But the truth table

method doesn™t detect this, since it is sensitive only to the meanings of the

truth-functional connectives.

As we expand our language to include quanti¬ers, we will ¬nd many logical

equivalences that are not tautological equivalences. But this is not to say

there aren™t a lot of important and interesting tautological equivalences. We™ve

already highlighted three in the last chapter: double negation and the two

DeMorgan equivalences. We leave it to you to check that these principles are,

in fact, tautological equivalences. In the next section, we will introduce other

principles and see how they can be used to simplify sentences of fol.

Chapter 4

Logical and tautological equivalence / 109

Remember

Let S and S be a sentences of fol built up from atomic sentences

by means of truth-functional connectives alone. To test for tautological

equivalence, we construct a joint truth table for the two sentences.

1. S and S are tautologically equivalent if and only if every row of the

joint truth table assigns the same values to S and S .

2. If S and S are tautologically equivalent, then they are logically equiv-

alent.

3. Some logically equivalent sentences are not tautologically equivalent.

Exercises

In Exercises 4.12-4.18, use Boole to construct joint truth tables showing that the pairs of sentences are

logically (indeed, tautologically) equivalent. To add a second sentence to your joint truth table, choose

Add Column After from the Table menu. Don™t forget to specify your assessments, and remember,

you should build and ¬ll in your own reference columns.

4.12 (DeMorgan)

‚ ¬(A ∨ B) and ¬A § ¬B

4.13 4.14

(Associativity) (Associativity)

‚ ‚

(A § B) § C and A § (B § C) (A ∨ B) ∨ C and A ∨ (B ∨ C)

4.15 4.16

(Idempotence) (Idempotence)

‚ ‚

A § B § A and A § B A ∨ B ∨ A and A ∨ B

4.17 4.18

(Distribution) (Distribution)

‚ ‚

A § (B ∨ C) and (A § B) ∨ (A § C) A ∨ (B § C) and (A ∨ B) § (A ∨ C)

4.19 (tw-equivalence) Suppose we introduced the notion of tw-equivalence, saying that two sen-

tences of the blocks language are tw-equivalent if and only if they have the same truth value

in every world that can be constructed in Tarski™s World.

1. What is the relationship between tw-equivalence, tautological equivalence and logical

equivalence?

2. Give an example of a pair of sentences that are tw-equivalent but not logically equiv-

alent.

Section 4.2

110 / The Logic of Boolean Connectives

Section 4.3

Logical and tautological consequence

Our main concern in this book is with the logical consequence relation, of

which logical truth and logical equivalence can be thought of as very special

cases: A logical truth is a sentence that is a logical consequence of any set

of premises, and logically equivalent sentences are sentences that are logical

consequences of one another.

As you™ve probably guessed, truth tables allow us to de¬ne a precise notion

of tautological consequence, a strict form of logical consequence, just as they

allowed us to de¬ne tautologies and tautological equivalence, strict forms of

logical truth and logical equivalence.

Let™s look at the simple case of two sentences, P and Q, both built from

atomic sentences by means of truth-functional connectives. Suppose you want

to know whether Q is a consequence of P. Create a joint truth table for P

and Q, just like you would if you were testing for tautological equivalence.

After you ¬ll in the columns for P and Q, scan the columns under the main

connectives for these sentences. In particular, look at every row of the table in

which P is true. If each such row is also one in which Q is true, then Q is said

tautological consequence

to be a tautological consequence of P. The truth table shows that if P is true,

then Q must be true as well, and that this holds simply due to the meanings

of the truth-functional connectives.

Just as tautologies are logically necessary, so too any tautological conse-

quence Q of a sentence P must also be a logical consequence of P. We can

see this by proving that if Q is not a logical consequence of P, then it can™t

possibly pass our truth table test for tautological consequence.

Proof: Suppose Q is not a logical consequence of P. Then by our def-

inition of logical consequence, there must be a possible circumstance

in which P is true but Q is false. This circumstance will determine

truth values for the atomic sentences in P and Q, and these values

will correspond to a row in the joint truth table for P and Q, since

all possible assignments of truth values to the atomic sentences are

represented in the truth table. Further, since P and Q are built up

from the atomic sentences by truth-functional connectives, and since

the former is true in the original circumstance and the latter false,

P will be assigned T in this row and Q will be assigned F. Hence, Q

is not a tautological consequence of P.

Let™s look at a very simple example. Suppose we wanted to check to see

whether A ∨ B is a consequence of A § B. The joint truth table for these sen-

Chapter 4

Logical and tautological consequence / 111

tences looks like this.

A B A§B A∨B

T T

t t

F T

t f

F T

f t

F F

f f

When you compare the columns under these two sentences, you see that the

sentences are most de¬nitely not tautologically equivalent. No surprise. But

we are interested in whether A § B logically implies A ∨ B, and so the only

rows we care about are those in which the former sentence is true. A § B is only

true in the ¬rst row, and A ∨ B is also true in that row. So this table shows

that A ∨ B is a tautological consequence (and hence a logical consequence) of

A § B.

Notice that our table also shows that A § B is not a tautological conse-

quence of A ∨ B, since there are rows in which the latter is true and the former

false. Does this show that A § B is not a logical consequence of A ∨ B? Well,

we have to be careful. A § B is not in general a logical consequence of A ∨ B,

but it might be in certain cases, depending on the sentences A and B. We™ll

ask you to come up with an example in the exercises.

Not every logical consequence of a sentence is a tautological consequence

of that sentence. For example, the sentence a = c is a logical consequence of logical vs. tautological

consequence

the sentence (a = b § b = c), but it is not a tautological consequence of it.

Think about the row that assigns T to the atomic sentences a = b and b = c,

but F to the sentence a = c. Clearly this row, which prevents a = c from being

a tautological consequence of (a = b § b = c), does not respect the meanings

of the atomic sentences out of which the sentences are built. It does not

correspond to a genuinely possible circumstance, but the truth table method

does not detect this.

The truth table method of checking tautological consequence is not re-

stricted to just one premise. You can apply it to arguments with any number

of premises P1 , . . . , Pn and conclusion Q. To do so, you have to construct a

joint truth table for all of the sentences P1 , . . . , Pn and Q. Once you™ve done

this, you need to check every row in which the premises all come out true to

see whether the conclusion comes out true as well. If so, the conclusion is a

tautological consequence of the premises.

Let™s try this out on a couple of simple examples. First, suppose we want

to check to see whether B is a consequence of the two premises A ∨ B and ¬A.

The joint truth table for these three sentences comes out like this. (Notice

that since one of our target sentences, the conclusion B, is atomic, we have

simply repeated the reference column when this sentence appears again on

Section 4.3

112 / The Logic of Boolean Connectives

the right.)

A B A∨B ¬A B

T F T

t t

T F F

t f

T T T

f t

F T F

f f

Scanning the columns under our two premises, A ∨ B and ¬A, we see that

there is only one row where both premises come out true, namely the third.

And in the third row, the conclusion B also comes out true. So B is indeed a

tautological (and hence logical) consequence of these premises.

In both of the examples we™ve looked at so far, there has been only one

row in which the premises all came out true. This makes the arguments easy

to check for validity, but it™s not at all something you can count on. For

example, suppose we used the truth table method to check whether A ∨ C

is a consequence of A ∨ ¬B and B ∨ C. The joint truth table for these three

sentences looks like this.

A B C A ∨ ¬B B∨C A∨C

Tf T T

t t t

Tf T T

t t f

Tt T T

t f t

Tt F T

t f f

Ff T T

f t t

Ff T F

f t f

Tt T T

f f t

Tt F F

f f f

Here, there are four rows in which the premises, A ∨ ¬B and B ∨ C, are

both true: the ¬rst, second, third, and seventh. But in each of these rows the