Can an arbitrary formula in propositional logic be converted to 2CNF, preserving equivalence?

235 Views Asked by At

Suppose I have an arbitrary formula $\Phi$ in propositional logic. Is there a way to convert $\Phi$ to a 2-CNF formula $\Psi$ such that $\Phi \equiv \Psi$? If not, why not?

1

There are 1 best solutions below

0
On BEST ANSWER

No. Some functions can't get expressed using no more than two variables. For instance consider the following function

 x  y  z  F(x, y, z)
 0  0  0  1
 0  0  1  1
 0  1  0  1
 0  1  1  0
 1  0  0  1
 1  0  1  1
 1  1  0  1
 1  1  1  1