Subsection 2.3.4 The Size of the Truth Table Grows Quickly
Here’s the filled in table:
|
|
|
|---|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
The number of rows doubles each time we add a new variable since we must, for each combination of all of the earlier variables, now allow for the new variable to take on the value T and also for it to take on the value F. This graph of the powers of 2 shows how quickly the number of rows grows once the number of variables goes above 15 or so.
Let’s do an example. We’ll build a truth table for the following three-variable expression:
\(( \wedge \neg) \rightarrow \neg \)
The first three columns of the truth table will be labeled p, q, and r. Just as we did when we only had two variables, we need to specify every possible combination of truth values. The order in which we write the truth values in our table doesn’t matter. But, particularly as we move to larger numbers of variables, we need to write them systematically so that we’re sure of getting them all. We can generalize the system that we have used for the two variable case. Begin with the column corresponding to the first variable (in this case, p). Enter T in the first half of the rows and F in the second half of them. At this point, we have:
| p | q | r |
|---|---|---|
| T | ||
| T | ||
| T | ||
| T | ||
| F | ||
| F | ||
| F | ||
| F |
Then we move to the column corresponding to the second variable (i.e., q). Enter T in the first quarter of the rows, F in the second quarter, T in the third quarter and F in the last quarter. At this point, we have:
| p | q | r |
|---|---|---|
| T | T | |
| T | T | |
| T | F | |
| T | F | |
| F | T | |
| F | T | |
| F | F | |
| F | F |
Finally, we move to the column corresponding to the third (and last) variable (i.e., r). Enter T in the first eighth of the rows (which, in the case of three variables, is exactly one row), F in the next eighth, T in the next eighth, and so forth, alternating values. At this point, we have:
| p | q | r |
|---|---|---|
| T | T | T |
| T | T | F |
| T | F | T |
| T | F | F |
| F | T | T |
| F | T | F |
| F | F | T |
| F | F | F |
As we predicted, there are exactly eight rows.
Recall that we are trying to build a truth table for the expression (p ∧ ¬q) → ¬r. So we will want a final column that tells us the truth value of that expression given any set of truth values that may occur for the individual variables p, q, and r. Thus the final column’s title will be (p ∧ ¬q) → ¬r. To compute the values for that column, we’ll do the same thing we did in the case of complex statements involving just two variables: We’ll introduce working columns that specify the truth values for the intermediate expressions. We’ll then compute the final answer by using those working columns. Here’s what we get when we do that:
| p | q | r | ¬q | p ∧ ¬q | ¬r | (p ∧ ¬q) → ¬r |
|---|---|---|---|---|---|---|
| T | T | T | F | F | F | T |
| T | T | F | F | F | T | T |
| T | F | T | T | T | F | F |
| T | F | F | T | T | T | T |
| F | T | T | F | F | F | T |
| F | T | F | F | F | T | T |
| F | F | T | T | F | F | T |
| F | F | F | T | F | T | T |
We notice that the expression that we’re working with is almost (but not quite) always true. It is false in exactly one case: p is true, q is false, and r is true .
Problems 2.3.1.
Build a truth table for the expression: (r ∧ (p ∨ q)) → ¬(r ∨ p).