
Introduction to Logic

Tools for Thought

Satisfaction is the opposite of evaluation. We begin with one or more compound sentences and try to figure out which truth assignments satisfy those sentences. One nice feature of Propositional Logic is that there are effective procedures for finding truth assignments that satisfy Propositional Logic sentences. In this section, we look at a method based on truth tables.
A truth table for a propositional language is a table showing all of the possible truth assignments for the proposition constants in the language. The columns of the table correspond to the proposition constants of the language, and the rows correspond to different truth assignments for those constants.

The following figure shows a truth table for a propositional language with just three proposition constants (p, q, and r). Each column corresponds to one proposition constant, and each row corresponds to a single truth assignment. The truth assignments i and j defined in the preceding section correspond to the third and sixth rows of this table, respectively.
p 
q 
r 
1 
1 
1 
1 
1 
0 
1 
0 
1 
1 
0 
0 
0 
1 
1 
0 
1 
0 
0 
0 
1 
0 
0 
0 
Note that, for a propositional language with n proposition constants, there are n columns in the truth table and 2^{n} rows.

In solving satisfaction problems, we start with a truth table for the proposition constants of our language. We then process our sentences in turn, for each sentence placing an x next to rows in the truth table corresponding to truth assignments that do not satisfy the sentence. The truth assignments remaining at the end of this process are all possible truth assignments of the input sentences.

As an example, consider the sentence p ∨ q ⇒ q ∧ r. We can find all truth assignments that satisfy this sentence by constructing a truth table for p, q, and r. See below. We place an x next to each row that does not satisfy the sentence (rows 2, 3, 4, 6). Finally, we take the remaining rows (1, 5, 7, 8) as answers.

p 
q 
r 


1 
1 
1 

x 
1 
1 
0 
x 
x 
1 
0 
1 
x 
x 
1 
0 
0 
x 

0 
1 
1 

x 
0 
1 
0 
x 

0 
0 
1 


0 
0 
0 


The disadvantage of the truth table method is computational complexity. As mentioned above, the size of a truth table for a language grows exponentially with the number of proposition constants in the language. When the number of constants is small, the method works well. When the number is large, the method becomes impractical. Even for moderate sized problems, it can be tedious. Even for an application like Sorority World, where there are only 16 proposition constants, there are 65,536 truth assignments.
Over the years, researchers have proposed ways to improve the performance of truth table checking. However, the best approach to dealing with large vocabularies is to use symbolic manipulation (i.e. logical reasoning and proofs) in place of truth table checking. We discuss these methods in Lessons 4 and 5.

Use the arrow keys to navigate.
