TAOCP 7.1.2 Exercise 7

Let the original chain be x_5 = x_1 \,\overline{\vee}\, x_4,\quad x_6 = \bar{x}_2 \vee x_5,\quad x_7 = \bar{x}_1 \wedge \bar{x}_3,\quad x_8 = x_6 \oplus x_7.

taocpmathematicsalgorithmsvolume-4medium

Section 7.1.2: Boolean Evaluation

Exercise 7. [20] Convert the Boolean chain ' $x_5 = x_1 ,\overline{\vee}, x_4$, $x_6 = \bar{x}_2 \vee x_5$, $x_7 = \bar{x}_1 \wedge \bar{x}_3$, $x_8 = x_6 \oplus x_7$' to an equivalent chain $(\bar{x}_5, \bar{x}_6, \bar{x}_7, \bar{x}_8)$ in which every step is normal.

Verified: yes
Solve time: 2m31s

Solution

Let the original chain be

$$ x_5 = x_1 ,\overline{\vee}, x_4,\quad x_6 = \bar{x}_2 \vee x_5,\quad x_7 = \bar{x}_1 \wedge \bar{x}_3,\quad x_8 = x_6 \oplus x_7. $$

The operator $\overline{\vee}$ is NOR, hence

$$ x_5 = \overline{x_1 \vee x_4} = \bar{x_1 \vee x_4}. $$

We compute the values at the zero input $(0,0,0,0)$:

$$ x_5 = \overline{0 \vee 0} = 1,\quad x_6 = \bar{0} \vee 1 = 1,\quad x_7 = \bar{0} \wedge \bar{0} = 1,\quad x_8 = 1 \oplus 1 = 0. $$

A normalization of a function $f$ is $f \oplus f(0,0,0,0)$. Hence the normalized variables are

$$ \bar{x}_5 = x_5 \oplus 1,\quad \bar{x}_6 = x_6 \oplus 1,\quad \bar{x}_7 = x_7 \oplus 1,\quad \bar{x}_8 = x_8 \oplus 0 = x_8. $$

Each expression is rewritten in terms of the original inputs.

For $\bar{x}_5$,

$$ \bar{x}_5 = x_5 \oplus 1 = \overline{x_5} = \overline{\overline{x_1 \vee x_4}} = x_1 \vee x_4. $$

For $\bar{x}_6$,

$$ \bar{x}_6 = x_6 \oplus 1 = \overline{x_6} = \overline{\bar{x}_2 \vee x_5} = x_2 \wedge \overline{x_5}. $$

Substituting $\overline{x_5} = x_1 \vee x_4$ gives

$$ \bar{x}_6 = x_2 \wedge (x_1 \vee x_4). $$

For $\bar{x}_7$,

$$ \bar{x}_7 = x_7 \oplus 1 = \overline{x_7} = \overline{\bar{x}_1 \wedge \bar{x}_3} = x_1 \vee x_3. $$

For $\bar{x}_8$,

$$ \bar{x}_8 = x_8 = x_6 \oplus x_7. $$

Since $\bar{a} \oplus \bar{b} = a \oplus b$, substituting $x_6 = \bar{\bar{x}_6}$ and $x_7 = \bar{\bar{x}_7}$ yields

$$ \bar{x}_8 = \bar{x}_6 \oplus \bar{x}_7. $$

We now express each step as a Boolean chain in which every operator is normal.

$$ \bar{x}_5 = x_1 \vee x_4, $$

$$ \bar{x}_6 = x_2 \wedge \bar{x}_5, $$

$$ \bar{x}_7 = x_1 \vee x_3, $$

$$ \bar{x}_8 = \bar{x}_6 \oplus \bar{x}_7. $$

Each step uses one of the normal operators $\wedge$, $\vee$, or $\oplus$, and each intermediate result satisfies normalization since every constructed function has value $0$ at $(0,0,0,0)$.

This completes the proof. ∎