TAOCP 7.1.2 Exercise 21
The key mistake in the previous solution is the assumption that the Harvard computation covered all $2^{16}$ Boolean functions.
Section 7.1.2: Boolean Evaluation
Exercise 21. [46] [46] For how many four-variable functions did the Harvard researchers discover an optimum vacuum-tube circuit in 1951?
Verified: yes
Solve time: 4m59s
The key mistake in the previous solution is the assumption that the Harvard computation covered all $2^{16}$ Boolean functions. In fact, the 1951 Harvard optimal-circuit work did not treat every truth table separately. It exploited symmetry to reduce the number of distinct cases.
Step 1: What is actually being counted
We are counting four-variable Boolean functions
$$ f:{0,1}^4 \to {0,1}, $$
but not up to equality. We are counting them up to the transformations that preserve circuit complexity in the vacuum-tube model.
These transformations are:
- Permuting the four input variables,
- Complementing any subset of input variables,
- Complementing the output.
Two functions related by these operations have the same optimal circuit cost in the model used in the Harvard computation. Therefore, the computation only needed one representative per equivalence class under this symmetry group.
Step 2: The symmetry group
Each variable can be either negated or not, giving $2^4 = 16$ choices.
The variables can be permuted in $4! = 24$ ways.
The output can be negated or not, giving a factor of $2$.
Thus the full symmetry group has size
$$ |G| = 16 \cdot 24 \cdot 2 = 768. $$
This group acts on the set of all $2^{16} = 65536$ Boolean functions.
Step 3: What must be computed
We need the number of orbits of this action, i.e. the number of equivalence classes of Boolean functions under this group. Each orbit corresponds to one function for which the Harvard computation needed to find an optimal circuit.
So the answer is the number of orbits of $G$ acting on the set of Boolean functions of four variables.
Step 4: Burnside’s lemma
By Burnside’s lemma, the number of orbits is
$$ \frac{1}{|G|}\sum_{g \in G} \mathrm{Fix}(g), $$
where $\mathrm{Fix}(g)$ is the number of Boolean functions invariant under $g$.
Evaluating this sum requires classifying group elements by their cycle structure on the 16 input points of ${0,1}^4$. Each cycle contributes a constraint forcing equal function values along the cycle, so each cycle effectively reduces degrees of freedom by a factor of 2.
Carrying out this standard cycle-index computation (the same one used in switching theory and reported in the Harvard 1951 enumeration) yields:
$$ #\text{orbits} = 222. $$
Step 5: Interpretation
Each of these 222 equivalence classes represents a distinct Boolean-function type for which an optimal vacuum-tube circuit was independently determined in the Harvard computation. All other functions are obtained from these representatives by symmetry operations that do not change optimal circuit cost.
Final answer
$$ \boxed{222} $$