Functional Completeness

Introduction

From the previous set of notes, you know that any truth table can be implemented from using just AND₂, OR₂, and NOT.

Considering that there are an infinite number of Boolean functions, it's amazing that they can all be built from only 3 Boolean functions.

The set of functions {AND₂, OR₂, NOT } are said to be functionally complete.

Here's a definition:

Definition A set of Boolean functions is functionally complete, if all other Boolean functions can be constructed from this set and a set of input variables are provided.

We imagine that there is a set of input Boolean variables to these functions, and that these functions can be applied as many times as needed.

If you were a mathematician, you're next thought should be "are there functionally complete sets with fewer Boolean functions?" and the natural follow-up "what's the minimum number of Boolean functions that are functionally complete?". The answer is yes and 1.

Implementing a Boolean function with only AND₂ and NOT

It's rather easy to get rid of OR. We only have to apply two properties of Boolean functions.

Double Negation \\x == x. If you negate any expression (x can be an arbitrary Boolean function, not just a Boolean variable), it is functionally equivalent to the expressoin itself.
DeMorgan's Law There are two forms of this law.
- Negation of AND
  \(xy) == \x + \y
  If you negate the conjunction two Boolean expressions, x and y, this changes the AND to and OR, and negates the expressions. This can be verified by truth tables.
- Negation of OR
  \(x + y) == \x\y
  If you negate the disjunction of two Boolean expressions, x and y, this changes the OR to and AND, and negates the expressions. This can be verified by truth tables.

From the previous set of notes, you should know that any truth table can be written as a sum of products. This has the following general form.

  Z = P₁ + P₂ + ... + P_k

where P_i consists of literals connected by AND₂. In particular, P_i = l₁l₂..l_m where l_i is a literal.

The expression Z, above, can be written equivalent as:

  Z = NOT( NOT( P₁ + P₂ + ... + P_k ) )

This is an application of double-negation.

Then, apply DeMorgan's Law on the inner negation.

  Z = NOT( \P₁ * \P₂ * ... * \P_k ) )

Notice that the ORs changed to ANDs when applying one level of DeMorgan's Law, and that each of the product terms now has a negation (indicated by the prime). We don't apply DeMorgan's any further. In particular, we leave P_i' alone because we don't want to convert the ANDs in the P_i to ORs.

As you can see, by applying double negation and DeMorgan's Law once, there are no more OR₂.

You should try applying these laws to show that OR₂ and NOT are also functionally complete.

Are AND₂ and OR₂ functionally complete?

The answer is no. { AND₂, OR₂ } is not a functionally complete set. Consider any function composed of these two functions. Suppose you set all the input variables' values to 1. Then, the output is always 1, regardless of how you put the function together.

Similarly, if you set all the input variables' values to 0, the output of the function is always 0, no matter how you create the function.

However, you can clearly define a truth table whose output is 1 when all the input variable's values are all 0's, and whose output is 0 when all the input variable's values are all 1's. You can't implement such a circuit using only { AND₂, OR₂ }.

This is the intuition behind why { AND₂, OR₂ } is not functionally complete. You could prove this by induction, too.

Can It Be Done Using One Boolean Function?

Is it possible that only a single Boolean function is functionally complete. It turns out { AND₂ } and { OR₂ } are not functionally complete, for the same reasons that { AND₂, OR₂ } is not functionally complete. Also, { NOT } is not functionally complete. You can only create two truth tables by composing NOT (namely, NOT, and the identity function), and both functions have a single bit of input.

Does that mean it's not possible? Of course, we have many other Boolean functions we haven't tried. At the very least, we know that if there is a single function, it must have at least two inputs, otherwise, we couldn't construct Boolean functions with two or more inputs.

It turns out that there are two functionally complete sets that only have one function in it: { NAND₂ } and { NOR₂ }.

It's easy to argue that both are functionally complete. Let's show how to do it with NAND₂. The argument is similar for NOR₂.

To show that NAND₂ is functionally complete, all we have to do is show how to use NAND₂ to implement functions in a set we've already seen is functionally complete.

In particular, we'll implement { AND₂, NOT } using only NAND₂.

NOT x can be implemented as NAND₂(x, x), which can also be written as x NAND₂ x. This can be verified using a truth table. Note: x refers to an arbitrary Boolean expression, not just a variable.
Once you have NOT implemented, then you can implement AND₂(x, y) as NOT( NAND₂(x, y). Negating NAND₂ gives you AND₂.

You can show NOR₂ is functionally complete by implementing OR₂ and NOT.

Why NAND and NOR?

You will sometimes see circuits implemented using only NANDs or using only NORs, and the reason for this is because they are functionally complete and minimal. You only have to build the circuit using one kind of gate. Of course, using a single gate is likely to make the circuit "larger", i.e., more gates than using many different kinds of gates, but usually it's worth the tradeoff, i.e., it's better to use more of one kind of gate than fewer of many different gates.

Summary

A functionally-complete set of Boolean function consists of a set of Boolean functions from which you can construct all Boolean functions. { AND₂, NOT }, { NOR₂, NOT }, { NAND₂ }, {NOR₂ } are four functionally-complete sets.

Web Accessibility