# Is any 2-CNF has 2-DNF representation?

I was asked a question whether I could come up with a 2-CNF over several variables that has no 2-DNF representation. However I thought that any CNF can be converted to DNF through some manipulations e.g. De Morgan, distributivity, etc.

How about $$\phi = (x_1 \vee x_2) \wedge (x_1 \vee x_3) \wedge (x_1 \vee x_4)$$? This formula is satisfied iff $$x_1$$ is true, or $$x_2$$, $$x_3$$, and $$x_4$$ are all true.
Suppose that $$\phi$$ had a $$2$$-DNF representation $$\phi'$$ and assume (w.l.o.g.) that:
• All clauses of $$\phi$$ contain exactly two literals (you can rewrite $$\ell$$ as $$(\ell \wedge \ell)$$).
• $$\phi'$$ contains no clauses that are trivially false (i.e., no clauses of the form $$(x_i \wedge \overline{x_i})$$).
Then, no clause $$(\ell_1 \wedge \ell_2)$$ of $$\phi'$$ can contain two literals for variables other than $$x_1$$, since otherwise setting $$\ell_1$$ and $$\ell_2$$ to true, and the rest of the variables to false, would satisfy $$\phi'$$ but not $$\phi$$.
Therefore, all clauses have one literal that is either $$x_1$$ or $$\overline{x_1}$$. However, no clause of the form $$(\overline{x_1} \wedge \ell)$$ can exist, since otherwise $$\ell \neq x_1$$ and setting $$\ell$$ to true and all the other variables to false would satisfy $$\phi'$$ but not $$\phi$$.
The only remaining case is the one in which all clauses are of the form $$(x_1 \wedge \ell)$$. Then, setting $$x_1$$ to false and $$x_2$$, $$x_3$$, $$x_4$$ to true satisfies $$\phi$$ but not $$\phi'$$.