A Boolean function with *n* variables can be seen as a function from an
*n*-tuple of Booleans to a Boolean. Alternatively, we can describe the
function by the set of *n*-tuples for which the output is "true".

Consider all functions for which this set contains only one element. We will
refer to these functions as "singletons". There are a total of
2^{n} singletons. Because we want to produce all *m*
possible output functions, we will, in particular, need to produce all
singletons. In fact, after we produce the 2^{n} singletons, the
rest of the functions can be created easily by OR-ing singletons. (Except for
the always-"false" function, but that can be created using "*A* AND NOT
*A*", where *A* is the input to any of the existing negation gates.
Alternatively, one can produce the always-"false" function by AND-ing any two
singletons.)
The number we
seek is therefore equal to the number of NOT gates required to create the
2^{n} singletons.

Let *M _{i}*, for

To show this, suppose that the number of negations actually used is *k*,
then let *f _{i}*, for

Suppose now that some *M _{i}* is describable as the intersection
of some subset of the

We therefore need at least *n*+1 masks. As all these masks are
intersections of subsets of the same *k* variables, we know that
*k*≥log_{2}(*n*+1), which is what we were trying to prove.

Now that we know it's impossible to solve with less than
*k*=ceil(log_{2}(*n*+1)) negations, we turn to the
constructive task of showing how to create any singleton (and thereby any
function) using just *k* NOT gates.

The *k* functions *f _{i}* in this case will be, by the order
in which we construct them, as follows. Let the Hamming weight of a tuple
be the number of "true" values in it. The function

In order to describe any singleton of weight *w* we merely AND the relevant
function with the AND of the *w* variables that participate in the tuple
that the singleton returns "true" for.

It is now left only to show that the *f _{i}* functions can be
computed by a single negation each. This is done by induction: after

Side-note: A natural follow-up question to this one is "is this solution
unique?". The answer can be found by considering that the *t _{i}*
used form a particular path from the all-"false" tuple to
the all-"true" tuple, and we could have chosen any other such path of length

To show this, consider, again, the tuples *t*_{0} through
*t*_{n}. Let us name the Boolean function we are trying to
implement *B*, and let us define the function *F*(*i*) to
be 1 if *B*(*t*_{i}) is "true" and 0 if it is "false".
*F* is a numerical function that occasionally increases and
occasionally decreases in value.

Here are some interesting properties regarding the function *F*:

- If
*B*is simply one of the basic variables (a gate array with no gates at all in it),*F*never decreases. - If
*B*can be described as an AND/OR combination of certain inputs (whether basic variables or pre-computed functions),*F*can only decrease in places where the corresponding*F*-function of at least one of the inputs also decreases. *F*has at most one more place in which it increases than in which it decreases.- A negation transforms every increase of the input to a decrease of the output, and vice versa.

Suppose *B* is the negation of the XOR of the original inputs.
Its *F* function is 1, 0, 1, 0, .... . This means that it decreases
floor((*n*+1)/2)=ceil(*n*/2) times. For this to happen, its gate
array must include at least *k* gates, where *k* satisfies
2^{k}-1≥ceil(*n*/2). This means that *k* is at
least ceil(log_{2}(ceil((*n*+2)/2))), which is simply
ceil(log_{2}(*n*+2))-1.

To show that this is not only a bound but also the worst-case, we present
an explicit construction for a gate array with this number of negations that
implements a general function, *B*.

We begin by recalling that
in Part 2, above, we showed how a singleton function can be described as the
intersection of two functions, *m _{i}* and

Because in Part 2 we needed to be able to represent every function with the
same *m _{i}* masks, there was only one possible choice of
masks. In Part 3 we can mold a set of

Let us define *m _{i}*, for 0≤

*t*has Hamming weight 2*i*.*t*has Hamming weight 2*i*+1 and*B*(*t*)="true".*t*has Hamming weight 2*i*-1 and*B*(*t*)="false".

*t*has Hamming weight greater than 2*i*.*t*has Hamming weight 2*i*and*B*(*t*)="true".

It remains to be shown that all these masks can be represented by the desired
number of negations. The reader is welcomed to verify that
what we need is a procedure that produces
from *k* negations 2^{k} masks. For this we can use a
procedure completely analogous to that described in Part 2. Our
*f _{i}* functions for this purpose will be the union of all

Here is an interesting follow-up question to Part 3: We have shown that if only
a single function is calculated, this allows us (for certain values of *n*)
to save a single NOT gate over what is needed in order to calculate all *m*
functions. This is an easy proof that (for these *n* values) it is not
always possible to extend a gate array that calculates any specific function,
*f*, into a gate array that calculates all *m* functions without
requiring to add additional NOT gates. Let us
extend this observation to gate arrays from *n* to 2. These calculate two
functions, *f* and *g*. The question is, for which (*f*,*g*)
pairs is it always possible to extend any gate array calculating both *f*
and *g* into a gate array calculating all *m* functions, without
requiring for this to add additional NOT gates into the gate array. There are
exactly four such (*f*,*g*) pairs for any *n*. Can you find
them? (This follow-up question was developed jointly with Eli Biham. Thank
you, Eli!)