# Is there an algorithm to find out if a truthtable can be represented as 2-sat, and if so find its 2-cnf?

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?

• What is a 2CNF representation? – Yuval Filmus Jun 17 '18 at 7:51

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.