Using your Head is Permitted

August 2009 solution

Part 2:

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ⁿ 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ⁿ 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ⁿ singletons.

Let M_i, for i ranging between 0 and n be the singleton that only returns "true" given the tuple t_i=(x₀,..., x_n-1), where x_j 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(log₂(n+1)) negations.

To show this, suppose that the number of negations actually used is k, then let f_i, 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 M_i 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 m_i, where m stands for "mask". Clearly, m_i cannot be true for the tuple in which any other M_j 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 M_i.

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₂(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₂(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 f_i will be the function that yields "true" iff the Hamming weight of its input tuple is less than 2^k-i modulo 2^k+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 f_i 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 f_i 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 2^k-is and 2^k-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=2^k-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 2^k-i modulo 2^k+1-i, so by negating it we calculate f_i+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 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 n+1, instead. From this observation, it is easy to show that our choice of m_i is unique, and that if n is a Mersenne number, then so is our choice of f_i and the order in which the f_i are calculated.

Part 3:

To show this, consider, again, the tuples t₀ 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:

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.

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₂(ceil((n+2)/2))), which is simply ceil(log₂(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 a_i, 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 m_i and a_i. More economically, we can group all a_i that relate to the same m_i together. This will result in a representation of a general function as the union of several intersections between an m_i (a different m_i in each case) and a g_i, where g_i 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 m_i masks, there was only one possible choice of masks. In Part 3 we can mold a set of m_i to meet the specific requirements of the function at hand.

Let us define m_i, 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".

1. t has Hamming weight greater than 2i.
2. t has Hamming weight 2i 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 m_i satisfying that i is smaller than 2^k-i modulo 2^k+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 m_i form a pairwise-disjoint division of the entire tuple space, and the union of all m_i 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