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.


1 Answer 1


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'$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.