2 / 5
Propositional Logic & Truth Tables
Propositional Logic & Truth Tables
Proposition
A statement that is either true (T) or false (F), but not both.
Logical Connectives
- Negation: $\lnot p$ — "not $p$"
- Conjunction: $p \land q$ — "$p$ and $q$"
- Disjunction: $p \lor q$ — "$p$ or $q$"
- Conditional: $p \to q$ — "if $p$ then $q$"
- Biconditional: $p \leftrightarrow q$ — "$p$ if and only if $q$"
Conditional $p \to q$
False only when $p$ is true and $q$ is false. Logically equivalent to $\lnot p \lor q$.
Example 1
Build a truth table for $p \land (\lnot q)$.
| $p$ | $q$ | $\lnot q$ | $p \land \lnot q$ |
|---|---|---|---|
| T | T | F | F |
| T | F | T | T |
| F | T | F | F |
| F | F | T | F |
Example 2
Show $p \to q \equiv \lnot p \lor q$ by truth table.
Both columns match for all 4 rows of input, confirming logical equivalence.
Example 3
Is $(p \lor q) \land (\lnot p)$ a tautology?
When $p = T, q = F$: $(T \lor F) \land F = F$. Not a tautology.
Practice Problems
1. Build a truth table for $p \lor q$.
2. Truth table for $p \to q$.
3. What is the negation of "All cats are black"?
4. Is $p \land \lnot p$ a contradiction?
5. Converse of $p \to q$?
6. Contrapositive of $p \to q$?
7. Truth table for $p \leftrightarrow q$.
8. Is $p \lor \lnot p$ a tautology?
9. Write in symbols: "If it rains, the ground is wet."
10. Negate: $p \land q$.
11. How many rows in a truth table with 3 variables?
12. Simplify: $\lnot(\lnot p)$.
Show Answer Key
1. F only when both F
2. F only when T→F
3. "There exists a cat that is not black."
4. Yes
5. $q \to p$
6. $\lnot q \to \lnot p$
7. T when both same, F when different
8. Yes (law of excluded middle)
9. $r \to w$
10. $\lnot p \lor \lnot q$ (De Morgan)
11. $2^3 = 8$
12. $p$ (double negation)