Part 3: Truth Tables
Why Truth Tables Matter
Remember playing a board game where you consider all possible moves before deciding? Truth tables do something similar for logical statements. They list every possible combination of truth values for your basic propositions (like "It's raining" or "I have an umbrella") and show whether a larger, compound statement (like "It's raining AND I have an umbrella") is true or false in each scenario.
Building on What We've Learned
In Part 2, we introduced three connectives:
- Negation: "not" (\(\neg\))
- Conjunction: "and" (\(\land\))
- Disjunction: "or" (\(\lor\), used inclusively)
Now, we'll systematically show how each connective behaves in every possible scenario of truth and falsehood. This methodical approach helps us avoid mistakes (like confusing exclusive "or" with inclusive "or").
Connecting Back
From Part 2, recall:
- \(\neg p\) flips \(p\)'s truth value.
- \(p \land q\) is true only if both \(p\) and \(q\) are true.
- \(p \lor q\) is true if either \(p\) or \(q\) (or both) are true.
Truth tables will make these rules crystal clear by enumerating all possibilities.
Truth Table for Negation (\(\neg\))
Consider a single proposition \(p\). It can be either true (T) or false (F). A simple table for \(p\) and its negation \(\neg p\) is:
| \(p\) | \(\neg p\) |
|---|---|
| T | F |
| F | T |
Reading the rows:
1. If \(p\) is true, then \(\neg p\) is false.
2. If \(p\) is false, then \(\neg p\) is true.
Flipping a Coin
- Let \(p\) = "The coin shows heads."
- Then \(\neg p\) = "It is not the case that the coin shows heads" (in other words, "The coin shows tails").
If \(p\) is true (the coin is heads), \(\neg p\) is false (not heads means tails, which is false in this scenario). If \(p\) is false (the coin is not heads, i.e., tails), then \(\neg p\) is true.
Truth Table for Conjunction (\(p \land q\))
When we deal with two propositions \(p\) and \(q\), each can be either T or F. This means there are four possible combinations of truth values. The truth table for \(p \land q\) is:
| \(p\) | \(q\) | \(p \land q\) |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
Interpretation: \(p \land q\) is true only in the first row, where both \(p\) and \(q\) are true. In every other case, at least one of \(p\) or \(q\) is false, making \(p \land q\) false.
Two Conditions for a Concert
Suppose:
- \(p\) = "We have tickets."
- \(q\) = "The venue is open."
Then \(p \land q\) = "We have tickets and the venue is open." For the concert outing to be successful (true), both conditions must hold:
- If you don't have tickets, you can't get in (even if the venue is open).
- If the venue is closed, you can't get in even if you have tickets.
The table shows that only when both \(p\) and \(q\) are T (tickets and open) is \(p \land q\) true.
Truth Table for Disjunction (\(p \lor q\))
Again, consider two propositions \(p\) and \(q\). The truth table for the inclusive "or" (\(\lor\)) is:
| \(p\) | \(q\) | \(p \lor q\) |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
Interpretation: \(p \lor q\) is false only in the last row (when both \(p\) and \(q\) are false). In all other cases (at least one true), \(p \lor q\) is true.
Inclusive vs. Exclusive Recap
Remember, this table is for inclusive "or". If we wanted an exclusive or (true when exactly one of \(p\) or \(q\) is true, but not both), the truth values in the first row would be different. (Exclusive or would give F when both are true.) Inclusive "or" covers the case where both can be true.
Example:
- \(p\) = "I have a discount coupon."
- \(q\) = "I have enough cash."
\(p \lor q\) = "Either I have a discount coupon or I have enough cash (or both)."
- If I have at least one of those, the statement is true. Only if I have neither (no coupon and not enough cash) is the statement false.
Compound Truth Tables
We can create truth tables for more complex expressions that combine multiple connectives. For example, let's analyze \(\neg p \lor (p \land q)\).
Example: \(\neg p \lor (p \land q)\)
To build the table, list all combinations for \(p\) and \(q\), then compute sub-expressions:
| \(p\) | \(q\) | \(\neg p\) | \(p \land q\) | \(\neg p \lor (p \land q)\) |
|---|---|---|---|---|
| T | T | F | T | T |
| T | F | F | F | F |
| F | T | T | F | T |
| F | F | T | F | T |
How the table is constructed:
1. List all possible truth combinations for \(p\) and \(q\) (the first two columns).
2. Compute \(\neg p\) for each row.
3. Compute \(p \land q\) for each row.
4. Finally, determine \(\neg p \lor (p \land q)\) using the results from the previous two columns.
Notice in the final column, the result is T for every row except one. In fact, \(\neg p \lor (p \land q)\) is true in all cases except when \(p\) is true and \(q\) is false (that was the second row). If you look closely, the final column is all T's except one F.
In the final column, being all T in every row would mean the expression is a tautology (always true). Here it's not all T, but mostly. We won't draw conclusions yet, but keep this in mind for later when we discuss special types of compound statements.
This methodical approach (breaking down complex statements into parts and evaluating each combination) helps us unravel complex logical expressions without guesswork.
Truth Tables in Decision-Making and Analysis
Truth tables have practical uses beyond homework exercises. They ensure no scenario is overlooked:
Validating Arguments
By using a truth table, you can check whether an argument's conclusion follows from its premises. If there's no row where all premises are true and the conclusion is false, the argument is logically valid.
Circuit Design
In digital electronics, truth tables describe how logic gates (AND, OR, NOT, etc.) operate. Engineers design and verify circuits (like computer processors) using truth tables to ensure the outputs are correct for all input combinations.
Software Testing
Programmers use truth-table-like thinking to test all combinations of certain conditions in code (especially complex if conditions) to ensure a program behaves correctly in every case. This is akin to covering every row of a truth table.
Legal Analysis
To analyze complex laws with multiple conditions, legal experts might use a structure like a truth table to map out when certain legal outcomes apply. This helps clarify how different facts of a case influence the verdict.
Software Testing Application
Consider a login system with two checks:
- \(p\): "User entered the correct password"
- \(q\): "User passed two-factor authentication (2FA)"
Suppose the access rule is: "A user is allowed in if (they entered the correct password AND passed 2FA) OR (they entered the correct password AND have an admin override)." In logical form, if we let \(r\) = "User has admin override", the rule could be \((p \land q) \lor (p \land r)\).
A truth table for \((p \land q) \lor (p \land r)\) helps testers ensure all scenarios (both conditions met, one met, none met, etc.) yield the expected outcome (allow or deny access).
Common Misconceptions
-
"The logical 'or' must exclude both being true."
Reality: By default, logical "or" is inclusive; both can be true. Exclusive or is a special case we have to specify separately. -
"Truth tables are only for math classes, not real life."
Reality: Truth tables (or the systematic thinking behind them) clarify any situation with clear yes/no conditions, from planning events to troubleshooting electronics. -
"If there are many propositions, truth tables are impossible to use."
Reality: It's true that truth tables grow quickly (2^n rows for n propositions). For large \(n\), other techniques or software are used. But for small numbers of propositions, truth tables are a straightforward and reliable tool. -
"A truth table can be done arbitrarily; there's no standard method."
Reality: There is a standard method: list all combinations of truth values for the basic propositions, then compute stepwise. This ensures consistency and that no case is missed.
Exercises
3.1. Construct a truth table for exclusive or (XOR) of two propositions \(p\) and \(q\). Hint: XOR is true when exactly one of \(p\) or \(q\) is true (and false otherwise). Verify that your final column matches the definition (true for one true input, false for both true or both false).
3.2. Build a truth table for \((p \land \neg q) \to \neg r\). How many rows will it have? (List them all.) Which rows make the implication false?
3.3. Using a truth table, determine if the expression \(p \lor (q \land \neg q)\) is a tautology, contradiction, or contingency (see Part 8 for definitions of these terms, if needed).
3.4. Write the conditions for a simple household alarm system and then represent them in a truth table. For example: "\(a\) = motion sensor detects movement, \(b\) = door sensor detects door open. Alarm sounds if \(a \lor b\)."
3.5. (Challenge) If a compound statement has 3 distinct propositions, how many rows will a complete truth table have? If it has 4 distinct propositions? Explain the pattern.
Next: In Part 4: If-Then Statements, we'll focus on the conditional connective (\(\to\)), learn its truth table, and see why it's defined the way it is.