Day 23 — Propositions & truth tables
Day 23 — Propositions & truth tables
Stage III · concept day
Goal: Decide what is a proposition; build complete truth tables for formulas using \(\neg\), \(\wedge\), \(\vee\), \(\rightarrow\), \(\leftrightarrow\), and exclusive or; recognize tautologies, contradictions, and contingencies; translate English carefully with sufficient/necessary conditions; respect connective precedence.
Why this matters
Every if, assertion, test, and API contract is a claim that is either true or false in a given state. Truth tables are the exhaustive way to check small logical claims—the same idea as exhaustive testing of a boolean expression with \(2^n\) inputs. Stage III trains you to justify, not just compute. Later proof methods, quantifiers, and type-level reasoning all rest on solid propositional habits: know when an implication fails, know what “only if” means, and never treat \(\rightarrow\) as “causes.”
Theory
Propositions
A proposition (or statement) is a declarative sentence that is true or false, not both, and not “undecided,” in ordinary classical logic.
| Sentence | Proposition? | Why |
|---|---|---|
| \(2+2=4\) | Yes | Has a truth value (true) |
| \(7\) is even | Yes | False, but still a proposition |
| Close the door. | No | Command |
| What is \(2+2\)? | No | Question |
| \(x > 3\) (with free \(x\)) | Not yet | Open sentence / predicate—needs a value for \(x\) (Day 26) |
| This sentence is false. | Pathological | Liar paradox—excluded from ordinary propositional logic |
| The hash is valid. | Yes | In a fixed state of the system |
Atomic propositions (\(p\), \(q\), \(r\), …) have no internal logical structure for our purposes. Compound propositions are built from atoms with connectives.
Connectives defined by truth tables
We use T / F (or \(1\) / \(0\)). For \(n\) atoms there are \(2^n\) rows—list every combination systematically (binary counting: FFF, FFT, FTF, … or TTT, TTF, …). Never skip a row.
Negation \(\neg p\) (“not \(p\)”):
| \(p\) | \(\neg p\) |
|---|---|
| T | F |
| F | T |
Conjunction \(p \wedge q\) (“\(p\) and \(q\)”): true only when both are true.
| \(p\) | \(q\) | \(p \wedge q\) |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
Disjunction \(p \vee q\) (“\(p\) or \(q\)”): inclusive—true when at least one is true.
| \(p\) | \(q\) | \(p \vee q\) |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
Exclusive or \(p \oplus q\) (or \(p \,\mathrm{XOR}\, q\)): true when exactly one of \(p\), \(q\) is true.
| \(p\) | \(q\) | \(p \oplus q\) |
|---|---|---|
| T | T | F |
| T | F | T |
| F | T | T |
| F | F | F |
In symbols: \(p \oplus q \equiv (p \vee q) \wedge \neg(p \wedge q) \equiv (p \wedge \neg q) \vee (\neg p \wedge q)\). Specs that say “or” usually mean inclusive unless they say “exactly one,” “xor,” or “either … or … but not both.”
Implication \(p \rightarrow q\) (“if \(p\) then \(q\)”; \(p\) is antecedent, \(q\) is consequent): false only when \(p\) is true and \(q\) is false.
| \(p\) | \(q\) | \(p \rightarrow q\) |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
The last two rows are vacuous truth: a false hypothesis makes the implication true. That matches mathematics (“if \(n\) is both even and odd, then …”) and default classical reasoning: from a false premise, anything follows as an implication, not as free invention of facts.
Equivalent rewriting (proved by table later / Day 24–25):
\[p \rightarrow q \;\equiv\; \neg p \vee q.\]
Biconditional \(p \leftrightarrow q\) (“\(p\) if and only if \(q\)”; “\(p\) iff \(q\)”): true when \(p\) and \(q\) have the same truth value.
| \(p\) | \(q\) | \(p \leftrightarrow q\) |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
Also: \(p \leftrightarrow q \equiv (p \rightarrow q) \wedge (q \rightarrow p)\).
Reading implication in English
All of these mean \(p \rightarrow q\):
- If \(p\), then \(q\).
- \(p\) implies \(q\).
- \(p\) only if \(q\).
- \(q\) if \(p\).
- \(q\) whenever \(p\).
- \(q\) provided that \(p\).
- \(p\) is sufficient for \(q\); \(q\) is necessary for \(p\).
Sufficient vs necessary (memorize).
| Phrase | Meaning | Arrow |
|---|---|---|
| \(p\) is sufficient for \(q\) | \(p\) is enough to guarantee \(q\) | \(p \rightarrow q\) |
| \(p\) is necessary for \(q\) | \(q\) cannot hold without \(p\) | \(q \rightarrow p\) |
| \(p\) is necessary and sufficient for \(q\) | iff | \(p \leftrightarrow q\) |
“\(p\) only if \(q\)” is not \(q \rightarrow p\); it is \(p \rightarrow q\). Say the sentence aloud: “You get dessert only if you eat vegetables” means dessert implies vegetables were eaten—not the reverse.
Tautology, contradiction, contingency
- Tautology: true for every assignment (e.g. \(p \vee \neg p\), the law of excluded middle).
- Contradiction: false for every assignment (e.g. \(p \wedge \neg p\)).
- Contingency: true for some assignments, false for others (most interesting formulas).
Two formulas are logically equivalent when their biconditional is a tautology—full treatment Day 25. Today, detect tautologies by finishing a table whose final column is all T.
Building multi-column tables
For a compound formula, add subexpression columns in order of evaluation (innermost first). Example skeleton for \((p \rightarrow q) \wedge (q \rightarrow r)\): columns \(p\), \(q\), \(r\), \(p\rightarrow q\), \(q\rightarrow r\), then the conjunction—\(8\) rows.
Systematic row order for three variables \(p,q,r\):
| \(p\) | \(q\) | \(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 |
(Binary counting from \(111\) down to \(000\), or the reverse—pick one convention and stick to it.)
Precedence of connectives
When parentheses are omitted, common convention (always parenthesize when unsure):
- \(\neg\) (tightest)
- \(\wedge\)
- \(\vee\)
- \(\rightarrow\)
- \(\leftrightarrow\) (loosest)
So \(\neg p \vee q \rightarrow r\) means \(((\neg p) \vee q) \rightarrow r\), not \(\neg(p \vee q) \rightarrow r\) and not \(\neg p \vee (q \rightarrow r)\).
Implication and biconditional are often treated as right-associative when chained: \(p \rightarrow q \rightarrow r\) means \(p \rightarrow (q \rightarrow r)\). Prefer parentheses.
Compound shapes worth recognizing
| Shape | Name / role |
|---|---|
| \(p \vee \neg p\) | Tautology (excluded middle) |
| \(p \wedge \neg p\) | Contradiction |
| \((p \rightarrow q) \wedge (q \rightarrow p)\) | Biconditional |
| \((p \vee q) \wedge \neg(p \wedge q)\) | XOR |
| \(\neg p \vee q\) | Implication in “or” form |
| \((p \wedge q) \rightarrow p\) | Always true (and-elimination as formula) |
Worked examples
Example 1 — Full table for implication
Build the table for \(p \rightarrow q\). Only the row \(p=\mathrm{T}\), \(q=\mathrm{F}\) is false. English: “If it rains, the ground is wet” fails only on a rainy dry-ground day. If it does not rain, the implication is true whether or not the ground is wet—vacuous or non-vacuous, but true.
Example 2 — Tautology \((p \wedge q) \rightarrow p\)
| \(p\) | \(q\) | \(p\wedge q\) | \((p\wedge q)\rightarrow p\) |
|---|---|---|---|
| T | T | T | T |
| T | F | F | T |
| F | T | F | T |
| F | F | F | T |
Every row is T: a tautology.
Example 3 — Contingency \((p \rightarrow q) \rightarrow (q \rightarrow p)\)
This stacks an implication with its converse. Try \(p=\mathrm{F}\), \(q=\mathrm{T}\):
- \(p\rightarrow q = \mathrm{T}\)
- \(q\rightarrow p = \mathrm{F}\)
- Outer: \(\mathrm{T} \rightarrow \mathrm{F} = \mathrm{F}\)
So the formula is not a tautology. Implication is not symmetric; “if authenticated then grant” is not “if grant then authenticated.”
Example 4 — Exclusive vs inclusive or
\(p \vee q\) is T when both are T. \(p \oplus q\) is F when both are T. If a config says “enable feature A or feature B,” decide whether both may be on. In code, || is inclusive; XOR is a separate operator or pattern.
Example 5 — Nested formula always true
Evaluate \(p \rightarrow (q \vee \neg q)\) for all \(p,q\). The subformula \(q \vee \neg q\) is always T, so the implication is always T—a tautology independent of \(p\).
Example 6 — Translate then table
“The system is ready only if the cache is warm.” Let \(r\) = ready, \(w\) = warm. “\(r\) only if \(w\)” is \(r \rightarrow w\). One failing scenario: ready=true, warm=false. Ready and not warm is the unique failure mode of the claim.
Example 7 — Sufficient and necessary
Claim: “Having a valid token is necessary for API access.” Let \(t\) = valid token, \(a\) = access granted. Necessary means \(a \rightarrow t\) (if access, then token). A sufficient condition for access might be “valid token and rate limit ok”: \((t \wedge r) \rightarrow a\). Do not confuse the two directions when writing security specs.
Example 8 — Three-variable table (partial)
Is \((p \rightarrow q) \vee (q \rightarrow p)\) a tautology? For any \(p,q\), either \(p\) is F (then \(p\rightarrow q\) is T) or \(p\) is T. If \(p\) is T and \(q\) is F, then \(p\rightarrow q\) is F but \(q\rightarrow p\) is T, so the disjunction is T. If both true or both false, both implications true. Tautology—even though neither implication alone is always true.
Example 9 — Precedence trap
Without parentheses, \(\neg p \wedge q\) means \((\neg p)\wedge q\), not \(\neg(p\wedge q)\). Tables:
| \(p\) | \(q\) | \(\neg p\) | \((\neg p)\wedge q\) | \(\neg(p\wedge q)\) |
|---|---|---|---|---|
| T | T | F | F | F |
| T | F | F | F | T |
| F | T | T | T | T |
| F | F | T | F | T |
Different final columns—not the same. De Morgan (Day 24) will relate \(\neg(p\wedge q)\) to \(\neg p \vee \neg q\).
Example 10 — Biconditional as same truth value
\(p \leftrightarrow q\) fails exactly when one is T and the other F—same failure pattern as XOR of \(p\) with \(\neg q\), or as \(\neg(p \oplus q)\). Check: \(p \leftrightarrow q \equiv \neg(p \oplus q)\).
Example 11 — Contradiction detector
Is \((p \rightarrow q) \wedge (p \wedge \neg q)\) satisfiable? If \(p\wedge\neg q\) is T, then \(p\) is T and \(q\) is F, so \(p\rightarrow q\) is F. The conjunction is always F—a contradiction. This is the pattern of assuming \(p\rightarrow q\) and finding a counterexample instance.
Example 12 — English carefully
“Access is denied only if the token is expired or revoked.” Let \(d\) = denied, \(e\) = expired, \(v\) = revoked. “\(d\) only if \((e\vee v)\)” means \(d \rightarrow (e \vee v)\). It does not say that expired tokens always cause denial (\(e \rightarrow d\) is a different claim).
Exercises
Solve by hand. Show full tables where asked. Check only after each problem (or batch of 2–3).
- Classify each as proposition, open sentence, or neither: (a) \(n\) is prime. (b) \(17\) is prime. (c) Please open a PR. (d) \(2^n > n\) for all natural \(n\). (e) \(x+y=y+x\).
- Build the complete truth table for \(\neg(p \wedge q)\) and for \(\neg p \vee \neg q\). (Preview of De Morgan.)
- Build the complete truth table for \(p \rightarrow q\) and for \(\neg q \rightarrow \neg p\) (contrapositive). Are the final columns identical?
- Is \((p \rightarrow q) \vee (q \rightarrow p)\) a tautology? Prove with a table.
- Is \((p \leftrightarrow q) \leftrightarrow ((p \rightarrow q) \wedge (q \rightarrow p))\) a tautology? Full table or structured argument.
- Translate to symbols (define atoms clearly): “If the user is authenticated and authorized, then access is granted.”
- Translate: “Access is denied only if the token is expired or revoked.”
- Give one sufficient condition and one necessary condition for “the file is readable,” in plain English, then in symbols.
- Build a table for \((p \vee q) \wedge \neg(p \wedge q)\) (XOR). When is it true?
- Without a full \(8\)-row table, argue that \((p \wedge (p \rightarrow q)) \rightarrow q\) is a tautology (modus ponens as a formula). Optional: verify with \(4\) rows on \(p,q\).
- Find a contingency that uses all three of \(p,q,r\) and has exactly two T rows (or argue carefully if your attempt fails).
- English pitfall: “If it is raining, then I carry an umbrella” when it is not raining and I carry an umbrella—is the implication true or false? Explain using the table.
- Parenthesize fully under standard precedence: \(\neg p \vee q \rightarrow r \leftrightarrow s\).
- Show with a table that \(p \oplus q \equiv (p \vee q) \wedge \neg(p \wedge q)\).
- Is \(p \rightarrow (q \rightarrow p)\) a tautology? Table.
- Is \((p \rightarrow q) \rightarrow p\) a tautology? If not, give a failing assignment.
- Translate: “A process is runnable if and only if it is not blocked and not terminated.”
- Prove by table: \(p \leftrightarrow q \equiv (p \wedge q) \vee (\neg p \wedge \neg q)\).
- How many rows does a truth table need for a formula with \(5\) distinct atoms? With \(n\) atoms?
- Construct a formula that is a contradiction using only \(p\), \(\rightarrow\), and \(\neg\) (no \(\wedge\)).
- “\(p\) unless \(q\)” is often formalized as \(\neg q \rightarrow p\) (or \(p \vee q\)). Explain with an English sentence about retries/timeouts.
- Give an assignment making \((p \rightarrow q) \wedge (q \rightarrow r) \wedge p \wedge \neg r\) false in the sense of unsatisfiable—show no assignment works (contradiction pattern).
CS connection
- Boolean expressions in code (
&&,||,!) match \(\wedge\), \(\vee\), \(\neg\); languages differ on short-circuit evaluation, not on classical truth values of pure expressions. - Specifications / preconditions: “If the API is called with a valid token, then …” is an implication; vacuous cases matter when writing tests for invalid input (the implication should still hold).
- Exhaustive testing of pure boolean logic is exactly a truth table (\(2^n\) cases). Beyond a handful of variables, switch to algebraic simplification (Days 24–25) or SAT solvers—but the semantics stay the same.
- Assertions and property-based tests encode propositions about program state.
- Feature flags and permissions: “admin or (user and owner)” is compound propositional structure; mistakes in parentheses match precedence mistakes.
- XOR appears in checksums, toggle bits, and “exactly one of two modes.”
Common pitfalls
| Pitfall | What to do instead |
|---|---|
| Treating \(\rightarrow\) as “causes” or temporal sequence | Use only the truth-table definition |
| Forgetting vacuous truth | False \(\rightarrow\) anything is true |
| Assuming \(\rightarrow\) is symmetric | Converse \(q \rightarrow p\) is different; check tables |
| Inclusive vs exclusive “or” | Default \(\vee\) is inclusive |
| Skipping rows | Systematically list all \(2^n\) assignments |
| Calling open sentences propositions | Bind variables or quantify (Day 26+) |
| Misreading “only if” | “\(p\) only if \(q\)” is \(p \rightarrow q\) |
| Confusing sufficient and necessary | Sufficient: \(\rightarrow\); necessary: \(\leftarrow\) |
| \(\neg p \wedge q\) vs \(\neg(p \wedge q)\) | Precedence: \(\neg\) binds tightest |
| Claiming a contingency is a tautology after checking 1–2 rows | Finish the table |
Checkpoint
- Define proposition; give example and non-example
- Recite truth tables for \(\wedge\), \(\vee\), \(\rightarrow\), \(\leftrightarrow\), \(\oplus\) without looking
- Build a \(4\)-row table cold for a compound formula
- Build (or outline) an \(8\)-row table for three atoms
- Identify tautology / contradiction / contingency from a finished table
- Translate one English “only if” correctly
- State sufficient vs necessary with arrows
- Parenthesize a mixed formula under standard precedence
- Exercises completed (or logged failures)
- One CS connection sentence in your own words
Two personal takeaways:
- …
- …
Deep dive — implication in natural language (more)
| English | Logic | Common error |
|---|---|---|
| \(p\) only if \(q\) | \(p\rightarrow q\) | swapping to \(q\rightarrow p\) |
| \(p\) if \(q\) | \(q\rightarrow p\) | |
| \(p\) if and only if \(q\) | \(p\leftrightarrow q\) | |
| \(p\) unless \(q\) | \(\neg q\rightarrow p\) (common) | treating as XOR |
| \(p\) whenever \(q\) | \(q\rightarrow p\) |
Systematic table construction recipe
- List atoms in fixed order.
- Create \(2^n\) rows via binary counting.
- Add columns for subexpressions from inside out.
- Final column: classify tautology / contradiction / contingency.
- Optional: mark the single F row of an implication.
Connection to later days
- Day 24: rewrite without building huge tables.
- Day 25: \(A\equiv B\) means final columns match.
- Day 26+: atoms become predicates \(P(x)\).
- Day 33: fallacies are invalid truth-table inferences.
More worked examples
Example 13 — Three-var contingency
\((p\vee q)\rightarrow r\): fails when \(p=T,q=F,r=F\) among others.
Example 14 — Vacuous in specs
“If the list is nonempty, head is defined”: when empty, implication true—spec still holds.
Additional exercises
- Build full table for \((p\leftrightarrow q)\rightarrow(p\rightarrow q)\).
- Translate: “The cache is warm if the system is ready” vs “only if.”
- Give assignments making \(p\oplus q\oplus r\) true (odd number of Ts—verify).
- Explain why testing three random assignments never proves a tautology.
Tomorrow
Day 24 — Boolean algebra. Full law list, dual principle, light DNF/CNF, circuit analogy—algebraic simplification beyond brute-force tables.