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

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.

• Does equivalent mean equisatisfiable here? – Dmitri Chubarov Aug 19 '17 at 5:19
• @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. – Farewell Stack Exchange Aug 19 '17 at 19:51

## 1 Answer

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.

• 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. – rus9384 Aug 18 '17 at 15:40
• So Ariel's answer implies that rus9384's comment is wrong then. – Farewell Stack Exchange Aug 18 '17 at 15:41
• 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? – Dmitri Chubarov Aug 19 '17 at 5:30
• @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. – Ariel Aug 19 '17 at 6:19