1
$\begingroup$

I know that not all truthtables have a corresponding 2-cnf representation, but is there a way to find out if a given truthtable has a 2-cnf representation, and if so to find what that is?

$\endgroup$
  • $\begingroup$ What is a 2CNF representation? $\endgroup$ – Yuval Filmus Jun 17 '18 at 7:51
3
$\begingroup$

This answer assumes that a 2CNF representation of a function is a 2CNF (on the same set of variables) that agrees with the function on all inputs.

Let's say that a clause $C$ is consistent with a function $f$ if $\lnot C \Rightarrow \lnot f$. Let $C_1,\ldots,C_m$ be the collection of 2-clauses consistent with your function $f$. Then $f$ has a 2CNF representation if and only if $f = C_1 \lor \cdots \lor C_m$. This gives a quasilinear time algorithm for deciding whether $f$, given as a truth table, has a 2CNF representation.

$\endgroup$

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.