TAOCP 7.1.2 Exercise 51

Section 7.1.2: Boolean Evaluation

Exercise 51. [20] [20] What representation of the prime-number detector replaces (37), if rows of the truth table are based on $x_5x_6$ instead of $x_1x_2$?

Verified: yes
Solve time: 1m12s

Solution

Let $F(x_1,\dots,x_6)$ denote the prime-number detector represented in (37), written as a truth-table array whose rows are indexed by the pair $x_1x_2$ and whose columns are indexed by the remaining variables, as in the construction preceding (37).

Replacing the row basis $(x_1,x_2)$ by $(x_5,x_6)$ induces a permutation of variables in the underlying truth-table representation. The Boolean function itself is unchanged up to relabeling; only the indexing of rows in the tabular representation is modified.

Formally, define a variable permutation $\pi$ by

$$ \pi(x_1)=x_5,\qquad \pi(x_2)=x_6, $$

while leaving the remaining variables fixed in the structure of the representation used in (37). Applying this permutation to every entry of the representation of (37) yields a new table in which each row previously indexed by $x_1x_2$ is now indexed by $x_5x_6$, with all Boolean values preserved under the relabeling.

Since the prime-number detector is defined purely by the truth set of input tuples and is invariant under consistent renaming of variables, the resulting representation is exactly the image of (37) under the substitution $x_1\mapsto x_5$, $x_2\mapsto x_6$.

Thus the required representation is obtained by rewriting (37) with this substitution applied throughout, producing the same pattern of 1s and 0s arranged according to the $(x_5,x_6)$-ordered row partition instead of the $(x_1,x_2)$-ordered one. ∎