Exponential blow-up of CNF to DNF $2^{n}$ terms?

Question

Why does every CNF formula for $(x_{1} \vee y_{1}) \wedge (x_{2} \vee y_{2})\wedge \ldots \wedge (x_{n} \vee y_{n})$ have at least $2^{n}$ terms?

This statement is on the Wikipedia page for DNF form here: https://en.wikipedia.org/wiki/Disjunctive_normal_form

But, I don't understand why it's true. Can someone please clarify? As shown above, the CNF has $2n$ terms. I'm not sure why the DNF has $2^{n}$ at least terms though.

Answer 1

Assuming the $x_i$ and $y_i$ variables are all different, you do indeed get $2^n$ terms, because you are going to have to keep Distributing $\land$ over $\lor$ to get the CNF into DNF. For example:

$$(A \lor B) \land (C \lor D)=$$

$$((A \lor B) \land C) \lor ((A \lor B) \land D )=$$

$$(A \land C) \lor (B \land C) \lor (A \land D) \lor (B \land D)$$

So, with $n=3$:

$$(A \lor B) \land (C \lor D) \land (E \lor F)=$$

$$ ((A \land C) \lor (B \land C) \lor (A \land D) \lor (B \land D)) \land E) \lor ((A \land C) \lor (B \land C) \lor (A \land D) \lor (B \land D)) \land F)=$$

$$ (A \land C \land E) \lor (B \land C\land E) \lor (A \land D\land E) \lor (B \land D\land E) \lor (A \land C \land F) \lor (B \land C\land F) \lor (A \land D\land F) \lor (B \land D\land F)$$

Now, if you look at the $8$ terms that you end up with, you'll notice that each term consists of exactly one variable from each of the original terms $A \lor B$, $C \lor D$, and $E \lor F$, and there are exactly $2^n$ ways to do this.

This principle can be generalized to something like this as well:

$$(A \lor B) \land (C \lor D \lor E)$$

So now you have two terms, but one with $2$ variables, and the other with $3$. So, we don't get a nice $2^n$. Still, the number of ways to pick exactly one variable from each term is $2 \cdot 3= 6$. Indeed, doing so gets you:

$$(A \land C) \lor (A \land D) \lor (A \land E) \lor (B \land C) \lor (B \land D) \lor (B \land E)$$

... which is exactly what you would get when doing all the Distributions. (so ... what I am saying is that you don;t have to go through all the Distributions step by step ... you can really do all those in 1 step!)

Answer 2

For each of the $2^n$ subsets $A$ of $\{1,2,\ldots,n\}$, there must be a conjunction that is true of $x_i\leftrightarrow i\in A$ and $y_i\leftrightarrow i\notin A$ for all $i$. Hence this conjunction can contain as literals at most $x_i$, $\neg y_i$ for $i\in A$ and $\neg x_i$, $y_i$ for $i\notin A$. Suppose for some $j$, this conjunction contains neither $x_j$ nor $y_j$. Then this conjunction (and the whole DNF) is true when $x_i\leftrightarrow i\in A\setminus\{j\}$ and $y_i\leftrightarrow i\notin A\cup\{j\}$. But for this case, the original CNF is false. We conclude that our conjunction contains at least (and hence exactly) one of $x_i, y_i$ for each $i$. It follows that our conjunction is flase for any subset $A'\ne A$ of $\{1,2,\ldots,n\}$ and $x_i\leftrightarrow i\in A'$ and $y_i\leftrightarrow i\notin A'$ for all $i$. Hence for each the $2^n$ subset we find a different conjunction, meaning that there are at least $2^n$ conjunctions. (We also saw that each of these conjunctins must contain at least $n$ terms)