Let S be a
boolean expression in
conjunctive normal form. S is expressed as the
products of
sums (where product is defined as
AND, and sum is defined as
OR).
For example: (a+b) * (-b + c) * (-a + b + c)
The satisfiability of a boolean expression in conjunctive normal form was the first problem proven to be np-complete. See Cook's Theorem.