Let S be a boolean expression
in conjunctive normal form
. S is expressed as the product
s of sum
s (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.