Reasoning: An Introduction to Logic, Sets, and Functions

Subsection 2.7.3 Satisfiability

Let’s return to the truth table for (p ∧ q) ∨ p:

Here we see that the truth value of the expression (p ∧ q) ∨ p depends upon the truth values of the variables: it is neither always true nor always false.

We will say that expressions like this are satisfiable. In other words, there is some way to satisfy them by making them true. If we are asked, “For what values is (p ∧ q) ∨ p satisfied?” we could answer, “For p being true and q being true.” We could also answer, “For p being true and q being false.” In fact, we can omit any mention of q and simply say, “Whenever p is true.”

Proving that an expression is satisfiable is straightforward. We can simply build a truth table for it. If at least one row of the final column is T, then the expression can be made true somehow and thus it is satisfiable.

The problem of determining whether a formula is satisfiable is often nicknamed the SAT problem. It turns out to play an important role in a lot of computing applications, including, for example, verifying that computer circuits do what they are supposed to do. You might then say, “Wonderful. We have an important problem and we have a simple way to solve it. All we have to do is build a truth table.”

The difficulty is that the real world problems that we’d like to solve this way may involve hundreds of thousands of variables. And recall that the number of rows in a truth table of n variables is 2n. Oops. If we really want to solve those problems, we’ll need to be a lot cleverer. Because of the importance of doing so, a lot of effort gets devoted to finding exactly such clever techniques. Just as a quick measure of this, we’ll point out that there’s an important world-wide conference devoted to it every year.