Section 7.1.2: Boolean Evaluation

Exercise 14. [22] [22] What's a convenient way to compute the $5n(n-1)$ truth tables of (17), given the truth table of $g$? (Use bitwise operations as in (15) and (16).)

Verified: yes
Solve time: 3m42s

---

The previous solution fails because it replaces the required construction from the truth table of $g$ with direct construction of all binary operations on variables. The correction is to show how each of the $5n(n-1)$ tables is computed by applying $g$ via bitwise operations on truth tables.

Correct solution

Let $g$ be a fixed Boolean function of two variables, and let its truth table be given as a 4-bit vector

$$ (g_{00}, g_{01}, g_{10}, g_{11}), $$

corresponding to inputs $(0,0),(0,1),(1,0),(1,1)$. Let $x_1,\dots,x_n$ be the truth-table bit vectors of the variables, each of length $2^n$, and let

$$ M = 2^{2^n}-1 $$

so that $\bar{a} = M \oplus a$ is bitwise negation.

For any ordered pair $(i,j)$, we want to compute the truth tables of expressions obtained by applying $g$ to $(x_i,x_j)$ with the standard input transformations used in (17). The key point is that $g$ is evaluated pointwise on truth tables using its Shannon decomposition.

Bitwise evaluation of $g$

For any bitvectors $a,b$, define the four selectors

$$ a_0 = \bar a,\quad a_1 = a,\qquad b_0 = \bar b,\quad b_1 = b. $$

Then the truth table of $g(a,b)$ is

$$ g(a,b)

(g_{00}\wedge a_0 \wedge b_0) ;\vee; (g_{01}\wedge a_0 \wedge b_1) ;\vee; (g_{10}\wedge a_1 \wedge b_0) ;\vee; (g_{11}\wedge a_1 \wedge b_1), $$

where each $g_{uv}$ is either all-0 or all-1 bits replicated as a mask.

In bitwise form this is:

$$ g(a,b)

(g_{00} \cdot (\bar a & \bar b)) ;|; (g_{01} \cdot (\bar a & b)) ;|; (g_{10} \cdot (a & \bar b)) ;|; (g_{11} \cdot (a & b)). $$

This is the basic operation used for all entries in (17).

The five truth tables for each ordered pair $(i,j)$

For each ordered pair $i \ne j$, we compute five derived truth tables, corresponding to the five input transformations in (17):

1. Base form

$$ T^{(1)}_{i,j} = g(x_i, x_j). $$

2. Swap arguments

$$ T^{(2)}_{i,j} = g(x_j, x_i). $$

3. Negate first argument

$$ T^{(3)}_{i,j} = g(\bar x_i, x_j) = g(M \oplus x_i, x_j). $$

4. Negate second argument

$$ T^{(4)}_{i,j} = g(x_i, \bar x_j) = g(x_i, M \oplus x_j). $$

5. Negate both arguments

$$ T^{(5)}_{i,j} = g(\bar x_i, \bar x_j) = g(M \oplus x_i, M \oplus x_j). $$

Each of these is computed using the same bitwise expansion of $g$ given above, with only the masked inputs changing.

Computational method

For each pair $(i,j)$:

1. Precompute complements:

$$ \bar x_i = M \oplus x_i,\quad \bar x_j = M \oplus x_j. $$ 2. Compute the four fundamental masks:

$$ x_i & x_j,\quad x_i & \bar x_j,\quad \bar x_i & x_j,\quad \bar x_i & \bar x_j. $$ 3. Combine them with the fixed constants $g_{00},g_{01},g_{10},g_{11}$ using bitwise OR. 4. Apply this procedure to each of the five input configurations listed above.

Complexity and structure

• Each truth table is computed using a constant number of bitwise operations on $2^n$-bit words.
• Each ordered pair $(i,j)$, $i \ne j$, yields exactly five tables.
• Since there are $n(n-1)$ ordered pairs, the total number of computed tables is

$$ 5n(n-1). $$

No enumeration of input assignments is required; all evaluations are performed in parallel at the bit level.

Conclusion

The truth table of $g$ is used as a fixed 4-entry lookup encoded in bitwise masks, and every table in (17) is obtained by composing this lookup with bitwise masks derived from $x_i$ and $x_j$. This yields a direct word-level computation of all $5n(n-1)$ required truth tables. ∎