Exponential Blowup when converting DNF to KNF, proof of minimality

Question

Given the following boolean formula in KNF $$ (x_1 \lor y_1) \land (x_2 \lor y_2) \land \ldots (x_n \lor y_n) $$ we have the equivalent KNF \begin{align*} & (x_1 \land x_2 \land \ldots \land x_n) \\ \lor & (y_1 \land x_2 \land \ldots \land x_n) \\ \lor & (x_1 \land y_2 \land \ldots \land x_n) \\ \lor & (y_1 \land y_2 \land \ldots \land x_n) \\ & \vdots \\ \lor & (y_1 \land y_2 \land \ldots \land y_n) \end{align*} where in every clause some subset $A \subseteq \{y_1, \ldots, y_n\}$ are $y_i$'s, the rest are $x_i$'s. So we have $2^{n}$ clauses, one for every subset.

But how to show that the resulting KNF is minimal, i.e. that the exponential blowup is inavoidable?

Answer 1

The given CNF (Conjunctive Normal Form) consists of $n$ binary disjunctive clauses. The clauses are independent of each other, as each of the input variables does occur in exactly one clause. Each clause can be fulfilled in three ways:

$$\begin{aligned} x_k \land \lnot y_k \\ \lnot x_k \land y_k \\ x_k \land y_k \\ \end{aligned}$$

The $n$ clauses lead to $3^n$ minterms with $2n$ literals each.

The suggested DNF (Disjunctive Normal Form) consists of $2^n$ implicants (conjunctive clauses) with $n$ literals each. Each implicant has $n$ undetermined and $n$ fixed literals and thus covers $2^n$ minterms. To show that all implicants are essential, it is sufficient to show that each implicant exclusively covers one of the $3^n$ minterms.

Example:
The following Karnaugh Mahoney map illustrates an example for $n=3$:

CNF: $$(x_1 \lor y_1) \land (x_2 \lor y_2) \land (x_3 \lor y_3)$$

DNF: $$(x_1 \land y_2 \land x_3) \lor (y_1 \land y_2 \land x_3) \lor (x_1 \land x_2 \land x_3) \lor (y_1 \land x_2 \land x_3) \lor (x_1 \land y_2 \land y_3) \lor (y_1 \land y_2 \land y_3) \lor (x_1 \land x_2 \land y_3) \lor (y_1 \land x_2 \land y_3)$$

A Karnaugh map might look more familiar:

Each of the eight implicants covers eight minterms. In this example, the eight exclusively covered minterms are: $21, 22, 25, 26, 37, 38, 41, 42$
Example: Implicant $x_1 \land y_2 \land x_3$ has $3$ literals, while three remaining literals $x_2$, $y_1$ and $y_3$ are not specified and thus undetermined. There are $8$ possible choices for the undetermined literals. Hence, the implicant covers $2^3$ minterms. Each grid $1$-cell in the map corresponds to one minterm. There are $3^3 = 27$ minterms for this example as each of the $3$ CNF clauses has $3$ ways to be fulfilled. None of the eight implicants can be removed without uncovering one minterm. Therefore, the DNF is irredundant or minimal.

Why is the suggested cover minimal for all $n$?
For the general case, the $2^n$ minterms exclusively covered by one implicant have $n$ false (inverted) literals and $n$ true (positive) literals. The $2^n$ implicants do not have any false literals. The exclusively covered minterms therefore correspond to exactly one implicant each. None of the implicants can be removed. The implicants cannot be reduced in terms of number of literals without disregarding CNF clauses. The suggested DNF cover is minimal.