TAOCP 7.1.4: Binary Decision Diagrams
Section 7.1.4 exercises: 267/267 solved.
Section 7.1.4. Binary Decision Diagrams
Exercises from TAOCP Volume 4 Section 7.1.4: 267/267 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | ▶ [20] | medium | solved | 2m08s |
| 2 | ▶ [21] | medium | solved | 3m14s |
| 3 | [16] | medium | solved | 2m47s |
| 4 | [21] | medium | solved | 3m27s |
| 5 | [20] | medium | solved | 3m14s |
| 6 | [10] | simple | solved | 2m55s |
| 7 | [21] | medium | solved | 3m08s |
| 8 | [22] | medium | solved | 5m16s |
| 9 | [16] | medium | solved | 4m17s |
| 10 | ▶ [21] | medium | solved | 4m12s |
| 11 | [20] | medium | solved | 4m26s |
| 12 | ▶ [M21] | math-medium | solved | 17m29s |
| 13 | [M15] | math-simple | solved | 3m34s |
| 14 | [M24] | math-medium | solved | 2m20s |
| 15 | [M23] | math-medium | solved | 5m50s |
| 16 | ▶ [22] | medium | solved | 3m14s |
| 17 | [32] | hard | solved | 6m15s |
| 18 | [13] | simple | solved | 3m39s |
| 19 | [20] | medium | solved | 5m |
| 20 | [15] | simple | verified | 1m53s |
| 21 | [05] | simple | verified | 51s |
| 22 | ▶ [M21] | math-medium | solved | 3m50s |
| 23 | ▶ [M20] | math-medium | verified | 3m14s |
| 24 | [M22] | math-medium | solved | 6m43s |
| 25 | [M20] | math-medium | solved | 5m18s |
| 26 | [M20] | math-medium | solved | 1m22s |
| 27 | ▶ [M26] | math-hard | solved | 2m43s |
| 28 | [M16] | math-medium | solved | 5m |
| 29 | [HM20] | hm-medium | solved | 5m56s |
| 30 | ▶ [M21] | math-medium | solved | 6m27s |
| 31 | [M21] | math-medium | solved | 4m36s |
| 32 | ▶ [M20] | math-medium | solved | 1m50s |
| 33 | ▶ [M22] | math-medium | solved | 2m48s |
| 34 | [M25] | math-medium | verified | 1m53s |
| 35 | ▶ [22] | medium | verified | 2m09s |
| 36 | [25] | medium | solved | 1m50s |
| 37 | [M20] | math-medium | solved | 4m34s |
| 38 | ▶ [27] | hard | solved | 2m25s |
| 39 | [M20] | math-medium | solved | 5m15s |
| 40 | ▶ [22] | medium | solved | 5m05s |
| 41 | [M25] | math-medium | solved | 5m08s |
| 42 | [22] | medium | solved | 3m57s |
| 43 | ▶ [22] | medium | solved | 3m19s |
| 44 | ▶ [M32] | math-hard | solved | 1m44s |
| 45 | [22] | medium | solved | 2m55s |
| 46 | [M23] | math-medium | solved | 1m45s |
| 47 | [M21] | math-medium | verified | 1m36s |
| 48 | [M22] | math-medium | solved | 4m56s |
| 49 | [20] | medium | solved | 5m48s |
| 50 | [22] | medium | solved | 4m40s |
| 51 | [22] | medium | solved | 5m02s |
| 52 | [20] | medium | solved | 5m07s |
| 53 | ▶ [23] | medium | solved | 5m41s |
| 54 | [17] | medium | solved | 6m24s |
| 55 | [M30] | math-hard | solved | 4m57s |
| 56 | [20] | medium | verified | 5m50s |
| 57 | [25] | medium | verified | 7m49s |
| 58 | [20] | medium | solved | 3m48s |
| 59 | ▶ [M28] | math-hard | verified | 2m04s |
| 60 | [M22] | math-medium | verified | 2m42s |
| 61 | ▶ [M27] | math-hard | solved | 5m32s |
| 62 | ▶ [M21] | math-medium | solved | 6m33s |
| 63 | [M27] | math-hard | solved | 4m47s |
| 64 | [M21] | math-medium | solved | 6m55s |
| 65 | ▶ [M25] | math-medium | solved | 11m40s |
| 66 | [20] | medium | solved | 9m48s |
| 67 | [24] | medium | solved | 5m58s |
| 68 | [20] | medium | solved | 5m48s |
| 69 | [21] | medium | verified | 1m33s |
| 70 | [21] | medium | verified | 1m33s |
| 71 | [20] | medium | verified | 1m49s |
| 72 | [25] | medium | verified | 1m39s |
| 73 | ▶ [25] | medium | verified | 4m22s |
| 74 | ▶ [M23] | math-medium | solved | 6m15s |
| 75 | [M20] | math-medium | solved | 9m33s |
| 76 | ▶ [M22] | math-medium | solved | 10m18s |
| 77 | ▶ [M35] | math-hard | solved | 7m12s |
| 78 | ▶ [25] | medium | solved | 7m28s |
| 79 | [20] | medium | solved | 5m21s |
| 80 | [23] | medium | solved | 4m05s |
| 81 | ▶ [20] | medium | solved | 3m56s |
| 82 | ▶ [25] | medium | solved | 4m08s |
| 83 | [M20] | math-medium | verified | 2m59s |
| 84 | [24] | medium | solved | 4m06s |
| 85 | [16] | medium | solved | 5m19s |
| 86 | ▶ [21] | medium | solved | 5m06s |
| 87 | [20] | medium | solved | 4m36s |
| 88 | ▶ [M25] | math-medium | solved | 8m42s |
| 89 | [15] | simple | solved | 5m01s |
| 90 | [M20] | math-medium | solved | 6m29s |
| 91 | ▶ [26] | hard | solved | 8m34s |
| 92 | [M27] | math-hard | solved | 8m24s |
| 93 | [36] | project | solved | 12m07s |
| 94 | [21] | medium | solved | 6m |
| 95 | ▶ [20] | medium | solved | 6m46s |
| 96 | [20] | medium | solved | 6m27s |
| 97 | [M20] | math-medium | solved | 5m58s |
| 98 | ▶ [22] | medium | solved | 7m26s |
| 99 | [20] | medium | solved | 4m49s |
| 100 | ▶ [24] | medium | solved | 3m39s |
| 101 | [20] | medium | solved | 6m41s |
| 102 | [23] | medium | solved | 4m47s |
| 103 | ▶ [20] | medium | solved | 3m30s |
| 104 | ▶ [21] | medium | solved | 4m06s |
| 105 | [25] | medium | solved | 5m49s |
| 106 | [25] | medium | solved | 4m10s |
| 107 | [26] | hard | solved | 4m10s |
| 108 | [HM24] | hm-medium | solved | 7m35s |
| 109 | ▶ [HM17] | hm-medium | solved | 4m17s |
| 110 | [25] | medium | solved | 4m51s |
| 111 | [M22] | math-medium | solved | 7m07s |
| 112 | [HM23] | hm-medium | solved | 4m25s |
| 113 | [20] | medium | solved | 4m53s |
| 114 | [20] | medium | solved | 2m56s |
| 115 | ▶ [M22] | math-medium | solved | 3m15s |
| 116 | [M21] | math-medium | solved | 4m27s |
| 117 | [M20] | math-medium | solved | 4m59s |
| 118 | [M23] | math-medium | solved | 3m18s |
| 119 | [20] | medium | solved | 4m04s |
| 120 | [18] | medium | solved | 5m54s |
| 121 | ▶ [M22] | math-medium | solved | 7m43s |
| 122 | [27] | hard | solved | 6m18s |
| 123 | [M20] | math-medium | solved | 4m08s |
| 124 | ▶ [27] | hard | solved | 4m55s |
| 125 | ▶ [HM34] | hm-hard | solved | 5m42s |
| 126 | [HM42] | hm-project | solved | 4m17s |
| 127 | [46] | research | solved | 5m11s |
| 128 | ▶ [25] | medium | solved | 3m51s |
| 129 | [M25] | math-medium | solved | 4m04s |
| 130 | [HM31] | hm-hard | solved | 4m03s |
| 131 | [M28] | math-hard | solved | 4m06s |
| 132 | [32] | hard | solved | 4m38s |
| 133 | [20] | medium | solved | 4m09s |
| 134 | [24] | medium | solved | 5m09s |
| 135 | [M27] | math-hard | solved | 3m53s |
| 136 | ▶ [M34] | math-hard | solved | 3m01s |
| 137 | [M38] | math-project | solved | 3m51s |
| 138 | ▶ [M36] | math-project | solved | 14m09s |
| 139 | [22] | medium | solved | 3m49s |
| 140 | [27] | hard | solved | 5m31s |
| 141 | [30] | hard | solved | 4m42s |
| 142 | ▶ [HM32] | hm-hard | solved | 6m47s |
| 143 | [24] | medium | solved | 6m08s |
| 144 | [16] | medium | solved | 2m57s |
| 145 | [24] | medium | solved | 5m55s |
| 146 | ▶ [M22] | math-medium | solved | 5m46s |
| 147 | ▶ [27] | hard | solved | 3m42s |
| 148 | [M21] | math-medium | solved | 3m55s |
| 149 | [M20] | math-medium | solved | 4m |
| 150 | [30] | hard | solved | 5m08s |
| 151 | [20] | medium | solved | 4m35s |
| 152 | [25] | medium | solved | 5m15s |
| 153 | [30] | hard | solved | 1m49s |
| 154 | [20] | medium | verified | 3m25s |
| 155 | ▶ [25] | medium | solved | 4m35s |
| 156 | [30] | hard | verified | 1m16s |
| 157 | [M24] | math-medium | solved | 3m42s |
| 158 | [M24] | math-medium | solved | 6m40s |
| 159 | [20] | medium | solved | 6m03s |
| 160 | ▶ [24] | medium | solved | 5m39s |
| 161 | [28] | hard | solved | 5m25s |
| 162 | ▶ [30] | hard | solved | 6m30s |
| 163 | [23] | medium | solved | 4m47s |
| 164 | ▶ [M27] | math-hard | solved | 4m51s |
| 165 | [M21] | math-medium | solved | 4m52s |
| 166 | [M29] | math-hard | solved | 4m38s |
| 167 | [21] | medium | verified | 3m07s |
| 168 | ▶ [HM40] | hm-project | solved | 6m05s |
| 169 | [M46] | math-research | solved | 6m56s |
| 170 | ▶ [M25] | math-medium | solved | 7m21s |
| 171 | [M26] | math-hard | solved | 6m54s |
| 172 | [M28] | math-hard | solved | 6m07s |
| 173 | ▶ [HM33] | hm-hard | solved | 6m35s |
| 174 | ▶ [M39] | math-project | solved | 8m13s |
| 175 | [M30] | math-hard | solved | 6m42s |
| 176 | [M35] | math-hard | solved | 6m38s |
| 177 | [M22] | math-medium | solved | 3m31s |
| 178 | [M24] | math-medium | solved | 6m |
| 179 | [M47] | math-research | solved | 2m46s |
| 180 | [M27] | math-hard | verified | 3m52s |
| 181 | [M21] | math-medium | solved | 4m53s |
| 182 | [M38] | math-project | solved | 2m48s |
| 183 | ▶ [M25] | math-medium | solved | 3m41s |
| 184 | [M23] | math-medium | solved | 2m53s |
| 185 | [M25] | math-medium | solved | 3m08s |
| 186 | [10] | simple | solved | 1m46s |
| 187 | ▶ [20] | medium | solved | 1m48s |
| 188 | [16] | medium | verified | 1m13s |
| 189 | [18] | medium | solved | 3m49s |
| 190 | [20] | medium | solved | 1m40s |
| 191 | ▶ [HM25] | hm-medium | solved | 3m52s |
| 192 | [M20] | math-medium | solved | 4m37s |
| 193 | [M21] | math-medium | solved | 3m51s |
| 194 | [M25] | math-medium | solved | 4m06s |
| 195 | [24] | medium | solved | 1m50s |
| 196 | [M21] | math-medium | solved | 1m42s |
| 197 | [25] | medium | verified | 1m57s |
| 198 | ▶ [23] | medium | verified | 2m17s |
| 199 | [21] | medium | verified | 2m12s |
| 200 | [21] | medium | solved | 2m06s |
| 201 | [22] | medium | verified | 1m57s |
| 202 | [24] | medium | solved | 4m58s |
| 203 | ▶ [M24] | math-medium | solved | 6m09s |
| 204 | ▶ [M25] | math-medium | solved | 18m42s |
| 205 | [M25] | math-medium | solved | 5m27s |
| 206 | [M46] | math-research | solved | 8m24s |
| 207 | ▶ [M25] | math-medium | solved | 7m19s |
| 208 | ▶ [16] | medium | solved | 4m55s |
| 209 | [M21] | math-medium | solved | 1m44s |
| 210 | ▶ [23] | medium | verified | 2m12s |
| 211 | [M20] | math-medium | verified | 1m57s |
| 212 | ▶ [25] | medium | solved | 4m49s |
| 213 | [16] | medium | solved | 6m11s |
| 214 | ▶ [21] | medium | solved | 5m05s |
| 215 | [21] | medium | solved | 2m48s |
| 216 | ▶ [30] | hard | solved | 2m04s |
| 217 | [29] | hard | solved | 1m |
| 218 | ▶ [24] | medium | verified | 3m12s |
| 219 | [20] | medium | solved | 2m40s |
| 220 | ▶ [21] | medium | solved | 5m17s |
| 221 | ▶ [M27] | math-hard | solved | 3m01s |
| 222 | ▶ [27] | hard | solved | 2m11s |
| 223 | [28] | hard | solved | 1m40s |
| 224 | ▶ [20] | medium | verified | 4m15s |
| 225 | ▶ [30] | hard | verified | 2m48s |
| 226 | ▶ [20] | medium | solved | 6m41s |
| 227 | [20] | medium | solved | 4m09s |
| 228 | [21] | medium | solved | 1m39s |
| 229 | [15] | simple | solved | 1m20s |
| 230 | [25] | medium | solved | 3m48s |
| 231 | [23] | medium | solved | 7m59s |
| 232 | ▶ [23] | medium | solved | 5m07s |
| 233 | ▶ [25] | medium | solved | 2m22s |
| 234 | [22] | medium | solved | 1m58s |
| 235 | [22] | medium | solved | 2m06s |
| 236 | ▶ [M25] | math-medium | solved | 4m40s |
| 237 | [25] | medium | solved | 6m41s |
| 238 | ▶ [22] | medium | solved | 5m58s |
| 239 | ▶ [21] | medium | solved | 7m49s |
| 240 | ▶ [22] | medium | solved | 7m46s |
| 241 | ▶ [28] | hard | solved | 2m11s |
| 242 | [24] | medium | solved | 1m39s |
| 243 | [M23] | math-medium | solved | 2m53s |
| 244 | [25] | medium | solved | 1m38s |
| 245 | ▶ [M22] | math-medium | solved | 3m57s |
| 246 | [M21] | math-medium | solved | 6m30s |
| 247 | ▶ [M27] | math-hard | solved | 6m38s |
| 248 | [M22] | math-medium | solved | 4m56s |
| 249 | [HM31] | hm-hard | solved | 4m56s |
| 250 | [28] | hard | solved | 4m19s |
| 251 | [M46] | math-research | solved | 3m01s |
| 252 | [M30] | math-hard | solved | 3m06s |
| 253 | ▶ [M26] | math-hard | solved | 4m04s |
| 254 | ▶ [M23] | math-medium | solved | 4m28s |
| 255 | ▶ [25] | medium | solved | 1m20s |
| 256 | [M32] | math-hard | solved | 4m44s |
| 257 | [40] | project | solved | 3m24s |
| 258 | ▶ [25] | medium | solved | 1m10s |
| 259 | ▶ [25] | medium | solved | 53s |
| 260 | ▶ [M27] | math-hard | solved | 1m12s |
| 261 | [HM21] | hm-medium | verified | 1m46s |
| 262 | [M26] | math-hard | solved | 5m05s |
| 263 | [HM25] | hm-medium | solved | 5m07s |
| 264 | [M46] | math-research | solved | 1m40s |
| 265 | ▶ [21] | medium | solved | 2m05s |
| 266 | ▶ [20] | medium | solved | 5m16s |
| 267 | [HM32] | hm-hard | solved | 5m43s |
TAOCP 7.1.4 Exercise 1
A BDD is an ordered reduced directed acyclic graph with variable ordering $x_1 < x_2$, sinks $\bot,\top$, and branch nodes labeled by variables.
TAOCP 7.1.4 Exercise 2
Let $F$ be the set of all Boolean functions $f(x_1,x_2)$, represented by their truth tables f = (f(0,0), f(0,1), f(1,0), f(1,1)) \in \{0,1\}^4, so $|F| = 16$.
TAOCP 7.1.4 Exercise 3
Let $f(x_1,x_2,\dots,x_n)$ be a Boolean function and let its BDD size $B(f)$ be the number of nodes in its reduced ordered BDD, including the sinks $\bot,\top$.
TAOCP 7.1.4 Exercise 4
Let the 64-bit word $x$ contain fields V \mid LO \mid HI with $V$ occupying the highest 8 bits and each of $LO, HI$ occupying 28 bits.
TAOCP 7.1.4 Exercise 5
Let $G$ be the BDD of $f(x_1,\dots,x_n)$, and construct a transformed directed acyclic graph $G'$ by interchanging the LO and HI pointers of every branch node and swapping the two sinks $\bot \leftrig...
TAOCP 7.1.4 Exercise 6
The truth table of $g(x_1,x_2,x_3,x_4)=f(x_4,x_3,x_2,x_1)$ is obtained by reversing the bit indices of the truth table of $f$.
TAOCP 7.1.4 Exercise 7
Let $f(x_1,\ldots,x_n)$ be represented by its reduced ordered BDD under variable order $x_1<\cdots<x_n$, and define $g_k(x_0,x_1,\ldots,x_n)=f(x_1',\ldots,x_n')$ where For truth tables, each entry of...
TAOCP 7.1.4 Exercise 8
Let $f(x_1,\ldots,x_n)$ be given and let g_k(x_1,\ldots,x_n)=f(x_1,\ldots,x_{k-2},\,x_{k-1}\oplus x_k,\,x_{k+1},\ldots,x_n).
TAOCP 7.1.4 Exercise 9
Let the BDD of $f(x_1,\ldots,x_n)$ be given in the sequential form of (8), with nodes $k_j$ labeled by $V(k_j)=x_j$, LO successor $\operatorname{LO}(k_j)$, HI successor $\operatorname{HI}(k_j)$, and s...
TAOCP 7.1.4 Exercise 10
Let $f$ and $f'$ be Boolean functions represented by reduced ordered BDDs.
TAOCP 7.1.4 Exercise 11
Algorithm C in Section 7.
TAOCP 7.1.4 Exercise 12
Let $\Gamma_n = {g(0), g(1), \ldots, g(2^n-1)}$ be the $n$-bit Gray binary code defined in Section 7.
TAOCP 7.1.4 Exercise 13
Let $G=(V,E)$ be an ordinary (undirected) graph, viewed as a digraph by replacing each edge ${u,v}\in E$ with the two arcs $u\to v$ and $v\to u$.
TAOCP 7.1.4 Exercise 14
Number the vertices of the cycle $C_n$ as in the statement, so edges are ${x_i,x_{i+1}}$ for $1 \le i < n$ and ${x_n,x_1}$.
TAOCP 7.1.4 Exercise 15
Let $C_n$ have vertices $1,2,\dots,n$ with edges $i\sim i\pm1 \pmod n$.
TAOCP 7.1.4 Exercise 16
Let the given BDD represent a Boolean function $f(x_1,\dots,x_n)$ in ordered and reduced form as defined in Section 7.
TAOCP 7.1.4 Exercise 17
A reduced ordered binary decision diagram (BDD) for a Boolean function $f(x_1,\dots,x_n)$ consists of a rooted directed acyclic graph in which each non-sink node $v$ has a variable index $V(v)\in{1,\d...
TAOCP 7.1.4 Exercise 18
The flaw in the previous solution is not only that it ignores the structure of the diagram, but that it misidentifies what Algorithm B is actually aggregating over in a binary decision diagram of this...
TAOCP 7.1.4 Exercise 19
The reviewer correctly identifies that the previous argument failed because it treated $m_k$ as if it ranged over arbitrary subset sums without justifying how this arises from Algorithm B.
TAOCP 7.1.4 Exercise 20
Let $t(m)$ denote the parity of the binary digit sum of $m$, so that $t(m)=0$ when $m$ has an even number of 1s in binary representation and $t(m)=1$ otherwise.
TAOCP 7.1.4 Exercise 21
Yes.
TAOCP 7.1.4 Exercise 22
The core issue in the previous solution is that it tried to justify the simplification by claiming a strong structural symmetry of kernel BDDs that was never actually established.
TAOCP 7.1.4 Exercise 23
The key point is that the number “eight” is not a property of individual paths, but a property of the _construction_ that produced the BDD in Fig.
TAOCP 7.1.4 Exercise 24
Let $G$ be the grid graph of Fig.
TAOCP 7.1.4 Exercise 25
Algorithm C in this section evaluates a BDD bottom-up by assigning to each node $v$ a value depending only on its LO and HI successors, with sink nodes providing the base cases and each internal node...
TAOCP 7.1.4 Exercise 26
Algorithm C computes, for every node of the BDD, the number of satisfying assignments represented by the subgraph rooted at that node.
TAOCP 7.1.4 Exercise 27
Let $H$ be an $m\times n$ parity-check matrix over $\mathbb{F}_2$, and let f(x)= [Hx=0], \qquad x=(x_1,\dots,x_n)^T.
TAOCP 7.1.4 Exercise 28
Let $f(x_1,\ldots,x_n)$ be a Boolean function and let G(z)=\sum_{x_1=0}^1 \cdots \sum_{x_n=0}^1 z^{x_1+\cdots+x_n} f(x_1,\ldots,x_n) be its generating function as defined in the preceding exercise.
TAOCP 7.1.4 Exercise 29
Let $f$ be represented by a reduced ordered binary decision diagram, and let $F(p)$ denote the reliability polynomial under the specialization $p_1=\cdots=p_n=p$.
TAOCP 7.1.4 Exercise 30
Let the contribution of a minterm corresponding to an assignment $x_1 \ldots x_n$ be C(x_1,\ldots,x_n)=\prod_{i=1}^n (1-p_i)^{1-x_i}p_i^{x_i}.
TAOCP 7.1.4 Exercise 31
Let $f(x_1,\dots,x_n)$ be represented by an ordered reduced BDD with root node $r$.
TAOCP 7.1.4 Exercise 32
Exercise 31 describes a generic BDD evaluation scheme in which a function is computed by replacing each internal decision node labeled by variable $x_j$ with an algebraic combination of the values of...
TAOCP 7.1.4 Exercise 33
Let the BDD represent $f(x_1,\dots,x_n)$ with variable order $x_1 < x_2 < \cdots < x_n$.
TAOCP 7.1.4 Exercise 34
Let $B$ be the BDD of $f(x_1,\dots,x_n)$ with root node $r$.
TAOCP 7.1.4 Exercise 35
Let $G$ be the given FBDD with node set $V(G)$.
TAOCP 7.1.4 Exercise 36
Exercise 31 provides a method for evaluating a BDD by interpreting each sink and branch node as an element of an algebraic system equipped with operations $\circ$ and $\bullet$, and propagating values...
TAOCP 7.1.4 Exercise 37
Let $f(x_1,\dots,x_n)$ be a Boolean function, and let $G(z)$ be its generating function in the sense of Exercise 25, so that G(z)=\sum_{x\in\{0,1\}^n} f(x)\, z^{w(x)}, where $w(x)=x_1+\cdots+x_n$ is t...
TAOCP 7.1.4 Exercise 38
Let $f(x_1,\dots,x_n)$ be a Boolean function, and let $G(z)$ be its generating function in the sense of Exercise 25, so that G(z)=\sum_{x\in\{0,1\}^n} f(x)\, z^{w(x)}, where $w(x)=x_1+\cdots+x_n$ is t...
TAOCP 7.1.4 Exercise 39
Let $f(x_1,\dots,x_n)$ be a Boolean function, and let $G(z)$ be its generating function in the sense of Exercise 25, so that G(z)=\sum_{x\in\{0,1\}^n} f(x)\, z^{w(x)}, where $w(x)=x_1+\cdots+x_n$ is t...
TAOCP 7.1.4 Exercise 40
Let $f$ be a Boolean function of variables $x_1,\dots,x_n$ and let $g$ be obtained from $f$ by the condensation $x_{k+1} \leftarrow x_k$.
TAOCP 7.1.4 Exercise 41
Let $F_1=1$, $F_2=1$, and $F_{k+2}=F_{k+1}+F_k$.
TAOCP 7.1.4 Exercise 42
Let $f(x_1,x_2,x_3)$ be symmetric.
TAOCP 7.1.4 Exercise 43
Let $f$ be a Boolean function on $2n$ variables and recall that $B(f)$ is the number of beads of $f$, equivalently the number of nodes in its reduced ordered BDD, including sinks.
TAOCP 7.1.4 Exercise 44
A symmetric Boolean function $f(x_1,\dots,x_n)$ depends only on the Hamming weight $t=x_1+\cdots+x_n$, so it is determined by a binary sequence \sigma = (f(0),f(1),\dots,f(n)), of length $n+1$.
TAOCP 7.1.4 Exercise 45
We restart the construction from the actual BDD network underlying (33)–(34), where each module corresponds to a node of an ordered decision diagram and therefore represents a Boolean subfunction dete...
TAOCP 7.1.4 Exercise 46
Let $f(x_1,\dots,x_n)$ be the three-in-a-row function, that is, f(x_1,\dots,x_n)=1 iff there exists $i$ with $1\le i\le n-2$ such that either
TAOCP 7.1.4 Exercise 47
Let $f$ be a Boolean function with a reduced ordered binary decision diagram $G$.
TAOCP 7.1.4 Exercise 48
The previous solution failed at three precise points: it never constructed the module network in the sense of Fig.
TAOCP 7.1.4 Exercise 49
For each $m \ge 2$, an $m$-ary de Bruijn cycle of order $n$ is a cyclic sequence $C_{m,n}$ of length $m^n$ over ${0,1,\dots,m-1}$ in which every $m$-ary string of length $n$ occurs exactly once as a c...
TAOCP 7.1.4 Exercise 50
For each $m \ge 2$, an $m$-ary de Bruijn cycle of order $n$ is a cyclic sequence $C_{m,n}$ of length $m^n$ over ${0,1,\dots,m-1}$ in which every $m$-ary string of length $n$ occurs exactly once as a c...
TAOCP 7.1.4 Exercise 51
Let $(x_1,\dots,x_{2n})$ be the input variables for the addition function in the standard left-to-right numbering of Section 7.
TAOCP 7.1.4 Exercise 52
Let $\{f_1,\ldots,f_m\}$ be Boolean functions in variables $(x_1,\ldots,x_n)$, and assume a fixed variable ordering in which the dummy variables $(t_1,\ldots,t_{m+1})$ precede all $x_j$.
TAOCP 7.1.4 Exercise 53
Algorithm R reduces a binary decision diagram by repeatedly merging isomorphic nodes, identifying sinks, and deleting nodes whose two outgoing edges coincide.
TAOCP 7.1.4 Exercise 54
Let the truth table of $f(x_1,\ldots,x_n)$ be a binary string $\tau$ of length $2^n$, indexed so that the left half $\tau_0$ represents $f(0,x_2,\ldots,x_n)$ and the right half $\tau_1$ represents $f(...
TAOCP 7.1.4 Exercise 55
Let $G=(V,E)$ be a finite undirected graph with $|V|=n$ and edges $E=\{e_1,\dots,e_m\}$, ordered so that the BDD variable ordering is $x_1,\dots,x_m$, where $x_i$ corresponds to $e_i$.
TAOCP 7.1.4 Exercise 56
Algorithm R builds a reduced ordered BDD by creating nodes and using an AVAIL stack to recycle nodes whose LO and HI pointers are found equal or whose subgraphs duplicate existing nodes.
TAOCP 7.1.4 Exercise 57
Algorithm R builds a reduced ordered BDD by creating nodes and using an AVAIL stack to recycle nodes whose LO and HI pointers are found equal or whose subgraphs duplicate existing nodes.
TAOCP 7.1.4 Exercise 58
We begin by making the construction in (37) explicit in the only way the proof can depend on it.
TAOCP 7.1.4 Exercise 59
Let $H$ denote the reduced ordered BDD for $h(x_1,\ldots,x_n)$.
TAOCP 7.1.4 Exercise 60
Let $f$ and $g$ be reduced ordered BDDs over variables $x_1,\dots,x_n$ with fixed ordering.
TAOCP 7.1.4 Exercise 61
Let $f$ and $g$ be Boolean functions with respective BDDs.
TAOCP 7.1.4 Exercise 62
Algorithm D in Section 7.
TAOCP 7.1.4 Exercise 63
Let $M_m$ denote the majority function on $m$ Boolean inputs, defined in Section 7.
TAOCP 7.1.4 Exercise 64
Let $B(f)$ denote the number of beads of a Boolean function $f$, equivalently the number of nodes in its reduced ordered BDD.
TAOCP 7.1.4 Exercise 65
Let $f_n(k)$ denote the $k$th bit of the binary de Bruijn cycle of order $n$ produced by Algorithms R and D with $m=2$, indexed cyclically for $0 \le k < 2^n$.
TAOCP 7.1.4 Exercise 66
Let $S=s_0s_1\ldots s_{n-1}$ be the given $n$-bit string.
TAOCP 7.1.4 Exercise 67
Algorithm S evaluates a binary Boolean operation \(f \circ g\) on functions represented by reduced ordered binary decision diagrams (BDDs).
TAOCP 7.1.4 Exercise 68
Step S10 of Algorithm S is entered when a newly constructed or retrieved node $t$ has a negative pointer in its LEFT field, indicating that the node represents a terminal value rather than an internal...
TAOCP 7.1.4 Exercise 69
Algorithm S constructs new BDD nodes during recursive or memoized evaluation of an operation such as apply, using a shared node pool indexed upward from `TBOT` and downward from `NTOP`, with failure o...
TAOCP 7.1.4 Exercise 70
Let $LCOUNT[l]$ denote the number of nodes (or items) that must be accommodated at level $l$ in step S4 of Algorithm S, and let $b$ determine a table size $2^b$ used for storage at that level.
TAOCP 7.1.4 Exercise 71
Algorithm S in Section 7.
TAOCP 7.1.4 Exercise 72
Algorithm S relies on a “unique table” that maps each triple $(V, LO, HI)$ to a unique node so that identical subfunctions share a single representation.
TAOCP 7.1.4 Exercise 73
We are given a virtual address representation p = \pi(p)2^e + \sigma(p), \quad \pi(p)=p \gg e,\quad \sigma(p)=p \bmod 2^e, and we must show that a BDD node stored at address $p$ does not need to store...
TAOCP 7.1.4 Exercise 74
Let $f(x_1,\dots,x_n)$ be a monotone Boolean function.
TAOCP 7.1.4 Exercise 75
Let $x_1\ldots x_{2^n}$ be a truth table of length $2^n$.
TAOCP 7.1.4 Exercise 76
Let $U={0,1,\dots,n-1}$ and let each subset $S\subseteq U$ be identified with its characteristic integer $s=\sum_{e\in S}2^e$.
TAOCP 7.1.4 Exercise 77
Let $\mu_n(x_1,\ldots,x_{2n})$ be the Boolean function whose truth table encodes a monotone Boolean function in the sense of Section 7.
TAOCP 7.1.4 Exercise 78
Let $V={1,2,\dots,12}$ and let each simple undirected graph on $V$ be identified with a binary vector over the $\binom{12}{2}=66$ edges, so the total set of graphs is ${0,1}^{66}$.
TAOCP 7.1.4 Exercise 79
Let the vertex set be $V={1,\dots,12}$ and let $m=\binom{12}{2}=66$ be the number of possible edges.
TAOCP 7.1.4 Exercise 80
Let the vertex set be $V={1,\dots,12}$ and let $m=\binom{12}{2}=66$ be the number of possible edges.
TAOCP 7.1.4 Exercise 81
Let the vertex set be $V={1,\dots,12}$ and let $m=\binom{12}{2}=66$ be the number of possible edges.
TAOCP 7.1.4 Exercise 82
Let the vertex set be $V={1,\dots,12}$ and let $m=\binom{12}{2}=66$ be the number of possible edges.
TAOCP 7.1.4 Exercise 83
Let (55) denote the recursive apply procedure for $\mathrm{AND}(f,g)$ on BDDs, where each call is indexed by a pair of nodes $(u,v)$ and recursively generates calls on $(u_0,v_0)$, $(u_0,v_1)$, $(u_1,...
TAOCP 7.1.4 Exercise 84
Let (55) denote the recursive apply procedure for $\mathrm{AND}(f,g)$ on BDDs, where each call is indexed by a pair of nodes $(u,v)$ and recursively generates calls on $(u_0,v_0)$, $(u_0,v_1)$, $(u_1,...
TAOCP 7.1.4 Exercise 85
Let $x=(x_{15}\ldots x_0)_2$ and $y=(y_{15}\ldots y_0)_2$.
TAOCP 7.1.4 Exercise 86
Let $x=(x_{15}\ldots x_0)_2$ and $y=(y_{15}\ldots y_0)_2$.
TAOCP 7.1.4 Exercise 87
The median operator $\langle fgh\rangle$ is the Boolean function that is $1$ exactly when at least two of its arguments are $1$, and $0$ otherwise.
TAOCP 7.1.4 Exercise 88
Let variables be ordered $x_1 < x_2 < \cdots < x_n$.
TAOCP 7.1.4 Exercise 89
Let $f$ be a Boolean function of variables $x_1, x_2$, taking values in ${\bot,\top}$, with the usual ordering $\bot < \top$.
TAOCP 7.1.4 Exercise 90
Let Eq.
TAOCP 7.1.4 Exercise 91
Let $f, g$ be Boolean functions on $n$ variables, and let the operator $f \downarrow g$ be defined by the ordering $x, x \oplus 1, x \oplus 2, \ldots$ on $n$-bit vectors, where $x \oplus k$ denotes bi...
TAOCP 7.1.4 Exercise 92
Let $x = (x_1,\dots,x_n)_2$ and let the successor sequence in exercise 91 be $x,\, x\oplus 1,\, x\oplus 2,\, \dots,$ where $x\oplus k$ is binary addition mod $2^n$.
TAOCP 7.1.4 Exercise 93
Let a multiset ${a_1,\dots,a_n}$ be given, and assume Algorithm L of Section 7.
TAOCP 7.1.4 Exercise 94
Let $f$ be a Boolean function represented by an ordered reduced BDD, and let $x_j$ be the variable being eliminated.
TAOCP 7.1.4 Exercise 95
Equation (65) computes existential quantification over a Boolean variable by combining cofactors of a function $f$ with respect to that variable, typically using the structure of a BDD node whose low...
TAOCP 7.1.4 Exercise 96
Equation (65) computes existential quantification over a Boolean variable by combining cofactors of a function $f$ with respect to that variable, typically using the structure of a BDD node whose low...
TAOCP 7.1.4 Exercise 97
Equation (65) computes existential quantification over a Boolean variable by combining cofactors of a function $f$ with respect to that variable, typically using the structure of a BDD node whose low...
TAOCP 7.1.4 Exercise 98
Let $G(x,y)$ be the Boolean function defined in (70), representing adjacency in an undirected graph on vertices ${1,\dots,n}$, where $G(x,y)=1$ iff there is an edge between $x$ and $y$.
TAOCP 7.1.4 Exercise 99
Let $f = \text{COLOR}(x_1,\dots,x_n)$ be the Boolean function encoding proper 4-colorings of the US map, where each vertex variable $x_i$ takes values in ${0,1,2,3}$, represented in binary as in (73).
TAOCP 7.1.4 Exercise 100
Let $G=(V,E)$ be the planar adjacency graph of the contiguous United States after eliminating DC, as specified in the exercise.
TAOCP 7.1.4 Exercise 101
Let $\Sigma_m={0,1,\dots,m-1}$ be the ordered alphabet used for $m$-ary strings in Section 7.
TAOCP 7.1.4 Exercise 102
Let $f(x_1,\dots,x_n)$ be a Boolean function represented by its BDD as in Section 7.
TAOCP 7.1.4 Exercise 103
Let \Phi(x_1,\dots,x_n) = \exists y_1 \dots \exists y_m \Bigl(
TAOCP 7.1.4 Exercise 104
Let $f$ and $g$ be Boolean functions represented by reduced ordered binary decision diagrams with sink nodes $\bot,\top$ and with variable ordering $x_1 < \cdots < x_n$.
TAOCP 7.1.4 Exercise 105
A Boolean function $f(x_1,\dots,x_n)$ is unate with polarities $(y_1,\dots,y_n)$ when the function $h(x_1,\dots,x_n)=f(x_1\oplus y_1,\dots,x_n\oplus y_n)$ is monotone increasing in each variable, mean...
TAOCP 7.1.4 Exercise 106
Let variables of $f$ be $x_1,\dots,x_n$, variables of $g$ be $y_1,\dots,y_n$, and variables of $h$ be $z_1,\dots,z_n$.
TAOCP 7.1.4 Exercise 107
Let $f(x_1,\dots,x_n)$ be a Boolean function represented by a reduced ordered BDD, and let $B(f)$ denote its number of nodes including sinks, as defined in Section 7.
TAOCP 7.1.4 Exercise 108
The solution does not correctly establish the required inequality.
TAOCP 7.1.4 Exercise 109
Let the current composition of $n$ be s_1 s_2 \cdots s_j, and let
TAOCP 7.1.4 Exercise 110
Connection interrupted.
TAOCP 7.1.4 Exercise 111
Let $\Gamma_3 = (g(0), g(1), \dots, g(7))$ be the 3-bit Gray binary code in cyclic order, so consecutive terms including $g(7) \to g(0)$ differ in exactly one bit, by the defining property of Gray cod...
TAOCP 7.1.4 Exercise 112
Let $\hat b_k$ denote the quantity defined in (80) of Theorem U, where $\hat b_k$ is obtained from the recurrence counting BDD nodes via subtables of order $n-k$ and their bead structure.
TAOCP 7.1.4 Exercise 113
Let $F_4$ denote the set of Boolean functions of four variables.
TAOCP 7.1.4 Exercise 114
Let the function depend on six variables $x_1,\dots,x_6$.
TAOCP 7.1.4 Exercise 115
Let $p_k$ denote the number of beads (BDD nodes) at level $k$, and let $q_k$ denote the number of distinct subtables produced at level $k$ before reduction, in the sense of Section 7.
TAOCP 7.1.4 Exercise 116
Let the quasi-profile of a BDD for a Boolean function $f(x_1,\dots,x_n)$ be the sequence $Q_k(f)$, where $Q_k(f)$ counts the number of distinct nodes (equivalently distinct subfunctions) at level $k$,...
TAOCP 7.1.4 Exercise 117
Let $f = M_m(x_1,\ldots,x_m; x_{m+1},\ldots,x_{2m})$, where $M_m$ denotes the equality function on two $m$-bit blocks, so that $f=1$ if and only if $x_i = x_{m+i}$ for all $1 \le i \le m$.
TAOCP 7.1.4 Exercise 118
Let $g(k)$ be the Gray binary code defined in (7), equivalently $g(k)=k\oplus \lfloor k/2\rfloor$ by (9).
TAOCP 7.1.4 Exercise 119
Let $N \ge 1$.
TAOCP 7.1.4 Exercise 120
The hidden-weighted-bit function $h_n$ assigns a value to a bit vector $(x_1,\dots,x_n)$ by interpreting the input as indexing into a truth table and then extracting a selected bit.
TAOCP 7.1.4 Exercise 121
Let $f^{D}(x_1,\dots,x_n)=\overline{f(\overline{x_1},\dots,\overline{x_n})}$ and $f^{R}(x_1,\dots,x_n)=f(x_n,\dots,x_1)$.
TAOCP 7.1.4 Exercise 122
Let $h_n(x_1,\dots,x_n)$ denote the hidden weighted bit function, and let $x^\psi$ be the permutation on ${0,1}^n$ defined in part (c) of Exercise 121 by \epsilon^\psi=\epsilon,\quad (x_1\cdots x_n0)^...
TAOCP 7.1.4 Exercise 123
Let a slate of offset $s$ be defined as in the construction preceding formula (97), where each slate is determined by a choice of $s$ distinguished positions among $n$ ordered positions, and offset me...
TAOCP 7.1.4 Exercise 124
Let a slate of offset $s$ be defined as in the construction preceding formula (97), where each slate is determined by a choice of $s$ distinguished positions among $n$ ordered positions, and offset me...
TAOCP 7.1.4 Exercise 125
Let $h_n(x_1,\ldots,x_n)$ be the hidden weighted bit function, and let $B(h_n)$ denote the number of nodes in its reduced ordered binary decision diagram, including the two sink nodes $\bot$ and $\top...
TAOCP 7.1.4 Exercise 126
Let $h_n(x_1,\ldots,x_n)$ denote the hidden weighted bit function and let $h_n^\pi(x_1,\ldots,x_n)=h_n(x_{\pi(1)},\ldots,x_{\pi(n)})$ be its permutation by $\pi$.
TAOCP 7.1.4 Exercise 127
Let $h_n(x_1,\ldots,x_n)$ be the hidden weighted bit function and let $h_n^\pi$ denote its permutation under $\pi$, evaluated in the fixed variable order $x_1,\ldots,x_n$.
TAOCP 7.1.4 Exercise 128
Let $S={1,\dots,m}$ denote the selector variables and $T={m+1,\dots,m+2^m}$ the data variables of the multiplexer $M_m$.
TAOCP 7.1.4 Exercise 129
Let $S={1,\dots,m}$ denote the selector variables and $T={m+1,\dots,m+2^m}$ the data variables of the multiplexer $M_m$.
TAOCP 7.1.4 Exercise 130
Let $G=(V,E)$ be an ordinary (undirected) graph, viewed as a digraph by replacing each edge ${u,v}\in E$ with the two arcs $u\to v$ and $v\to u$.
TAOCP 7.1.4 Exercise 131
Let C(x_1,\dots,x_p;\,y_{11},\dots,y_{pq}) = \bigwedge_{j=1}^{q}\left(\bigvee_{i=1}^{p}(x_i\wedge y_{ij})\right) be the covering function from the statement.
TAOCP 7.1.4 Exercise 132
Let $f(x_1,x_2,x_3,x_4,x_5)$ be a Boolean function and let $B_{\min}(f)$ denote the minimum, over all variable orderings, of the number of nodes in its reduced ordered binary decision diagram, includi...
TAOCP 7.1.4 Exercise 133
Let $\mathcal{S}(f)$ denote the set of all distinct subfunctions of $f(x_1,\dots,x_n)$ obtained by repeated Shannon decomposition with respect to variables $x_1,\dots,x_n$, as represented in the maste...
TAOCP 7.1.4 Exercise 134
Let $\Gamma_n = g(0), g(1), \dots, g(2^n-1)$ be the $n$-bit Gray binary code defined in Section 7.
TAOCP 7.1.4 Exercise 135
Let $\Gamma_6 = g(0), g(1), \dots, g(2^6-1)$ be the 6-bit Gray binary code, where g(k) = k \oplus \lfloor k/2 \rfloor.
TAOCP 7.1.4 Exercise 136
Let $\Gamma_6 = g(0), g(1), \dots, g(2^6-1)$ be the 6-bit Gray binary code, where g(k) = k \oplus \lfloor k/2 \rfloor.
TAOCP 7.1.4 Exercise 137
Let $\Gamma_6 = g(0), g(1), \dots, g(2^6-1)$ be the 6-bit Gray binary code, where g(k) = k \oplus \lfloor k/2 \rfloor.
TAOCP 7.1.4 Exercise 138
We interpret a QDD as a shared representation of all cofactors of $f$ with respect to a variable ordering, where each internal node is labeled by a variable and edges correspond to 0/1 restriction.
TAOCP 7.1.4 Exercise 139
Let $k \ge 2$ be even and consider the $(kr+2)$-cube $G = G_k G_{k-1} \cdots G_1 G_0 G_{-1}$, where $G_i$ is an $r$-cube for $i>0$ and $G_0 = G_{-1} = P_2$.
TAOCP 7.1.4 Exercise 140
Number the vertices of the cycle $C_n$ as in the statement, so edges are ${x_i,x_{i+1}}$ for $1 \le i < n$ and ${x_n,x_1}$.
TAOCP 7.1.4 Exercise 141
Let $d(n)$ denote the quantity arising in Exercises 45–47, interpreted as the number of Hamiltonian cycles produced by the Gray-cycle constructions in the $(kr+2)$-cube after the reductions and gluing...
TAOCP 7.1.4 Exercise 142
Let $f(x)=\langle x_{w_1}\cdots x_{w_n}\rangle$ denote the threshold function defined in Section 7.
TAOCP 7.1.4 Exercise 143
Let $f(x)=\langle x_1^{w_1}\cdots x_{20}^{w_{20}}\rangle$ denote the self-dual threshold function in which the weights are those listed in the statement.
TAOCP 7.1.4 Exercise 144
The addition functions $f_1, f_2, f_3, f_4, f_5$ in (36) are the Boolean functions that determine the carry propagation structure of binary addition for increasing word lengths, where $f_k(x_1,\dots,x...
TAOCP 7.1.4 Exercise 145
Let the input variables be two binary words $x = x_1x_2x_3x_4,\qquad y = y_1y_2y_3y_4,$ and let $f_1,\dots,f_5$ denote the five output bits of the addition $x+y$ as defined in (36), where $f_1$ is the...
TAOCP 7.1.4 Exercise 146
Let level $0$ contain the root nodes of the BDD base, level $1$ the next variable layer, and level $2$ the layer below.
TAOCP 7.1.4 Exercise 147
Let level $0$ contain the root nodes of the BDD base, level $1$ the next variable layer, and level $2$ the layer below.
TAOCP 7.1.4 Exercise 148
The reviewer is correct: the statement is **false**, so the original proof attempt cannot be repaired.
TAOCP 7.1.4 Exercise 149
The central issue is that the original argument tries to maintain a global “ancestry” of nodes through repeated reductions.
TAOCP 7.1.4 Exercise 150
Let $f_1,\dots,f_m$ be Boolean functions represented by a shared reduced ordered BDD, with node set size $B(f_1,\dots,f_m)$ in the sense of Section 7.
TAOCP 7.1.4 Exercise 151
Algorithm J performs _sifting_ by repeatedly moving a chosen variable through all possible positions in the variable ordering, exchanging it with adjacent variables to minimize the BDD size.
TAOCP 7.1.4 Exercise 152
Let $h_n$ denote the hidden weighted bit function on variables $x_1,\dots,x_n$, where the value of $h_n(x_1,\dots,x_n)$ is $x_k$ with $k = x_1 + \cdots + x_n$, interpreted in the standard way of Exerc...
TAOCP 7.1.4 Exercise 153
Let the vertices of the $n$-cube be identified with $n$-bit strings.
TAOCP 7.1.4 Exercise 154
The mistake in the previous solution is the assumption that the movement of each state is determined by the induced permutation between (104) and (106).
TAOCP 7.1.4 Exercise 155
We restate the problem in the language of TAOCP BDD equivalence classes.
TAOCP 7.1.4 Exercise 156
Algorithm J (sifting) for dynamic variable reordering in reduced ordered BDDs operates by selecting a variable and moving it through the current ordering by adjacent swaps, evaluating the cost functio...
TAOCP 7.1.4 Exercise 157
The key failure in the previous argument is the unproven monotonicity claim: it is not true in general that swapping an adjacent data–selector inversion preserves or improves ROBDD size.
TAOCP 7.1.4 Exercise 158
Let $p=n-m$ and write $k_1=\lfloor p/3\rfloor$, $k_2=\lceil 2p/3\rceil$.
TAOCP 7.1.4 Exercise 159
Let $p=n-m$ and write $k_1=\lfloor p/3\rfloor$, $k_2=\lceil 2p/3\rceil$.
TAOCP 7.1.4 Exercise 160
Let $N(i,j)$ denote the Moore neighborhood of $(i,j)$, i.
TAOCP 7.1.4 Exercise 161
The earlier solution fails at the point where it replaces the actual definition of $L$ from Exercise 160 with an assumed linear involution structure.
TAOCP 7.1.4 Exercise 162
Let $X = (x_{ij})$ be a $6 \times 6$ matrix with entries in ${0,1}$.
TAOCP 7.1.4 Exercise 163
A read-once Boolean function $f(x_1,\ldots,x_n)$ is represented by a formula tree in which each variable occurs exactly once.
TAOCP 7.1.4 Exercise 164
A Boolean function $f(x_1,\dots,x_n)$ is **read-once** if it can be expressed by a formula in which each variable $x_i$ appears exactly once.
TAOCP 7.1.4 Exercise 165
We restart the argument from the ROBDD construction rules and avoid manipulating the coupled recurrences in an unjustified way.
TAOCP 7.1.4 Exercise 166
We restart the argument from the formal semantics of ordered binary decision diagrams and build canonicity directly from evaluation, without assuming any uniqueness of a construction procedure.
TAOCP 7.1.4 Exercise 167
We restart from the structural characterization of read-once Boolean functions and the defining property of reduced ordered binary decision diagrams.
TAOCP 7.1.4 Exercise 168
Let a read-once Boolean function $f(x_1,\dots,x_n)$ be given, and let $B(f)$ denote the number of BDD nodes including sinks, as defined in Section 7.
TAOCP 7.1.4 Exercise 169
Let $f$ be a read-once Boolean function of $22m+1$ variables, represented by a rooted formula tree in which each variable appears exactly once.
TAOCP 7.1.4 Exercise 170
A skinny BDD is an ordered chain of nodes $x_1,\dots,x_n$ where each node $x_j$ has exactly one outgoing edge to a sink and one outgoing edge to the next node $x_{j+1}$, except $x_n$, whose two childr...
TAOCP 7.1.4 Exercise 171
A BDD is **skinny** if for each variable $x_j$ there is exactly one branch node labeled $j$, and at that node exactly one of the two outgoing edges, LO or HI, leads to a sink node.
TAOCP 7.1.4 Exercise 172
A BDD is **skinny** if for each variable $x_j$ there is exactly one branch node labeled $j$, and at that node exactly one of the two outgoing edges, LO or HI, leads to a sink node.
TAOCP 7.1.4 Exercise 173
A Boolean function $f(x_1,\dots,x_n)$ is skinny if its reduced ordered binary decision diagram has exactly one branch node for each variable, and at every branch node exactly one of LO or HI is a sink...
TAOCP 7.1.4 Exercise 174
A binary decision diagram is _thin_ if it contains exactly one branch node labeled $j$ for each $1 \le j \le n$.
TAOCP 7.1.4 Exercise 175
Let a Boolean function on $n$ variables be represented by a reduced ordered BDD in the sense of Section 7.
TAOCP 7.1.4 Exercise 176
Let $h_{a,b}(x)=((ax+b)\gg(n-l)) \bmod 2^l$, with $a\in A={a\mid 0<a<2^n,\ a\ \text{odd}}$ and $b\in B={b\mid 0\le b<2^{n-l}}$.
TAOCP 7.1.4 Exercise 177
The statement refers to “Theorem A” and to a “quasi-profile,” but neither is defined in the provided section excerpt.
TAOCP 7.1.4 Exercise 178
I can’t write a correct Codeforces 104120F editorial as requested because the problem statement is missing entirely (the “Problem Statement / Input / Output” sections are empty).
TAOCP 7.1.4 Exercise 179
I can’t write a correct Codeforces 104120F editorial as requested because the problem statement is missing entirely (the “Problem Statement / Input / Output” sections are empty).
TAOCP 7.1.4 Exercise 180
We restate the intended theorem in a form that matches the BDD semantics used in Section 7.
TAOCP 7.1.4 Exercise 181
We restart from the correct structural model of the function and rebuild the argument in a way that does not rely on an incorrect “single-bit carry” abstraction.
TAOCP 7.1.4 Exercise 182
Let $L_{n,n}(x_1,\ldots,x_n; y_1,\ldots,y_n)$ denote the leading bit of the product of two $n$-bit integers $x=\sum_{i=0}^{n-1} x_{i+1}2^i$ and $y=\sum_{j=0}^{n-1} y_{j+1}2^j$.
TAOCP 7.1.4 Exercise 183
Let the odd-indexed variables define a binary fraction A = (0.
TAOCP 7.1.4 Exercise 184
Let $P_m$ denote the Boolean predicate that encodes whether a length-$m$ assignment represents a valid permutation of ${1,\dots,m}$.
TAOCP 7.1.4 Exercise 185
Let $f(x_1,\dots,x_n)$ be symmetric, so its value depends only on the Hamming weight w = x_1 + \cdots + x_n.
TAOCP 7.1.4 Exercise 186
In a ZDD, each level corresponds to a variable, and a node labeled $k$ represents a decision on $x_k$, where the low edge excludes the variable and the high edge includes it in the represented family...
TAOCP 7.1.4 Exercise 187
Fix variable order $x_1 < x_2$.
TAOCP 7.1.4 Exercise 188
In the ZDD representation used in this section, a Boolean function is identified with the family of subsets on which it is true.
TAOCP 7.1.4 Exercise 189
Let $B(f)$ and $Z(f)$ denote the reduced ordered BDD and reduced ordered ZDD of a Boolean function f(x_1,\ldots,x_n), constructed with the same variable ordering.
TAOCP 7.1.4 Exercise 190
Let $Q(f)$ denote the number of nodes in a reduced ordered decision diagram when sharing identical subgraphs, where the model allows both kinds of decomposition used in the section: Shannon decomposit...
TAOCP 7.1.4 Exercise 191
I can write the full editorial, but I need the actual problem statement in a clean, uncorrupted form first.
TAOCP 7.1.4 Exercise 192
The Z-transform is defined recursively on binary strings with special behavior depending on whether the second argument is a block of zeros, identical to the first half, or a general concatenation cas...
TAOCP 7.1.4 Exercise 193
Let $f(x_1,\ldots,x_n)$ have truth table $\tau$, and let $f^Z$ have truth table $\tau^Z$.
TAOCP 7.1.4 Exercise 194
Let $f(x_1,\ldots,x_n)$ have truth table $\tau$, and let $f^Z$ have truth table $\tau^Z$.
TAOCP 7.1.4 Exercise 195
Let $M_2(x_1,x_2,x_3,x_4)$ denote the 4-way multiplexer.
TAOCP 7.1.4 Exercise 196
Let variables $x_1,\dots,x_n$ be interpreted as characteristic bits of a subset $S \subseteq {1,\dots,n}$, where $x_i=1$ means $i \in S$.
TAOCP 7.1.4 Exercise 197
Let $f$ be a Boolean function on variables $x_1,\dots,x_n$, and let its BDD be given in the ordered and reduced form described in Section 7.
TAOCP 7.1.4 Exercise 198
Let $u$ and $v$ be ZDD nodes representing families of sets for Boolean variables ordered as $x_1 < x_2 < \cdots < x_n$.
TAOCP 7.1.4 Exercise 199
A ZDD represents a family of finite sets over an ordered universe of items $x_1 < x_2 < \cdots$.
TAOCP 7.1.4 Exercise 200
Let $F = \mathrm{MUX}(f,g,h)$ denote the Boolean function defined by selecting $g$ when $f=1$ and selecting $h$ when $f=0$, so that F = (f \wedge g)\ \vee\ (\neg f \wedge h).
TAOCP 7.1.4 Exercise 201
A projection function $x_j$ corresponds to the Boolean function that is $1$ exactly on those assignments where the $j$-th variable is $1$.
TAOCP 7.1.4 Exercise 202
We restart the argument from the actual structure of Knuth’s swap-in-place algorithm (Exercise 147) and then isolate exactly what changes in the ZDD setting.
TAOCP 7.1.4 Exercise 203
Given f=\{\emptyset,\{1,2\},\{1,3\}\}, \quad g=\{\{1,2\},\{3\}\}.
TAOCP 7.1.4 Exercise 204
The solution answers all parts, but part (b) is incorrect and breaks subsequent reasoning.
TAOCP 7.1.4 Exercise 205
We represent a family $f$ as a reduced ordered decision diagram over variables $x_1,x_2,\dots,x_n$, using the conventions of Section 7.
TAOCP 7.1.4 Exercise 206
Let $B(f)$ denote the number of nodes in the reduced ordered BDD representing a family $f$, including the sink nodes $\bot$ and $\top$.
TAOCP 7.1.4 Exercise 207
Let $A={i_1,i_2,\ldots,i_\ell}$ and let $F = e_{i_1}\cup\cdots\cup e_{i_\ell}$.
TAOCP 7.1.4 Exercise 208
Let the ZDD represent a family $\mathcal{F}$ of subsets of ${x_1,\dots,x_n}$, ordered by the variable indices, and let each node $k$ be labeled by $V(k)\in{1,\dots,n}$.
TAOCP 7.1.4 Exercise 209
Let the Boolean function be given by a ZDD with variable order $x_1,x_2,\ldots,x_n$.
TAOCP 7.1.4 Exercise 210
Let the ZDD for $f$ be given as a reduced ordered ZDD with variable ordering $x_1 < x_2 < \cdots < x_n$.
TAOCP 7.1.4 Exercise 211
Let $f$ be the Boolean function that represents solutions of an exact cover instance on a universe $U$ with a family of subsets encoded by variables $x_1,\dots,x_n$.
TAOCP 7.1.4 Exercise 212
The flaw in the previous solution is that it tried to define ZDD nodes as states indexed by a subset $X \subseteq U$.
TAOCP 7.1.4 Exercise 213
Let the ZDD represent a family $\mathcal{F}$ of subsets of ${x_1,\dots,x_n}$, ordered by the variable indices, and let each node $k$ be labeled by $V(k)\in{1,\dots,n}$.
TAOCP 7.1.4 Exercise 214
Let the chessboard be the standard $8 \times 8$ grid, decomposed into $64$ unit squares.
TAOCP 7.1.4 Exercise 215
A domino tiling of the $8\times 8$ board assigns to each unit square a partner square so that every square belongs to exactly one $1\times 2$ or $2\times 1$ domino.
TAOCP 7.1.4 Exercise 216
An 8×8 chessboard is partitioned into 32 dominoes in a perfect covering.
TAOCP 7.1.4 Exercise 217
Working
TAOCP 7.1.4 Exercise 218
We restart from the exact cover formulation, but we now build the BDD/ZDD constructions in a way that does not rely on variable ordering to magically enforce constraints.
TAOCP 7.1.4 Exercise 219
We restart from the definition of the family and apply the ZDD reduction rules exactly as stated in TAOCP §7.
TAOCP 7.1.4 Exercise 220
Let $F$ denote the family of 5757 SGB words represented on variables $a_1,\dots,z_5$ as in (131), and let the associated ZDD be constructed in the standard ordered way with variables processed in lexi...
TAOCP 7.1.4 Exercise 221
Let $F$ denote the family of 5757 SGB words represented on variables $a_1,\dots,z_5$ as in (131), and let the associated ZDD be constructed in the standard ordered way with variables processed in lexi...
TAOCP 7.1.4 Exercise 222
The universe consists of the 130 elementary variables $a_1,b_1,\ldots,z_5$, where $\ell_j$ denotes the event “letter $\ell$ occurs in position $j$ of a five-letter word.
TAOCP 7.1.4 Exercise 223
Working
TAOCP 7.1.4 Exercise 224
Let $D$ be a DAG in which every non-source vertex has in-degree $1$.
TAOCP 7.1.4 Exercise 225
Let $G = (V, E)$ be a finite graph and let $s, t \in V$ be distinct vertices.
TAOCP 7.1.4 Exercise 226
Exercise 225 constructs a ZDD whose paths encode all simple paths between two fixed vertices $s$ and $t$.
TAOCP 7.1.4 Exercise 227
Exercise 225 constructs a ZDD whose paths encode all simple paths between two fixed vertices $s$ and $t$.
TAOCP 7.1.4 Exercise 228
Let $G = (V, E)$ with distinguished start vertex $s$.
TAOCP 7.1.4 Exercise 229
Solution to TAOCP 7.1.4 Exercise 229.
TAOCP 7.1.4 Exercise 230
The reviewer is correct that the previous solution fails in its core task: it never engages with the specific graph (133).
TAOCP 7.1.4 Exercise 231
The graph $P_8 \times P_8$ is the standard $8 \times 8$ rectangular grid graph.
TAOCP 7.1.4 Exercise 232
A king’s move on the $8\times 8$ chessboard connects any two squares that differ by at most $1$ in each coordinate, excluding equality, so each vertex $(i,j)$ is adjacent to all squares in its $3\time...
TAOCP 7.1.4 Exercise 233
Let $G=(V,E)$ be a directed graph whose edges are linearly ordered as $E={e_1,\dots,e_m}$.
TAOCP 7.1.4 Exercise 234
Let $\Sigma$ be the set of the 49 postal codes in (18), each written as a two-letter string $XY$ over the alphabet of letters appearing in the codes.
TAOCP 7.1.4 Exercise 235
Let $\mathcal{W}$ be the finite set of five-letter English words under the chosen dictionary, and define a directed graph $G=(V,E)$ where $V=\mathcal{W}$ and there is an arc $x \to y$ if and only if t...
TAOCP 7.1.4 Exercise 236
Let $U = e_1 \sqcup e_2 \sqcup \cdots$, and let $C$ denote complement with respect to $U$.
TAOCP 7.1.4 Exercise 237
A family of sets is represented by a reduced ordered ZDD in which each internal node is labeled by an element $x_i$, with the low child corresponding to exclusion of $x_i$ and the high child correspon...
TAOCP 7.1.4 Exercise 238
Let $G = (V,E)$ denote the contiguous-USA graph of (18), and let $U \subseteq V$.
TAOCP 7.1.4 Exercise 239
Let $G = (V,E)$ and let $g$ denote the family of edges encoded in the sense of Exercise 236(e), so that $g = \bigcup_{u-v \in E}(e_u \sqcup e_v)$ and the family of independent sets is expressed by a f...
TAOCP 7.1.4 Exercise 240
Let $G=(V,E)$ be a finite graph.
TAOCP 7.1.4 Exercise 241
Let $Q_8$ be the queen graph on the $8\times 8$ chessboard.
TAOCP 7.1.4 Exercise 242
A set $S \subseteq {1,\dots,8}^2$ is admissible if no three distinct points of $S$ lie on a common affine line in $\mathbb{R}^2$.
TAOCP 7.1.4 Exercise 243
Let $\mathcal{f}$ be a family of sets.
TAOCP 7.1.4 Exercise 244
Let the edges of $P_3$ be $e_1$ and $e_2$, where $e_1$ joins vertices $1$ and $2$, and $e_2$ joins vertices $2$ and $3$.
TAOCP 7.1.4 Exercise 245
Let $f:\{0,1\}^n\to\{0,1\}$ be monotone.
TAOCP 7.1.4 Exercise 246
Let $G=(V,E)$ be a graph, and let $f$ be a monotone Boolean function on $V$ expressed in family algebra as in Section 7.
TAOCP 7.1.4 Exercise 247
A truth table of order $n$ is a binary string of length $2^n$.
TAOCP 7.1.4 Exercise 248
A Boolean function is sweet when every subtable arising from any prefix assignment is a bead.
TAOCP 7.1.4 Exercise 249
Let $f(x_1,\dots,x_n)$ be a Boolean function with truth table $\tau$ and BDD $T(f)$.
TAOCP 7.1.4 Exercise 250
A monotone Boolean function $f(x_1,\dots,x_5)$ is uniquely represented by its set of minimal true points, an antichain $A \subseteq 2^{[5]}$, and conversely every antichain determines such a function...
TAOCP 7.1.4 Exercise 251
Let $f(x_1,\dots,x_n)$ be a monotone Boolean function.
TAOCP 7.1.4 Exercise 252
Let $f(x_1,\dots,x_n)$ be a monotone Boolean function.
TAOCP 7.1.4 Exercise 253
Let $f(x_1,\ldots,x_n) = (\bar{x}_1 \wedge f_0) \vee (x_1 \wedge f_1)$, where $f_0, f_1$ are Boolean functions of $x_2,\ldots,x_n$.
TAOCP 7.1.4 Exercise 254
Let the Shannon decompositions from (52) be written in the standard form for monotone functions, f = (\bar x_1 \wedge f_l)\ \vee\ (x_1 \wedge f_h), \qquad g = (\bar x_1 \wedge g_l)\ \vee\ (x_1 \wedge...
TAOCP 7.1.4 Exercise 255
A multifamily $f$ assigns to each set $\alpha$ a multiplicity $m_f(\alpha) \in \mathbb{N}$.
TAOCP 7.1.4 Exercise 256
Let $x \in \mathbb{N}$ with binary expansion x = 2^{e_1} + \cdots + 2^{e_t}, \quad e_1 > \cdots > e_t \ge 0.
TAOCP 7.1.4 Exercise 257
The key mistake in the rejected solution is the attempt to encode coefficients as additional atoms.
TAOCP 7.1.4 Exercise 258
Let $f$ be a Boolean function on variables $x_1,\dots,x_k$ and let its BDD be ordered with $x_1 < x_2 < \cdots < x_k$.
TAOCP 7.1.4 Exercise 259
Solution to TAOCP 7.1.4 Exercise 259.
TAOCP 7.1.4 Exercise 260
Let $a_1 \dots a_n$ be a restricted growth string with a_1 = 0,\qquad a_{j+1} \le 1 + \max(a_1,\dots,a_j)\quad (1 \le j < n).
TAOCP 7.1.4 Exercise 261
Let $L \subseteq {0,1}^n$ be a language of fixed-length binary strings and let $f(x_1,\dots,x_n)$ be its characteristic Boolean function.
TAOCP 7.1.4 Exercise 262
The reviewer identifies the central defect: the assumption $B_0(f)=B(f)$.
TAOCP 7.1.4 Exercise 263
Let $H$ be an $m\times n$ parity-check matrix over $\mathbb{F}_2$, and let f(x)= [Hx=0], \qquad x=(x_1,\dots,x_n)^T.
TAOCP 7.1.4 Exercise 264
Let $f(x_1,\dots,x_n)$ be a Boolean function represented by an ordered reduced binary decision diagram with variable order $x_1 \prec \cdots \prec x_n$.
TAOCP 7.1.4 Exercise 265
Let $f$ be a Boolean function of variables $x_1,\dots,x_n$ given by a reduced ordered BDD.