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.
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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'$.
