1 of 2

20.3 Truth-Functional Completeness (TFC)

Soundness and completeness are important metalogic topics, but they are just a small part of the whole area of knowledge.

Another key issue in metalogic is called truth-functional completeness (TFC).

Terminology warning: “truth-functional completeness” is not the same thing as “completeness” that we have been talking about. We use these terms because they are well entrenched in the field, but we know that makes it confusing.

Truth-functional completeness (TFC): the ability to express any possible truth function.

TFC means this: a logical system is truth-functionally complete if it can express any possible truth function.

TFC concerns the expressive power of a system: a system can say or express anything that it is designed to say. (Completeness that we discussed in Section 20.1, by contrast, concerns whether the proof system can provide a formal proof of any valid argument.)

Take BOOL, for example. BOOL is supposed to capture the logic of conjunction, disjunction, and negation, which are truth-functional operators. Since BOOL’s intended application is truth-functional logic, it would be unfortunate if there were some truth functions BOOL couldn’t express.

What we’ll see, though, is that BOOL in fact is truth-functionally complete.

First, a review question.

How can we prove that BOOL is truth-functionally complete? Let’s first consider how many truth functions there are. It will be helpful to write truth functions in a line in the text like this: TFFF. The first value is the first row, and the last value is the last row, so that is just the truth function for conjunction.

The number of rows in a truth function is just determined by the number of atomic sentences in it. One atomic has 2 rows; two atomics have 4 rows; three atomics have 8 rows; etc.

But there’s no limit to how many atomic sentences a complex sentence could have. There could be a complex sentence with 100 atomics, or 101 atomics, or 102 atomics, and so on.

That means there are an infinite number of possible truth functions, consisting of more and more rows.

So we cannot prove that BOOL is truth functionally complete by showing, one at a time, that BOOL can express each truth function. Since there are an infinite number of truth functions, we could never finish the task.

Instead, we need a different plan. The important thing to notice is that, even though there are an infinite number of possible truth functions, each one has a fixed, finite number of rows.

All sentences of BOOL are finitely long.

The way we’ve created BOOL, it cannot have infinitely long sentences. There is no sentence like P&Q&R&S&…, going on forever.

There are various reasons why infinitely long sentences would cause problems for our logical system. For example, imagine a sentence with an infinite number of negations: ~~~~…P. If P is true, is that sentence true or false? It doesn’t really work to say it is either, which means our connectives are no longer truth functional; or we have to sacrifice bivalence.

Classical logics: logical systems created with certain standard properties, like bivalence and finitely long sentences, that make them powerful but easy to learn and use.

Like many of the decisions we make, though, in building our logical system, from an abstract point of view, nothing says it is impossible to have a system with infinitely long sentences. Just like it’s possible to get rid of bivalence, and have systems with other truth values. But making those changes causes other major changes, which is why we are sticking with simple, or what is called “classical”, assumptions for the systems in this textbook. In an advanced logic class you can study “nonclassical” logics.

Back to our plan: prove that BOOL can express any possible truth function.

We know that each truth function is finitely long. That follows because each sentence is finitely long, and therefore has a set number of atomic sentences in it.

Algorithm: a fancy word for a step-by-step procedure.

Since each truth function is finitely long, we can define a step-by-step procedure for creating a sentence of BOOL that expresses it.

If we do that, we’ll have shown that BOOL is truth functionally complete, because, for any possible truth function, we know there’s a sentence of BOOL that expresses it.

TFC algorithm: a recipe for creating a sentence of BOOL that expresses a truth function, no matter what truth function it is.

We’ll call it the TFC algorithm. Algorithm is just a fancy word for a step-by-step procedure, a recipe for expressing any possible truth function in BOOL. Once you understand the algorithm, you will see that there is indeed no truth function BOOL cannot express.

For example, consider a random 8-rowed truth function like this.

The goal is to create a sentence of BOOL, so that, if we put it where the ? is and compute its truth function, it would be the exact one in the picture above.

Here’s how we’ll do it.

TFC Algorithm

Step 1: Create the reference columns for the truth function, and circle all the places where the truth function is T. (If there are no Ts, then make a contradiction, such as P&~P, which will express that truth function.)

In our example, there are three Ts to circle:

8 row truth function: FFTFTFTF. Three Ts circled.

Step 2: For each row with a T, create a conjunction in this way: if an atomic sentence is T on that row, put it in the conjunction; if it is F, put the negation in the conjunction.

For each of the Ts in our example, we create the conjunction:

8 row truth function: FFTFTFTF. Three Ts circled, and a conjunction next to each T.

Step 3: Disjoin all those conjunctions.

If we add disjunctions between each of these sentences:

8 row truth function: FFTFTFTF. Three Ts circled, and a conjunction next to each T, and all disjoined.

We get this: (P&~Q&R)v(~P&Q&R)v(~P&~Q&R). That is the sentence of BOOL we are after. It has the exact truth function we needed to express.

Think about computing its truth function. It has three disjuncts, and each disjunct is a conjunction. Each of those conjunctions is only going to be true in one way: on the specific row of the truth table it was designed for. For example, P&~Q&R is true just in case P is true and Q is false and R is true, which is row 3 of the truth table.

So the disjunction of those will be true on those three rows, which is exactly what we wanted.

We have proven that BOOL is TFC.

So the TFC algorithm works. Given any random truth function, it will generate a sentence of BOOL that expresses it, which means that BOOL is truth functionally complete.

Now it’s your turn to practice.