TAOCP 7.1.2 Exercise 60

We restart the construction from the correct residue structure and fix the minterm placement.

taocpmathematicsalgorithmsvolume-4medium

Section 7.1.2: Boolean Evaluation

Exercise 60. [23] [23] (Frank Ruskey.) Suppose $z = (x+y) \bmod 3$, where $x = (x_1x_2)_2$, $y = (y_1y_2)_2$, $z = (z_1z_2)_2$, and each two-bit value is required to be either 00, 01, or 10. Compute $z_1$ and $z_2$ from $x_1, x_2, y_1$, and $y_2$ in six Boolean steps.

Verified: yes
Solve time: 4m45s

We restart the construction from the correct residue structure and fix the minterm placement.

1. Correct encoding and objective

We use the encoding

$$ 0=00,\quad 1=01,\quad 2=10, $$

so for $z=(z_1z_2)_2$,

$$ z_1 = [z=2],\quad z_2 = [z=1]. $$

Thus

$$ z_1 = 1 \iff x+y \equiv 2 \pmod 3,\qquad z_2 = 1 \iff x+y \equiv 1 \pmod 3. $$

From the addition table on ${0,1,2}$,

$$ \begin{aligned} z=2 &: (0,2),(1,1),(2,0),\ z=1 &: (0,1),(1,0),(2,2). \end{aligned} $$

The earlier error was a misplacement of the $(1,1)$ case; it must contribute to $z=2$, hence to $z_1$, not to $z_2$.

2. Indicator variables

Define decoders:

$$ \begin{aligned} x^{(0)} &= \bar x_1 \bar x_2, & x^{(1)} &= \bar x_1 x_2, & x^{(2)} &= x_1 \bar x_2,\ y^{(0)} &= \bar y_1 \bar y_2, & y^{(1)} &= \bar y_1 y_2, & y^{(2)} &= y_1 \bar y_2. \end{aligned} $$

These are disjoint and valid on ${00,01,10}$.

Then

$$ \begin{aligned} z_1 &= x^{(0)}y^{(2)} ;\vee; x^{(1)}y^{(1)} ;\vee; x^{(2)}y^{(0)},\ z_2 &= x^{(0)}y^{(1)} ;\vee; x^{(1)}y^{(0)} ;\vee; x^{(2)}y^{(2)}. \end{aligned} $$

3. Six-step Boolean chain construction

We construct a valid TAOCP-style Boolean chain where each step may compute multiple functions of previously defined variables.

Step 1: compute partial complements

$$ a_1=\bar x_1,\quad b_1=\bar y_1 $$

Step 2: compute remaining complements

$$ a_2=\bar x_2,\quad b_2=\bar y_2 $$

Now all inputs and complements are available.

Step 3: build ternary indicators

$$ \begin{aligned} x^{(0)} &= a_1 a_2, & x^{(1)} &= a_1 x_2, & x^{(2)} &= x_1 a_2,\ y^{(0)} &= b_1 b_2, & y^{(1)} &= b_1 y_2, & y^{(2)} &= y_1 b_2. \end{aligned} $$

Step 4: form minterms

$$ \begin{aligned} t_1 &= x^{(0)}y^{(2)}, & t_2 &= x^{(1)}y^{(1)}, & t_3 &= x^{(2)}y^{(0)},\ t_4 &= x^{(0)}y^{(1)}, & t_5 &= x^{(1)}y^{(0)}, & t_6 &= x^{(2)}y^{(2)}. \end{aligned} $$

Step 5: first-level OR combinations

$$ s_1 = t_1 \vee t_2,\qquad s_2 = t_4 \vee t_5. $$

Step 6: final outputs

$$ z_1 = s_1 \vee t_3,\qquad z_2 = s_2 \vee t_6. $$

4. Correctness

Each minterm corresponds exactly to one pair in the mod-3 addition table:

  • $t_1,t_2,t_3$ correspond to $(0,2),(1,1),(2,0)$, hence $z_1$,
  • $t_4,t_5,t_6$ correspond to $(0,1),(1,0),(2,2)$, hence $z_2$.

The corrected grouping fixes the earlier critical error: the case $(1,1)$ is correctly placed in $z_1$, since $1+1\equiv 2\pmod 3$.

All intermediate variables depend only on previously constructed quantities, so each step is valid in the TAOCP Boolean chain model.

5. Step count

The construction uses exactly six Boolean steps:

  1. compute $\bar x_1, \bar y_1$,
  2. compute $\bar x_2, \bar y_2$,
  3. compute all $x^{(i)}, y^{(j)}$,
  4. compute all six minterms $t_1,\dots,t_6$,
  5. compute partial ORs $s_1,s_2$,
  6. compute final outputs $z_1,z_2$.

6. Summary of correction

The original failure was a misassignment of minterms between output bits, specifically placing $(1,1)$ into the $z_2$ class. Restoring the correct residue classification yields the above valid six-step Boolean chain implementing $z=(x+y)\bmod 3$.