Functional Completeness More about propositional logic

Any formula of propositional logic has a truth table. That is, for any assignment of truth values to its atoms, the formula itself gets a truth value. Semantically, then, it expresses a function from truth values to truth values, with as many arguments (inputs) as there are atoms in the formula. We call such an operation on truth values a truth function.

In the case of a unary function, with a single input corresponding to a single atom p, there are just four truth functions, which we may list as follows:

p	1	2	3	4
0	0	0	1	1
1	0	1	0	1

Clearly, all four of these are expressible by means of formulae using the atom p. Function 2 is the truth table for p itself, while function 3 is NOTp. Function 4 is expressed by any tautology such as p IMP p, and function 1 by a contradiction such as p AND NOTp.

Where there are two atoms, each truth table has four lines. Each of the four may be 0 or 1 (false or true) independently of the others, so there are 2⁴ or 16 possible binary truth functions:

p	q	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

These, too, can all be expressed in terms of p and q using the standard connectives. For example, function 14 is p IMP q while function 5 is q AND NOTp. You may amuse yourself by finding short formulae to express all the others.

16 is not a large number, but as the number of atoms increases, the number of truth functions grows dramatically. For three atoms, there are eight lines in the truth table, and 2⁸ or 256 truth functions, and generally for n atoms there are 2²ⁿ truth functions. That is, the number of truth functions is hyper-exponential in the vocabulary. It rapidly becomes very big. For example, for just 8 atomic formulae, the number of truth functions is 2²⁵⁶ which is on the scale of the number of particles in the observable universe—and eight sentences are hardly an extravagant basis for describing the world! Add a ninth atom (e.g. to describe three people in terms of three predicates) and the number of truth functions approaches the square of the number of particles: if every particle in the observable universe were another entire universe, the number of particles in all that is about how many non-equivalent things we can say with just nine atoms.

I haven't counted them, but the generally accepted estimate of the number of particles is somewhere around 10⁸⁰. Since 2²⁵⁶ is a little over 10⁷⁷, these numbers are within hand-waving distance of each other. Anyway, the moral is that with eight propositional atoms, you can say a lot!

The question arises, then, whether all truth functions are expressible using just the handful of connectives we normally study in propositional logic. The answer is yes, and the proof of this fact is actually quite simple. Consider, for example, the 3-adic truth function given by the table:

p	q	r	?
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	0

This is true in three cases, shown by the three occurrences of '1' in the table. Look at the first of these cases: the case in which p and q are false but r is true. We can easily construct a formula to be true in exactly that one case: NOTp AND NOTq AND r will do. Similarly, NOTp AND q AND r is true in exactly the one case where p is false and q and r are true, and finally the line having p and q true but r false is captured by p AND q AND NOTr. Here are the tables for those three conjunctions:

p	q	r	?	NOTp AND NOTq AND r	NOTp AND q AND r	p AND q AND NOTr
0	0	0	0	0	0	0
0	0	1	1	1	0	0
0	1	0	0	0	0	0
0	1	1	1	0	1	0
1	0	0	0	0	0	0
1	0	1	0	0	0	0
1	1	0	1	0	0	1
1	1	1	0	0	0	0

All we then need to do in order to obtain the desired truth function is to form the disjunction of these three formulae:

(NOTp AND NOTq AND r)  OR  (NOTp AND q AND r)  OR  (p AND q AND NOTr)

In virtue of the truth table for disjunction, this will get the value 1 wherever one of the three components has value 1, and will get 0 everywhere else, which is to say it has exactly the target truth table. Clearly, the technique is general: for any number of atoms and any required pattern of 1 and 0, form the conjunctions of literals necessary to specify all the lines getting 1, and disjoin the results. This does not generally give the shortest formula expressing the truth function in question, but it is at least always guaranteed to work.

This method of defining formulae to express truth functions always results in a formula in disjunctive normal form—a disjunction of conjunctionms of literals. It gives us an alternative proof (without going through any process of transformation) that every formula has an equivalent in disjunctive normal form, because clearly every formula has a truth table, which may be expressed as described. It also shows that negation, conjunction and disjunction are sufficient to express all truth functions. We say that the set {NOT, AND, OR} is functionally complete.

In view of De Morgan's laws, any formula of the form A OR B has an equivalent NOT(NOTA AND NOTB) which uses only conjunction and negation, so in fact disjunction is not needed for functional completeness: {NOT, AND} is already functionally complete. The set {NOT, OR} is similarly functionally complete, since conjunction can be expressed in terms of disjunction and negation, using another of De Morgan's laws. Moreover, since A OR B is equivalent to NOTA IMP B, we could use implication and negation instead of disjunction and negation, so {NOT, IMP} is also a functionally complete set of connectives.

By contrast, the set {AND, OR, IMP, IFF} is not functionally complete. This is quite easy to observe: if all atoms have the value 1, then all compounds made with these four connectives also have the value 1. In such a case, we say 1 is a fixed point for these operations. It follows that we cannot express any truth function which takes 1 to 0, so we cannot express negation, for example, with these connectives.

In general, to show that a set of connectives is functionally complete, we just need to show that they can define negation and any one of AND, OR or IMP. To show that they are not functionaly complete, there are two ways. The elegant proof method is to find a property they all share and preserve, like the fixed point noted above. We call this an invariant of the construction, and any truth function (negation in the example) not sharing the property is unreachable. Another example of a set which fails to be functionally complete is {IFF, NOT}, where one suitable invariant is that every definable truth function has an even number of "1" values in its table. The set {AND, OR, XOR} is also not functionally complete, as the value 0 is a fixed point for all of these connectives. Invariants for all functionally incomplete sets may be extracted from the classic work on sets of boolean functions by Emil Post Post.

The alternative to elegance is hard work: we may simply go laboriously through the possibilities, applying the chosen connectives to all the formulae (with up to two atoms) we reach, until we have tried all possibilities. If one of the 16 binary truth functions remains unreached, we know it cannot be generated from the chosen basis, so we have out negative result.

A curiosity worth noting is the connective NAND, sometimes called "Sheffer's stroke":

A / B   =   NOT(A AND B)

Clearly, p / p has the same truth table as NOTp, so negation is expressible in terms of NAND. Conjunction and NAND are the negations of each other, so p AND q has the same truth table as (p / q) / (p / q). Since conjunction and negation are expressible, so is every truth function, so {/} is functionally complete all by itself. The same is true of NOR, the negation of disjunction.