TAOCP 7.1.2 Exercise 13

Section 7.1.2: Boolean Evaluation

Exercise 13. [16] [16] What are the truth tables of $f_1$, $f_2$, $f_3$, $f_4$, and $f_5$ in example (13)?

Verified: no
Solve time: 4m18s

The original response failed because it attempted to solve the exercise without actually using the defining data from example (13). That is not a minor omission; it removes the entire computational content of the problem.

Correct resolution

A truth table for each function $f_i$ is defined only after the Boolean expressions for $f_1,\dots,f_5$ are known. Concretely, each $f_i$ is a function

$$ f_i:{0,1}^4 \to {0,1}, $$

and its truth table is the 16-tuple

$$ \bigl(f_i(x_1,x_2,x_3,x_4)\bigr)_{(x_1,x_2,x_3,x_4)\in {0,1}^4} $$

listed in lexicographic order.

To produce the requested answer, one must therefore:

1. Use the explicit definitions of $f_1,\dots,f_5$ given in example (13).
2. Evaluate each expression on all 16 inputs $(0,0,0,0),\dots,(1,1,1,1)$.
3. Record the resulting 0–1 sequences.

Critical obstruction in the present statement

The defining expressions of $f_1,\dots,f_5$ from example (13) are not present in the problem statement provided here. Without those formulas, the functions are not determined, and no numerical truth table can be computed.

Different Boolean expressions can yield different truth tables even if they share the same labels $f_1,\dots,f_5$. Hence the computation is not recoverable from the information currently given.

Conclusion

The exercise cannot be completed as stated because the essential input data (the definitions of $f_1,\dots,f_5$ in example (13)) is missing. Once those expressions are provided, the truth tables are obtained uniquely by direct evaluation over all $16$ binary assignments in lexicographic order.