Automata

Let  be a 3cnf-formula.  An  assignment to the variables of  is one where each clause contains two literals with unequal truth values.  In other words an  -assignment satisfies  without assigning three true literals in any clause.

a. Show that the negation of any -assignment to  is also an -assignment.
b. Let SAT be the collection of 3cnf-formulas that have an -assignment.  Show that we obtain a polynomial time reduction from 3SAT to SAT by replacing each clause cI

(y1 V y2 V y3)

by the two clauses

(y1 V y2 V zI) and ( V y3 V b)

where zI is a new variable for each clause cI and b is a single additional new variable.
c. Conclude that SAT is NP-complete

See attached file for full problem description.