The Satisfiability Problem

We will use capital letters $A_i$, $B_i$, to stand for logical variables. These stand for statements like ``221 is a prime number'' or ``TH is the most common two-letter sequence in English,'' which are either true or false, i. e., these variables have values of either T or F. $\sim A_i$ (``not $A_i$'') is the statement that $A_i$ is false, so it has value T if $A_i$ has value F, and $\sim A_i$ has value F if $A_i$ has value T. We will also be interested in more elaborate formulas:

$$A_1\hbox{ or }\sim A_2\hbox{ or }\sim A_4\hbox{ or }A_7\hbox{ or }A_8$$

This formula says that either $A_1$ is true or $A_2$ is false, or $A_4$ is false, etc. The value of this formula will be T unless $A_1={\bf F}$, $A_2={\bf T}$, $A_4={\bf T}$, $A_7={\bf F}$, $A_8={\bf F}$. Thus, there is only one way in which the formula will be false.

Figure 1 illustrates a satisfiability problem.

  

Figure 1: A small (SP)

We want to assign T, F to all the variables so that all of the formulas have value T. Even in this small example, it may take you a minute or so to find such an assignment.