Consider the following problem, called the Satisfiability Problem:

Given any Boolean expression, with

• logical variables and
• operators Not, And, Or, Implies

Can logical variables True and False be assigned to the variables, so that the resulting expression is True?

Possible Solutions?

One Approach: Brute Force

• Try all possible assignments of True and False to the variables.
• In the example, A, B, and C could each be True and False, for a total of 8 combinations.
• If there are N variables, this gives 2^N combinations to try.

created 3 January 2007 last revised 7 January 2007

previous   next