<<

. 21
( 107 .)



>>

informal proof.

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

<<

. 21
( 107 .)



>>