2
votes
Is there a 2SAT encoding for a NAND gate
It seems, based on the comments in other answers, that what you are after is a 2-CNF formula $\phi(q, a, b)$ equivalent to $q \iff \overline{a \land b}$. This is indeed not possible; the only possible ...
- 1,121
1
vote
Is there a 2SAT encoding for a NAND gate
There is no proof that it is impossible, but it is believed that it's unlikely to be possible, because if you could convert every circuit with NAND gates to 2CNF, you would have a proof that P = ...
D.W.♦
- 154k
Only top scored, non community-wiki answers of a minimum length are eligible