Proving that boolean 3-cnf satisfiability is NP-complete.

Given any boolean expression e, we will construct a boolean 3-cnf
expressin R(e), such that:
	a) If |e| = n, then |R(e)| = O(n).
	b) R(e) can be constructed from e in polynomial time.
	c) R(e) is satisfiable if and only if e is satisfiable.
Since 3-cnf satisfiability is trivially NP, and since we have already
proved that boolean satisfiability is NP-complete, we have that boolean
3-cnf satisfiability is NP-complete.

There is a context-free grammar that generates all boolean expressions.
Let T_e be the parse tree of e using this grammar.  Each internal node
of T_e corresponds to some subexpression of e.  The variables of R(e)
will consist of all the variables of e, together with one variable for
each internal node of T_e.  We call those the internal variables.
We postpone describing the clauses of R(e) for the moment.

Given an assignment of the variables of e, there is an induced assignment
on the internal variables.  Taken with the original assignment, this
gives an assignment of all the variables in R(e).  We will construct R(e)
in such a manner that a particular assignment of e is satisfying if and
only if the extension of that assignment to R(e) is satisfying.

If T_e has m nodes, then R_e initially has m+1 clauses, one for each
internal node and one that states that the whole expression is true.
We then take each of these clauses (which is not necessarily in CNF)
and replace it with an equivalent boolean expression which is the
conjunction of a small number of clauses of size 3.  We then conjoin
all these clauses to form R(e).