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 2n 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 2n 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 2n singletons.
Let Mi, for i ranging between 0 and n be the singleton that only returns "true" given the tuple ti=(x0,..., xn-1), where xj is true if j<i and false otherwise. We will show that in order to implement all n+1 of these singletons, one needs at least ceil(log2(n+1)) negations.
To show this, suppose that the number of negations actually used is k, then let fi, for i ranging from 1 to k, be the functions at the output of each individual NOT gate. Suppose now that these functions were all precomputed and that their outputs are given to us as additional inputs to the gate array. If so, then we now need to build a gate array from n+k inputs to m outputs, and we will not need for this negations at all. In fact, if we're only interested in singletons then there's also no reason to ever use OR gates. The singletons should all be describable as the intersection of a subset of the n+k inputs.
Suppose now that some Mi is describable as the intersection of some subset of the n+k inputs. We'll refer to the corresponding intersection of the precomputed variables as mi, where m stands for "mask". Clearly, mi cannot be true for the tuple in which any other Mj with j>i is true, because if the intersection of the original variables was true for the i'th tuple, it will also be true for the j'th tuple. This indicates that each mask can only be used in the description of a single Mi.
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≥log2(n+1), which is what we were trying to prove.
Now that we know it's impossible to solve with less than k=ceil(log2(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 fi 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 fi will be the function that yields "true" iff the Hamming weight of its input tuple is less than 2k-i modulo 2k+1-i. It is easy to ascertain that all functions that return "true" iff the input tuple is of some given Hamming weight w can be represented as the intersection of k elements, where the i'th element is either fi or its negation (depending on the chosen value of w).
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 fi functions can be computed by a single negation each. This is done by induction: after i negations we have the ability to create the functions that are true for tuples with Hamming weight between 2k-is and 2k-i(s+1) for any s. These can each be intersected with the function that is true for all tuples of Hamming weight at least w=2k-i(s+0.5) [which is simply the OR of all ANDS of w basic variables]. The OR of all these intersections is a function that is "true" iff the Hamming weight of its input tuple is at least 2k-i modulo 2k+1-i, so by negating it we calculate fi+1 as desired, completing the construction.
Side-note: A natural follow-up question to this one is "is this solution unique?". The answer can be found by considering that the ti 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 n+1, instead. From this observation, it is easy to show that our choice of mi is unique, and that if n is a Mersenne number, then so is our choice of fi and the order in which the fi are calculated.
To show this, consider, again, the tuples t0 through tn. 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(ti) 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:
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 2k-1≥ceil(n/2). This means that k is at least ceil(log2(ceil((n+2)/2))), which is simply ceil(log2(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, mi and ai, where the first is a mask (which, specifically, was true for the tuples with Hamming weight i) and the second was a function that can be calculated using AND gates alone. A general function is an OR of several singletons, so to represent it we calculate the union of several intersections of such mi and ai. More economically, we can group all ai that relate to the same mi together. This will result in a representation of a general function as the union of several intersections between an mi (a different mi in each case) and a gi, where gi is a general AND/OR function (but with no negations).
Because in Part 2 we needed to be able to represent every function with the same mi masks, there was only one possible choice of masks. In Part 3 we can mold a set of mi to meet the specific requirements of the function at hand.
Let us define mi, for 0≤i≤ceil(n/2), to be a function that returns "true" for a tuple t iff one of the following is 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 2k masks. For this we can use a procedure completely analogous to that described in Part 2. Our fi functions for this purpose will be the union of all mi satisfying that i is smaller than 2k-i modulo 2k+1-i. The details of this are left to the reader. We note that the same procedure works for any set of masks chosen such that the mi form a pairwise-disjoint division of the entire tuple space, and the union of all mi with i≥j, for any j, is a function that can be calculated without negations.
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!)
Back to riddle
Back to main page