Boolean Algebra | Truth Tables | Expressions from Truth Tables
Universal Functions | Function Reduction | Functions Classified

This Entry concerns Boolean Algebra¹, and proves a statement about Boolean functions. It shows that Boolean functions having three or more arguments may be expressed as a composition of functions having only two arguments, including a method for achieving this simplification. This implies that:

Any Boolean function, no matter how complex, can be implemented using electronic logic devices having only two inputs.

Definition of a Boolean Function

A general Boolean function has a number of arguments, and a unique value depending only upon those arguments - with the arguments and function value being limited to one of two distinct values, which we shall call true and false. Such a function is completely defined by a truth table, which we shall assume has no don't care entries, and no duplicate entries².

Argument Extraction

Suppose we have a function of n > 2 arguments, F say, represented by its truth table. We can select any argument, which we shall call X, and use it to split the given truth table into two equal parts, tables P and Q, say, by the following procedure.

Each entry in the table for F is examined in turn, and used to create a modified truth table item with X omitted. If the value of X was false, then the new item is added to table P, and if X was true the new item is added to table Q.

When this process is complete, the tables P and Q will each have only half the number of entries present in the F table. None of the details of F are lost, since the splitting process is readily reversed, by taking all the entries in P augmented with an argument X of value false, and adding all the entries in Q augmented with an argument X of value true³.

If the truth table of F is valid, then for every combination of arguments it contains one entry. It therefore contains entries where X is false with every combination of the other arguments, and entries where X is true with every combination of the other arguments. Thus each of the tables P and Q included every combination of all arguments of F except for X, and hence are valid truth tables for functions of n - 1 arguments. This justifies supposing that tables P and Q represent functions, which may as well be called P and Q respectively.

When X is false, the value of F is given by P, and when X is true, the value of X is given by Q, and hence

F = ( ( NOT X ) AND P ) OR ( X AND Q )

Using two auxiliary functions A and B, defined by A = ( NOT X ) AND P and B = X AND Q gives F = A OR B

Thus we have expressed F as a composition of functions of two arguments, and the sub-functions P and Q.

Completing the Simplification

We have shown that a function F of n arguments can be expressed as a composition of functions of two arguments, and the sub-functions P and Q, which have n-1 arguments only.

But the procedure used can also be applied to the sub-functions, each time reducing the number of arguments in the new sub-functions which are produced. Thus we must eventually reach a point where the sub-functions produced are functions of two arguments only.

All of the sub-functions produced by such repetition are combined using functions of two arguments only and hence we have shown that

All functions of more than two arguments can be expressed as compositions of functions of only two arguments.

Practical Note

The final composition of F obtained by this method may be far from optimum, in terms of the complexity of the expression which results. It is very dependent upon the order in which variables are extracted. However, the fact that this simplification is always possible is a useful guarantee for more heuristic methods.