. 36
( 107 .)


Still it is clear that the father™s assertion suggests that, other things equal, the
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.


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


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
t t
t f
f 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.
1st value
t t
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
1st value
2nd value

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

(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
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-
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
¬(¬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:


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


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.


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

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


. 36
( 107 .)