Using your Head is Permitted

August 2009 solution

Part 2:

The answer is that such a construction requires ceil(log2(n+1)) negations. Here's why.

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.

Part 3:

The number of negations needed to represent any specific Boolean function is ceil(log2(n+2))-1. This means that if n is a Mersenne number, one doesn't save on negations at all by having to implement only one function (in the worst case), compared to having to implement all functions together. In other cases, the saving is of a single NOT gate.

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:

  1. If B is simply one of the basic variables (a gate array with no gates at all in it), F never decreases.
  2. 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.
  3. F has at most one more place in which it increases than in which it decreases.
  4. A negation transforms every increase of the input to a decrease of the output, and vice versa.
Putting all this together, we get that if the maximal number of decrease positions after k negations is d(k), then after an additional negation it cannot be more than 2d(k)+1: the negation adds decreases everywhere where the function that was negated increases, but this can not be more than d(k)+1 places, because it couldn't have decreased in more than d(k) places, so at most d(k)+1 new decrease places were introduced, bringing the grand total to 2d(k)+1. This means that after a single negation this happens at most once, after two negations - three times, after three negations - seven times, and, in general, d(k)=2k-1.

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:

  1. t has Hamming weight 2i.
  2. t has Hamming weight 2i+1 and B(t)="true".
  3. t has Hamming weight 2i-1 and B(t)="false".
The corresponding gi functions are such that gi returns "true" for a tuple t iff one of the following is true:
  1. t has Hamming weight greater than 2i.
  2. t has Hamming weight 2i and B(t)="true".
It is easy to verify that all gi functions can be implemented without any NOT gates. Furthermore, it is easy to verify that the union of all mi AND gi is the required function.

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 ij, 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