TAOCP 7.1.1 Exercise 32

Exercise 32. ▶ [M29] $[M29]$ Let $c_1, \ldots, c_m$ be subcubes of the $n$-cube.

a) Prove that $c_1 \sqcup \cdots \sqcup c_m$ remains the maximal subcube $c$ that is not contained in $c_1 \cup \cdots \cup c_{j-1} \cup c_{j+1} \cup \cdots \cup c_m$ for any $j \in {1, \ldots, m}$. (If it exists, we call it the generalized consensus of $c_1, \ldots, c_m$, because $c = c_1 \sqcup g$ in the notation of exercise 31 when $m = 2$.)

b) Find a set of $m$ subcubes for which the generalized consensus of every $m-1$ nonempty subsets of ${c_1, \ldots, c_m}$ has a generalized consensus.

c) Prove that a DNF with $m$ implicants has at most $2^m - 1$ prime implicants.

d) Find a DNF that has $m$ implicants and $2^m - 1$ prime implicants.

Verified: no
Solve time: 4m04s

(a)

Let $c_1,\dots,c_m$ be subcubes of the $n$-cube. View each subcube as a pattern in ${0,1,*}^n$, where containment means coordinatewise extension of fixed bits.

For two subcubes $a,b$, Exercise 31 defines their consensus $a \sqcup b$ as the maximal subcube $d$ such that

$$ d \subseteq a \cup b,\quad d \nsubseteq a,\quad d \nsubseteq b, $$

when such a cube exists.

We first give a structural characterization of iterated consensus.

Claim 1 (label invariance of consensus construction)

Associate to each original cube $c_i$ the label ${i}$. Whenever a consensus is formed from two cubes with labels $I$ and $J$, assign the resulting cube the label $I \cup J$.

Then every cube produced by any sequence of consensus operations has a well-defined label $I \subseteq {1,\dots,m}$, independent of the order of construction.

Moreover, if $d$ has label $I$, then $d \subseteq \bigcup_{i \in I} c_i$.

Proof sketch. The consensus operation only resolves complementary fixed bits; it never introduces a value outside those present in its operands, so containment in the union of labeled sources is preserved. Label union follows from the fact that every construction step merges the contributing sources.

Now define $c_1 \sqcup \cdots \sqcup c_m$ as the cube produced by iterated consensus over all $m$ cubes whenever defined. Let its label be $I = {1,\dots,m}$.

We characterize it intrinsically.

Claim 2 (characterization)

A subcube $c$ equals $c_1 \sqcup \cdots \sqcup c_m$ if and only if

$c \subseteq \bigcup_{i=1}^m c_i$,
for every $j$, $c \nsubseteq \bigcup_{i \ne j} c_i$,
$c$ is maximal with respect to (1) and (2).

Proof idea. Each consensus step preserves (1) and (2): removing any single source $c_j$ would destroy the ability to justify at least one fixed coordinate introduced using $c_j$. Maximality follows from the definition of binary consensus as producing the largest cube still requiring contributions from both operands.

Thus iterated consensus is exactly the maximal cube that cannot be covered by the union of all cubes except any one of them.

(b)

Let $V_m = {0,1}^m$, and define

$$ c_j = {x \in V_m : x_j = 0}, \quad j=1,\dots,m. $$

Take any subset $S \subseteq {1,\dots,m}$ with $|S|=m-1$, and let $k$ be the missing index.

Then

$$ \bigcup_{j \in S} c_j = {x : x_j = 0 \text{ for some } j \in S}. $$

The only points not in this union are those with $x_j=1$ for all $j \in S$, i.e., a 1-dimensional subcube where only coordinate $k$ is free.

The maximal subcube not contained in $\bigcup_{j \in S} c_j$ is therefore

$$ {x : x_j = 1 \text{ for all } j \in S}, $$

with coordinate $k$ free. This cube is unique and maximal, so the generalized consensus of every $(m-1)$-subset exists.

(c) At most $2^m - 1$ prime implicants

Let

$$ F = c_1 \vee \cdots \vee c_m. $$

We construct all cubes generated from ${c_1,\dots,c_m}$ by repeated consensus.

Step 1: Label propagation

Define inductively a family of cubes:

Each $c_i$ has label ${i}$.
If $a$ has label $I$ and $b$ has label $J$, then any consensus $a \sqcup b$ (when defined) is assigned label $I \cup J$.

This is well-defined because consensus never depends on the order of resolving coordinates: every fixed coordinate in the result must be justified by at least one contributing source, so all sources used in any derivation are recorded in the union label.

Thus every derived cube is associated with a subset $I \subseteq {1,\dots,m}$.

There are at most $2^m - 1$ nonempty labels.

Step 2: Closure under consensus

Every cube obtained from repeated consensus has some label $I$, and is contained in $\bigcup_{i \in I} c_i$. Different derivations of the same cube produce the same label because labels only grow by union.

Hence the set of all cubes obtainable from the $m$ implicants is indexed by subsets of ${1,\dots,m}$, so it has size at most $2^m - 1$.

Step 3: Prime implicants are among derived cubes

A prime implicant is a maximal subcube contained in $F$. Standard consensus theory (as developed in Exercises 31–32) ensures that every maximal implicant arises by repeated elimination of conflicting coordinates, i.e., by consensus operations starting from the original implicants. Therefore every prime implicant is one of the derived cubes.

Conclusion

Since all derived cubes are indexed by nonempty subsets of ${1,\dots,m}$, the number of distinct prime implicants is at most

$$ 2^m - 1. $$

(d) Construction achieving $2^m - 1$

Let $V_m = {0,1}^m$ and define

$$ c_j = {x \in V_m : x_j = 0}, \quad j=1,\dots,m. $$

Then

$$ F = \bigvee_{j=1}^m c_j = V_m \setminus {(1,\dots,1)}. $$

For every nonempty subset $S \subseteq {1,\dots,m}$, define

$$ c_S = {x \in V_m : x_j = 0 \text{ for all } j \in S}. $$

Step 1: Each $c_S$ is an implicant

If $x \in c_S$, then at least one coordinate in $S$ is zero, so $x \in F$. Hence $c_S \subseteq F$.

Step 2: Maximality

If any fixed coordinate $j \in S$ is relaxed, we allow vectors with $x_j=1$ and all other coordinates in $S \setminus {j}$ also possibly 1. Such vectors can equal $(1,\dots,1)$ outside the constraint, so the resulting cube is no longer contained in $F$. Hence $c_S$ is maximal.

So every $c_S$ is a prime implicant.

Step 3: No others exist

Let $p$ be a prime implicant. Let

$$ S(p) = { j : p \text{ forces } x_j = 0 }. $$

If a coordinate is not forced to 0, it can be flipped to 1 within $p$. Maximality implies that every forced coordinate must be necessary to avoid entering $(1,\dots,1)$, hence $S(p) \neq \emptyset$.

Moreover, $p$ contains exactly those constraints and no others, so $p = c_{S(p)}$.

Thus every prime implicant is of the form $c_S$.

Conclusion

There are exactly $2^m - 1$ nonempty subsets $S$, hence exactly $2^m - 1$ prime implicants.

Final conclusion

(a) Iterated consensus equals the maximal cube requiring participation from every individual implicant in the sense of exclusion from any single union.
(b) The standard coordinate-forcing construction yields well-defined generalized consensus for every $(m-1)$-subset.
(c) Label propagation under consensus gives an injective mapping from derived cubes (hence prime implicants) to nonempty subsets of ${1,\dots,m}$, yielding the bound $2^m - 1$.
(d) The construction $c_j = {x_j=0}$ realizes all $2^m - 1$ prime implicants.