2
$\begingroup$

Does every 3CNF propositional formula has an equivalent 2CNF propositional formula?

Definitions:

3CNF propositional formula is conjunctive normal form propositional formula, which is just conjunction $\land$ of clauses, where each clause is disjunction $\lor$ of at most 3 literals, where each literal is just boolean variable either with or without not $\lnot$ operator/connective.

2CNF propositional formula is conjunctive normal form propositional formula, which is just conjunction $\land$ of clauses, where each clause is disjunction $\lor$ of at most 2 literals, where each literal is just boolean variable either with or without not $\lnot$ operator/connective.

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Does equivalent mean equisatisfiable here? $\endgroup$ – Dmitri Chubarov Aug 19 '17 at 5:19
  • $\begingroup$ @Dmitri Chubarov if propositional formula $A$ is equivalent to propositional formula $B$ then this imply that $A$ is equisatisfiable to $B$ and $B$ is equisatisfiable to $A$, but the converse is false: If $A$ is equisatisfiable to $B$ then not necessarily that $A$ is equivalent to $B$. My question is for equivalence but not for equisatisfiability. $\endgroup$ – Farewell Stack Exchange Aug 19 '17 at 19:51
4
$\begingroup$

The single clause 3CNF:

$\varphi = a\lor b\lor c$

does not have an equivalent 2CNF. Suppose $\psi=\bigwedge\limits_{i=1}^m \psi_i$ is an equivalent 2CNF. Let $\psi_i$ be one of its clauses, and assume it involves the variables $a,b$. An assignment which sets $c=1$, but does not satisfy $\psi_i$, satisfies $\varphi$ but not $\psi$, hence they are not equivalent.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Ah, got confused, it's only possible to make a 2CNF with same amount of positive assignments as for given 3CNF but they won't be equal. $\endgroup$ – rus9384 Aug 18 '17 at 15:40
  • $\begingroup$ So Ariel's answer implies that rus9384's comment is wrong then. $\endgroup$ – Farewell Stack Exchange Aug 18 '17 at 15:41
  • $\begingroup$ Why would this argument fail when we try to apply it to prove that $a \vee b \vee c \vee d$ does not have an equivalent 3CNF? $\endgroup$ – Dmitri Chubarov Aug 19 '17 at 5:30
  • $\begingroup$ @DmitriChubarov It wouldn't. To be able to express all boolean functions on $k$ variables, you need $k$-variable clauses. The NP completeness of 3SAT has nothing to do with it. $\endgroup$ – Ariel Aug 19 '17 at 6:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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