Section Progress:

20.4 More TFC

In the last section we proved that BOOL is truth functionally complete (TFC). In this section we use that result to prove several more things.

PROP is TFC.

For example, we can easily prove that PROP is also truth functionally complete. After all, PROP has all the Boolean connectives plus the conditionals. Any logical system that includes BOOL plus more will also be TFC.

What is more interesting is when something can be TFC with less than BOOL. BOOL has three connectives: &, v and ~. Next we’ll prove that we only need two of them, such as & and ~.

We can show that by adding one step to our TFC algorithm. The TFC algorithm has three steps, so here’s what we add:

Step 4: In the sentence that we have created, eliminate the disjunctions using this equivalence: ~(~X&~Y) ⇔ XvY.

For example, last section we generated this sentence using the algorithm: (P&~Q&R)v(~P&Q&R)v(~P&~Q&R).

Following the pattern in the equivalence, we need to negate each of those three disjuncts, and then put a wide-scope negation around the whole thing, and finally turn the disjunctions into conjunctions.

So we write: ~(~(P&~Q&R)&~(~P&Q&R)&~(~P&~Q&R)).

{ &, ~} is TFC
{ v, ~} is TFC

What our new algorithm shows is that with just this set of connectives: { &, ~}, we can express any possible truth function.

But this isn’t something special about conjunction. We could have given disjunction the glory using this equivalence: ~(~Xv~Y) ⇔ X&Y. So disjunction and negation together are also TFC.

Your turn to practice.

These early successes make it seem like truth functional completeness is easy to come by. As if any two connectives will do.

But that’s not so. For example, { &, v} is not TFC. In order to prove that, all we need to do is provide a counterexample: a truth function that that set of connectives can’t express.

That is because TFC requires the connectives to express any possible truth function. A single counterexample will do.

Our counterexample is negation: the set { &, v} can never express negation.

The problem isn’t that negation is unary and conjunction and disjunction are binary connectives. Putting one atomic in both input places, like P&P or PvP, makes them act like unary connectives.

{ &, v} is not TFC

The problem is that the truth function for negation, FT, has F on the top row. But & and v both have T on the top row. That means that, no matter how complex we make the sentence, ANY sentence made up of conjunctions and disjunctions will always have T in the top row.

So they will never be able to express negation.

Next, consider what happens when we add the conditionals.

{ &, v, →, ↔} is not TFC

The conditional and biconditional are both T on the top row, just like conjunction and disjunction. So even with all four of them, we’ll never be able to express negation.

{~} is not TFC

Negation alone is also not TFC. For one thing, it has an expressive limitation because it is unary, but that problem is not insurmountable. We can create a binary connective like P*Q, whose truth function is just equivalent to ~P.

Even with that problem fixed, negation still isn’t TFC. The deeper problem is that it can never express a tautology or taut-falsity, because negation alone will always have some Ts and some Fs.

Now that we’ve covered Boolean connectives, let’s see if you can figure out the conditional.

Now, were you just guessing, or can you justify your answer with a proof?

Remember the way we proved that { &, ~} and { v, ~} are TFC. We added a fourth step to the TFC algorithm, using an equivalence principle.

To prove that { →, ~} is TFC, we just need to add a fifth step to the proof of { v, ~}, using another equivalence principle.

Remember, the reason we want this equivalence principle is so we can take a sentence that only has negation and disjunctions in it, are rewrite it so it only has negations and arrows.

{ →, ~} is TFC

That is why we want the equivalence with PvQ on one side: no matter what the disjuncts look like, we can rewrite it as ~P→Q. If that still doesn’t make sense, look again at the top of this section at how we specified step 4.

That might make it seem like negation and anything is not TFC, but that’s not so. For example, ~ and ↔ are not TFC, though we won’t go over the proof here.

How about one connective alone? We saw that negation alone is not TFC. It is also clear that conjunction alone, or disjunction alone, is not TFC, since even together they were not TFC. The same goes for the conditional alone and the biconditional.

None of our connectives alone is TFC.

That makes it seem like no connective alone could be TFC. That’s the question we’ll answer in the next section.

20.4 More TFC