. 18
( 107 .)


5. NAKApqrs
4. P(∼ Q ∨ RS)

3.28 (Boolean searches) You have probably heard of tools for searching data that permit “full
 Boolean searches.” This means that the search language allows you to use the Boolean connec-
tives we have been studying. Before you can do a search, though, you have to ¬gure out what
dialect the search mechanism uses. Let™s try out a search engine that uses !, &, and |.
Using your web browser, go to the Alta Vista search page at http://www.altavista.com/.
Click on the link for Advanced Search, since only the advanced search page allows full
Boolean searches. Suppose you want to ¬nd information about the use of Tarski™s World at
other colleges and universities.
1. Type tarski in the search ¬eld and then click Search. You will ¬nd that there are way
too many web sites that mention Tarski, who was, after all, a famous logician.
2. Type tarski™s world in the search ¬eld and then click Search. This will ¬nd all sites
that contain the words “tarski™s world.” There are still quite a few, and many of them
are not colleges or universities, but book dealers and such. We need to exclude sites
whose web addresses end with “.com” or “.org.”

Section 3.8
92 / The Boolean Connectives

Figure 3.1: Boolean combinations of solids: A ∨ B,
A § ¬B, ¬A § B, and A § B.

3. Type tarski™s world & !(domain:com | domain:org) in the search ¬eld and then click
Search. This will ¬nd all sites that contain “tarski™s world” but do not contain either
the “.com” or “.org” domains in their web addresses.
4. Type tarski™s world & !(domain:com | domain:org) & (¬tch | proof) in the search ¬eld
and then click Search. This will ¬nd all sites that contain “tarski™s world,” do not
contain either the “.com” or “.org” domains in their web addresses, but do contain
either the word “¬tch” or the word “proof.”
5. Construct a search to ¬nd any web pages containing references to Tarski™s World and
Boole, but neither Fitch nor Submit. Print the list of sites that result from your search,
write your Boolean expression at the top, and turn it in to your instructor.

3.29 (Boolean solids) When we do a Boolean search, we are really using a generalization of the
 Boolean truth functions. We specify a Boolean combination of words as a criterion for ¬nding
documents that contain (or do not contain) those words. Another generalization of the Boolean
operations is to spatial objects. In Figure 3.1 we show four ways to combine a vertical cylinder
(A) with a horizontal cylinder (B) to yield a new solid. Give an intuitive explanation of how the
Boolean connectives are being applied in this example. Then describe what the object ¬(A § B)
would be like and explain why we didn™t give you a picture of this solid.

Chapter 3
Chapter 4

The Logic of Boolean

The connectives §, ∨, and ¬ are truth-functional connectives. Recall what
this means: the truth value of a complex sentence built by means of one of
these symbols can be determined simply by looking at the truth values of the
sentence™s immediate constituents. So to know whether P ∨ Q is true, we need
only know the truth values of P and Q. This particularly simple behavior is
what allows us to capture the meanings of truth-functional connectives using
truth tables.
Other connectives we could study are not this simple. Consider, the sen-
tence it is necessarily the case that S. Since some true claims are necessarily truth-functional vs.
true, that is, could not have been false (for instance, a = a), while other true
claims are not necessarily true (for instance, Cube(a)), we can™t ¬gure out the
truth value of the original sentence if we are only told the truth value of its
constituent sentence S. It is necessarily the case, unlike it is not the case, is
not truth-functional.
The fact that the Boolean connectives are truth functional makes it very
easy to explain their meanings. It also provides us with a simple but power-
ful technique to study their logic. The technique is an extension of the truth
tables used to present the meanings of the connectives. It turns out that we
can often calculate the logical properties of complex sentences by construct-
ing truth tables that display all possible assignments of truth values to the
atomic constituents from which the sentences are built. The technique can,
for example, tell us that a particular sentence S is a logical consequence of
some premises P1 , . . . , Pn . And since logical consequence is one of our main
concerns, the technique is an important one to learn.
In this chapter we will discuss what truth tables can tell us about three
related logical notions: the notions of logical consequence, logical equivalence,
and logical truth. Although we™ve already discussed logical consequence at
some length, we™ll tackle these in reverse order, since the related truth table
techniques are easier to understand in that order.

94 / The Logic of Boolean Connectives

Section 4.1
Tautologies and logical truth
We said that a sentence S is a logical consequence of a set of premises P1 , . . . , Pn
if it is impossible for the premises all to be true while the conclusion S is false.
That is, the conclusion must be true if the premises are true.
Notice that according to this de¬nition there are some sentences that are
logical consequences of any set of premises, even the empty set. This will be
true of any sentence whose truth is itself a logical necessity. For example,
given our assumptions about fol, the sentence a = a is necessarily true. So
of course, no matter what your initial premises may be, it will be impossible
for those premises to be true and for a = a to be false”simply because it is
impossible for a = a to be false! We will call such logically necessary sentences
logical truths.
logical truth
The intuitive notions of logical possibility and logical necessity have al-
ready come up several times in this book in characterizing valid arguments
and the consequence relation. But this is the ¬rst time we have applied them
to individual sentences. Intuitively, a sentence is logically possible if it could
logical possibility and
necessity be (or could have been) true, at least on logical grounds. There might be some
other reasons, say physical, why the statement could not be true, but there are
no logical reasons preventing it. For example, it is not physically possible to
go faster than the speed of light, though it is logically possible: they do it on
Star Trek all the time. On the other hand, it is not even logically possible for
an object not to be identical to itself. That would simply violate the meaning
of identity. The way it is usually put is that a claim is logically possible if
there is some logically possible circumstance (or situation or world) in which
the claim is true. Similarly, a sentence is logically necessary if it is true in
every logically possible circumstance.
These notions are quite important, but they are also annoyingly vague.
As we proceed through this book, we will introduce several precise concepts
that help us clarify these notions. The ¬rst of these precise concepts, which
we introduce in this section, is the notion of a tautology.
How can a precise concept help clarify an imprecise, intuitive notion? Let™s
think for a moment about the blocks language and the intuitive notion of
logical possibility. Presumably, a sentence of the blocks language is logically
possible if there could be a blocks world in which it is true. Clearly, if we can
construct a world in Tarski™s World that makes it true, then this demonstrates
that the sentence is indeed logically possible. On the other hand, there are
logically possible sentences that can™t be made true in the worlds you can

Chapter 4
Tautologies and logical truth / 95

build with Tarski™s World. For example, the sentence

¬(Tet(b) ∨ Cube(b) ∨ Dodec(b))

is surely logically possible, say if b were a sphere or an icosahedron. You can™t
build such a world with Tarski™s World, but that is not logic™s fault, just as it™s
not logic™s fault that you can™t travel faster than the speed of light. Tarski™s
World has its non-logical laws and constraints just like the physical world.
The Tarski™s World program gives rise to a precise notion of possibility
for sentences in the blocks language. We could say that a sentence is tw- tw-possible
possible if it is true in some world that can be built using the program. Our
observations in the preceding paragraph could then be rephrased by saying
that every tw-possible sentence is logically possible, but that the reverse is
not in general true. Some logically possible sentences are not tw-possible.
It may seem surprising that we can make such de¬nitive claims involving
a vague notion like logical possibility. But really, it™s no more surprising than
the fact that we can say with certainty that a particular apple is red, even
though the boundaries of the color red are vague. There may be cases where
it is hard to decide whether something is red, but this doesn™t mean there
aren™t many perfectly clear-cut cases.
Tarski™s World gives us a precise method for showing that a sentence of
the blocks language is logically possible, since whatever is possible in Tarski™s
World is logically possible. In this section, we will introduce another precise
method, one that can be used to show that a sentence built up using truth-
functional connectives is logically necessary. The method uses truth tables truth table method
to show that certain sentences cannot possibly be false, due simply to the
meanings of the truth-functional connectives they contain. Like the method
given to us by Tarski™s World, the truth table method works only in one
direction: when it says that a sentence is logically necessary, then it de¬nitely
is. On the other hand, some sentences are logically necessary for reasons that
the truth table method cannot detect.
Suppose we have a complex sentence S with n atomic sentences, A1 , . . . , An .
To build a truth table for S, one writes the atomic sentences A1 ,. . . , An across
the top of the page, with the sentence S to their right. It is customary to
draw a double line separating the atomic sentences from S. Your truth table
will have one row for every possible way of assigning true and false to the
atomic sentences. Since there are two possible assignments to each atomic
sentence, there will be 2n rows. Thus if n = 1 there will be two rows, if n = 2 number of rows in a
truth table
there will be four rows, if n = 3 there will be eight rows, if n = 4 there will
be sixteen rows, and so forth. It is customary to make the leftmost column
have the top half of the rows marked true, the second half false. The next

Section 4.1
96 / The Logic of Boolean Connectives

row splits each of these, marking the ¬rst and third quarters of the rows with
true, the second and fourth quarters with false, and so on. This will result
in the last column having true and false alternating down the column.
Let™s start by looking at a very simple example of a truth table, one for the
sentence Cube(a) ∨ ¬Cube(a). Since this sentence is built up from one atomic
sentence, our truth table will contain two rows, one for the case where Cube(a)
is true and one for when it is false.

Cube(a) Cube(a) ∨ ¬Cube(a)

In a truth table, the column or columns under the atomic sentences are
called reference columns. Once the reference columns have been ¬lled in, we
reference columns
are ready to ¬ll in the remainder of the table. To do this, we construct columns
of T™s and F™s beneath each connective of the target sentence S. These columns
are ¬lled in one by one, using the truth tables for the various connectives. We
start by working on connectives that apply only to atomic sentences. Once
this is done, we work on connectives that apply to sentences whose main
connective has already had its column ¬lled in. We continue this process until
the main connective of S has had its column ¬lled in. This is the column that
shows how the truth of S depends on the truth of its atomic parts.
Our ¬rst step in ¬lling in this truth table, then, is to calculate the truth
values that should go in the column under the innermost connective, which in
this case is the ¬. We do this by referring to the truth values in the reference
column under Cube(a), switching values in accord with the meaning of ¬.

Cube(a) Cube(a) ∨ ¬Cube(a)

Once this column is ¬lled in, we can determine the truth values that should
go under the ∨ by looking at the values under Cube(a) and those under the
negation sign, since these correspond to the values of the two disjuncts to
which ∨ is applied. (Do you understand this?) Since there is at least one T in
each row, the ¬nal column of the truth table looks like this.

Cube(a) Cube(a) ∨ ¬Cube(a)

Chapter 4
Tautologies and logical truth / 97

Not surprisingly, our table tells us that the sentence Cube(a) ∨ ¬Cube(a)
cannot be false. It is what we will call a tautology, an especially simple kind
of logical truth. We will give a precise de¬nition of tautologies later. Our
sentence is in fact an instance of a principle, P ∨ ¬P, that is known as the law law of excluded middle
of the excluded middle. Every instance of this principle is a tautology.
Let™s next look at a more complex truth table, one for a sentence built up
from three atomic sentences.
(Cube(a) § Cube(b)) ∨ ¬Cube(c)
In order to make our table easier to read, we will abbreviate the atomic
sentences by A, B, and C. Since there are three atomic sentences, our table
will have eight (23) rows. Look carefully at how we™ve arranged the T™s and
F™s and convince yourself that every possible assignment is represented by one
of the rows.
A B C (A § B) ∨ ¬C


. 18
( 107 .)