Part 8: More on Truth Tables
Why Understanding Truth Tables Matters
Throughout our journey, we've used truth tables as a reliable, step-by-step way to see exactly when a compound statement is true or false. Think of them as blueprints that show how different combinations of propositional truth values affect the overall expression.
Recap: The Five Propositional Connectives
We've encountered five key connectives. Here are their standard truth tables:
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 |
Building and Reading Truth Tables
Complete Truth Table
A complete truth table explicitly lists all intermediate columns for sub-expressions. You construct it step by step:
- List all possible truth combinations of your basic propositions (\(p, q, r, \dots\)).
- Compute intermediate columns for \(\neg p\), \(p \lor q\), etc., as needed.
- Combine these columns to determine the truth of the final expression.
Example: \(p \land q \leftrightarrow \neg(\neg p \lor \neg q)\)
Consider the expression:
We want a complete table that shows each sub-expression. We'll create columns for \(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 true in every row, so:
In mathematics, this is a classic identity: \(p \land q\) is logically equivalent to \(\neg(\neg p \lor \neg q)\) — this is one form of De Morgan's Law. This equivalence demonstrates how we can transform a conjunction into a form that uses negation and disjunction instead.
Condensed Truth Table
A condensed table omits columns for expressions you don't explicitly need. You still see all row combinations of (\(p, q, r, \dots\)), but you only compute intermediate columns if they help you find the final expression's truth.
Condensed Table Example
Suppose you want to analyze \(p \land \neg q \to \neg r\). You might just keep track of enough steps to see when \(\neg q\) is true, and then how that affects \(\neg r\). With three propositions, you have \(2^3 = 8\) rows, but you can skip adding separate columns for everything else if you don't need them.
For instance, you might create a condensed table with just:
| \(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 |
| ... | ... | ... | ... | ... | ... | ... |
This is more efficient than creating a full table with every possible intermediate expression.
Deeper Look: Why Some Expressions Are Always True or False
An expression that's true in every row of its truth table is a tautology (or logically valid). For example, the final result in our complete table for \(p \land q \leftrightarrow \neg(\neg p \lor \neg q)\) shows all T. That means no matter how you assign truth values to \(p\) and \(q\), that expression ends up true.
Tautology: True under all valuations of \(p, q, \dots\).
Contradiction: False under all valuations (the final column would be all F).
Contingency: True in some valuations and false in others.
Real-Life Example of a Tautology
"It's raining or it's not raining." In logic, \(p \lor \neg p\).
No matter how you define "raining" (true or false), that statement is always true, hence a tautology.
Examples in Each Category
Tautology Example: \(p \lor \neg p\) (Law of Excluded Middle)
No matter what truth value \(p\) has, this expression is always true.
Contradiction Example: \(p \land \neg p\)
This expression is always false, as a statement cannot be both true and false simultaneously.
Contingency Example: \(p \to q\)
This is true in some cases and false in others, depending on the values of \(p\) and \(q\).
Applications of Truth Tables
Validating Arguments
Truth tables allow us to check whether an argument's conclusion necessarily follows from its premises. If there's no row where all premises are true but the conclusion is false, the argument is valid.
Circuit Design
In digital electronics, truth tables represent how logic gates operate. Engineers use them to design and verify circuits that implement specific logical functions.
Software Testing
Programmers use truth table concepts to ensure all possible combinations of inputs are tested in conditional statements and decision branches.
Legal Analysis
To analyze complex laws with multiple conditions, legal experts sometimes use truth-table-like structures to determine when certain legal consequences apply.
Software Testing Application
Consider a login system with two checks: * \(p\): "User has entered correct password" * \(q\): "User has verified their identity via two-factor authentication"
The access condition might be: \((p \land q) \lor (p \land \text{admin\_override})\)
A truth table would help testers ensure all possible scenarios are tested properly.
Common Misconceptions
"A table with fewer columns is incomplete or incorrect."
Reality: You can condense a table if you carefully track only what's necessary.
"If an expression is false in one row, it's automatically a contradiction."
Reality: A contradiction is false in every row. Many expressions are false in some rows (making them contingent).
"De Morgan's laws are special extra rules."
Reality: They come directly from the logic definitions—like \(\neg(p \lor q) \equiv \neg p \land \neg q\)—and you can verify them by standard truth tables.
"Truth tables are only useful in academic settings."
Reality: Truth tables have practical applications in computer programming, digital circuit design, and analyzing complex conditions in various fields.
Exercises
Complete Truth Tables
8.1. Construct the complete truth table for \(\neg(p \lor q) \to \neg q\).
8.2. Construct the complete truth table for \(\neg(p \land q) \leftrightarrow (\neg p \lor q)\).
Condensed Truth Tables
8.3. Make a condensed table for \(p \lor q \leftrightarrow \neg(\neg p \land \neg q)\).
Hint: This is another famous De Morgan equivalence.
8.4. Condensed table for \(\neg(p \leftrightarrow q) \leftrightarrow (p \leftrightarrow \neg q)\).
Check whether it's a tautology, contradiction, or contingency.
8.5. \((p \land q) \lor r \;\leftrightarrow\; p \land (q \lor r)\)
Decide if it's valid or not by reading your condensed table's final column.
8.6. \((p \land q) \lor r \;\leftrightarrow\; (p \lor r) \land (q \lor r)\)
Another expression to test with a condensed table.
8.7. \((p \to (q \land r)) \leftrightarrow ((p \to q) \land (p \to r))\)
8.8. \((p \land q \to r) \leftrightarrow ((p \to r) \land (q \to r))\)
8.9. \((p \to (q \to r)) \leftrightarrow ((p \to q) \to r)\)
8.10. \((p \to (q \to r)) \leftrightarrow (p \land q \to r)\)
Going Deeper
8.11. Identify any tautologies or contradictions in the above exercises (8.1–8.10). Justify your answer.
8.12. Provide a real-life scenario or example that corresponds to a tautology. For instance, "Either I have an umbrella or I don't have an umbrella." Show how you could form that statement symbolically and see it's always true.
8.13. Find or create an expression (using at least three propositions) that is a contradiction. Show that no matter how you assign truth values, it's always false.
Practical Applications
8.14. Design a truth table for a simple alarm system that should activate under these conditions: motion is detected AND it's nighttime, OR the panic button is pressed. Use variables \(m\) for motion, \(n\) for nighttime, and \(b\) for button.
8.15. Create a truth table to represent a voting system where a proposal passes if: either a majority (2 out of 3) of board members vote yes, OR the chairperson and at least one other member vote yes. Use variables \(a\), \(b\), and \(c\) for the regular members and \(d\) for the chairperson.
8.16. A self-driving car must decide when to apply emergency braking. Create a truth table for the logical expression that determines when the car should brake, given these variables: * \(o\): obstacle detected ahead * \(s\): car speed is above 20mph * \(h\): human has overridden the system * \(m\): system is in maintenance mode
Famous Logical Equivalences
Here are some important logical equivalences that can be verified using truth tables:
De Morgan's Laws
- \(\neg(p \land q) \equiv \neg p \lor \neg q\)
- \(\neg(p \lor q) \equiv \neg p \land \neg q\)
Distribution Laws
- \(p \land (q \lor r) \equiv (p \land q) \lor (p \land r)\)
- \(p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)\)
Implication Equivalences
- \(p \to q \equiv \neg p \lor q\)
- \(\neg(p \to q) \equiv p \land \neg q\)
Double Negation
- \(\neg\neg p \equiv p\)
Final Thoughts
Truth tables are fundamental to logic:
- They systematically reveal when statements or compound expressions hold.
- They expose equivalences, contradictions, and tautologies.
- They're your best checking mechanism to ensure clarity in complex arguments.
- They bridge theoretical concepts with practical applications in computing and decision-making.
With this final part, you've completed a tour through the basic landscape of propositional logic—from simple statements to negations, conditionals, biconditionals, and advanced truth table techniques. Congratulations on building a solid foundation!
Next Steps: Explore how these skills evolve into more advanced logical forms, proofs, and even applications in computer science, mathematics, and everyday decision-making. Keep practicing with new statements, and before long, you'll be as comfortable reading logical expressions as reading a simple sentence.