# Boolean Function Reduction

Created | Updated Jul 9, 2013

Boolean Algebra
| Truth Tables
| Expressions from Truth Tables

Universal Functions
| Function Reduction
| Functions Classified

This Entry concerns Boolean Algebra^{1}, 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^{2}.

### 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*^{3}.

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.

^{1}Named after George Boole (1815 - 1864), an English mathematician.

^{2}These assumptions are not a restriction on the function, but only on the form of truth table.

^{3}The definition of

*F*is not changed if the entries in its truth table are rearranged.