Section 3.2 Compound Statements, Truth Tables, and Logical Equivalence
In the previous section we were introduced to statements and our four foundational logical operators -- the negation (\(!p\)), the conjunction (\(p\land q\)), the disjunction (\(p \lor q\)), and the implication (\(p\to q\)). We described \(p\) and \(q\) as atomic statements and these statements involving operators as compound logical statements. We also evaluated the conditions under which these compound logical statements are true by constructing tables called truth tables. A single table summarizing the results from that previous section appears below: Table 3.2.1.
| \(p\) | \(q\) | \(!p\) | \(p\land q\) | \(p\lor q\) | \(p \to q\) |
|---|---|---|---|---|---|
| T | T | F | T | T | T |
| T | F | F | F | T | F |
| F | T | T | F | T | T |
| F | F | T | F | F | T |
Given your previous experience with mathematics, it likely comes as no surprise to you that we can combine our statements and logical operators together to build more complex logical statements. These more complex statements will be the focus of this section of our text.
Subsection 3.2.1 Truth Tables
In both the previous section and also the introduction to this section, we’ve utilized truth tables to analyse the conditions under which our compound logical statements are true or false. We’ve used this structures without much explanation though, so we’ll take a moment to discuss them here.
In short, a truth table is a stucture which allows us to systematically analyze truth values for logical statements. The number of rows and columns in a truth table will depend on the complexity of the logical statement to be analysed. For a logical statement that includes \(n\) distinct atomic statements, a truth table with \(2^n\) rows is required to capture all of the combinations of truth and falsity for each of the atomic statements. The number of columns in the truth table will vary with the number of operators in the statement. You can (and should) use the strategy below when constructing a truth table to analyze a logical statement or argument.
- Identify the number of atomic statements included in the compound logical statement.
- Build a truth table with \(2^n\) rows (not including the header row), where \(n\) is the number of atomic statements you identified in step 1.
- Build a column for each of the individual atomic statements.
- Look for any negation operators attached to atomic statements and build a column in the truth table for each negated atomic statement that appears.
- The order of operations for logic are: parentheses, negations, conjunctions/disjunctions (left to right), and then implications. Slowly add columns to your truth table according to this order of operations that will build up to the full compound logical statement you are analyzing.
Consider the following truth table as an example for analyzing the truth values of \(\left(p\lor !q\right)\to !r\text{.}\) Table 3.2.2.
Consider the following questions before trying to fill in the truth table on your own.
| \(p\) | \(q\) | \(r\) | \(!q\) | \(!r\) | \(p\lor !q\) | \(\left(p \lor !q\right)\to !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 |
- Why are there 8 rows in this truth table? Is having 8 correct?
- Why isn’t there a \(!p\) column if there are columns for \(!q\) and \(!r\text{?}\)
- Are 7 columns appropriate here? Can we fill in each column by looking at the truth values in at most two columns to the left of it?
Now fill in the remaining truth values before moving on.
Subsection 3.2.2 Compound Statements and Truth Tables
You have all the tools you need to analyze compound logical statements with the help of truth tables. As such, this subsection mainly consists of embedded example problems for you to solve. As usual, these embedded examples are interactive and will help you check your understanding. The earliest examples involve truth tables that are mostly set up for you. The final examples ask you to construct nearly all aspects of the truth tables while you build your solutions. The examples slowly build you up to being able to approach these problems independently.
Checkpoint 3.2.3. Evaluating a Truth Table I.
Checkpoint 3.2.4. Evaluating a Truth Table II.
Checkpoint 3.2.5. Evaluating a Truth Table III.
Checkpoint 3.2.6. Evaluating a Truth Table IV.
Checkpoint 3.2.7. Evaluating a Truth Table V.
Checkpoint 3.2.8. Evaluating a Truth Table VI.
Now you’ll be more responsible for building your own truth table. The rows are predetermined, but you’ll need to fill in the column headings.
Checkpoint 3.2.9. Building a Truth Table I.
Checkpoint 3.2.10. Building a Truth Table II.
Checkpoint 3.2.11. Building a Truth Table III.
Checkpoint 3.2.12. Building a Truth Table IV.
How did you do with building those truth tables? Are you gaining confidence in constructing the tables and using them to evaluate the conditions under which a compound logical expression are true or false? In the next subsection, we’ll see how to use truth tables to determine whether compound logical statements are equivalent to one another.
Subsection 3.2.3 Logical Equivalence
Now that we know how to evaluate logical expressions, the next natural question to ask is "when are two logical expressions equivalent to one another?". Simply put, two expressions are logically equivalent if they have exactly the same truth values under the same conditions. In terms of their truth tables, they have exactly the same combination of trues and falses in exactly the same order (as long as the atomic statements are arranged identically). This means that, if we build a truth table for each of the statements in queston, ensuring that the tables include the same atomic statements and that the truth values for those atomic statements appear in the same order, then two statements are logically equivalent if the final columns in their truth tables are identical.
For example, we might consider the logical statements \(p\to q\) and \(q\lor !p\text{.}\) We can construct and compare their truth tables below: Table 3.2.13.
and Table 3.2.14.
Notice that the final columns of the two truth tables are identical. Since \(p\to q\) and \(q\lor !p\) are true and false under exactly the same conditions, we have identified that they are logically equivalent. In this case, we’ll write that \(p\to q \equiv q\lor !p\text{.}\)
| \(p\) | \(q\) | \(p \to q\) |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
| \(p\) | \(q\) | \(!p\) | \(q\lor !p\) |
|---|---|---|---|
| T | T | F | T |
| T | F | F | F |
| F | T | T | T |
| F | F | T | T |
Perhaps you also noticed that building two truth tables was inefficient and took up lots of space and effort. We can condense our work into a single truth table as long as we compare the columns in the truth table that correspond to our statements in question. For example, consider the truth table below as an alternative to the two tables above. Table 3.2.15.
Notice still that the two columns corresponding to our statements, \(p\to q\) and \(q\lor !p\) are identical.
| \(p\) | \(q\) | \(!p\) | \(p\to q\) | \(q\lor !p\) |
|---|---|---|---|---|
| T | T | F | T | T |
| T | F | F | F | F |
| F | T | T | T | T |
| F | F | T | T | T |
Check your understanding in the following examples by building the truth tables and determining whether the statements are logically equivalent.
