Monotone 3SAT | Discussions of NP-Complete Problems

I told Daniel when he gave me his Monotone Satisfiability reduction that the actual problem mentioned in G&J was Monotone 3-Satisfiability. So he went off and did that reduction too.
The Problem:
Monotone 3 SAT. This is a more restrictive case of Monotone SAT

The Description:
Given an formula of clauses $F' = \wedge_{i=1}^{n} C'_{i}$ where each clause in $F'$ contains all negated or non-negated variables, and each clause $C_{i}$ contains at most $3$ variables. Does there exist an assignment of the variables so that $F'$ is satisfied?

Example:

$\\ F_{1} = (x_{1} \vee x_{3}) \wedge \\ (\neg x_{2} \vee \neg x_{3} \vee \neg x_{4}) \wedge \\ (x_{3} \vee x_{2} \vee x_{4}) \wedge \\ ( \neg x_{3} \vee \neg x_{5} \vee \neg x_{1})$
the following assignment satisfies $F'_{1}$ :
$\\ x_{1} \mapsto True\\ x_{2} \mapsto False\\ x_{3} \mapsto True\\ x_{4} \mapsto True\\ x_{5} \mapsto False$
However:
$\\ F_{2} = (\neg x_{1} \vee \neg x_{2} \vee \neg x_{3}) \wedge \\ (x_{1} \vee \neg x_{2} \vee \neg x_{3}) \wedge\\ (\neg x_{1} \vee x_{2} \vee \neg x_{3})\wedge \\ (\neg x_{1} \vee \neg x_{2} \vee x_{3})\wedge\\ (x_{1} \vee x_{2} \vee \neg x_{3})\wedge\\ (\neg x_{1} \vee x_{2} \vee x_{3})\wedge\\ (x_{1} \vee \neg x_{2} \vee x_{3})\wedge\\ (x_{1} \vee x_{2} \vee x_{3})$
And the following is $F_{2}'$ in Monotone 3SAT form:
$\\ F_{2}' = (\neg x_{1} \vee \neg x_{2} \vee \neg x_{3}) \wedge \\ (\neg y_{1} \vee \neg x_{2} \vee \neg x_{3}) \wedge\\ (\neg x_{1} \vee \neg y_{2} \vee \neg x_{3})\wedge \\ (\neg x_{1} \vee \neg x_{2} \vee \neg y_{3})\wedge \\ (x_{1} \vee x_{2} \vee y_{3})\wedge\\ (y_{1} \vee x_{2} \vee x_{3})\wedge\\ (x_{1} \vee y_{2} \vee x_{3})\wedge\\ (x_{1} \vee x_{2} \vee x_{3}) \wedge \\ (y_{1} \vee x_{1}) \wedge (\neg y_{1} \vee \neg x_{1}) \wedge \\ (y_{1} \vee x_{2}) \wedge (\neg y_{2} \vee \neg x_{2})\wedge \\ (y_{1} \vee x_{3}) \wedge (\neg y_{3} \vee \neg x_{3})$
are both unsatisfiable.

The reduction:
In the following reduction we are given an instance of 3SAT,
$F = \wedge_{i=1}^{n} C_{i}$ . Here each clause is of the form:
$C_{i} = x_{i1} \vee ... \vee x_{ik_i}$ where
$k_{i} < 4$
and each $x_{ik_i}$ is a literal of the form $\neg z_{l} \ or \ z_{l}$ .
We use the following construction to build an instance of Monotone 3 SAT out of the above instance of 3SAT :
In each clause $C_{i}$ we have at most one literal, $z_{l} \ or \ \neg z_{l}$ that is not of the same parity as the rest of the literals in the clause. For every such literal, we may preform the following substitution:
$z_{l} \rightarrow \neg y_{l} \ or \ \neg z_{l} \rightarrow y_{l}$ this yields a modified clause $C'_{i}$ .
Now we must be able to guarantee that $z_{l}$ and $y_{l}$ are mapped to opposite truth values, so we introduce the new clause:
$C''_{i} \ = \ ( z_{l} \vee y_{l}) \wedge ( \neg z_{l} \vee \neg y_{l})$ and conjunct it onto our old formula $F$ producing a new formula $F'$ .

For example:
$C_{i} \ = \ (z_{l_1} \vee z_{l_2} \vee \neg z_{l_3})$ so we preform the substitution
$\neg z_{l_3} \rightarrow y_{l_3}$
so $C'_{i} \ = \ (z_{l_1} \vee z_{l_2} \vee y_{l_3})$ and $C''_{i} \ = \ (z_{l_3} \vee y_{l_3}) \wedge ( \neg z_{l_3} \vee \neg y_{l_3})$

Now repeating this procedure will result in a new formula: $F' = (\wedge_{i=1}^{n} C'_{i}) \wedge (\wedge_{k=1}^{m} C''_{k})$ .
We claim logical equivalence between the $C_{i} \wedge C''_{i}$ and $C'_{i} \wedge C''_{i}$ This is semantically intuitive as the $C''_{i}$ clause requires all substituted literal $y_{l}$ in $C'_{i}$ to take the value opposite of $z_{l}$ this was the stipulation for the substitution initially. It is also verifiable by truth table construction for:
$\\ (z_{l_1} \vee z_{l_2} \vee \neg z_{l_3}) \wedge (z_{l_3} \vee y_{l_3}) \wedge ( \neg z_{l_3} \vee \neg y_{l_3}) \Leftrightarrow \\ (z_{l_1} \vee z_{l_2} \vee y_{l_3}) \wedge (z_{l_3} \vee y_{l_3}) \wedge ( \neg z_{l_3} \vee \neg y_{l_3})$

$True_{3SAT} \Rightarrow True_{Monotone \ 3 \ SAT}$ :
If there exists a truth assignment $\phi_{F}$ that satisfies $F$ , then we may extent this truth assignment to produce $\phi_{G}$ which will satisfy
$G = F \wedge (\wedge_{k=1}^{m} C''_{k})$ by letting $\phi_{G} (z_{l}) = \phi_{F} (x_{l})$ for all $l$ and letting $\phi_{G}(y_{l}) = \neg \phi_{F}(z_{l})$ for all $l$ .
Obviously if $F$ is satisfiable $G$ must be by the above construction of $\phi_{G}$ . So by the above claim we have that $\phi_{G}$ will satisfy $F'$ .
$True_{Monotone \ 3 \ SAT} \Rightarrow True_{3SAT}$ :
Continuing from the above, if we have a truth assignment $\phi_{F'}$ that satisfies $F'$ , then by the claim above it also must satisfy $G$ . And $F$ is a sub-formula of $G$ so any truth assignment that satisfies $G$ must also satisfy $F$ .