child can have dessert if he eats the dreaded beans. But again, the suggestion

can be cancelled. Suppose the father goes on to say: If you eat the beans, I™ll

check to see if there™s any ice cream left. This cancels the implication that

dessert is guaranteed.

Remember

If the assertion of a sentence carries with it a suggestion that could be

cancelled (without contradiction) by further elaboration by the speaker,

then the suggestion is a conversational implicature, not part of the content

of the original claim.

Section 7.3

190 / Conditionals

Exercises

7.22 Suppose Claire asserts the sentence Max managed to get Carl home. Does this logically imply,

or just conversationally implicate, that it was hard to get Carl home? Justify your answer.

7.23 Suppose Max asserts the sentence We can walk to the movie or we can drive. Does his assertion

logically imply, or merely implicate, that we cannot both walk and drive? How does this di¬er

from the soup or salad example?

7.24 Consider the sentence Max is home in spite of the fact that Claire is at the library. What would

be the best translation of this sentence into fol? Clearly, whether you would be inclined to use

this sentence is not determined simply by the truth values of the atomic sentences Max is home

and Claire is at the library. This may be because in spite of the fact is, like because, a non-truth-

functional connective, or because it carries, like but, additional conversational implicatures. (See

our discussion of because earlier in this chapter and the discussion of but in Chapter 3.) Which

explanation do you think is right? Justify your answer.

Section 7.4

Truth-functional completeness

We now have at our disposal ¬ve truth-functional connectives, one unary

(¬), and four binary (§, ∨, ’, ”). Should we introduce any more? Though

we™ve seen a few English expressions that can™t be expressed in fol, like

because, these have not been truth functional. We™ve also run into others, like

neither. . . nor. . . , that are truth functional, but which we can easily express

using the existing connectives of fol.

The question we will address in the current section is whether there are any

truth-functional connectives that we need to add to our language. Is it possible

that we might encounter an English construction that is truth functional but

which we cannot express using the symbols we have introduced so far? If so,

this would be an unfortunate limitation of our language.

How can we possibly answer this question? Well, let™s begin by thinking

about binary connectives, those that apply to two sentences to make a third.

How many binary truth-functional connectives are possible? If we think about

the possible truth tables for such connectives, we can compute the total num-

ber. First, since we are dealing with binary connectives, there are four rows

in each table. Each row can be assigned either true or false, so there are

24 = 16 ways of doing this. For example, here is the table that captures the

truth function expressed by neither. . . nor. . . .

Chapter 7

Truth-functional completeness / 191

P Q Neither P nor Q

F

t t

F

t f

F

f t

T

f f

Since there are only 16 di¬erent ways of ¬lling in the ¬nal column of such

a table, there are only 16 binary truth functions, and so 16 possible binary

truth-functional connectives. We could look at each of these tables in turn

and show how to express the truth function with existing connectives, just as

we captured neither P nor Q with ¬(P ∨ Q). But there is a more general and

systematic way to show this.

Suppose we are thinking about introducing a binary truth-functional con-

nective, say . It will have a truth table like the following, with one of the

values true or false in each row.

P Q PQ

1st value

t t

nd

2 value

t f

3rd value

f t

4th value

f f

If all four values are false, then we can clearly express P Q with the

sentence P § ¬P § Q § ¬Q. So suppose at least one of the values is true.

How can we express P Q? One way would be this. Let C1 , . . . , C4 stand for

the following four conjunctions:

C1 = (P § Q)

C2 = (P § ¬Q)

C3 = (¬P § Q)

C4 = (¬P § ¬Q)

Notice that sentence C1 will be true if the truth values of P and Q are as

speci¬ed in the ¬rst row of the truth table, and that if the values of P and Q

are anything else, then C1 will be false. Similarly with C2 and the second row

of the truth table, and so forth. To build a sentence that gets the value true

in exactly the same rows as P Q, all we need do is take the disjunction of the

appropriate C™s. For example, if P Q is true in rows 2 and 4, then C2 ∨ C4 is

equivalent to this sentence.

What this shows is that all binary truth functions are already expressible

using just the connectives ¬, §, and ∨. In fact, it shows that they can be ex-

pressed using sentences in disjunctive normal form, as described in Chapter 4.

Section 7.4

192 / Conditionals

It™s easy to see that a similar procedure allows us to express all possible

unary truth functions. A unary connective, say , will have a truth table like

this:

P P

1st value

t

2nd value

f

If both of the values under P are false, then we can express it using the

sentence P § ¬P. Otherwise, we can express P as a disjunction of one or

more of the following:

C1 = P

C2 = ¬P

C1 will be included as one of the disjuncts if the ¬rst value is true, and C2

will be included if the second value is true. (Of course, in only one case will

there be more than one disjunct.)

Once we understand how this procedure is working, we see that it will

apply equally well to truth-functional connectives of any arity. Suppose, for

example, that we want to express the ternary truth-functional connective

de¬ned by the following truth table:

P Q R ™(P, Q, R)

T

t t t

T

t t f

F

t f t

F

t f f

T

f t t

F

f t f

T

f f t

F

f f f

A fairly good English translation of ™(P, Q, R) is if P then Q, else R. When

we apply the above method to express this connective, we get the following

sentence:

(P § Q § R) ∨ (P § Q § ¬R) ∨ (¬P § Q § R) ∨ (¬P § ¬Q § R)

More generally, if ™ expresses an n-ary connective, then we can use this

procedure to get a sentence that is tautologically equivalent to ™(P1 , . . . , Pn ).

First, we de¬ne the conjunctions C1 , . . . , C2n that correspond to the 2n rows

of the truth table. We then form a disjunction D that contains Ck as a disjunct

if and only if the k th row of the truth table has the value true. (If all rows

Chapter 7

Truth-functional completeness / 193

contain false, then we let D be P1 § ¬P1 .) For reasons we™ve already noted,

this disjunction is tautologically equivalent to ™(P1 , . . . , Pn ).

We have just sketched a proof that any truth function, of any arity what-

soever, can be expressed using just the Boolean connectives ¬, §, and ∨. This

is a su¬ciently interesting fact that it deserves to be highlighted. We™ll say

that a set of connectives is truth-functionally complete if the connectives in truth-functional

completeness

the set allow us to express any truth function. We can then highlight this

important fact as a theorem:

Theorem The Boolean connectives ¬, §, and ∨ are truth-functionally com-

plete.

A theorem is just a conclusion the author ¬nds particularly interesting or is

particularly proud of having proven.

There are other collections of operators that are truth-functionally com-

plete. In fact, we could get rid of either § or ∨ without losing truth-functional

completeness. For example, P ∨ Q can be expressed using just ¬ and § as

follows:

¬(¬P § ¬Q)

What this means is that we could get rid of all the occurrences of ∨ in our

sentences in favor of ¬ and §. Alternatively, we could get rid of § in favor

of ¬ and ∨, as you™ll see in Exercise 7.25. Of course either way, the resulting

sentences would be much longer and harder to understand.

We could in fact be even more economical in our choice of connectives.

Suppose we used P “ Q to express neither P nor Q. It turns out that the

connective “ is, all by itself, truth-functionally complete. To see this, notice

that ¬P can be expressed as:

P“P

which says neither P nor P, and P § Q can be expressed as:

(P “ P) “ (Q “ Q)

which says neither not P nor not Q. Thus in theory we could use just this one

truth-functional connective and express anything we can now express using

our current ¬ve.

There are two disadvantages to economizing on connectives. First, as we™ve disadvantages of

economy

already said, the fewer connectives we have, the harder it is to understand our

sentences. But even worse, our proofs become much more complicated. For

example, if we always expressed § in terms of ¬ and ∨, a single application of

the simple rule of § Intro would have to be replaced by two uses of ⊥ Intro,

Section 7.4

194 / Conditionals

one use of ∨ Elim, and one use of ¬ Intro (see Exercise 7.26). This is why

we haven™t skimped on connectives.

Remember

1. A set of connectives is truth-functionally complete if the connectives

allow us to express every truth function.

2. Various sets of connectives, including the Boolean connectives, are

truth-functionally complete.

Exercises

7.25 (Replacing §, ’, and ”) Use Tarski™s World to open the ¬le She¬er™s Sentences. In this ¬le,

‚ you will ¬nd the following sentences in the odd-numbered positions:

1. Tet(a) § Small(a)

3. Tet(a) ’ Small(a)

5. Tet(a) ” Small(a)

7. (Cube(b) § Cube(c)) ’ (Small(b) ” Small(c))

In each even-numbered slot, enter a sentence that is equivalent to the one above it, but which

uses only the connectives ¬ and ∨. Before submitting your solution ¬le, you might want to try

out your sentences in several worlds to make sure the new sentences have the expected truth

values.

7.26 (Basic versus de¬ned symbols in proofs) Treating a symbol as basic, with its own rules, or as a

‚ de¬ned symbol, without its own rules, makes a big di¬erence to the complexity of proofs. Use

Fitch to open the ¬le Exercise 7.26. In this ¬le, you are asked to construct a proof of ¬(¬A ∨ ¬B)

from the premises A and B. A proof of the equivalent sentence A § B would of course take a

single step.

7.27 (Simplifying if. . . then. . . else) Assume that P, Q, and R are atomic sentences. See if you can