. 20
( 107 .)


coarse to recognize that the row containing the F does not represent a genuine

Section 4.1
102 / The Logic of Boolean Connectives

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

You should be able to think of any number of sentences that are not
tautological, but which nonetheless seem logically necessary. For example, the
¬(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.
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.


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-

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


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
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. 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 f f f f f
t t f t t t f f f
t f t t f f f f t
t f f t t t f f t
f t t t f f t f f
f t f t t t t f f
f f t f f f 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
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


. 20
( 107 .)