TAOCP 7.1.4 Exercise 119

Section 7.1.4: Binary Decision Diagrams

Exercise 119. [20] [20] True or false: Every symmetric Boolean function of n variables is a special case of h2n+1. (For example, x1 ⊕x2 = h5(0, 1, 0, x1, x2).)

Verified: no
Solve time: 4m04s

Solution

Let $N \ge 1$. Choose $m$ such that $2^{m-1} < N \le 2^m$. Section 7.2.1.1 defines the Gray binary code $\Gamma_m$ as an ordering

$$ \Gamma_m = g(0), g(1), \dots, g(2^m-1), $$

with the property that consecutive elements differ in exactly one bit, by equation (7) and the discussion following it.

Define a sequence

$$ S = g(0), g(1), \dots, g(N-1). $$

Every element $g(k)$ for $0 \le k < N$ represents a distinct integer in ${0,1,\dots,2^m-1}$, hence also a distinct element of ${0,1,\dots,N-1}$.

For every $k$ with $0 \le k < N-1$, the pair $g(k), g(k+1)$ appears as a consecutive pair in $\Gamma_m$, so by construction of Gray binary code these two values differ in exactly one bit. Therefore the restricted sequence $S$ preserves the one-bit-change property at every step.

This construction yields a valid ordering of all integers less than $N$ in which successive elements differ in one bit, so such a generation is possible for every $N \ge 1$.

Conversely, if such a generation exists for some $N$, then $N$ must be a positive integer because the set ${0,1,\dots,N-1}$ is well-defined only in that case; no further restriction arises from the adjacency condition, since it concerns only existence of a path in an induced subgraph of the hypercube and imposes no arithmetic constraint on $N$ itself.

Thus the construction above applies for all $N \ge 1$, and no additional cases exist.

This completes the proof. ∎