Simple discrete math problem: A and B in 3CNF

I need to write (A and B) in 3CNF, and for whatever reason, I can only come up with (A or B) in 3CNF (A OR B OR X) AND (NOT(X) OR A OR B). Any help is greatly appreciated!

1 Answer

How about $(A \lor A \lor A) \land (B \lor B \lor B)$?

If you need three different variables in each clause, you can use

$$(A \lor x_1 \lor x_2) \land (B \lor x_1 \lor x_2) \land \\ (\lnot x_1 \lor y_1 \lor z_1) \land (\lnot x_1 \lor y_1 \lor \lnot z_1) \land (\lnot x_1 \lor \lnot y_1 \lor z_1) \land (\lnot x_1 \lor \lnot y_1 \lor \lnot z_1) \land \\ (\lnot x_2 \lor y_2 \lor z_2) \land (\lnot x_2 \lor y_2 \lor \lnot z_2) \land (\lnot x_2 \lor \lnot y_2 \lor z_2) \land (\lnot x_2 \lor \lnot y_2 \lor \lnot z_2).$$

• Just an addition: there are infinitely many ways to make a CNF that is satisfiable iff $A\land B=1$. Sep 14, 2017 at 21:06