WORK IN PROGRESS. Please do not comment.

It is frequently stated that NAND gates can implement any logic function, which although correct, is not the full picture, which is developed here. With simple reasoning and truth tables, the universal Boolean functions are determined. These universal functions are capable of expressing any Boolean function, however complex that function might be. This is couched in terms of Boolean functions and arguments, not in the hardware oriented terms of gates and inputs, as the facts presented are properties of Boolean algebra, not particular devices.

Proofs will be presented for two key statements. Firstly that

All Boolean functions, of any number of arguments, can be expressed in terms of a specific Boolean function of two arguments, provided this is the NAND or the NOR function: no other function will do.

and secondly that

All Boolean functions, of any number of arguments, can be expressed in terms of the NAND function alone, or can be expressed in terms of the NOR function alone.

The proof of the first statement is constructive, that is, it is not merely an existence theorem. The usefulness of the proof is limited however, due to the somewhat arbitrary nature of the process used to reduce a complex expression to an expression involving functions of two arguments only. The proof of second statement is very practical indeed, enabling an expression to be written in terms of the NAND function, or in terms of the NOR function, more or less by inspection.

Proving the Statements

Proof of First Statement

All Boolean functions of three or more arguments can be expressed as functions of two arguments only, by a tedious but elementary method, as shown in Boolean Function Reduction.
Reference to a list of all functions of two arguments, such as Boolean Functions Classified, shows that these include all the functions of fewer arguments. Thus, it suffices to consider only functions with two arguments, then show that universal functions exist, and enumerate them all.

Anticipating the method developed in the proof of the second statement, it is a simple matter to express each of the 16 functions of two arguments in terms of the NAND function, and to do the same in terms of the NOR function. The difficult part of proving the first statement is showing this to be impossible using any of the other functions with two arguments.

The concept of values preserved is the key to determining which functions can be universal functions. Any function which has the value true when all its arguments happen to have the value true is said to preserve true. Among the functions with only two arguments, the AND, OR, EQUIVALENCE and IMPLICATION functions preserve true, but the NAND, NOR, XOR and INHIBIT functions do not. Similarly, a function which has the value false when all its arguments happen to have the value false is said to preserve false, and of the functions with two arguments, AND, OR, XOR and INHIBIT functions preserve false, but NAND, NOR, EQUIVALENCE and IMPLICATION functions do not. Observe that the NAND and NOR functions do not preserve either true or false.

The intention is to construct an expression for some general function with two arguments, in terms of a single, universal function with two arguments. To distinguish the arguments of the general function from the argument of our universal function in an expression, the arguments of the universal function will be referred to as variables.

Suppose that a candidate universal function preserves true. Then we can consider the case when all the arguments of the general function are true, but the value of this function need not be. If the candidate preserves true, we can consider the case that all variables are true. It is known that the general function need not preserve true, but our


Let such a function be chosen, and consider forming an expression involving this function, and given variables. These variables are the arguments of a general function, which is to be synthesized using the chosen function. Using any combination of the variables as arguments of the chosen function, each of which correspond to an expression involving the function, when all variables are true, the value of the chosen function will be true. Using the value of this

Similarly, a function giving the value false when both arguments are false cannot express another which has the value true when both arguments are false, and so cannot be universal.

A universal function must give the value false when both arguments are true, and the value true output when both arguments are false. With these two lines of the four line truth table fixed, the possible truth tables are

The two NOT functions involve only one argument, and therefore cannot be used to take account of two arguments, and the only remaining candidates for universal functions are NOR and NAND. It remains to be shown that each alone can implement all other functions.

Every function is expressible in terms of AND, OR and NOT function, as shown in Boolean Expressions from Truth Tables, so we now need to show that these functions can all be expressed in terms of NAND alone, or in terms of NOR alone.

Using only the function NAND ( A, B ) = NOT ( A AND B ), we derive:
 

Using only the function NOR ( A, B ) = NOT ( A OR B ), we derive:
 

Proof of Second Statement

Both the NAND and NOR functions may have more than two arguments, and the number of arguments used may be chosen to suit the occasion. This simplifies the implementation of a general function, by avoiding the need to express the function in terms of functions of only two variables. Given any function specified in terms of a truth table, a Boolean expression can be derived in either the sum of products form, or the product of sums form. Both forms are always possible, as shown in Boolean Expressions from Truth Tables.

These two forms have several features in common. The arguments of the given function are used, either literally or in complemented form, to give terms. These terms are combined, using a primary logic connective, which is the AND function in the sum of products form, and the OR function in the product of sums form. The intermediate values thus obtained are combined using a secondary logic connective, which is the OR function in the sum of products form, and the AND function in the product of sums form. This added abstraction of primary and secondary connective may seen an unnecessary complication, but it takes on concrete form, and simplifies the description, as the two forms are now considered separately.

Sum of Products Form

The expression of a function as a sum of products leads directly to an expression using only NAND functions. The primary AND connective forms the logical products, then the secondary OR connective forms the logical sum of those products. The terms appearing in the products are either literal or complemented arguments of the original function, but the NOT function needed for any complement is obtained from a NAND function, by using NOT A = NAND ( A,A ) as shown above.

The NAND function may be considered to give the complement of the product of its arguments, so that, if used as the primary connective, the NAND function gives the complement of the required intermediate value. By de Morgan's Laws, the NAND function may also be considered to give the sum of the complements of its arguments, so that, if used as the secondary connective, the intermediate values must be complemented. This fits perfectly with the results given by use of NAND functions as the primary connective, so that a sum of products can be expressed as a NAND of NANDs by inspection.

Product of Sums Form

The expression of a function as a product of sums leads directly to an expression using only NOR functions. The primary OR connective forms the logical sums, then the secondary AND connective forms the logical product of those sums. The terms appearing in the sums are either literal or complemented arguments of the original function, but the NOT function needed for any complement is obtained from a NOR function, by using NOT A = NOR ( A,A ) as shown above.

The NOR function may be considered to give the complement of the sum of its arguments, so that, if used as the primary connective, the NOR function gives the complement of the required intermediate value. By de Morgan's Laws, the NOR function may also be considered to give the product of the complements of its arguments, so that, if used as the secondary connective, the intermediate values must be complemented. This fits perfectly with the results given by use of NOR functions as the primary connective, so that a sum of products can be expressed as a NOR of NORs by inspection.

Summary

Summarising the above, it has been proved that

All Boolean functions, of any number of arguments, can be expressed in terms of the NAND function alone, or can be expressed in terms of the NOR function alone.

Practicalities

The implementation of functions in terms of NAND or NOR functions can readily be performed. The resulting implementation is correct, but may not be optimum. As examples, implementations of the XOR (exclusive or) function will be found in both NAND and NOR forms. The XOR function can be expressed as a sum of products as ( A AND NOT ( B ) ) OR ( NOT ( A ) AND B ), or as a product of sums as ( A OR B ) AND ( NOT ( A ) OR NOT ( B ) ).

For NAND implementation of a function, it is usually best to use the sum of products form of the expression representing that function. The function takes the form X OR Y, where X is A AND NOT ( B ) and Y is NOT ( A ) AND B. The sum X OR Y is formed as NAND ( NOT ( X ), NOT ( Y ) ). The two complemented products, NOT ( X ) and NOT ( Y ) then become NAND functions, without further manipulation. For instance, NOT ( A AND NOT ( B ) ) is just NAND ( A, NOT ( B ) ). The XOR function can therefore be implemented as NAND ( NAND ( A, NOT ( B ) ), NAND ( NOT ( A ), B ) ), and with a little practice such an implementation can be produced directly from the sum of products expression.

For NOR implementation of a function, it is usually best to use the product of sums form of the expression representing that function. The function takes the form X AND Y, where X is A OR B  and Y is NOT ( A ) OR NOT ( B ). The product X AND Y is formed as NOR ( NOT ( X ), NOT ( Y ) ). The two complemented sums, NOT ( X ) and NOT ( Y ) then become NOR functions, without further manipulation. For instance, NOT ( A OR B ) is just NOR ( A, B ). The XOR function can therefore be implemented as NOR ( NOR ( A, B ), NOR ( NOT ( A ), NOT ( B ) ) ), and with a little practice such an implementation can be produced directly from the product of sums expression.

The NAND implementation given above for the XOR function is not the 'standard' solution, but was presented to show the basic method used. The XOR function is so frequently required (for example in arithmetic units and parity generators) that it has been highly optimised. In this case, the optimum form is obtained if the term A AND NOT ( B ) is expanded to A AND ( NOT ( A ) OR NOT ( B ) ) and the term NOT ( A ) AND B is expanded to( NOT ( A ) OR NOT ( B ) ) AND B. These expansions are counter-intuitive, but both expansions collapse to the original form when the developed in full and redundant terms are eliminated. They have the common expression NOT ( A ) OR NOT ( B ), which of course is NAND ( A, B ). The optimised form of XOR is then NAND ( NAND ( A, NAND ( A, B ) ), NAND ( B, NAND ( A, B ) ).