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

Connectives

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.

non-truth-functional

true, that is, could not have been false (for instance, a = a), while other true

operators

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.

93

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.

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)

T

F

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)

F

t

T

f

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)

Tf

t

Tt

f

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

T T T

T T F

T F T

T F F

F T T

F T F