The truth functional completeness of SL
The question of the truth functional completeness of SL is the question of whether SL is
an adequate language for sentential logic. Can it be used to symbolize all the forms
that truth-functionally compound sentences can have? Recall that a truth functional
connective is a connective that builds a compound sentence that is always exactly one
of true or false depending on the truth values of the component sentence(s) it connects.
At first sight it seems that SL could not possibly be truth-functionally complete, because
it contains only one unary and four binary connectives, and there are many more. For
example, speaking in English, I can say “It is neither raining nor snowing.” This is a
compound sentence of English. It is compounded from two simple sentences, “It is
raining,” and “It is snowing,” using the English connective, “[It is] neither [the case that]
… nor [the case that] …” Moreover, this connective is a truth-functional connective. For
each combination of truth values that might be assigned to the component sentences,
the connective determines a unique truth value for the compound. The sentence, “It is
neither raining nor snowing” is true if and only if both the sentence “It is raining” and the
sentence, “It is snowing” are false. In all other cases — if one or the other is true or
both are (which sometimes happens) — the compound sentence is false. This rule
does not correspond to any of the rules for the five connectives of SL. So it looks like
SL comes up short at giving us symbols for one of the truth functional connectives of
English — “neither … nor …,” which assigns truth values in accord with a rule we do not
have a connective to represent.
Nor is this the only such case. In English the connective “Either … or …” is often used
in what is called a “strong” or “exclusive sense.” If I say, “I will either take early
retirement or accept the promotion,” someone could accuse me of lying if I did both (as
well, of course, as if I did not do either). So, when used in this sense, “either … or …”
builds a compound sentence that is true if and only if exactly one of its component
sentences is true, but that is false when either both are true or when both are false.
Again, a survey of the rules for the connectives of SL shows that we have no connective
that assigns truth values to compound sentences in this way. Once again, SL comes up
short at providing us with symbols for truth-functional connectives that exist in English.
Just how bad is this problem? How many connectives has SL failed to symbolize?
To help us grasp the magnitude of this problem, I here introduce the notion of a
“characteristic truth table.” The textbook introduces this notion early in chapter 2 and
again in chapter 3.1, but I have avoided using it up until now because the connectives of
SL are better understood by understanding their semantic rules and truth tables are
constructed with fewer mistakes when constructed in accord with the semantic rules.
There has therefore been no call to speak of characteristic truth tables.
Now, the proper occasion has arisen to introduce them. 2
A characteristic truth table is a truth table that represents what assignments a truth
function makes under each of the possible circumstances.
For example, a unary truth function makes an assignment under two possible
circumstances: when a sentence is true, and when it is false. The negation truth
function does this, and we represent the assignments it makes under these
circumstances on a characteristic table as follows:
The table tells us that when a sentence (be it atomic or compound) is true, the negation
function assigns an F, and when it is false the function assigns a T.
Similarly, a binary truth function makes an assignment under four possible
circumstances: when two sentences are true, when one is true and the other is false,
when the one is false and the other is true, and when both are false. The characteristic
tables for &, v, ⊃, and ≡ specify what assignments the conjunction, disjunction,
conditional, and biconditional truth functions make under each of these possible
circumstances. They look like this:
& v ⊃ ≡
T T T T T T T T T T T T
T F F T F T T F F T F F
F T F F T T F T T F T F
F F F F F F F F T F F T
If we want, we can add characteristic tables for the two English connectives I mentioned
earlier, for purposes of comparison. To make the comparison easier, I here collect all
the separate tables together onto one and use “↓” to symbolize the “neither … nor …”
truth function and “/” to symbolize “either … or … but not both.”
& v ⊃ ≡ ↓ /
T T T T T T F F
T F F T F F F T
F T F T T F F T
F F F F T T T F
Here you see exactly how the different rules for the English connectives dictate different
characteristic truth tables.
Looking at these tables, you might be struck by something. “Neither … nor …” is the
contradictory of “v.” All we need to do is consider the truth tab
efor ~(… v …) and w
arrive at the truth table for “Neither … nor …” Similarly, “Either … or … but not both” is 3
the contradictory of “≡.” All we need to do is consider the truth table for ~(… ≡ …) and
we arrive at the truth table for “Either … or … but not both.”
v ~( v ) ↓ ≡ ~( ≡ ) /
T T T F F T F F
T F T F F F T T
F T T F F F T T
F F F T T T F F
In light of this discovery you might start to think that perhaps we don’t need to worry that
SL does not have enough connectives to represent all the truth functions. Granted, we
have no special symbol in SL for either a “neither … nor …” or a “strong or” truth
functional connective. But it looks like we can construct sentences of SL that are truth
functionally equivalent to sentences made using these missing connectives. So we
don’t need the missing connectives. When we run into English sentences that use
these truth functions we can “translate” them into slightly more compound sentences of
SL that use only the connectives we have available, but that mean exactly the same
thing (that is, that receive the same truth values on all possible truth value
assignments). We can translate “neither … nor …” as ~( … v …), and we can translate
the “strong or” as ~( … ≡ …). The former is not surprising if you think of “Neither” as a
slurring of “Not (either … or …).”
But we are not quite out of the woods yet. We have only considered two English truth
functional connectives that are not symbolized in SL. There may be others. How do we
know that we can handle all of them in the way we have just handled “neither … nor …”
and the “strong or?”
Let me make the question I am asking a bit more precise by introducing a notion that
the textbook brings up in Ch. 6.2: that of a sentence that “expresses” a truth function.
We will say that a sentence of SL expresses a truth function if and only if it has the
same column of T’s and F’s under its main connective that appears on the
characteristic truth table for that truth function. So, trivially, the sentence “A v B”
expresses the “v” truth function and, non-trivially, the sentence “~(A ≡ B)” expresses the
“strong or” truth function.
The question we are asking is whether, for any compound sentence of English or any
other natural language, compounded using any truth functional connective of that
language, there is a sentence of SL that expresses that truth function: that has the
same column of T’s and F’s under its main connective as appears on the characteristic
truth table for the truth function.
This question begs a prior one: just how many truth functions are there anyway?
Considering things in terms of characteristic truth tables gives us a way to begin to
answer this question. Let’s begin by asking just how many unary truth functions there
could be. If we consider just unary truth functions, we can see that only four are 4
possible. There is the truth function that assigns a T to the compound sentence,
regardless of the truth value of its immediate component; the truth function that assigns
the same truth value to the compound sentence that its immediate component has; the
truth function that assigns the opposite truth value to the compound sentence that its
immediate component has; and the truth function that assigns an F to the compound
sentence, regardless of the truth value of the immediate component. The four possible
truth functions are listed on the following table. Obviously, there can be no others.
P U1 U2 U3 U4
T T T F F
F T F T F
(The characteristic truth tables for the 4 truth functions are here amalgamated on one
table, but you should think of the left hand column and one of each of the other columns
as making up 4 separate characteristic tables.)
As it turns out, both English and SL use only one of these truth functions, #3. Perhaps
that is because there is not much point to using the others. We have no use for a unary
connective that does not change the truth value of its immediate component — it is
redundant — and no interest in ones that draw no distinctions and just make everything
true and everything false. Nonetheless, there are sentences of SL that express the U1,
U2, and U4 truth functions, and that therefore can be substituted for them wherever we
might have a need to do so; namely, the sentences (P v ~P), P, and (P & ~P). And, of
course, ~P does the job for U3. Each of these sentences has the same column of T’s
and F’s under its main connective as appears on the characteristic truth table for that
truth function. (P v ~P) is true on any tva, P always has the same truth value as itself
wherever it occurs, ~P has the opposite truth value of P on any tva, and (P & ~P) is
always false on any tva.
Now what about binary truth functions?
There are 16 different ways of mapping four pairs of truth values onto a single column of
truth values, and hence 16 different binary truth functions. Beginning with the one that
assigns a T in all circumstances and ending with the one that assigns an F in all
circumstances they are:
B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 B11 B12 B13 B14 B15 B16
T T T T T T F T T F T F F T F F F F
T F T T T F T T F T F T F F T F F F
F T T T F T T F T T F F T F F T F F
F F T F T T T F F F T T T F F F T F
It is an entertaining exercise to run through this list and try to think up sentences of SL
that express each of these truth functions. And we might think that if we can do this,
then we are out of the woods and can consider SL to have the resources to represent
any truth function and so to be a complete language for doing truth functional logic. 5
But we aren’t out of the woods, because there is no reason to limit connectives to unary
and binary truth functions. There can be trinary or three place connectives that connect
three sentences into a compound sentence, four-place connectives, five-place
connectives, and so on without end. And these connectives can be truth-functional —
they can have their own rules for determining truth values for the compound sentence in
all possible circumstances. So we need to worry about three-place truth functions, four-
place truth functions, and so on without end.
Since there are 8 possib8e ways for two truth values to be distributed over three
sentences, there are 2 or 256 different possible three-place truth functions.
There are 65,536 different possible 4-place truth functions.
And, to repeat, there is no limit to how many places a connective can have. (The
formula for hownmany different truth functions there are for n sentences is 2 raised to
the power of 2 .)
We are not going to be able to satisfy ourselves by brute force that SL is adequate to
express all of these truth functions, that is, by running through each of the possible truth
functions in turn and finding a sentence of SL that expresses it. There are too many for
that — infinitely many.
Neither can we dismiss this problem by saying that we don’t have names for any higher
place connectives in English and so can safely ignore them. Even if that were true (and
English is surprisingly more resourceful than you might think at first, as we will see in a
moment), we don’t want SL to be a language that is adequate just for the truth-
functional logic of speakers of English. We want SL to be adequate for speakers of any
language whatsoever, even super-intelligent speakers of massively complex languages
that don’t exist.
So how can we be assured that SL is truth functionally complete —that there is a
sentence of SL that will express any truth function?
We can get that assurance if we can come up with an algorithm for constructing a
sentence of SL that will express any truth function anyone chooses to be worried about.
An algorithm is a mechanical procedure — a routine sequence of steps — that is
guaranteed to produce the right result. If we can come up with such an algorithm for
constructing sentences of SL that express truth functions, then we won’t need to run
through all the infinitely many truth functions to check if SL can handle each of them.
We will be able to be assured that given any one of them, we can simply apply the
algorithm and be assured of getting the sentence we are looking for.
To satisfy your curiosity, here is that algorithm. WARNING: there are some concepts
that will have to be further explained. I will also need to explain why the algorithm is
guaranteed never to fail. 6
The sentence of SL that expresses any arbitrarily given truth function is
the disjunction of the characteristic sentences for each line of the
characteristic table on which the truth function assigns a T. If there are no
such lines it is the conjunction of the characteristic sentence for the first
line and its negation.
Now for the explanations.
Remember that each truth function has its own characteristic truth table. Here, by way
of example, is a characteristic truth table for an arbitrarily selected three-place truth
function, “T?,” — one of 256 others.
T T T T
T T F F
T F T F
T F F T
F T T F
F T F F
F F T F
F F F T
This table tells us that this mystery truth function assigns a T to a compound of three
immediate components if and only if either each of the components is true, or the first is
true and the others are false, or all are false; otherwise it assigns an F to the compound.
We don’t care whether there is an English name for this truth function. — Though there
is: “All or none or just the first of A, B, and C.” Some might quibble that this is not a
single English name for a three-place truth function but a des
names for a number of simpler truth functions. They are party-poopers (though they
would have a fine time trying to incorporate “all,” “none,” and “just the first of” into SL).
Regardless, the point is that there is such a truth function, whether it has its own name
in English or not, and we want to know if SL can express it.
Let’s proceed with showing how there is an effective procedure for constructing a
sentence of SL that will express this (or any other) truth-function.
To begin with, we will use our stock of atomic sentences of SL to name the columns on
the left side of a characteristic table, taking them in alphabetical order and going from
left to right. So the left side of the characteristic table given above will look like this: 7
A B C
T T T
T T F
T F T
T F F
F T T
F T F
F F T
F F F
Now note that for each (horizontal) row on this partial truth table below the first, there is
a sentence of SL (one using just the atomic sentence letters listed on the top row of the
characteristic table, and the connectives “~” and “&”) that is true if and only if its atomic
components get the truth value assignments specified on that row and that is otherwise
false. We call this the characteristic sentence for that line.
The characteristic sentence for a line on a truth table is, firstly, the iterated conjunction
of each of the atomic sentence letters on the top row of the table. An iterated
conjunction is created by taking the first two sentence letters from the left and making a
conjunction using them, then taking that conjunction and making a conjunction with the
next atomic sentence letter over