TAOCP 7.1.2: Boolean Evaluation
Section 7.1.2 exercises: 85/85 solved.
Section 7.1.2. Boolean Evaluation
Exercises from TAOCP Volume 4 Section 7.1.2: 85/85 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [24] | medium | verified | 7m11s |
| 2 | [21] | medium | solved | 8m12s |
| 3 | [M23] | math-medium | solved | 6m34s |
| 4 | [M28] | math-hard | solved | 8m11s |
| 5 | ▶ [21] | medium | solved | 5m54s |
| 6 | [20] | medium | verified | 6m15s |
| 7 | [20] | medium | verified | 2m31s |
| 8 | ▶ [20] | medium | verified | 6m12s |
| 9 | [20] | medium | verified | 2m05s |
| 10 | ▶ [20] | medium | solved | 6m28s |
| 11 | ▶ [22] | medium | solved | 8m11s |
| 12 | [15] | simple | verified | 6m02s |
| 13 | [16] | medium | solved | 4m18s |
| 14 | [22] | medium | verified | 3m42s |
| 15 | [28] | hard | solved | 5m26s |
| 16 | [HM23] | hm-medium | solved | 6m11s |
| 17 | ▶ [25] | medium | solved | 8m04s |
| 18 | ▶ [35] | hard | solved | 2m46s |
| 19 | [M22] | math-medium | solved | 3m55s |
| 20 | ▶ [40] | project | solved | 1m49s |
| 21 | [46] | research | verified | 4m59s |
| 22 | [21] | medium | verified | 3m18s |
| 23 | ▶ [23] | medium | solved | 6m04s |
| 24 | [47] | research | solved | 33m07s |
| 25 | ▶ [17] | medium | verified | 2m18s |
| 26 | [25] | medium | solved | 4m33s |
| 27 | ▶ [23] | medium | solved | 5m52s |
| 28 | [26] | hard | solved | 3m46s |
| 29 | [M28] | math-hard | solved | 10m54s |
| 30 | [M25] | math-medium | solved | 3m20s |
| 31 | [21] | medium | solved | 4m06s |
| 32 | [HM16] | hm-medium | solved | 2m54s |
| 33 | [HM22] | hm-medium | solved | 8m15s |
| 34 | ▶ [22] | medium | solved | 4m42s |
| 35 | [23] | medium | solved | 11m20s |
| 36 | ▶ [M28] | math-hard | solved | 5m09s |
| 37 | [M28] | math-hard | solved | 5m48s |
| 38 | [25] | medium | solved | 6m52s |
| 39 | ▶ [M21] | math-medium | solved | 4m14s |
| 40 | [25] | medium | solved | 5m35s |
| 41 | [M22] | math-medium | solved | 2m58s |
| 42 | [30] | hard | verified | 4m38s |
| 43 | ▶ [28] | hard | verified | 5m19s |
| 44 | ▶ [26] | hard | verified | 1m40s |
| 45 | [HM20] | hm-medium | verified | 1m48s |
| 46 | ▶ [HM21] | hm-medium | solved | 4m59s |
| 47 | [M23] | math-medium | solved | 3m28s |
| 48 | [HM23] | hm-medium | verified | 1m53s |
| 49 | [HM25] | hm-medium | verified | 3m47s |
| 50 | [24] | medium | verified | 4m51s |
| 51 | [20] | medium | verified | 1m12s |
| 52 | [23] | medium | solved | 3m53s |
| 53 | [HM22] | hm-medium | solved | 4m |
| 54 | [29] | hard | verified | 5m10s |
| 55 | [24] | medium | solved | 5m59s |
| 56 | ▶ [16] | medium | verified | 1m38s |
| 57 | [19] | medium | verified | 1m20s |
| 58 | ▶ [30] | hard | solved | 4m53s |
| 59 | [29] | hard | solved | 4m27s |
| 60 | [23] | medium | verified | 4m45s |
| 61 | [24] | medium | verified | 3m58s |
| 62 | [HM23] | hm-medium | solved | 5m01s |
| 63 | [HM35] | hm-hard | solved | 2m05s |
| 64 | [25] | medium | verified | 2m49s |
| 65 | ▶ [35] | hard | verified | 1m15s |
| 66 | [20] | medium | verified | 1m31s |
| 67 | ▶ [40] | project | solved | 4m51s |
| 68 | [M25] | math-medium | verified | 2m30s |
| 69 | [M24] | math-medium | solved | 4m51s |
| 70 | ▶ [M27] | math-hard | solved | 2m48s |
| 71 | ▶ [M26] | math-hard | verified | 1m54s |
| 72 | [M24] | math-medium | verified | 4m52s |
| 73 | ▶ [20] | medium | solved | 5m39s |
| 74 | [25] | medium | solved | 2m10s |
| 75 | [20] | medium | verified | 1m10s |
| 76 | ▶ [M26] | math-hard | solved | 2m45s |
| 77 | ▶ [35] | hard | solved | 4m27s |
| 78 | [26] | hard | solved | 4m50s |
| 79 | [32] | hard | solved | 4m09s |
| 80 | ▶ [M29] | math-hard | solved | 4m22s |
| 81 | [23] | medium | solved | 5m59s |
| 82 | ▶ [M32] | math-hard | verified | 4m53s |
| 83 | [21] | medium | solved | 6m16s |
| 84 | [M30] | math-hard | verified | 3m41s |
| 85 | ▶ [M28] | math-hard | solved | 9m26s |
TAOCP 7.1.2 Exercise 1
The key issue in the previous attempt is that it treated a mixed Boolean expression as if it could be freely reassociated using distributivity identities that do not hold.
TAOCP 7.1.2 Exercise 2
The previous solution fails because it treats “padding by tautologies” as if it does not affect either depth or cost in the TAOCP circuit model.
TAOCP 7.1.2 Exercise 3
Let $S=\{a^{(1)},\dots,a^{(k)}\}\subseteq\{0,1\}^n$ be the set of inputs on which $f$ is true.
TAOCP 7.1.2 Exercise 4
The lower bound is correct.
TAOCP 7.1.2 Exercise 5
We restart from the _actual TAOCP constructional meaning_ of the angle-bracket operator used in Exercise 7.
TAOCP 7.1.2 Exercise 6
We prove the statement: A Boolean function $f(x_1,\ldots,x_n)$ is normal (i.
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.
TAOCP 7.1.2 Exercise 8
Let $n$ be fixed and work in Knuth’s truth-table order, where the row indexed by $j\in\{0,\dots,2^n-1\}$ corresponds to the binary expansion of $j$, and $x_k(j)$ is the $k$-th binary digit of $j$, i.
TAOCP 7.1.2 Exercise 9
Algorithm L assigns to each normal Boolean function $f$ its minimum length $L(f)$ but does not retain any information about how the value $L(f)$ is achieved.
TAOCP 7.1.2 Exercise 10
We restart from a clean separation between **syntactic formula depth** and the **algorithm’s labels**, removing all circular use of the computed function $D$.
TAOCP 7.1.2 Exercise 11
The previous solution fails because it silently turned $U(f)$ into an exact-length function by assuming global optimality of decompositions.
TAOCP 7.1.2 Exercise 12
The previous solution failed because it replaced scheme (13) with an abstract left-fold instead of deriving the evaluation order actually defined in TAOCP.
TAOCP 7.1.2 Exercise 13
The original response failed because it attempted to solve the exercise without actually using the defining data from example (13).
TAOCP 7.1.2 Exercise 14
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.
TAOCP 7.1.2 Exercise 15
Let $S_k(x_1,\dots,x_n)$ denote the symmetric Boolean function that is $1$ iff exactly $k$ of its arguments are $1$.
TAOCP 7.1.2 Exercise 16
The previous argument fails because it tries to replace the actual structure of minimum-memory computation with arbitrary DAG compression and unproved “instruction bounds.
TAOCP 7.1.2 Exercise 17
The error in the previous solution is that it implicitly assumes a calling discipline on registers that was never enforced.
TAOCP 7.1.2 Exercise 18
Let $C_m(f)$ denote the minimum-memory complexity of a Boolean function $f(x_1,\ldots,x_5)$, defined as the least number of working registers required in a straight-line Boolean chain in which each st...
TAOCP 7.1.2 Exercise 19
Let a Boolean chain consist of variables x_1,\dots,x_n and successive definitions
TAOCP 7.1.2 Exercise 20
Working
TAOCP 7.1.2 Exercise 21
The key mistake in the previous solution is the assumption that the Harvard computation covered all $2^{16}$ Boolean functions.
TAOCP 7.1.2 Exercise 22
Let $S_k(x_1,\dots,x_n)$ be the Boolean function that equals $1$ iff exactly $k$ of its arguments are $1$.
TAOCP 7.1.2 Exercise 23
We restart from the correct symmetry analysis and then explain the extra identification that explains why Figure 10 contains 16 optimal chains even though the function symmetry count is 18.
TAOCP 7.1.2 Exercise 24
The previous solution fails at the only point where it matters: it does not establish a lower bound for tree complexity.
TAOCP 7.1.2 Exercise 25
Let $m = 2^{2^n}$, and let $f_0,\dots,f_{m-1}$ be the enumeration of all Boolean functions of $n$ variables, where $f_k(x_1,\dots,x_n)$ is defined by the binary expansion of $k$.
TAOCP 7.1.2 Exercise 26
The statement is **false**.
TAOCP 7.1.2 Exercise 27
The critical error in the previous solution is not merely a bookkeeping issue: it is a violation of the straight-line program model.
TAOCP 7.1.2 Exercise 28
Working
TAOCP 7.1.2 Exercise 29
The missing point in the previous solution is the justification that the block-combining circuit from Exercise 27 has constant depth.
TAOCP 7.1.2 Exercise 30
Let s(n)=s\!
TAOCP 7.1.2 Exercise 31
Solution to TAOCP 7.1.2 Exercise 31.
TAOCP 7.1.2 Exercise 32
The correct argument must stay within the structure of the explicit solution given in (30), and must not invoke characteristic polynomials or linear constant-coefficient recurrences.
TAOCP 7.1.2 Exercise 33
Let $m_i$ denote the minterm corresponding to the binary vector of $i$, for $0 \le i < 2^n$, where $m_i$ is the conjunction of literals $x_k$ or $\bar{x}_k$ according to the binary expansion of $i$.
TAOCP 7.1.2 Exercise 34
The construction must be repaired at the output stage and the definition of the suffix information must be made precise.
TAOCP 7.1.2 Exercise 35
Solution to TAOCP 7.1.2 Exercise 35.
TAOCP 7.1.2 Exercise 36
The error in the previous writeup is a conflation of _schedule phases_ with _critical-path length_.
TAOCP 7.1.2 Exercise 37
Let $p_k = x_1 \wedge x_2 \wedge \cdots \wedge x_k$.
TAOCP 7.1.2 Exercise 38
Let the inputs be $x_1,\dots,x_n \in \{0,1\}$, and let t=\sum_{j=1}^n x_j be the number of ones.
TAOCP 7.1.2 Exercise 39
The flaw in the previous solution is the separation of “selector construction” and a later “global OR stage.
TAOCP 7.1.2 Exercise 40
We restart the argument from the beginning, avoiding any assumption of sliding-window “updates.
TAOCP 7.1.2 Exercise 41
Let $A(n)$ denote the number of binary gates in an $n$-bit conditional-sum adder constructed recursively as described, and let $D(n)$ denote its depth.
TAOCP 7.1.2 Exercise 42
Let u_k = x_k \wedge y_k,\qquad v_k = x_k \oplus y_k,\qquad 0 \le k < n, and let $c_k$ be the carry bits in binary addition.
TAOCP 7.1.2 Exercise 43
Let the transducer be applied to input $a_1\cdots a_n$, producing outputs $b_1\cdots b_n$, with state sequence $q_0,q_1,\ldots,q_n$ defined by q_j = d(q_{j-1},a_j), \quad b_j = c(q_{j-1},a_j), as requ...
TAOCP 7.1.2 Exercise 44
Let inputs be $(x_1,\ldots,x_n)$ and $(y_1,\ldots,y_n)$, and define binary addition as in (25), producing sum bits $(z_1,\ldots,z_n)$ and carry bits $(c_1,\ldots,c_{n+1})$ with $c_1=0$.
TAOCP 7.1.2 Exercise 45
The expression $n^2(n+1)^2\cdots (n+r-1)^2$ treats the construction of a Boolean chain as if step $i$ allows an arbitrary independent choice of an ordered pair of earlier objects, with $(n+i-1)$ avail...
TAOCP 7.1.2 Exercise 46
Let $s=\lfloor 2^n/n\rfloor$.
TAOCP 7.1.2 Exercise 47
Let $f : \{0,1\}^n \to \{0,1\}^m$.
TAOCP 7.1.2 Exercise 48
Let F(n,r)=(r-1)!
TAOCP 7.1.2 Exercise 49
Let $F(r)$ be the number of Boolean functions on $n$ variables representable by formulas of length at most $r$.
TAOCP 7.1.2 Exercise 50
Let $x_1x_2x_3x_4$ be the binary representation of $0,\dots,15$ (with $x_1$ the most significant bit).
TAOCP 7.1.2 Exercise 51
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 v...
TAOCP 7.1.2 Exercise 52
The original argument fails because it replaces the actual expression (48) with an abstract separable model.
TAOCP 7.1.2 Exercise 53
The previous solution correctly derived the parameter scales but failed at the only step that matters in TAOCP asymptotics: substitution into the actual expression (48).
TAOCP 7.1.2 Exercise 54
A correct solution must explicitly construct a Boolean chain (an ordered sequence of allowed operations with reuse) and not merely describe a minterm expansion.
TAOCP 7.1.2 Exercise 55
The previous solution fails because it invents modular identities and then “accounts for sharing” without defining an actual Boolean circuit.
TAOCP 7.1.2 Exercise 56
A 4-variable Boolean function is represented by a truth table of length $16$.
TAOCP 7.1.2 Exercise 57
In Figure (45), the seven-segment encoding assigns a distinct display pattern to each 4-bit input $(x_1x_2x_3x_4)_2$, corresponding to the hexadecimal digits $0$ through $15$.
TAOCP 7.1.2 Exercise 58
Let $F:\{0,1\}^4\to\{0,1\}^4$ be a $4\times 4$-bit S-box written as F(x)=(f_1(x),f_2(x),f_3(x),f_4(x)).
TAOCP 7.1.2 Exercise 59
The previous solution fails because it misuses a vectorized Shannon node as a single step.
TAOCP 7.1.2 Exercise 60
We restart the construction from the correct residue structure and fix the minterm placement.
TAOCP 7.1.2 Exercise 61
The threshold computation for $t = [p \ge 5]$ is already correct, so the only task is to repair the conditional reduction step so that it actually implements subtraction of $5t$ in a consistent binary...
TAOCP 7.1.2 Exercise 62
The flaw in the previous solution is the overly crude and, more importantly, asymptotically lossy counting of Boolean chains, which artificially introduced an extra factor of $2$ in the exponent and f...
TAOCP 7.1.2 Exercise 63
We restart from the structure implicit in Exercises 62–63.
TAOCP 7.1.2 Exercise 64
Place the digits $1,\dots,9$ in the Lo Shu magic square \begin{array}{ccc} 8 & 1 & 6\\ 3 & 5 & 7\\ 4 & 9 & 2
TAOCP 7.1.2 Exercise 65
Let a tic-tac-toe position $P$ be a configuration of marks on the $3 \times 3$ board together with the player to move.
TAOCP 7.1.2 Exercise 66
The strategy in exercise 65 is a refinement of the optimal-play construction from (47)–(56), where each position is assigned a value under minimax evaluation: win, draw, or loss.
TAOCP 7.1.2 Exercise 67
The earlier solution failed at a single structural point: it replaced the minimax definition with an unproved rule hierarchy.
TAOCP 7.1.2 Exercise 68
Let $x = x_1 \ldots x_n$ and interpret it as an integer k = \sum_{i=1}^n x_i 2^{n-i}, \qquad 0 \le k < 2^n.
TAOCP 7.1.2 Exercise 69
Work in the Boolean ring $(\mathbb{F}_2,\oplus,\cdot)$.
TAOCP 7.1.2 Exercise 70
Let the $3 \times 3$ Boolean matrix $(60)$ be written in the standard form X = \begin{pmatrix} x_1 & x_2 & x_3 \\ x_4 & x_5 & x_6 \\
TAOCP 7.1.2 Exercise 71
Fix an assignment $y \in {0,1}^{n-3}$ to the variables ${x_1,\ldots,x_n}\setminus{x_i,x_\ell,x_m}$.
TAOCP 7.1.2 Exercise 72
Let $f : \{0,1\}^n \to \{0,1,*\}$ be a random function with independent pointwise distribution \mathbb{P}(f(x)=0)=p,\quad \mathbb{P}(f(x)=1)=q,\quad \mathbb{P}(f(x)=*)=r,\quad p+q+r=1.
TAOCP 7.1.2 Exercise 73
The reviewer correctly identifies that the previous argument relied on an unproved monotonicity principle.
TAOCP 7.1.2 Exercise 74
Let $P$ be the set of unordered pairs ${i,j}$ with $1 \le i < j \le n$ that have not yet been certified as satisfying or failing the decomposition condition tested by the Shen–McKellar–Weiner procedur...
TAOCP 7.1.2 Exercise 75
The function $S_{0,n}(x_1,\ldots,x_n)$ is the symmetric Boolean function that is true exactly when none of the variables are 1.
TAOCP 7.1.2 Exercise 76
We correct the argument by rebuilding the construction in a strictly sequential chain model and by explicitly separating what is computed once per $l$ and what is reused only within that single chain...
TAOCP 7.1.2 Exercise 77
The original proof fails because it tries to impose a Shannon-style decomposition on the _syntactic structure_ of a straight-line program.
TAOCP 7.1.2 Exercise 78
The previous solution fails because it tries to track “dependency sets” through gates and then infer structural constraints from how those sets “evolve under restriction.
TAOCP 7.1.2 Exercise 79
We work in the model of Boolean chains as in TAOCP: a chain is a binary tree whose internal nodes are binary operations, and whose leaves are variable occurrences (possibly repeated).
TAOCP 7.1.2 Exercise 80
The reviewer is correct that the previous proof does not establish the stated inequalities.
TAOCP 7.1.2 Exercise 81
The previous argument fails because it incorrectly tries to partition operations into “depth” and “span” contributions and then treats the depth $d$ as if it bounds a set of operations.
TAOCP 7.1.2 Exercise 82
The previous solution was incorrect in its interpretation of what is required.
TAOCP 7.1.2 Exercise 83
Let the given Boolean chain for $f(x_1,\dots,x_n)$ contain $p$ canalizing operations, listed in their order along the chain: g_1, g_2, \dots, g_p.