Logic and Proof MT24, 3-CNF formulas

Suppose we have a CNF formula $\Phi$. Then we can convert it into an equivalent 3CNF formula by adding appropriate extra variables, e.g.

\[(a \vee b \vee c \vee d \vee e) \mapsto (a \vee b \vee q _ 1) \wedge (\overline{q _ 1} \vee c \vee q _ 2) \wedge (\overline q _ 2 \vee d \vee e)\]

Since this can be done in polynomial time, we are done.

Pick some clause $C$ of $\Phi$. Then:

If $C$ has one literal, say $\ell$, then introduce two new variables $q _ 1$ and $q _ 2$ and replace $C$ by

\[(\ell \vee q _ 1 \vee q _ 2) \wedge (\ell \vee q _ 1 \vee \overline{q _ 2} ) \wedge (\ell \vee \overline{q _ 1} \vee q _ 2 ) \wedge (\ell \vee \overline{q _ 1} \vee \overline{q _ 2} )\]

(Here $q _ 1$ and $q _ 2$ cycle through all possible truth assignments, so that we require $\ell$ to be satisfied).

If $C$ has two literals, say $\ell _ 1$ and $\ell _ 2$, replace $C$ by

\[(\ell _ 1 \vee \ell _ 2 \vee q _ 1) \wedge (\ell _ 1 \vee \ell _ 2 \vee \overline{q _ 1})\]

If $C$ has three literals, we don’t need to do anything.

If $C$ has more than three literals, we have $C = \ell _ 1 \vee \ell _ 2 \vee \cdots \vee l _ k$ for $k > 3$. Let $q _ 1, \cdots, q _ {n-3}$ be $n-3$ new variables. Replace $C$ by

\[(\ell _ 1 \vee \ell _ 2 \vee q _ 1) \wedge (\ell _ 3 \vee \overline{q _ 1} \vee q _ 2) \wedge (\ell _ 4\vee \overline{q _ 2} \vee q _ 3) \wedge \cdots \wedge (\ell _ {k-2} \vee \overline{q _ {k-4} } \vee q _ {k-3}) \vee (\ell _ {k-1} \wedge \ell _ k \wedge \overline {q _ {k-3} })\]

If there is a satisfying assignment of $C$, we can satisfy this clause by using the same truth values for $\ell _ i$ and alternating $q$ appropriately. If there is a satisfying assignment of the new clause, there must be at least one literal $\ell _ i$ satisfied, so $C$ is also satisfied.