Part 8: More on Truth Tables
Why Understanding Truth Tables Matters
Throughout our journey, we've used truth tables as a reliable way to see when a compound statement is true or false. Think of them as blueprints showing how different combinations of truth values for propositions affect an overall expression.
Recap: The Five Propositional Connectives
We’ve encountered five key logical connectives. Here are their standard truth tables for reference:
Negation (\(\neg\))
| \(p\) | \(\neg p\) |
|---|---|
| T | F |
| F | T |
Conjunction (\(p \land q\))
| \(p\) | \(q\) | \(p \land q\) |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
Disjunction (\(p \lor q\))
| \(p\) | \(q\) | \(p \lor q\) |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
Conditional (\(p \to q\))
| \(p\) | \(q\) | \(p \to q\) |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
Biconditional (\(p \leftrightarrow q\))
| \(p\) | \(q\) | \(p \leftrightarrow q\) |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
These tables are the building blocks for constructing truth tables of more complex expressions.
Building and Reading Truth Tables
Complete Truth Table
A complete truth table explicitly lists all intermediate columns for sub-expressions, building up to the final result. You construct it step by step:
- List all possible truth combinations of your basic propositions (\(p, q, r, ...\)). For \(n\) basic propositions, you'll have \(2^n\) rows covering every combination of T/F.
- Compute intermediate columns for smaller parts of the expression (\(\neg p\), \(p \lor q\), etc.) as needed.
- Combine these intermediate results to determine the truth of the final compound expression in each row.
Example: \(p \land q \leftrightarrow \neg(\neg p \lor \neg q)\)
Let's do a complete table for the expression:
\(\(p \land q \;\leftrightarrow\; \neg(\neg p \lor \neg q).\)\)
We suspect this might always be true (it looks like a known logical equivalence: the right side resembles the logical NOT of an OR, which by De Morgan's law equals \(p \land q\)). The truth table will confirm if it's always true (a tautology).
We'll create columns for each sub-expression: \(p\), \(q\), \(p \land q\), \(\neg p\), \(\neg q\), \(\neg p \lor \neg q\), \(\neg(\neg p \lor \neg q)\), and finally \(p \land q \leftrightarrow \neg(\neg p \lor \neg q)\).
| \(p\) | \(q\) | \(p \land q\) | \(\neg p\) | \(\neg q\) | \(\neg p \lor \neg q\) | \(\neg(\neg p \lor \neg q)\) | \(p \land q \leftrightarrow \neg(\neg p \lor \neg q)\) |
|---|---|---|---|---|---|---|---|
| T | T | T | F | F | F | T | T |
| T | F | F | F | T | T | F | T |
| F | T | F | T | F | T | F | T |
| F | F | F | T | T | T | F | T |
Notice the final column is T in every row. This shows:
\(\(p \land q \;\equiv\; \neg(\neg p \lor \neg q),\)\)
which is indeed a tautology (they are equivalent for all possible truth values of \(p\) and \(q\)). This is a formal statement of one of De Morgan's laws (the negation of an OR is the AND of the negations).
Condensed Truth Table
Sometimes we don't need to show every intermediate step. A condensed table omits columns for sub-expressions that we don't need to explicitly see. We still include all combinations of basic propositions, but we calculate only the parts we're interested in.
Condensed Table Example
Suppose we want to analyze the expression \(p \land \neg q \to \neg r\). Instead of writing out every possible sub-expression, we might keep just enough columns to reach the final result. With three propositions \(p, q, r\), there are \(2^3 = 8\) rows. We might choose columns for \(p\), \(q\), \(r\), then \(\neg q\), then \(p \land \neg q\), then \(\neg r\), and finally \(p \land \neg q \to \neg r\):
| \(p\) | \(q\) | \(r\) | \(\neg q\) | \(p \land \neg q\) | \(\neg r\) | \(p \land \neg q \to \neg 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 didn't include separate columns for (for example) \(p \land \neg q \to \neg r\)’s subparts separately (like we combined computing the implication in one go at the end). The final column can be filled in by reasoning or by computing mentally using earlier columns. This is more efficient than a fully expanded table, but relies on your understanding to fill in some steps.
Deeper Look: Tautologies, Contradictions, and Contingencies
An expression that's true in every row of its truth table is called a tautology (or is logically valid). If it's false in every row, it's a contradiction. If it's true in some rows and false in others, it's a contingency.
In our complete table example above, the final column was all T, indicating a tautology. Let's summarize:
- Tautology: True under all possible truth assignments to its basic propositions. (Example: \(p \lor \neg p\) is always true, often called the Law of Excluded Middle.)
- Contradiction: False under all possible assignments (the final column would be all F). (Example: \(p \land \neg p\) is always false.)
- Contingency: True in some cases and false in others.
Example of a Tautology
"It's raining or it's not raining." In logical form: \(p \lor \neg p\). No matter the truth value of "\(p\)" ("It's raining"), the statement is always true. This is a tautology.
Examples in Each Category
-
Tautology Example: \(p \lor \neg p\) (the Law of Excluded Middle). For any truth value of \(p\), either \(p\) is true or \(\neg p\) is true. The table would be T in all rows.
-
Contradiction Example: \(p \land \neg p\). This is always false — \(p\) cannot be both true and false at the same time.
-
Contingency Example: \(p \to q\). As we've seen, \(p \to q\) can be true or false depending on \(p\) and \(q\). Some rows of its truth table are true (when \(p\) is false or \(q\) is true), and one row is false (when \(p\) is true and \(q\) false).
Applications of Truth Tables (Continued)
Truth tables are not just academic; they play a role in various domains:
Validating Arguments (using truth tables)
As mentioned, you can use truth tables to test argument validity by checking all cases. If you append the premises and conclusion in a table and find no row where premises are all true and conclusion false, the argument is valid (truth-table method for validity).
Circuit Design (revisited)
When designing a logical circuit (say for an electronics project or a computer chip), you might start with a desired truth table (behavior) and then derive a circuit that matches it. Conversely, for a given circuit, you can derive the truth table to understand its behavior fully.
Software Testing (exhaustive testing)
Consider conditions in an if statement with multiple clauses combined by AND/OR. A truth table of those conditions helps ensure you've tested every critical combination. For instance, if a decision depends on three booleans, there are 8 combinations to test; a truth table enumerates them clearly.
Legal and Policy Analysis
Complex regulations often involve multiple conditions (if X and Y but not Z, then outcome W, etc.). Making a truth table of conditions (where T/F indicates whether a condition is met) can help spot if there are any scenarios not accounted for or if some rule is redundant or contradictory.
Example: Complex Condition Analysis
Policy Logic Check
A policy states: "An employee gets a bonus if they have worked at the company for more than 5 years or (they have worked at least 2 years and made a significant achievement), and they are not under any disciplinary action."
Let:
- \(p\) = "Worked > 5 years"
- \(q\) = "Worked ≥ 2 years AND made significant achievement"
- \(r\) = "Under disciplinary action"
The rule can be expressed as: \((p \lor q) \land \neg r\).
To ensure this policy makes sense, a truth table for \((p \lor q) \land \neg r\) could be examined. It will show, for instance, that if an employee has not worked ≥2 years (so \(p\) and \(q\) are false), then even if they're not under discipline, they won't get a bonus (because the experience/achievement condition fails). The table can reveal if any combination seems unfair or unintended, prompting a policy revision.
Common Misconceptions (Advanced)
-
"If the final column isn't all T or all F, the statement must be random."
Reality: A mix of T and F in the final column (contingency) often still has patterns. For instance, \(p \to q\) is false in only one specific scenario. Recognizing those patterns is key to understanding logical relationships (like equivalences and implications between statements). -
"Two different-looking expressions can't have the same truth table."
Reality: They can! As we saw, \(p \land q\) and \(\neg(\neg p \lor \neg q)\) had identical truth tables (hence they are equivalent). Part of advanced logical analysis is identifying when different expressions actually mean the same thing logically. -
"To check two expressions are equivalent, I have to compare them in general, I can't just use one truth table."
Reality: You can create a single truth table with both expressions side by side. If their columns match for every row, they are logically equivalent. This truth-table method is a sure-fire way (though it can be tedious for many variables).
Exercises
8.1. Construct a truth table for \((p \land r) \lor (\neg p \land \neg r)\). Is this a tautology, contradiction, or contingency? (Hint: Compare to the biconditional truth table form.)
8.2. Determine via truth table whether \((p \to r) \land (q \to r)\) is equivalent to \((p \lor q) \to r\). (This asks if having two separate conditions implying \(r\) is the same as their disjunction implying \(r\).)
8.3. Use a truth table to check if \(\neg p \lor (p \land q)\) is equivalent to \(p \land q\). (This can tell you if a certain logical simplification is valid.)
8.4. Provide a brief real-world interpretation of a tautology and a contradiction (in terms of a statement or rule that is always true or always false).
8.5. Explain why a tautology can never be false (by referencing the truth table concept). Also, explain why a contradiction can never be true.
8.6. Imagine a simple electrical circuit that has two switches (A and B) in parallel controlling a light (meaning the light is on if either switch is on). Write the logical expression for the light being on in terms of A and B (use, say, \(A\) for "Switch A is ON"). Create a truth table for this expression and identify it as tautology, contradiction, or contingency.
8.7. (Challenge) We have three conditions in a board game that determine if a player gets a bonus: \(p\) = has the most points, \(q\) = found the secret item, \(r\) = helped another player. The rule is: "The player gets a bonus if either (\(p\) is true, or both \(q\) and \(r\) are true), but not if all three conditions are true." Express this rule in a logical formula and then create a truth table for it. Identify any contingencies (rows where sometimes they get a bonus, sometimes not, depending on conditions).
8.8. Provide a real-life scenario or statement that corresponds to a tautology. For instance, "Either I will go to the party or I will not go to the party." Then do the same for a contradiction. Explain why each fits the definition.
With these truth table skills, you can confidently analyze even complex logical statements and arguments. The next parts of the course will introduce Predicate Logic (where we talk about "all" and "some") and other advanced topics, building on the foundation we've established in propositional logic.