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).
Exercise 28. [**] $[2\dagger]$ (W. V. Quine, 1952.) If $f(x_1, \ldots, x_n)$ is a monotone function with prime implicants $p_1, \ldots, p_m$, let $g(y_1, \ldots, y_m) = \bigwedge_{f(x_1,\ldots,x_n)=1}(y_j \mid p_j(x) = 1)$. For example, the "random" function (23) is $f(x_1, \ldots, x_5)$, and it has five prime implicants given by (29) and (30); so $g(y_1, \ldots, y_5)$ is
$$(y_1 \vee y_2) \wedge (y_1 \vee y_3) \wedge (y_1 \vee y_4) \wedge (y_1 \vee y_5) \wedge (y_2 \vee y_3) \wedge (y_2 \vee y_4) \wedge (y_2 \vee y_5) \wedge (y_3 \vee y_4 \vee y_5)$$
in this case. Prove that every shortest DNF expansion of $g$ corresponds to a prime implicant of the monotone function $g$.
Verified: yes
Solve time: 4m
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). $$
For each clause $C_x$, define the index set
$$ S_x={j : p_j(x)=1}, $$
so
$$ g(y)=\bigwedge_x \left(\bigvee_{j\in S_x} y_j\right). $$
A conjunction $T=\bigwedge_{j\in S} y_j$ satisfies $T \models g$ if and only if $S$ is a hitting set of the family ${S_x}_x$: for every $x$, $S\cap S_x\neq \varnothing$.
A prime implicant of $g$ is a hitting set $S$ such that no proper subset of $S$ is still a hitting set.
Step 1: Structure of terms in a DNF
Let
$$ G = T_1 \vee \cdots \vee T_t $$
be a DNF for $g$, where each $T_i$ is a conjunction of positive literals. Each $T_i$ corresponds to a set $S_i\subseteq {1,\dots,m}$.
Because $G \equiv g$, every $S_i$ is a hitting set.
Step 2: Non-prime terms admit strictly stronger implicants
Assume some term $T = \bigwedge_{j\in S} y_j$ is not prime as an implicant of $g$. Then there exists $k\in S$ such that
$$ S' = S\setminus{k} $$
is still a hitting set, hence
$$ T' = \bigwedge_{j\in S'} y_j $$
is also an implicant of $g$.
Crucially, as sets of assignments,
$$ T \subseteq T', $$
so every assignment satisfying $T$ also satisfies $T'$. Thus $T'$ strictly dominates $T$.
Step 3: Dominated terms cannot appear in a minimum-term DNF
Let $G$ be a DNF with the minimum possible number of terms.
Assume $G$ contains a non-prime term $T$, and let $T'$ be the strictly stronger implicant obtained above.
Form
$$ G' = (G \setminus {T}) \vee T'. $$
Then:
- $G' \equiv g$, because replacing $T$ by an equivalent-or-stronger implicant preserves correctness.
- $T'$ covers every assignment previously covered by $T$.
Now consider redundancy:
Any term $U$ in $G'$ such that $U \subseteq T'$ as sets of assignments is redundant, because $T'$ already covers all of $U$. In particular, $T$ is no longer present, and any term whose region is contained in $T'$ can be deleted without affecting the function.
This yields a DNF equivalent to $g$ with no more terms than $G'$ and with at least one strict redundancy elimination whenever such containment occurs.
Hence, if a minimum-term DNF contained a non-prime term, we could replace it by a strictly stronger implicant and then simplify away all dominated terms. This produces a DNF representing $g$ with strictly fewer terms unless no term is dominated, i.e. unless every term is already inclusion-minimal.
Therefore, in any minimum-term DNF, no term can be non-minimal under implication.
Step 4: Converting implication-minimality into primeness
If a term $T$ is not a prime implicant, then it is not inclusion-minimal as a hitting set. Hence it is strictly dominated by a smaller implicant $T'$.
If such a term appeared in a minimum DNF, it would be replaceable by $T'$, after which $T$ becomes redundant (its entire region is contained in $T'$). This contradicts the assumption that the original DNF had minimum number of terms, because a dominated term can always be eliminated after replacement without requiring any compensating new term.
Thus no term in a minimum-term DNF can fail to be inclusion-minimal among implicants.
Conclusion
Every term in every shortest DNF of $g$ must be an inclusion-minimal implicant of $g$, i.e. a prime implicant.
Therefore every shortest DNF expansion of $g$ corresponds term-by-term to a prime implicant of $g$. ∎