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.