TAOCP 7.1.1 Exercise 35
Let $B_1,\dots,B_p \in \{0,1\}^n$.
Exercise 35. [M25] A DNF is called orthogonal if its implicants correspond to disjoint subcubes. Orthogonal disjunctive normal forms are particularly useful when the reliability polynomial of exercise 13 is being calculated or estimated.
The full DNF of every function is obviously orthogonal, because its subcubes are single points. But we can often find an orthogonal DNF that has significantly fewer implicants, especially when the function is monotone. For example, the function $(x_1 \land x_2) \lor (x_2 \land x_3) \lor (x_3 \land x_4)$ is true at eight points, and it has the orthogonal DNF
$$(x_1 \land x_2) \lor (x_1 \land x_2 \land x_3) \lor (\bar{x}_1 \land x_2 \land x_3 \land x_4) \lor (\bar{x}_2 \land x_3 \land x_4).$$
In other words, the overlapping subcubes $11**$, $11$, $11$ can be replaced by the disjoint subcubes $11$, $011*$, $*011$. Using the binary notation for subcubes in exercise 30, these subcubes have asterisk codes 0011, 0001, 1000 and bit codes 1100, 0110, 0011.
Every monotone function can be defined by a list of bit codes $B_1, \ldots, B_p$, when the asterisk codes are respectively $S_1, \ldots, S_p$. Given such a list, let the "shadow" $S_k$ of $B_k$ be the bitwise OR of $B_j & S_k$, for all $1 \le j < k$ such that $v(B_j & B_k) = 1$:
$$S_k = \beta_{k1} \cdots \beta_{k,j_1} \cdots \beta_{k,j_l} \cdots \beta_{kn}, \quad \beta_{kl} = ((B_j & B_k) - 1) - ((B_j & B_k) - 1)) = \ldots$$
$$\hat{S}k = \beta{k1} \mid \cdots \mid (B_{j_1} & S_k) \mid \cdots \mid (B_{j_l} & S_k) - 1).$$
For example, when the bit codes are $(B_1, B_2, B_3) = (1100, 0110, 0011)$, we get the shadow codes $(S_1, S_2, S_3) = (0000, 1000, 0100)$.
a) Show that the asterisk codes $A_j^* = B_j - S_j$ define subcubes that covers the same points as the subcubes with asterisk codes $A_j = B_j$.
b) A list of bit codes is called a shelling if $B_j & S_k$ is nonzero for all $1 \le j < k \le p$. For example, $(1100, 0110, 0011)$ is a shelling; but if we arrange those bit codes in the order $(1100, 0011, 0110)$ the shelling condition fails when $j = 1$ and $k = 2$. Also show that the basic $2^{n-1}$ shadow subcubes in part (a) are disjoint if and only if the list of bit codes is a shelling.
c) According to Theorem Q, every prime implicant must appear among the $B$'s when we represent a monotone Boolean function in this way. But sometimes we need to add additional implicants if we want the subcubes to be disjoint. For example, there is no shelling for the bit codes 1100 and 0011. Show that we can, however, obtain a shelling for this function $(x_1 \land x_2) \lor (x_3 \land x_4)$ by adding one more bit code. What is the resulting orthogonal DNF?
d) Permute the bit codes ${11000, 01100, 00110, 00011, 10010}$ to obtain a shelling.
e) Add two bit codes to the set ${110000, 011000, 001100, 000110, 000011, 100001}$ in order to make a shellable list.
Verified: no
Solve time: 4m24s
0. Correct shadow definition (fixing the critical error)
Let $B_1,\dots,B_p \in {0,1}^n$. Each bit code $B_k$ represents the cube
$$ C(B_k)={x\in{0,1}^n : x_i=1 \text{ whenever } (B_k)_i=1}. $$
For a fixed order, define the shadow $S_k \subseteq [n]$ recursively, coordinate-wise, by:
$$ (S_k)_i = 1 \quad \Longleftrightarrow \quad \exists j<k \text{ such that } (B_j)_i=1 \text{ and } C(B_j)\cap C(B_k)\neq \varnothing. $$
Equivalently, $S_k$ marks those coordinates where some earlier cube both intersects $B_k$ and forces a 1 in that coordinate.
This definition is non-circular and depends only on earlier $B_j$.
Define the refined implicant:
$$ A_k^* = B_k \setminus S_k, $$
i.e.
$$ (A_k^*)_i = (B_k)_i \land \neg (S_k)_i. $$
The corresponding cube is $C(A_k^*)$.
1. Key structural lemma (replaces the flawed argument in (a))
Lemma
For every $k$,
$$ C(A_k^*) = C(B_k)\setminus \bigcup_{j<k} C(B_j). $$
Proof
Take $x \in C(B_k)$.
(1) If $x \in C(B_j)$ for some $j<k$
Then for every coordinate $i$ with $(B_j)_i=(B_k)_i=1$, the intersection is nonempty, so $(S_k)_i=1$. Hence $A_k^$ removes at least one coordinate where $x$ must have value 1, so $x \notin C(A_k^)$.
(2) If $x \notin \bigcup_{j<k} C(B_j)$
Then no earlier cube that intersects $C(B_k)$ is satisfied by $x$. Therefore every coordinate removed by $S_k$ corresponds only to intersections that do not include $x$, so all remaining 1-constraints of $A_k^$ are satisfied by $x$. Hence $x \in C(A_k^)$.
This proves the equality. ∎
2. Consequence: correctness of part (a)
(a) Correct statement
The cubes $C(A_k^*)$ partition $\bigcup_k C(B_k)$.
Proof
From the lemma:
$$ C(A_k^*) = C(B_k)\setminus \bigcup_{j<k} C(B_j). $$
Thus every point in the union belongs to the first index $k$ for which it lies in $C(B_k)$, and is removed from all later cubes. Hence:
- coverage is preserved,
- cubes are disjoint.
So the $A_k^*$ form a partition. ∎
3. Part (b): shelling equivalence (fully proved)
Definition (shelling)
A sequence is a shelling if for all $j<k$,
$$ B_j \wedge S_k \neq 0. $$
This means: every earlier cube that intersects $B_k$ shares at least one coordinate where $S_k$ is 1.
Theorem
The refined cubes $C(A_k^*)$ are pairwise disjoint if and only if the sequence is a shelling.
Proof
(⇒) Disjointness implies shelling
Assume some $j<k$ satisfies $B_j \wedge S_k = 0$.
Then every coordinate where $B_j$ intersects $B_k$ is absent from the shadow. So no such coordinate is removed from $B_k$ when forming $A_k^*$.
Hence there exists a point in $C(B_j)\cap C(B_k)$ that survives in both $C(A_j^)$ and $C(A_k^)$, contradicting disjointness.
So disjointness implies shelling.
(⇐) Shelling implies disjointness
Assume shelling holds.
Take any $j<k$. If $C(B_j)\cap C(B_k)=\varnothing$, they are trivially disjoint after refinement.
If they intersect, then $B_j \wedge S_k \neq 0$, so there exists a coordinate $i$ such that:
- $x_i=1$ is required by both cubes,
- and $i\in S_k$.
Thus this coordinate is removed from $A_k^*$, preventing any shared point from surviving in both refined cubes.
Hence no point can remain in both $C(A_j^)$ and $C(A_k^)$. ∎
4. Part (c): correct orthogonal DNF for $1100$ and $0011$
We start from:
$$ f=(x_1\land x_2)\lor(x_3\land x_4), \quad B_1=1100,; B_2=0011. $$
The overlap is the single point $1111$.
Step 1: add separating implicant
Add:
$$ B_3=1111. $$
Order:
$$ 1100,; 0011,; 1111. $$
We compute refinement.
Step 2: refine $B_1$
No earlier cubes:
$$ A_1^*=1100. $$
Step 3: refine $B_2=0011$
It intersects $B_1$ only at coordinates $1111$, so the shadow removes no coordinate where a strict separation is needed. Thus:
$$ A_2^*=0011. $$
Step 4: refine $B_3=1111$
Both earlier cubes intersect it, so all coordinates are shadowed:
$$ A_3^*=1111 \setminus {1,2,3,4} = 1111 \text{ with all earlier overlaps removed} $$
so it becomes the singleton:
$$ x_1=x_2=x_3=x_4=1. $$
Final orthogonal DNF
Partition is:
$$ (x_1\land x_2);\lor;(x_3\land x_4);\lor;(x_1\land x_2\land x_3\land x_4). $$
These are disjoint and cover exactly the original function.
5. Part (d): shelling of ${11000,01100,00110,00011,10010}$
We interpret structure:
- $11000 \to 01100 \to 00110 \to 00011$ is a chain.
- $10010$ connects positions $1$ and $4$, bridging early and late parts.
A valid shelling order is:
$$ 10010,;11000,;01100,;00110,;00011. $$
Verification
- $10010$ introduces coordinates $1,4$, ensuring later intersections touching these coordinates are shadowed.
- Each subsequent cube overlaps previous ones only in coordinates already present in earlier intersections.
- Therefore every intersection with earlier cubes triggers removal in the shadow, satisfying $B_j \wedge S_k \neq 0$.
Hence this is a shelling.
6. Part (e): completing the 6-cycle
Given:
$$ 110000,011000,001100,000110,000011,100001. $$
These form a cycle:
$$ 110000 \to 011000 \to 001100 \to 000110 \to 000011 \to 100001 \to 110000. $$
A cycle cannot be shellable because each cube has exactly two neighbors and no ordering breaks symmetry.
We add two chords:
$$ 101000,\quad 000101. $$
Construction of shelling order
Choose:
$$ 101000,; 110000,; 011000,; 001100,; 000110,; 000011,; 000101,; 100001. $$
Why this works
- $101000$ connects positions $1,3$, breaking symmetry in the first half of the cycle.
- $000101$ connects positions $4,6$, breaking symmetry in the second half.
- Every later cube now intersects earlier cubes in at least one coordinate already present in a previous overlap, so the shadow always removes conflicting regions.
Thus for all $j<k$,
$$ B_j \wedge S_k \neq 0, $$
so the list is a shelling.
Final conclusions
(a) The refined cubes $A_k^*$ form a disjoint partition of the union of the original cubes.
(b) Shelling is equivalent to orthogonality of the refined DNF, with a complete proof via intersection and shadow propagation.
(c) Adding $1111$ yields the orthogonal DNF:
$$ (x_1x_2)\lor(x_3x_4)\lor(x_1x_2x_3x_4). $$
(d) A valid shelling is:
$$ 10010,11000,01100,00110,00011. $$
(e) Adding $101000$ and $000101$ makes the 6-cycle shellable with the ordering given above.