TAOCP 7.1.1: Boolean Basics
Section 7.1.1 exercises: 132/132 solved.
Section 7.1.1. Boolean Basics
Exercises from TAOCP Volume 4 Section 7.1.1: 132/132 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [15] | simple | verified | 4m04s |
| 2 | [17] | medium | verified | 2m04s |
| 3 | ▶ [19] | medium | verified | 2m16s |
| 4 | [24] | medium | solved | 5m47s |
| 5 | [24] | medium | verified | 2m07s |
| 6 | [21] | medium | verified | 5m07s |
| 7 | [20] | medium | verified | 2m12s |
| 8 | [24] | medium | solved | 9m08s |
| 9 | [16] | medium | verified | 1m09s |
| 10 | [17] | medium | verified | 5m01s |
| 11 | [M25] | math-medium | verified | 2m34s |
| 12 | ▶ [M23] | math-medium | solved | 6m18s |
| 13 | [20] | medium | verified | 1m20s |
| 14 | [20] | medium | verified | 8m23s |
| 15 | ▶ [M20] | math-medium | verified | 2m23s |
| 16 | [15] | simple | verified | 57s |
| 17 | [10] | simple | verified | 1m07s |
| 18 | ▶ [30] | hard | verified | 4m |
| 19 | [20] | medium | solved | 4m45s |
| 20 | [M21] | math-medium | solved | 4m41s |
| 21 | [M20] | math-medium | verified | 1m33s |
| 22 | [20] | medium | verified | 4m36s |
| 23 | [15] | simple | verified | 1m04s |
| 24 | [M30] | math-hard | verified | 1m31s |
| 25 | [M21] | math-medium | solved | 5m29s |
| 26 | [M25] | math-medium | solved | 6m23s |
| 27 | [M31] | math-hard | solved | 5m45s |
| 28 | [**] | verified | 4m | |
| 29 | [22] | medium | solved | 28s |
| 30 | ▶ [27] | hard | solved | 4m30s |
| 31 | ▶ [28] | hard | solved | 4m29s |
| 32 | ▶ [M29] | math-hard | solved | 4m04s |
| 33 | [M21] | math-medium | verified | 2m59s |
| 34 | ▶ [HM37] | hm-project | solved | 6m59s |
| 35 | [M25] | math-medium | solved | 4m24s |
| 36 | [M21] | math-medium | solved | 4m19s |
| 37 | ▶ [M21] | math-medium | solved | 4m31s |
| 38 | [25] | medium | verified | 59s |
| 39 | ▶ [25] | medium | verified | 1m05s |
| 40 | [23] | medium | solved | 4m45s |
| 41 | [20] | medium | verified | 1m12s |
| 42 | [20] | medium | verified | 1m01s |
| 43 | [20] | medium | solved | 5m21s |
| 44 | [M23] | math-medium | solved | 3m30s |
| 45 | [M20] | math-medium | solved | 6m04s |
| 46 | [20] | medium | verified | 2m51s |
| 47 | [20] | medium | verified | 1m34s |
| 48 | ▶ [21] | medium | verified | 1m24s |
| 49 | [22] | medium | verified | 2m38s |
| 50 | [HM23] | hm-medium | solved | 4m59s |
| 51 | ▶ [22] | medium | solved | 4m18s |
| 52 | [25] | medium | solved | 5m43s |
| 53 | [23] | medium | verified | 2m09s |
| 54 | [20] | medium | verified | 58s |
| 55 | ▶ [30] | hard | solved | 4m25s |
| 56 | ▶ [20] | medium | verified | 1m20s |
| 57 | [40] | project | solved | 6m27s |
| 58 | [37] | project | solved | 5m25s |
| 59 | [M20] | math-medium | solved | 5m55s |
| 60 | [10] | simple | verified | 1m15s |
| 61 | [13] | simple | verified | 1m01s |
| 62 | [25] | medium | verified | 1m11s |
| 63 | [20] | medium | verified | 2m44s |
| 64 | [23] | medium | solved | 5m38s |
| 65 | ▶ [M21] | math-medium | verified | 1m09s |
| 66 | [M25] | math-medium | solved | 5m20s |
| 67 | ▶ [HM40] | hm-project | solved | 2m38s |
| 68 | [46] | research | solved | 4m12s |
| 69 | ▶ [M36] | math-project | solved | 4m16s |
| 70 | ▶ [M39] | math-project | solved | 4m56s |
| 71 | ▶ [M21] | math-medium | solved | 4m22s |
| 72 | [M22] | math-medium | verified | 1m23s |
| 73 | [M22] | math-medium | solved | 5m40s |
| 74 | [M21] | math-medium | solved | 3m35s |
| 75 | [M36] | math-project | solved | 5m19s |
| 76 | [M35] | math-hard | solved | 1m |
| 77 | [M28] | math-hard | solved | 4m01s |
| 78 | ▶ [M36] | math-project | solved | 3m50s |
| 79 | ▶ [M27] | math-hard | solved | 4m32s |
| 80 | [27] | hard | verified | 2m16s |
| 81 | [26] | hard | verified | 2m21s |
| 82 | [25] | medium | solved | 4m20s |
| 83 | ▶ [38] | project | verified | 4m08s |
| 84 | [30] | hard | solved | 4m36s |
| 85 | ▶ [M25] | math-medium | solved | 3m48s |
| 86 | [45] | project | verified | 4m11s |
| 87 | [24] | medium | solved | 3m28s |
| 88 | [M21] | math-medium | verified | 1m10s |
| 89 | [24] | medium | verified | 1m09s |
| 90 | [21] | medium | verified | 1m15s |
| 91 | [46] | research | solved | 4m29s |
| 92 | [46] | research | solved | 4m34s |
| 93 | [M20] | math-medium | verified | 2m14s |
| 94 | [M21] | math-medium | verified | 2m42s |
| 95 | [M25] | math-medium | verified | 2m30s |
| 96 | [HM25] | hm-medium | verified | 3m52s |
| 97 | [10] | simple | verified | 1m05s |
| 98 | [M25] | math-medium | solved | 4m09s |
| 99 | ▶ [20] | medium | solved | 3m43s |
| 100 | [20] | medium | verified | 2m |
| 101 | [M25] | math-medium | verified | 7m52s |
| 102 | [M31] | math-hard | solved | 4m34s |
| 103 | [HM25] | hm-medium | solved | 7m12s |
| 104 | [25] | medium | solved | 8m17s |
| 105 | [M25] | math-medium | solved | 8m47s |
| 106 | ▶ [M35] | math-hard | solved | 9m42s |
| 107 | [7] | simple | verified | 4m48s |
| 108 | [M21] | math-medium | verified | 12m31s |
| 110 | [M23] | math-medium | solved | 6m48s |
| 111 | [M36] | math-project | solved | 6m07s |
| 112 | ▶ [M97] | math-research | solved | 8m03s |
| 113 | [24] | medium | solved | 9m23s |
| 114 | [20] | medium | verified | 2m30s |
| 115 | [M22] | math-medium | verified | 2m25s |
| 116 | ▶ [HM28] | hm-hard | solved | 9m14s |
| 117 | [M26] | math-hard | verified | 2m32s |
| 118 | [29] | hard | solved | 7m33s |
| 119 | [M8] | math-simple | solved | 6m46s |
| 120 | [23] | medium | solved | 7m06s |
| 121 | ▶ [M23] | math-medium | verified | 4m03s |
| 122 | [M25] | math-medium | solved | 6m12s |
| 123 | [46] | research | solved | 4m33s |
| 124 | [29] | hard | solved | 5m17s |
| 125 | [18] | medium | verified | 1m33s |
| 126 | [23] | medium | verified | 7m33s |
| 127 | [M25] | math-medium | verified | 6m15s |
| 128 | ▶ [29] | hard | verified | 3m31s |
| 129 | [M23] | math-medium | solved | 4m26s |
| 130 | [M31] | math-hard | solved | 5m55s |
| 131 | [HM42] | hm-project | solved | 4m53s |
| 132 | ▶ [HM30] | hm-hard | solved | 5m30s |
| 133 | [20] | medium | verified | 1m47s |
TAOCP 7.1.1 Exercise 1
Let $x$ denote the proposition “it was so,” and let $y$ denote the proposition “it would be so” (equivalently, the consequent asserted under the condition that $x$ holds).
TAOCP 7.1.1 Exercise 2
Let $P$ denote the Pincus interpretation and $E$ the ordinary Earth interpretation.
TAOCP 7.1.1 Exercise 3
Let $x,y \in {-1,+1}$, with $-1$ representing falsehood and $+1$ representing truth.
TAOCP 7.1.1 Exercise 4
Let $x \bar\wedge y$ denote NAND, i.
TAOCP 7.1.1 Exercise 5
Let a \mid b \;=\; a \bar{\wedge} b \;=\; \overline{a\wedge b}.
TAOCP 7.1.1 Exercise 6
Let a=f(0,0),\qquad b=f(0,1),\qquad c=f(1,0),\qquad d=f(1,1), so that the binary operation $\circ$ is represented by the truth table $abcd$.
TAOCP 7.1.1 Exercise 7
Let $f(x,y)$ denote the operation $x \circ y$.
TAOCP 7.1.1 Exercise 8
Let $B=\{0,1\}$.
TAOCP 7.1.1 Exercise 9
The statement is $(x \oplus y) \vee z = (x \vee z) \oplus (y \vee z).$ Using equation (5), $x\oplus y=1 \iff x\ne y.$ Take $x=0,\qquad y=1,\qquad z=1.$
TAOCP 7.1.1 Exercise 10
From the definition of the “random” function (22) in TAOCP, the Boolean function on two variables is f(0,0)=0,\quad f(1,0)=1,\quad f(0,1)=1,\quad f(1,1)=1.
TAOCP 7.1.1 Exercise 11
Equation (19) expresses every Boolean function $f(x_1,\ldots,x_n)$ uniquely as a multilinear polynomial, f(x_1,\ldots,x_n) = \sum_{S\subseteq\{1,\ldots,n\}} a_S \prod_{i\in S} x_i ,
TAOCP 7.1.1 Exercise 12
Let $g:\{0,1\}^n\to\{0,1\}$ be the Boolean function in (22), with values given by its truth table.
TAOCP 7.1.1 Exercise 13
Let $X_j$ be independent random variables with $\Pr(X_j = 1) = p_j, \qquad \Pr(X_j = 0) = 1 - p_j,$ and interpret $x_j$ in the Boolean function $f(x_1,\ldots,x_n)$ as $X_j$.
TAOCP 7.1.1 Exercise 14
We restart from the definitions used in Exercise 13 and the notion of self-duality.
TAOCP 7.1.1 Exercise 15
Let $f:\{0,1\}^n \to \{0,1\}$ be an arbitrary Boolean function.
TAOCP 7.1.1 Exercise 16
A full disjunctive normal form has the structure f(x_1,\ldots,x_n)=\bigvee_{k\in K} T_k(x_1,\ldots,x_n), where each $T_k$ is a minterm, that is, a conjunction of $n$ literals, each literal being eithe...
TAOCP 7.1.1 Exercise 17
The given De Morgan form is a conjunction of terms of the form $\overline{u_{i1}\wedge\cdots\wedge u_{ik_i}}$, followed by a single outer negation.
TAOCP 7.1.1 Exercise 18
The reviewer’s objections identify the key issue: the original proof tries to assign values to variables separately for each clause literal, which does not define a single consistent valuation.
TAOCP 7.1.1 Exercise 19
The previous solution failed because it never used the actual Boolean function specified in (22).
TAOCP 7.1.1 Exercise 20
Let $p$ be a prime implicant of $f \wedge g$.
TAOCP 7.1.1 Exercise 21
Let variables range over ${0,1}^n$.
TAOCP 7.1.1 Exercise 22
We restart from the definition and avoid introducing properties that cannot be justified.
TAOCP 7.1.1 Exercise 23
Let F = (\alpha \wedge \alpha z)\vee(\bar\alpha xz)\vee(x\bar y z).
TAOCP 7.1.1 Exercise 24
Let $A_k(x_1,\dots,x_{2^k})$ denote the Boolean function defined by a complete binary tree of height $k$ (with $2^k$ leaves), where the root is labeled $\wedge$ and levels alternate between $\wedge$ a...
TAOCP 7.1.1 Exercise 25
Let F(x_1,\ldots,x_n)=(x_1\vee x_2)\wedge(x_2\vee x_3)\wedge\cdots\wedge(x_{n-1}\vee x_n).
TAOCP 7.1.1 Exercise 26
Let f(x)=\bigwedge_{I\in\mathcal F}\bigvee_{i\in I}x_i, \qquad g(x)=\bigvee_{J\in\mathcal G}\bigwedge_{j\in J}x_j,
TAOCP 7.1.1 Exercise 27
Let m=|\mathcal F|,\qquad n=|\mathcal G|,\qquad N=m+n.
TAOCP 7.1.1 Exercise 28
Let $g$ be written in CNF form g(y_1,\dots,y_m)=\bigwedge_{x:\,f(x)=1}\left(\bigvee_{j:\,p_j(x)=1} y_j\right).
TAOCP 7.1.1 Exercise 29
Let v_1<v_2<\cdots<v_m be the given increasing sequence of $n$-bit integers, and let $j$ be fixed.
TAOCP 7.1.1 Exercise 30
The previous solution failed at one essential point: it treated “$C \subseteq V \cap (V \oplus 2^j)$” as if it could be checked in $O(1)$ time per coordinate without explaining how to avoid enumeratin...
TAOCP 7.1.1 Exercise 31
We rebuild the solution carefully, fixing all three issues identified in the review.
TAOCP 7.1.1 Exercise 32
Let $c_1,\dots,c_m$ be subcubes of the $n$-cube.
TAOCP 7.1.1 Exercise 33
Let $V = \{0,1\}^n$, $N = |V| = 2^n$, and let $T \subseteq V$ be the truth set of $f$, chosen uniformly among all $m$-subsets of $V$.
TAOCP 7.1.1 Exercise 34
Let $N=2^n$ and let $F\subseteq\{0,1\}^n$ be chosen uniformly among all $m$-subsets.
TAOCP 7.1.1 Exercise 35
Let $B_1,\dots,B_p \in \{0,1\}^n$.
TAOCP 7.1.1 Exercise 36
The proof fails at the point where the “shadow” $S_k$ is introduced without a correct structural link to lexicographic ordering, and where coordinatewise dominance is incorrectly inferred.
TAOCP 7.1.1 Exercise 37
The reviewer correctly identifies the structural mistake: the previous construction collapsed the overlapping nature of the clauses into independent blocks.
TAOCP 7.1.1 Exercise 38
Let the given function in disjunctive normal form be f = C_1 \vee C_2 \vee \cdots \vee C_m, where each clause $C_i$ is a conjunction of literals of the form $x_j$ or $\bar{x}_j$.
TAOCP 7.1.1 Exercise 39
Let the internal nodes of the extended binary tree be $v_1,\ldots,v_N$ and assign to each $v_k$ a Boolean variable $y_k$.
TAOCP 7.1.1 Exercise 40
The previously given CNF is internally inconsistent as written.
TAOCP 7.1.1 Exercise 41
Let $x_{ij}$ be a Boolean variable for $1 \le i \le m$, $1 \le j \le n$, with the intended meaning that pigeon $i$ is placed in hole $j$.
TAOCP 7.1.1 Exercise 42
Let the Boolean variables be $x, y$.
TAOCP 7.1.1 Exercise 43
Let $F$ be a CNF formula whose clauses are all Horn or Krom (2-literal), possibly mixed.
TAOCP 7.1.1 Exercise 44
The reviewer’s criticism is decisive: the previous argument never engages with equation (33) as a mathematical statement.
TAOCP 7.1.1 Exercise 45
Let $f$ be a Horn function on $n$ variables and let M_f \subseteq \{0,1\}^n be its set of models.
TAOCP 7.1.1 Exercise 46
Let the terminal alphabet of grammar (43) be $\Sigma=\{a_1,\dots,a_{11}\}$.
TAOCP 7.1.1 Exercise 47
Let $j \prec k$ be a relation on ${1,\dots,n}$ as in Algorithm 2.
TAOCP 7.1.1 Exercise 48
A Horn clause is a disjunction of literals containing at most one uncomplemented variable.
TAOCP 7.1.1 Exercise 49
Let $F$ and $G$ be sets of Horn clauses over variables $x_1,\ldots,x_n$, defining Boolean functions $f$ and $g$ by f(x)=1 \;\Longleftrightarrow\; x \models F, \quad g(x)=1 \;\Longleftrightarrow\; x \m...
TAOCP 7.1.1 Exercise 50
We first fix the probabilistic model.
TAOCP 7.1.1 Exercise 51
A correct solution must avoid two mistakes in the previous attempt: 1.
TAOCP 7.1.1 Exercise 52
We restart from first principles and fix the strategic gaps by treating the game as a finite two–player perfect-information game with possible repetition (draw by repetition of full state).
TAOCP 7.1.1 Exercise 53
Let the instance in Exercise (37) be the standard “impossible comedy festival” construction: six performers T=\text{Tomlin},\ U=\text{Unwin},\ V=\text{Vegas},\ X=\text{Xie},\ Y=\text{Yankovic},\ Z=\te...
TAOCP 7.1.1 Exercise 54
Let $S = {u_1, u_2, \ldots, u_k}$ be a strong component in the implication digraph of a 2CNF formula, where each $u_i$ is a literal.
TAOCP 7.1.1 Exercise 55
The logical reduction in the original solution is correct; the only failure is algorithmic: the construction expands each clause into all pairs, which is quadratic in clause size and does not meet the...
TAOCP 7.1.1 Exercise 56
Let $f(x,y,z)=(x\lor y)\land(x\lor z)\land(y\lor z).$ First simplify several specializations of $f$.
TAOCP 7.1.1 Exercise 57
The reviewer’s objections identify a real structural issue: the previous argument treated “reachability closure” as a complete description of game states without proving that alternating quantifiers d...
TAOCP 7.1.1 Exercise 58
The key mistake is treating Horn monotonicity of _static satisfiability_ as if it eliminates all interaction between quantifiers.
TAOCP 7.1.1 Exercise 59
The flaw in the previous solution is exactly that it tries to match _pairs indexed by the same $Q'$_ with _pairs indexed by the same $a'$_ using only multiset equalities.
TAOCP 7.1.1 Exercise 60
The median $\langle xyz \rangle$ in (43) equals the majority function $\langle xyz \rangle = (x \wedge y)\ \vee\ (y \wedge z)\ \vee\ (z \wedge x).$ For (a), let $a=x\wedge y$, $b=y\wedge z$, $c=x\wedg...
TAOCP 7.1.1 Exercise 61
The statement claims that for any Boolean binary operation $\circ$ in Table 1, the identity x \circ (yz) \;=\; (w \lor x)(w \lor y)(w \lor z) holds for some fixed Boolean value $w$ depending only on $...
TAOCP 7.1.1 Exercise 62
Let $A = f(x_1, x_2, 0, x_4, \ldots, x_n), \quad B = f(x_1, x_2, x_3, x_4, \ldots, x_n), \quad C = f(x_1, x_2, 1, x_4, \ldots, x_n).$ Since $f$ is monotone, replacing a variable by a larger bit cannot...
TAOCP 7.1.1 Exercise 63
Let $M_5(a_1,a_2,a_3,a_4,a_5)$ be the majority-of-five function, i.
TAOCP 7.1.1 Exercise 64
We prove both directions carefully, starting from the correct structural reading of the condition.
TAOCP 7.1.1 Exercise 65
Let $[n]={1,2,\ldots,n}$.
TAOCP 7.1.1 Exercise 66
Let $C$ be a coterie on $[n]=\{1,\dots,n\}$.
TAOCP 7.1.1 Exercise 67
Let a triangular grid of order $n$ consist of all triples $(x,y,z)$ of nonnegative integers with $x+y+z=n$.
TAOCP 7.1.1 Exercise 68
The previous solution fails because it never produces a genuine upper bound.
TAOCP 7.1.1 Exercise 69
We address the reviewer’s objections by rebuilding the argument from the ground up, without assuming any cyclic order, interval structure, or median decomposition.
TAOCP 7.1.1 Exercise 70
The previous solution failed because it replaced the given construction of $g$ with an unrelated “two-point modification” and never analyzed the actual formula.
TAOCP 7.1.1 Exercise 71
Let the median operation be $m(x,y,z)$ satisfying axioms $(51),(52),(59)$, where $(52)$ states full symmetry: m(x,y,z)=m(x_{\sigma(1)},x_{\sigma(2)},x_{\sigma(3)}) \quad (\sigma\in S_3).
TAOCP 7.1.1 Exercise 72
Let the median operation be written $\langle x,y,z\rangle$.
TAOCP 7.1.1 Exercise 73
Let $G$ be the median graph of the median algebra $M$.
TAOCP 7.1.1 Exercise 74
Let $I(u,v) = [u \mathinner{..} v]$ be defined by (57), so that t \in I(u,v) \quad \Longleftrightarrow \quad \langle u\, t\, v\rangle = t.
TAOCP 7.1.1 Exercise 75
We restart the proof cleanly from the axioms and avoid any assumption of symmetry or interval behavior not explicitly derived.
TAOCP 7.1.1 Exercise 76
Let $(M, xyz)$ be a system satisfying the median axioms (50), (51), and (52).
TAOCP 7.1.1 Exercise 77
A clean correction must avoid appealing to Θ-classes as black boxes and instead derive everything from the metric and median structure used in the statement: distances to a convex set, and uniqueness...
TAOCP 7.1.1 Exercise 78
Let $G$ be a median graph and fix the root $a$.
TAOCP 7.1.1 Exercise 79
Let $Q_m=\{0,1\}^m$.
TAOCP 7.1.1 Exercise 80
A partial cube is, by definition, a connected graph that admits an isometric embedding into a hypercube.
TAOCP 7.1.1 Exercise 81
We correct the proof by using the median property directly on a triple involving the root and the endpoints of an edge.
TAOCP 7.1.1 Exercise 82
The previous argument fails because it incorrectly assumes separability of the objective and performs illegal local substitutions.
TAOCP 7.1.1 Exercise 83
The error in the previous solution is exactly the unjustified assumption that the partial cube embedding behaves like a full product space.
TAOCP 7.1.1 Exercise 84
The reviewer correctly identifies two independent problems: 1.
TAOCP 7.1.1 Exercise 85
Let $D$ be an antisymmetric implication digraph on the literal set \{x_1,\bar x_1,\ldots,x_n,\bar x_n\}, closed under complementation of arcs.
TAOCP 7.1.1 Exercise 86
Let a=(uwx),\qquad b=(uxy),\qquad c=(abz)=((uwx)\,(uxy)\,z).
TAOCP 7.1.1 Exercise 87
The key error in the previous solution is the assumption that each undirected edge is encoded symmetrically.
TAOCP 7.1.1 Exercise 88
Let $t$ denote the size parameter of the free tree $\langle 74\rangle$, and let the CI-net constructed in the proof of Theorem F be evaluated under a parallel schedule in which every module fires at t...
TAOCP 7.1.1 Exercise 89
Let $N$ be the CI-net obtained before the construction $\langle 73\rangle$ is applied, and let $N'$ be the CI-net after appending the new cluster of modules that enforces $u \to v$ for given literals...
TAOCP 7.1.1 Exercise 90
Let a CI-net module computing $\oplus$ be available, with two inputs $a,b$ and output $a \oplus b$, where $\oplus$ is associative by equation (4) and satisfies $x \oplus 0 = x$ by equation (5).
TAOCP 7.1.1 Exercise 91
The reviewer’s objections are essentially correct: the previous argument collapses the distinction between _graph-dependent algebraic representations_ and a _single uniform CI-net family_, and this in...
TAOCP 7.1.1 Exercise 92
The previous argument fails only at the treatment of outputs.
TAOCP 7.1.1 Exercise 93
Let $X$ be a retract of a graph $G$.
TAOCP 7.1.1 Exercise 94
Let the hypercube be $Q_n = \{0,1\}^n$ with graph metric $d(\cdot,\cdot)$ equal to Hamming distance.
TAOCP 7.1.1 Exercise 95
**Answer: True.
TAOCP 7.1.1 Exercise 96
Let $f:\{0,1\}^n\to\{0,1\}$ be representable by real weights $w_1,\dots,w_n$ and threshold $t$ such that for all $x\in\{0,1\}^n$, f(x)=1 \implies \sum_{i=1}^n w_i x_i \ge t,\qquad f(x)=0 \implies \sum...
TAOCP 7.1.1 Exercise 97
For $n=2$ with $w_1=w_2=1$, the function in (81) has the form
TAOCP 7.1.1 Exercise 98
Working
TAOCP 7.1.1 Exercise 99
Solution to TAOCP 7.1.1 Exercise 99.
TAOCP 7.1.1 Exercise 100
Let f(x_1,\ldots,x_n) = [w_1 x_1 + \cdots + w_n x_n \ge t] be a threshold function, where $x_i \in {0,1}$ and $w_i, t \in \mathbb{R}$.
TAOCP 7.1.1 Exercise 101
Let $f_1=1,\ f_2=1,\ f_{k+1}=f_k+f_{k-1}$.
TAOCP 7.1.1 Exercise 102
We prove the defining identity for self-duality in all variables: \hat f(x_0,x_1,\ldots,x_n)=\overline{\hat f(\bar x_0,\bar x_1,\ldots,\bar x_n)}.
TAOCP 7.1.1 Exercise 103
Let $f:\{0,1\}^n\to\{0,1\}$ be monotone and self-dual, given by its prime implicants $S_1,\dots,S_m\subseteq[n]$.
TAOCP 7.1.1 Exercise 104
The solution proceeds from the method of Exercise 103: a threshold function f(x)=1 \quad \Longleftrightarrow \quad \sum_i w_i x_i \ge t is converted into a majority function by embedding it into an eq...
TAOCP 7.1.1 Exercise 105
The previous argument fails because it replaces a global constraint on the Boolean cube with an artificial linear ordering.
TAOCP 7.1.1 Exercise 106
Stopped thinking
TAOCP 7.1.1 Exercise 107
For functions of two variables, $N(f)$ is the number of input pairs $(x,y)\in{0,1}^2$ for which $f(x,y)=1$, and $\Sigma(f)$ is the vector sum of all such pairs.
TAOCP 7.1.1 Exercise 108
Let the order be the prefix-sum (majorization) order: \alpha \ge \beta \quad \Longleftrightarrow \quad s_k(\alpha)\ge s_k(\beta)\ \text{for all }k,\qquad s_k(\alpha)=\sum_{i=1}^k \alpha_i.
TAOCP 7.1.1 Exercise 110
Let $x \le y$ denote the majorization order of Exercise 109.
TAOCP 7.1.1 Exercise 111
Let $f:\{0,1\}^n\to\{0,1\}$ be monotone and self-dual, and define the product measure A(f)=\sum_{x} f(x)\,w(x), \qquad w(x)=\prod_{i=1}^n p_i^{x_i}(1-p_i)^{1-x_i}, with $1 \ge p_1 \ge \cdots \ge p_n \...
TAOCP 7.1.1 Exercise 112
For $m=2$, Chase order is (0,0),(1,0),(0,1),(1,1), so
TAOCP 7.1.1 Exercise 113
Let $x = x_1+\cdots+x_{12}$.
TAOCP 7.1.1 Exercise 114
Let $S_{4,5}(x,x,x,x,y,y,z)$ denote the switching function that takes value $1$ precisely when the total number of true inputs among its seven arguments, counted with multiplicity, lies between $4$ an...
TAOCP 7.1.1 Exercise 115
Let the expression in (92) be the given construction on the variables $x_0, x_1, \ldots, x_{2m}$ that evaluates a nested combination of the binary operation $\oplus$.
TAOCP 7.1.1 Exercise 116
The failure in the previous solution comes entirely from collapsing the structure of prime implicants of symmetric Boolean functions into a single “choose $t$ variables” model.
TAOCP 7.1.1 Exercise 117
A term in a disjunctive normal form (DNF) is a conjunction of literals, each literal being either $x_i$ or $\bar{x}_i$ for some $1 \le i \le n$.
TAOCP 7.1.1 Exercise 118
Let $U=\{0,1\}^4$.
TAOCP 7.1.1 Exercise 119
We determine the correct asymptotic order of $b(n)$, the maximum number of prime implicants of a Boolean function on $n$ variables.
TAOCP 7.1.1 Exercise 120
This function is $1$ exactly on inputs of odd Hamming weight.
TAOCP 7.1.1 Exercise 121
Let P=[0,m]\times[0,n] with product order, and define the involution
TAOCP 7.1.1 Exercise 122
Reduce to the symmetric coordinate representation.
TAOCP 7.1.1 Exercise 123
Start from the correct structural reduction and then fix the two issues raised in the review: duplication of hyperplanes and the unjustified use of a “general position” region count.
TAOCP 7.1.1 Exercise 124
Let the group $G$ be the Table 5 symmetry group on Boolean functions of four variables: permutations of coordinates, independent complementation of variables, and complementation of the output.
TAOCP 7.1.1 Exercise 125
A Boolean function $f(x,y)$ is canalizing if there exists a variable, say $x$, and a value $a \in {0,1}$ such that $f(a,y)$ is independent of $y$, and therefore constant as a function of $y$.
TAOCP 7.1.1 Exercise 126
A Boolean function $f:\{0,1\}^n \to \{0,1\}$ is **canalizing** if there exist an index $i$, a value $a\in\{0,1\}$, and a value $b\in\{0,1\}$ such that x_i=a \;\Rightarrow\; f(x)=b.
TAOCP 7.1.1 Exercise 127
Let $f$ be canalizing in variable $x_i$.
TAOCP 7.1.1 Exercise 128
A Boolean function $f : \{0,1\}^n \to \{0,1\}$ is **canalizing** if there exists an index $i$ and a bit $a \in \{0,1\}$ such that the restriction of $f$ to the set $\{x : x_i = a\}$ is constant.
TAOCP 7.1.1 Exercise 129
Let $C_n$ denote the number of canalizing Boolean functions on $\{0,1\}^n$.
TAOCP 7.1.1 Exercise 130
This part is correct in the proposed solution, and we briefly restate it cleanly.
TAOCP 7.1.1 Exercise 131
A Boolean function $f:\{0,1\}^n\to\{0,1\}$ is Horn iff its set of true assignments is closed under intersection.
TAOCP 7.1.1 Exercise 132
Parts (a)–(c) are already correct in substance, so only the structure is restated briefly.
TAOCP 7.1.1 Exercise 133
Let the outcomes of the $n$ independent coins be $x=(x_1,\ldots,x_n)\in{0,1}^n$, with $\Pr(x_k=1)=p_k,\qquad \Pr(x_k=0)=1-p_k.$ Write the index of a bit string $x$ as $i(x)=x_1+2x_2+4x_3+\cdots+2^{n-1...