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

It is frequently stated that NAND gates can implement any logic function. Although this is correct, it does not give 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. These are:

1. 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.

2. 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.

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 functions of fewer arguments. Thus, it suffices to consider only functions of two variables, show that universal functions then exist, and enumerate them.

Suppose that a function gives the value true when both arguments are true. Then, no matter how such functions are composed, it will be impossible to obtain the value false. Thus, such a function cannot express another which has the value false when both arguments are true, and so cannot be universal.

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 functions, 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.

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 seem 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 in our example 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, using only the expressions derived above. 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 in our example 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, using only the expressions derived above. 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 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 ) ).