Truth-functional Completeness
PL has five operators: the tilde, the wedge, the ampersand, the horseshoe, and the triple-bar. We know that these operators are truth-functions. They take truth-values as input and return a truth-value as an output. Our question in this section is the following: Can we describe all possible truth-functions using our five operators? That is, can we construct any truth-function from input to output using our operators? If the answer is yes, then our system of logic is truth-functionally complete. This is a question in what we call Metalogic, the logic of logic. In asking this question we are asking a question about our system of logic, and in answering it we are proving something about our system of logic. Other metalogical questions will appear later in the text.
A simplified version of the question we're asking is this: Can we construct all possible truth-tables using our five operators? Since a truth-table is a tabular expression of a function from input to output, if we can construct all possible truth-tables, then our system is functionally complete.
There are, of course, an infinite number of truth-tables. So how could we show that we can express them all in PL? We show that we have a recipe for constructing any possible truth-table.
Truth-tables come in many sizes. We remember that the number of rows of a truth-table is 2n, where n is the number of distinct sentence letters in the wff. Let's start with the truth-table for n=1. That has two rows:
| A | ? |
| T | ? |
| F | ? |
Here "A" can be T or F. What are the possible outputs?
| A | ? |
| T | T |
| F | T |
We could have all "T"s for the output. Then the wff we need is a tautology. So we can use "(A v ~A)" to give us that output.
| A | (A v ~A) |
| T | T |
| F | T |
Now consider the possible output where we always get an "F":
| A | ? |
| T | F |
| F | F |
Then the wff we need is a contradiction. So we can use "(A & ~A)" to give us that output.
| A | (A & ~A) |
| T | F |
| F | F |
Next consider the possible output where the output is the same as the input:
| A | ? |
| T | T |
| F | F |
For this we simply use "A" itself.
| A | A |
| T | T |
| F | F |
Finally, consider what happens when we go from a "T" input to an "F" output or an "F" input to a "T" output:
| A | ? |
| T | F |
| F | T |
This is represented by our good-old-fashioned tilde!
| A | ~A |
| T | F |
| F | T |
We've just shown that we can construct every possible function from truth-value inputs to truth-value outputs for truth-tables with one sentence distinct letter. Now we have to show that we can do so for truth-tables with two or more distinct sentence letters. For any such truth table, there are going to be three varieties: (1) truth-tables that have all "T"s for the final column, (2) truth-tables that have all "F"s on the final column, and truth-tables that have at least one "T" and at least one "F". For the first two cases, we simply need to construct tautologies and contradictions. So if the sentence letter "A" is one of our distinct sentence letters, for the truth-tables with all "T"s we make sure that we disjoin "(A v ~A) with the other sentence letters, and we'll get all "T"s for the final column. For the truth-table with all "F"s, we conjoin "(A&~A) with the sentence letters and we'll get all "F"s.
Now let's talk about the truth-tables where the output (the final column) has some Fs and some Ts. We form a wff as follows: Start with the first row where the whole wff comes out true: Construct a conjunction as follows: for each sentence letter, if the sentence letter is assigned "T" then make the sentence letter a conjunct. If it is assigned "F" make the negation of the sentence letter a conjunct. We'll call each of these conjunctions the "associated conjunctions" for that row. Do this for every row where the wff comes out true. Now take these conjunctions, and form a disjunction of all these conjunctions, remember to use only the conjunctions for the rows that come out true in the final column. The resulting wff is a wff with the truth-table in question.
For example, let's look at the truth table:
| A | B | ? |
| T | T | F |
| T | F | T |
| F | T | T |
| F | F | F |
Following our recipe, we construct the associated conjunctions (A &~B), for the second row, and (~A & B) for the third row . Now we disjoin the associated conjunctions : (A &~B) v (~A & B). (Don't worry about grouping here.) This disjunction has the truth-table in question:
| A | B | (A &~B) v (~A & B) |
| T | T | F |
| T | F | T |
| F | T | T |
| F | F | F |
And this recipe is perfectly general and will work for truth-tables of any size. So we have proven that using our operators (in fact, just using negation, conjunction and disjunction - we didn't need to use the horseshoe or the triple-bar) we can express any truth function. Therefore PL is functionally complete.
Here's another. What's the associated wff for:
| A | B | ? |
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | F |
First we list the associated conjunctions. For the first row, it's (A&B), and for the third, (~A & B). Since the wff comes out true on the first and third rows, we disjoin the conjunctions from those rows and get (A & B) v (~A & B).
| A | B | (A & B) v (~A & B) |
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | F |
As an exercise, construct an arbitrary truth-table, and then construct a wff which has that truth-table, using the recipe above. As another exercise, explain how our proof in this section is also a proof of the superfluousness of the horseshoe and the triple-bar as operators in PL.
 |
 |
| table of contents | List of Exercises |