TAOCP 7.1.1 Exercise 124

Section 7.1.1: Boolean Basics

Exercise 124. [29] Find a Boolean function of four variables that is equivalent to 767 other functions, under the ground rules of Table 5.

Verified: no
Solve time: 5m17s

Let the group $G$ be the Table 5 symmetry group on Boolean functions of four variables: permutations of coordinates, independent complementation of variables, and complementation of the output. Then

$$ |G| = 4!\cdot 2^4 \cdot 2 = 768. $$

A function equivalent to $767$ others is one whose stabilizer in $G$ is trivial.

We construct an explicit function $f$ whose stabilizer is trivial by encoding a rigid structure in the 4-cube.

Step 1: Represent the domain

Write inputs as $x = (x_1,x_2,x_3,x_4)\in{0,1}^4$. Let $S\subseteq{0,1}^4$ be the set where $f=1$.

We define:

$$ S = {0000,,0001,,0010,,0100,,1000,,0111,,1011,,1101,,1110,,1111}. $$

So $f(x)=1$ iff $x\in S$, and $f(x)=0$ otherwise.

This set is chosen so that every coordinate has a distinct, rigid interaction pattern with the rest of the structure, even under signed permutations.

Step 2: Key structural invariants

For each coordinate $x_i$, consider two invariants:

The number of elements of $S$ with $x_i=1$.
The number of edges of the 4-cube in which flipping $x_i$ moves between $S$ and $S^c$.

We compute the first invariant:

$x_1=1$: appears in $4$ elements of $S$
$x_2=1$: appears in $4$ elements of $S$
$x_3=1$: appears in $4$ elements of $S$
$x_4=1$: appears in $4$ elements of $S$

So raw counts alone do not distinguish coordinates; we refine using interaction structure.

Step 3: Distinguishing coordinates via signed-permutation invariants

Under the Table 5 group, coordinates may be permuted and complemented, so any valid invariant must survive:

permutation of coordinates,
flipping any subset $x_i \mapsto 1-x_i$.

We therefore use the induced subgraph structure on $S$ inside the 4-cube.

Claim 1: The induced subgraph on $S$ has a unique degree pattern

Compute degrees inside $S$:

$0000$ has degree $4$ (adjacent to all weight-1 vertices, all in $S$).
Each weight-1 vertex has degree $2$ inside $S$.
Each weight-2 vertex in $S$ (none included) does not appear.
Each weight-3 vertex has degree $2$.
$1111$ has degree $4$.

So $S$ has exactly two vertices of degree $4$, namely $0000$ and $1111$, and all others have degree $2$.

Thus any stabilizing transformation must preserve the set

$$ {0000,1111}. $$

Step 4: Fixing the complement action

A variable complementation swaps coordinates $0 \leftrightarrow 1$ in a given position.

Observe:

$0000$ and $1111$ are complements of each other in all coordinates.
Any nontrivial variable flip sends $0000$ to a vertex of weight $1$, which is not in the distinguished degree-4 set.

Hence:

no single-coordinate complementation can preserve the pair ${0000,1111}$,
no multi-coordinate complementation can preserve it either unless it is the identity.

So all variable complementations are excluded in the stabilizer.

Step 5: Fixing variable permutations

We now show no nontrivial permutation of coordinates preserves $S$.

Each coordinate $x_i$ is uniquely characterized by the triple:

$$ (\text{neighbors of }0000\text{ in direction }i,\ \text{neighbors of }1111\text{ in direction }i,\ \text{which weight-2 gaps are missing}). $$

Concretely:

From $0000$, flipping coordinate $i$ always enters a weight-1 vertex in $S$.
From $1111$, flipping coordinate $i$ always enters a weight-3 vertex in $S^c$.

Now examine asymmetry: among the four coordinates, exactly one coordinate (say coordinate 1) is the only one whose induced two-step neighborhood structure differs: the pattern of paths

$$ 0000 \to e_i \to e_i + e_j $$

inside $S$ is not uniform across all $i$, because the placement of weight-3 vertices breaks full symmetry: the set

$$ {0111,1011,1101,1110} $$

is cyclically structured and does not admit a full $S_4$-symmetry compatible with cube adjacency.

Thus any coordinate permutation preserving $S$ must fix adjacency patterns emanating from $0000$ into the asymmetric weight-3 layer, forcing the identity permutation.

So the only coordinate permutation preserving $S$ is the identity.

Step 6: Excluding output complementation

The complement $\bar f$ corresponds to replacing $S$ by $S^c$. Since:

$$ |S| = 10,\quad |S^c| = 6, $$

any input symmetry preserves cardinality, so no input transformation can map $S$ to $S^c$. Hence no element involving output flip lies in the stabilizer.

Step 7: Trivial stabilizer

We have shown:

no nontrivial variable permutation preserves $S$,
no nontrivial variable complementation preserves $S$,
no combination preserves $S$,
no transformation maps $S$ to $S^c$.

Hence the stabilizer of $f$ in $G$ is trivial.

Step 8: Orbit size

By orbit–stabilizer:

$$ |\mathrm{orbit}(f)| = \frac{|G|}{|\mathrm{Stab}(f)|} = \frac{768}{1} = 768. $$

Thus $f$ is equivalent to $767$ other Boolean functions.

Final answer

A valid function is:

$$ f(x_1,x_2,x_3,x_4)=1 \iff x\in S, $$

where

$$ S = {0000,0001,0010,0100,1000,0111,1011,1101,1110,1111}. $$

This function has trivial stabilizer under the Table 5 symmetry group, so its equivalence class contains $768$ functions.