possibility.

Section 4.1

102 / The Logic of Boolean Connectives

Figure 4.1: The relation between tautologies, logical truths, and tw-

necessities.

You should be able to think of any number of sentences that are not

tautological, but which nonetheless seem logically necessary. For example, the

sentence

¬(Larger(a, b) § Larger(b, a))

cannot possibly be false, yet a truth table for the sentence will not show this.

The sentence will be false in the row of the truth table that assigns T to both

Larger(a, b) and Larger(b, a).

We now have two methods for exploring the notions of logical possibility

and necessity, at least for the blocks language. First, there are the blocks

worlds that can be constructed using Tarski™s World. If a sentence is true

in some such world, we have called it tw-possible. Similarly, if a sentence is

true in all worlds that we can construct using Tarski™s World, we can call it

tw-necessary. The second method is that of truth tables. If a sentence comes

out true in every row of its truth table, we could call it tt-necessary or, more

traditionally, tautological. If a sentence is true in at least one row of its truth

table, we will call it tt-possible.

tt-possible

None of these concepts correspond exactly to the vague notions of logi-

Chapter 4

Tautologies and logical truth / 103

cal possibility and necessity. But there are clear and important relationships

between the notions. On the necessity side, we know that all tautologies are

logically necessary, and that all logical necessities are tw-necessary. These

relationships are depicted in the “Euler circle” diagram in Figure 4.1, where

we have represented the set of logical necessities as the interior of a circle

with a fuzzy boundary. The set of tautologies is represented by a precise cir-

cle contained inside the fuzzy circle, and the set of Tarski™s World necessities

is represented by a precise circle containing both these circles.

There is, in fact, another method for showing that a sentence is a logical

truth, one that uses the technique of proofs. If you can prove a sentence using proof and logical truth

no premises whatsoever, then the sentence is logically necessary. In the fol-

lowing chapters, we will give you some more methods for giving proofs. Using

these, you will be able to prove that sentences are logically necessary without

constructing their truth tables. When we add quanti¬ers to our language, the

gap between tautologies and logical truths will become very apparent, making

the truth table method less useful. By contrast, the methods of proof that we

discuss later will extend naturally to sentences containing quanti¬ers.

Remember

Let S be a sentence of fol built up from atomic sentences by means of

truth-functional connectives alone. A truth table for S shows how the

truth of S depends on the truth of its atomic parts.

1. S is a tautology if and only if every row of the truth table assigns true

to S.

2. If S is a tautology, then S is a logical truth (that is, is logically neces-

sary).

3. Some logical truths are not tautologies.

4. S is tt-possible if and only if at least one row of the truth table assigns

true to S.

Section 4.1

104 / The Logic of Boolean Connectives

Exercises

In this chapter, you will often be using Boole to construct truth tables. Although Boole has the capability

of building and ¬lling in reference columns for you, do not use this feature. To understand truth tables,

you need to be able to do this yourself. In later chapters, we will let you use the feature, once you™ve

learned how to do it yourself. The Grade Grinder will, by the way, be able to tell if Boole constructed

the reference columns.

4.1 If you skipped the You try it section, go back and do it now. Submit the ¬le Table Tautology 1.

‚

4.2 Assume that A, B, and C are atomic sentences. Use Boole to construct truth tables for each of

‚ the following sentences and, based on your truth tables, say which are tautologies. Name your

tables Table 4.2.x, where x is the number of the sentence.

1. (A § B) ∨ (¬A ∨ ¬B)

2. (A § B) ∨ (A § ¬B)

3. ¬(A § B) ∨ C

4. (A ∨ B) ∨ ¬(A ∨ (B § C))

4.3 In Exercise 4.2 you should have discovered that two of the four sentences are tautologies, and

hence logical truths.

1. Suppose you are told that the atomic sentence A is in fact a logical truth (for example,

a = a). Can you determine whether any additional sentences in the list (1)-(4) are

logically necessary based on this information?

2. Suppose you are told that A is in fact a logically false sentence (for example, a = a).

Can you determine whether any additional sentences in the list (1)-(4) are logical

truths based on this information?

In the following four exercises, use Boole to construct truth tables and indicate whether the sentence

is tt-possible and whether it is a tautology. Remember how you should treat long conjunctions and

disjunctions.

4.4 4.5

¬(B § ¬C § ¬B) A ∨ ¬(B ∨ ¬(C § A))

‚ ‚

4.6 4.7

¬[¬A ∨ ¬(B § C) ∨ (A § B)] ¬[(¬A ∨ B) § ¬(C § D)]

‚ ‚

4.8 Make a copy of the Euler circle diagram on page 102 and place the numbers of the following

sentences in the appropriate region.

1. a = b

2. a = b ∨ b = b

Chapter 4

Tautologies and logical truth / 105

3. a= b§b= b

4. ¬(Large(a) § Large(b) § Adjoins(a, b))

5. Larger(a, b) ∨ ¬Larger(a, b)

6. Larger(a, b) ∨ Smaller(a, b)

7. ¬Tet(a) ∨ ¬Cube(b) ∨ a = b

8. ¬(Small(a) § Small(b)) ∨ Small(a)

9. SameSize(a, b) ∨ ¬(Small(a) § Small(b))

10. ¬(SameCol(a, b) § SameRow(a, b))

4.9 (Logical dependencies) Use Tarski™s World to open Weiner™s Sentences. Fill in a table of the

‚| following sort for the ten sentences in this ¬le.

Sentence tw-possible tt-possible

1

2

3

.

.

.

10

1. In the ¬rst column, put yes if the sentence is tw-possible, that is, if it is possible to

make the sentence true by building a world, and no otherwise. If your answer is yes

for a sentence, then construct such a world and save it as World 4.9.x, where x is the

number of the sentence in question. Submit these worlds.

2. In the second column, put yes if the sentence is tt-possible, that is, if there is a row of

the truth table which makes the sentence true. If you think any sentence is tt-possible

but not tw-possible, construct a truth table in Boole for the sentence and submit it

as Table 4.9.x, where x is the number of the sentence in question.

3. Are any of the sentences tw-possible but not tt-possible? Explain why not. Turn in

your table and explanation to your instructor.

4.10 Draw an Euler circle diagram similar to the diagram on page 102, but this time showing the

relationship between the notions of logical possibility, tw-possibility, and tt-possibility. For

each region in the diagram, indicate an example sentence that would fall in that region. Don™t

forget the region that falls outside all the circles.

All necessary truths are obviously possible: since they are true in all possible circumstances,

they are surely true in some possible circumstances. Given this re¬‚ection, where would the

sentences from our previous diagram on page 102 ¬t into the new diagram?

4.11 Suppose that S is a tautology, with atomic sentences A, B, and C. Suppose that we replace

all occurrences of A by another sentence P, possibly complex. Explain why the resulting sentence

Section 4.1

106 / The Logic of Boolean Connectives

is still a tautology. This is expressed by saying that substitution preserves tautologicality.

Explain why substitution of atomic sentences does not always preserve logical truth, even

though it preserves tautologies. Give an example.

Section 4.2

Logical and tautological equivalence

In the last chapter, we introduced the notion of logically equivalent sentences,

sentences that have the same truth values in every possible circumstance.

When two sentences are logically equivalent, we also say they have the same

truth conditions, since the conditions under which they come out true or false

are identical.

The notion of logical equivalence, like logical necessity, is somewhat vague,

but not in a way that prevents us from studying it with precision. For here too

logical equivalence

we can introduce precise concepts that bear a clear relationship to the intuitive

notion we aim to understand better. The key concept we will introduce in this

section is that of tautological equivalence. Two sentences are tautologically

tautological equivalence

equivalent if they can be seen to be equivalent simply in virtue of the meanings

of the truth-functional connectives. As you might expect, we can check for

tautological equivalence using truth tables.

Suppose we have two sentences, S and S , that we want to check for tau-

tological equivalence. What we do is construct a truth table with a reference

column for each of the atomic sentences that appear in either of the two sen-

tences. To the right, we write both S and S , with a vertical line separating

them, and ¬ll in the truth values under the connectives as usual. We call this

a joint truth table for the sentences S and S . When the joint truth table is

joint truth tables

completed, we compare the column under the main connective of S with the

column under the main connective of S . If these columns are identical, then

we know that the truth conditions of the two sentences are the same.

Let™s look at an example. Using A and B to stand for arbitrary atomic

sentences, let us test the ¬rst DeMorgan law for tautological equivalence. We

would do this by means of the following joint truth table.

A B ¬ (A § B) ¬A ∨ ¬B

F Ff

t t t f

T Tt

t f f f

T Tf

f t f t

T Tt

f f f t

In this table, the columns in bold correspond to the main connectives of the

Chapter 4

Logical and tautological equivalence / 107

two sentences. Since these columns are identical, we know that the sentences

must have the same truth values, no matter what the truth values of their

atomic constituents may be. This holds simply in virtue of the structure of

the two sentences and the meanings of the Boolean connectives. So, the two

sentences are indeed tautologically equivalent.

Let™s look at a second example, this time to see whether the sentence

¬((A ∨ B) § ¬C) is tautologically equivalent to (¬A § ¬B) ∨ C. To construct a

truth table for this pair of sentences, we will need eight rows, since there are

three atomic sentences. The completed table looks like this.

A B C ¬ ((A ∨ B) § ¬C) (¬A § ¬B) ∨C

T T

t t t t f f f f f

F F

t t f t t t f f f

T T

t f t t f f f f t

F F

t f f t t t f f t

T T

f t t t f f t f f

F F

f t f t t t t f f

T T

f f t f f f t t t

T T

f f f f f t t t t

Once again, scanning the ¬nal columns under the two main connectives reveals

that the sentences are tautologically equivalent, and hence logically equivalent.

All tautologically equivalent sentences are logically equivalent, but the

reverse does not in general hold. Indeed, the relationship between these no- tautological vs. logical

equivalence

tions is the same as that between tautologies and logical truths. Tautological

equivalence is a strict form of logical equivalence, one that won™t apply to

some logically equivalent pairs of sentences. Consider the pair of sentences:

a = b § Cube(a)

a = b § Cube(b)

These sentences are logically equivalent, as is demonstrated in the following