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:
x_k \land \lnot y_k \\
\lnot x_k \land y_k \\
x_k \land y_k \\
The $n$ clauses lead to $3^n$ minterms with $2n$ literals each.
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.
The following Karnaugh Mahoney map illustrates an example for $n=3$:
$$(x_1 \lor y_1) \land (x_2 \lor y_2) \land (x_3 \lor y_3)$$
$$(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.