Day 9 — Propositional Logic, Boolean Algebra & Normal Forms
Day 9 — Propositional Logic, Boolean Algebra & Normal Forms
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.
Day 24 — Boolean algebra
Stage III · concept day
Goal: Master the standard Boolean algebra laws; use the dual principle; simplify propositional formulas algebraically; obtain DNF/CNF in simple cases; connect laws to digital circuits and boolean conditions in code.
Why this matters
Truth tables explode: \(n\) atoms need \(2^n\) rows. Algebra replaces row-by-row checking with rewrite rules—the same skill as simplifying if conditions, gate circuits, and query predicates. De Morgan alone pays for the day every time you push a negation through a compound test. Stage III is still about justification: name the law you use in each step.
Theory
Boolean algebra as a structure
Work with propositions under \(\wedge\), \(\vee\), \(\neg\), and constants \(\mathbf{T}\) (true, \(1\)) and \(\mathbf{F}\) (false, \(0\)). Two formulas are interchangeable when they are true under exactly the same assignments (logical equivalence, written \(=\) or \(\equiv\) between formulas). Day 25 sharpens \(\equiv\) as “biconditional is a tautology”; today treat laws as trusted rewrite rules you can also verify by small tables.
Full law list (core)
Assume \(p,q,r\) are formulas. Each law is an equivalence.
Commutative laws
\[ p \wedge q \equiv q \wedge p, \qquad p \vee q \equiv q \vee p. \]
Associative laws
\[ (p \wedge q) \wedge r \equiv p \wedge (q \wedge r), \qquad (p \vee q) \vee r \equiv p \vee (q \vee r). \]
So we may write \(p \wedge q \wedge r\) and \(p \vee q \vee r\) without ambiguity of association.
Distributive laws
\[ \begin{align*} p \wedge (q \vee r) &\equiv (p \wedge q) \vee (p \wedge r),\\ p \vee (q \wedge r) &\equiv (p \vee q) \wedge (p \vee r). \end{align*} \]
Both directions matter: expand or factor.
Identity laws
\[ p \wedge \mathbf{T} \equiv p, \qquad p \vee \mathbf{F} \equiv p. \]
Domination (annihilator) laws
\[ p \vee \mathbf{T} \equiv \mathbf{T}, \qquad p \wedge \mathbf{F} \equiv \mathbf{F}. \]
Idempotent laws
\[ p \wedge p \equiv p, \qquad p \vee p \equiv p. \]
Complement laws
\[ p \wedge \neg p \equiv \mathbf{F}, \qquad p \vee \neg p \equiv \mathbf{T}. \]
Double negation
\[ \neg(\neg p) \equiv p. \]
Absorption laws
\[ p \wedge (p \vee q) \equiv p, \qquad p \vee (p \wedge q) \equiv p. \]
De Morgan laws
\[ \neg(p \wedge q) \equiv \neg p \vee \neg q, \qquad \neg(p \vee q) \equiv \neg p \wedge \neg q. \]
Implication rewrite (bridge to Day 23)
\[ p \rightarrow q \equiv \neg p \vee q. \]
Biconditional rewrite
\[ p \leftrightarrow q \equiv (p \rightarrow q) \wedge (q \rightarrow p) \equiv (p \wedge q) \vee (\neg p \wedge \neg q). \]
Dual principle
From any equivalence, swap \(\wedge\) with \(\vee\) and \(\mathbf{T}\) with \(\mathbf{F}\) (and leave \(\neg\) as is, or dualize carefully) to obtain another valid equivalence—the dual. Example: identity \(p \wedge \mathbf{T} \equiv p\) dualizes to \(p \vee \mathbf{F} \equiv p\). De Morgan laws are duals of each other. Use duality as a memory aid and as a check that your law list is complete enough.
More precisely: if a formula is a tautology, its dual (with dualization of the whole expression) relates to a dual tautology in the standard Boolean lattice; for day-to-day work, dualizing identities is the useful habit.
Simplification strategy
- Eliminate \(\rightarrow\) and \(\leftrightarrow\) via rewrites.
- Push \(\neg\) inward with De Morgan + double negation until negations hit only atoms (negation normal form).
- Distribute to reach a target shape (DNF or CNF).
- Drop dominated/idempotent/absorbing junk with identity, complement, absorption.
- Name laws in the margin when writing formal chains.
DNF and CNF (lite)
A literal is an atom or its negation (\(p\) or \(\neg p\)).
- DNF (disjunctive normal form): OR of AND-clauses of literals, e.g. \((p \wedge \neg q) \vee (\neg p \wedge r)\).
- CNF (conjunctive normal form): AND of OR-clauses of literals, e.g. \((p \vee q) \wedge (\neg p \vee r)\).
From a truth table to DNF: for each row where the formula is T, form the AND of literals that describes that assignment; OR those minterms together. Empty OR (never T) is \(\mathbf{F}\).
From a truth table to CNF: for each row where the formula is F, form a clause that rules out that assignment; AND those clauses. Empty AND (never F) is \(\mathbf{T}\).
Algebraic distribution also yields DNF/CNF for small formulas without writing full tables.
Circuit analogy
- \(\wedge\) → AND gate; \(\vee\) → OR gate; \(\neg\) → NOT (inverter).
- Absorption and De Morgan reduce gate count (logic optimization).
- XOR is \((p \vee q) \wedge \neg(p \wedge q)\) or a dedicated XOR gate.
- Multi-level logic vs two-level (DNF/CNF) mirrors compiler IR and hardware synthesis at a cartoon level.
Algebra vs tables
| Method | Strength | Weakness |
|---|---|---|
| Truth table | Complete, mechanical | Exponential rows |
| Algebraic chain | Scales; explains structure | Easy to misapply a law |
| Hybrid | Table for \(2\)–\(3\) vars; algebra for patterns | Need judgment |
Worked examples
Example 1 — De Morgan push
\(\neg(p \wedge \neg q) \equiv \neg p \vee \neg(\neg q) \equiv \neg p \vee q\)
(De Morgan, double negation). Same as \(p \rightarrow q\).
Example 2 — Absorption
\(p \vee (p \wedge q) \equiv p\) by absorption. English: “error or (error and timeout)” collapses to “error.”
Example 3 — Distribute then clean
\((p \vee q) \wedge (p \vee \neg q) \equiv p \vee (q \wedge \neg q) \equiv p \vee \mathbf{F} \equiv p\)
(distributivity of \(\vee\) over \(\wedge\), complement, identity).
Example 4 — Simplify a guard
\(\neg(\neg p \vee q) \wedge p \equiv (p \wedge \neg q) \wedge p \equiv p \wedge \neg q\)
(De Morgan, double neg, idempotent/absorption on \(p\)).
Example 5 — Implication chain
\((p \rightarrow q) \wedge (q \rightarrow r) \rightarrow (p \rightarrow r)\) is the hypothetical syllogism formula (a tautology). Expand with \(\rightarrow\) rewrite if you want an algebraic marathon, or use a \(8\)-row table for \(p,q,r\). Intuition: if \(p\) then \(q\), if \(q\) then \(r\), so if \(p\) then \(r\).
Example 6 — DNF from table (sketch)
Formula \(p \leftrightarrow q\): true on TT and FF.
DNF: \((p \wedge q) \vee (\neg p \wedge \neg q)\).
Example 7 — CNF lite for XOR
\(p \oplus q\) is false on TT and FF. Ruling out TT: \(\neg p \vee \neg q\). Ruling out FF: \(p \vee q\).
CNF: \((p \vee q) \wedge (\neg p \vee \neg q)\).
Example 8 — Dual check
From \(p \wedge (p \vee q) \equiv p\), dualize: \(p \vee (p \wedge q) \equiv p\)—the other absorption law.
Example 9 — Consensus-style cleanup
\((p \wedge q) \vee (p \wedge \neg q) \equiv p \wedge (q \vee \neg q) \equiv p \wedge \mathbf{T} \equiv p\).
Example 10 — Nested De Morgan
\(\neg\bigl((p \vee q) \wedge r\bigr) \equiv \neg(p \vee q) \vee \neg r \equiv (\neg p \wedge \neg q) \vee \neg r\).
Example 11 — Circuit reduction
Expression: \((A \wedge B) \vee (A \wedge \neg B)\). Same as Example 9 with \(p=A\), \(q=B\) → reduces to wire \(A\) alone. Hardware: two ANDs and an OR collapse to a single wire.
Example 12 — Condition simplification in English
“Authenticated and (authenticated or guest)” → “authenticated” by absorption. Redundant checks in authorization policies often match absorption.
Example 13 — Prove complement law usage
\((p \vee q) \wedge \neg p \equiv (p \wedge \neg p) \vee (q \wedge \neg p) \equiv \mathbf{F} \vee (q \wedge \neg p) \equiv q \wedge \neg p\)
(distribute, complement, identity). So “(\(p\) or \(q\)) and not \(p\)” is “\(q\) and not \(p\).”
Example 14 — Toward NNF
\(\neg(p \rightarrow (q \wedge r)) \equiv \neg(\neg p \vee (q \wedge r)) \equiv p \wedge \neg(q \wedge r) \equiv p \wedge (\neg q \vee \neg r)\).
Exercises
Work by hand. Name laws in multi-step simplifications.
- Verify De Morgan \(\neg(p \wedge q) \equiv \neg p \vee \neg q\) with a \(4\)-row table.
- Simplify \(\neg(\neg p \wedge \neg q)\) fully.
- Simplify \(p \wedge (p \vee q) \wedge (q \vee \mathbf{T})\).
- Simplify \((p \rightarrow q) \wedge p\) to a short equivalent (use \(\rightarrow\) rewrite).
- Show algebraically: \(\neg(p \rightarrow q) \equiv p \wedge \neg q\).
- Expand \(p \vee (q \wedge r)\) and write the dual expansion of \(p \wedge (q \vee r)\).
- Put \(p \rightarrow (q \rightarrow r)\) into an equivalent form using only \(\neg,\vee\) (no \(\rightarrow\)).
- Find a DNF for \((p \vee q) \rightarrow r\) by table or algebra.
- Find a CNF for \(p \leftrightarrow q\).
- Simplify \((p \wedge q) \vee (p \wedge \neg q) \vee (\neg p \wedge q)\).
- Prove absorption \(p \vee (p \wedge q) \equiv p\) using distributivity, complement/identity (or table).
- Dualize the identity \(p \vee \mathbf{T} \equiv \mathbf{T}\).
- Simplify \(\neg p \vee (p \wedge q)\) .
- Show \((p \wedge q) \vee (p \wedge \neg q) \vee (\neg p \wedge q) \vee (\neg p \wedge \neg q) \equiv \mathbf{T}\).
- Circuit: how many two-input AND/OR gates does unsimplified \((A\wedge B)\vee(A\wedge\neg B)\) need vs simplified \(A\)?
- Is \(p \wedge (q \vee \neg q)\) equivalent to \(p\)? Justify with laws.
- Push all negations in: \(\neg\bigl((p \rightarrow q) \wedge r\bigr)\).
- Simplify \((p \vee q) \wedge (p \vee \neg q) \wedge (\neg p \vee q)\) as far as you can.
- Write XOR \(p \oplus q\) in DNF and in CNF.
- True or false: every formula has a unique shortest DNF. (Think; one sentence.)
- Simplify a permission check: \((admin \vee (user \wedge owner)) \wedge \neg guest\) assuming \(admin \rightarrow \neg guest\) is not given—do not use extra assumptions; only pure algebra on the written formula.
- Prove \(p \rightarrow (q \wedge r) \equiv (p \rightarrow q) \wedge (p \rightarrow r)\) by algebra or table.
- Prove \(p \rightarrow (q \vee r)\) is not equivalent to \((p \rightarrow q) \vee (p \rightarrow r)\) with a counterexample assignment.
- Using only laws, show \(p \vee (\neg p \wedge q) \equiv p \vee q\).
CS connection
- Compiler constant folding and condition simplification use absorption, domination, and complement.
- Firewall / IAM policies as boolean combinations of attributes; redundant clauses waste review attention.
- Hardware synthesis and PLA/ROM programming historically used sum-of-products (DNF).
- SAT solvers consume CNF; Tseitin encoding converts circuits to CNF efficiently (awareness).
- Short-circuit
&&/||evaluates left-to-right but denotational meaning of pure bools still matches classical algebra when both sides are defined.
- De Morgan rewrites
!(a && b)to!a || !b—common lint/refactor.
Common pitfalls
| Pitfall | What to do instead |
|---|---|
| Distributing only one way | Both \(\wedge\) over \(\vee\) and \(\vee\) over \(\wedge\) are valid |
| Dropping parentheses after De Morgan | \(\neg(p\wedge q)\) is \(\neg p\vee\neg q\), not \(\neg p\wedge\neg q\) |
| Assuming unique simplified form | Many equivalents; pick DNF/CNF or “obvious” short form |
| Using English absorption carelessly | Only apply the formal law |
| Forgetting \(\rightarrow\) rewrite before distributing | Convert \(\rightarrow\) first |
| Dualizing incorrectly | Swap \(\wedge/\vee\) and \(\mathbf{T}/\mathbf{F}\) systematically |
| Treating algebraic steps as optional names | Name laws when learning |
Checkpoint
- Recite commutative, associative, distributive, De Morgan, absorption
- Rewrite \(p\rightarrow q\) as \(\neg p\vee q\)
- Push negations to NNF on a nested formula
- Produce a small DNF from a table
- Produce a small CNF for XOR or \(\leftrightarrow\)
- Dualize one identity correctly
- Simplify a \(4\)–\(6\) step chain with named laws
- Exercises done or logged
Two takeaways:
- …
- …
Deep dive — proving a law by table and by algebra
Claim. \(p \vee (p \wedge q) \equiv p\).
Table proof. Four rows: when \(p=\mathrm{T}\), both sides T; when \(p=\mathrm{F}\), left is \(\mathrm{F}\vee(\mathrm{F}\wedge q)=\mathrm{F}\), right F. Match.
Algebra proof.
\(p \vee (p \wedge q) \equiv (p \wedge \mathbf{T}) \vee (p \wedge q) \equiv p \wedge (\mathbf{T} \vee q) \equiv p \wedge \mathbf{T} \equiv p\).
Practice both styles until either is fast.
More worked examples
Example 15 — CNF for implication
\(p\rightarrow q \equiv \neg p \vee q\) is already a single clause (CNF with one clause).
Example 16 — DNF for implication
\(\neg p \vee q \equiv (\neg p \wedge \mathbf{T}) \vee (q \wedge \mathbf{T})\) not minimal; better: from table, T rows give \((\neg p \wedge \neg q)\vee(\neg p \wedge q)\vee(p \wedge q)\), which simplifies to \(\neg p \vee q\) again.
Example 17 — Multi-step guard
\(\neg(p \vee \neg q) \vee (p \wedge q) \equiv (\neg p \wedge q) \vee (p \wedge q) \equiv q \wedge (\neg p \vee p) \equiv q\).
Example 18 — Idempotent after distribute
\((p\vee q)\wedge(p\vee q)\equiv p\vee q\).
Example 19 — Domination early
\((p \wedge q) \vee \mathbf{T} \equiv \mathbf{T}\)—stop; do not expand further.
Example 20 — XOR self
\(p \oplus p \equiv \mathbf{F}\); \(p \oplus \mathbf{F} \equiv p\); \(p \oplus \mathbf{T} \equiv \neg p\).
Additional exercises
- Simplify \(((p\rightarrow q)\rightarrow p)\rightarrow p\) (Law of Clavius / related)—table or algebra.
- Prove dual of absorption from dual principle + one absorption law.
- Convert \((p\leftrightarrow q)\rightarrow r\) to CNF (may be multi-clause).
- Show \(p \wedge (q \vee (p \wedge r)) \equiv (p \wedge q) \vee (p \wedge r)\) and name laws.
- Circuit: reduce \((A\vee B)\wedge(A\vee \neg B)\wedge(\neg A\vee B)\) gate count after algebra.
- Write a full NNF for \(\neg\bigl((p\rightarrow q)\leftrightarrow r\bigr)\).
Mini-checkpoint table
| Law | Can you state it cold? |
|---|---|
| De Morgan (both) | |
| Absorption (both) | |
| Distribute \(\wedge\) over \(\vee\) | |
| Distribute \(\vee\) over \(\wedge\) | |
| \(p\rightarrow q\) rewrite |
Tomorrow
Day 25 — Logical equivalence. \(\equiv\) as tautology of the biconditional; proof by table vs algebraic chain; replaceability; functional completeness awareness (\(\{\neg,\wedge\}\), NAND).
Day 25 — Logical equivalence
Stage III · concept day
Goal: Define logical equivalence via tautology of the biconditional; prove equivalences by truth table and by algebraic chains; use replaceability of equivalents; know that \(\{\neg,\wedge\}\) and \(\{\mathrm{NAND}\}\) are functionally complete (awareness).
Why this matters
Equivalence is the contract under which you may rewrite a condition without changing when it holds. Refactoring if logic, optimizing circuits, and transforming specifications all depend on \(\equiv\). Confusing equivalence with “sometimes related” is how bugs and false proofs enter. Today formalizes the standard you already used informally on Day 24.
Theory
Definition of logical equivalence
Formulas \(A\) and \(B\) are logically equivalent, written \(A \equiv B\) (or \(A \Leftrightarrow B\) in some texts), when
\[A \leftrightarrow B\]
is a tautology—true under every truth assignment to the atoms.
Equivalently: \(A\) and \(B\) receive the same truth value in every row of a joint truth table.
Note: \(A \leftrightarrow B\) is a formula (connective). \(A \equiv B\) is a meta-statement that the biconditional is always true. We still often write \(\equiv\) between formulas in algebraic chains.
Equivalence is an equivalence relation
On formulas (up to atoms in a fixed language):
- Reflexive: \(A \equiv A\).
- Symmetric: \(A \equiv B \Rightarrow B \equiv A\).
- Transitive: \(A \equiv B\) and \(B \equiv C \Rightarrow A \equiv C\).
So chains \(A \equiv B \equiv C \equiv \cdots\) are legitimate.
Proof method 1 — Truth table
- List all atoms in \(A\) or \(B\).
- Build columns for \(A\), \(B\), and optionally \(A \leftrightarrow B\).
- Check \(A\) and \(B\) match on every row (or final column of \(\leftrightarrow\) is all T).
Complete for \(n \le 3\) atoms routinely; \(n=4\) is \(16\) rows—doable but tedious.
Proof method 2 — Algebraic chain
Transform \(A\) into \(B\) by a sequence of named laws (Day 24). Each step preserves equivalence; transitivity gives \(A \equiv B\).
Good chains are directed: start from the more complex side, or meet in the middle. Never silently reverse a non-equivalence.
Proof method 3 — Semantic argument
Argue without a full grid: e.g. “\(A\) is true iff … iff \(B\) is true.” Still must cover all cases (often by cases on an atom).
Replaceability (substitution theorem, informal)
If \(A \equiv B\) and formula \(C_A\) contains \(A\) as a subformula, replacing that occurrence by \(B\) yields \(C_B\) with \(C_A \equiv C_B\).
You may rewrite inside larger formulas. This is why simplifying a sub-guard simplifies the whole condition.
Standard equivalences to own
\[ \begin{align*} p \rightarrow q &\equiv \neg p \vee q,\\ p \rightarrow q &\equiv \neg q \rightarrow \neg p && \text{(contrapositive)},\\ p \leftrightarrow q &\equiv (p \rightarrow q) \wedge (q \rightarrow p),\\ \neg(p \rightarrow q) &\equiv p \wedge \neg q,\\ p \rightarrow (q \rightarrow r) &\equiv (p \wedge q) \rightarrow r,\\ (p \rightarrow q) \wedge (p \rightarrow r) &\equiv p \rightarrow (q \wedge r),\\ \neg\neg p &\equiv p. \end{align*} \]
Plus all Day 24 lattice laws.
Contrapositive vs converse vs inverse
For implication \(p \rightarrow q\):
| Name | Formula | Equivalent to original? |
|---|---|---|
| Original | \(p \rightarrow q\) | — |
| Converse | \(q \rightarrow p\) | No (in general) |
| Inverse | \(\neg p \rightarrow \neg q\) | No (equiv to converse) |
| Contrapositive | \(\neg q \rightarrow \neg p\) | Yes |
Proving \(p\rightarrow q\) is exactly as hard as proving \(\neg q \rightarrow \neg p\)—often easier (Day 29).
Functional completeness (awareness)
A set \(S\) of connectives is functionally complete if every boolean function \(\{T,F\}^n \to \{T,F\}\) can be represented by a formula using only connectives from \(S\) (and variables).
- \(\{\neg, \wedge, \vee\}\) is complete (e.g. via DNF).
- \(\{\neg, \wedge\}\) is complete: \(p \vee q \equiv \neg(\neg p \wedge \neg q)\).
- \(\{\neg, \vee\}\) is complete dually.
- \(\{\rightarrow, \neg\}\) is complete: \(p \wedge q \equiv \neg(p \rightarrow \neg q)\).
- NAND alone: \(p \uparrow q \equiv \neg(p \wedge q)\) is complete (Sheffer stroke).
- NOR alone is complete (Peirce arrow).
- \(\{\wedge, \vee\}\) without negation is not complete (monotone functions only).
Hardware likes NAND for manufacturing uniformity; theory likes knowing one gate can generate all logic.
Equivalence vs implication
\(A \equiv B\) is stronger than “\(A\) implies \(B\).”
\(A \models B\) (entailment: whenever \(A\) is true, \(B\) is) means \(A \rightarrow B\) is a tautology, not necessarily the reverse.
Example: \(p \wedge q\) entails \(p\), but they are not equivalent.
Worked examples
Example 1 — Table: contrapositive
Show \(p \rightarrow q \equiv \neg q \rightarrow \neg p\) by comparing final columns (4 rows). They match; \(\equiv\) holds.
Example 2 — Algebra: \(\neg(p \rightarrow q)\)
\(\neg(p \rightarrow q) \equiv \neg(\neg p \vee q) \equiv \neg\neg p \wedge \neg q \equiv p \wedge \neg q\).
Example 3 — Exportation
\(p \rightarrow (q \rightarrow r) \equiv \neg p \vee (\neg q \vee r) \equiv (\neg p \vee \neg q) \vee r \equiv \neg(p \wedge q) \vee r \equiv (p \wedge q) \rightarrow r\).
Example 4 — Not equivalent
\(p \rightarrow (q \rightarrow r)\) vs \((p \rightarrow q) \rightarrow r\).
Assignment \(p=F,q=F,r=F\): left is T (false \(\rightarrow\) anything); right is \((T)\rightarrow F = F\). Not equivalent.
Example 5 — Replaceability
Since \(p \vee \neg p \equiv \mathbf{T}\), we have \(q \wedge (p \vee \neg p) \equiv q \wedge \mathbf{T} \equiv q\).
Example 6 — Prove biconditional form
\((p \rightarrow q) \wedge (q \rightarrow p) \equiv (\neg p \vee q) \wedge (\neg q \vee p)\).
Expanding to DNF yields \((p \wedge q) \vee (\neg p \wedge \neg q)\), classic iff.
Example 7 — Semantic argument
\(p \wedge (q \vee \neg q)\): inner is always T, so whole true iff \(p\) true. Hence \(\equiv p\).
Example 8 — Chain for absorption
\(p \vee (p \wedge q) \equiv (p \vee p) \wedge (p \vee q)\) wait—better:
\(p \vee (p \wedge q) \equiv (p \wedge \mathbf{T}) \vee (p \wedge q) \equiv p \wedge (\mathbf{T} \vee q) \equiv p \wedge \mathbf{T} \equiv p\).
(factor \(p\), domination, identity).
Example 9 — NAND expresses NOT
\(\neg p \equiv p \uparrow p\), because \(\neg(p \wedge p) \equiv \neg p\).
Example 10 — NAND expresses AND
\(p \wedge q \equiv \neg(p \uparrow q) \equiv (p \uparrow q) \uparrow (p \uparrow q)\).
Example 11 — Inequivalence with one counterexample
To disprove \(A \equiv B\), a single row where they differ suffices. To prove \(\equiv\), all rows (or a full algebraic derivation) are required.
Example 12 — Hypothetical syllogism as entailment
\((p\rightarrow q) \wedge (q\rightarrow r)\) entails \(p\rightarrow r\), i.e.
\(\bigl((p\rightarrow q) \wedge (q\rightarrow r)\bigr) \rightarrow (p\rightarrow r)\) is a tautology.
That is not the same as claiming \((p\rightarrow q) \wedge (q\rightarrow r) \equiv p\rightarrow r\) (false: left can force more structure).
Example 13 — CNF equivalence class
Two different CNFs can be equivalent: \((p\vee q) \wedge (p\vee \neg q) \equiv p\) as on Day 24. Same boolean function, different syntax.
Example 14 — Inverse fallacy preview
From \(p\rightarrow q\) you may not infer \(\neg p \rightarrow \neg q\). Counterexample: \(p=\) “divisible by \(4\)”, \(q=\) “even”; \(6\) is even and not divisible by \(4\), so original holds as a number-theory implication pattern for multiples, but carefully: on integers, \(4\mid n \Rightarrow 2\mid n\) is true; inverse “not multiple of \(4\) \(\Rightarrow\) odd” is false. Equivalence fails.
Exercises
- Prove by table: \(p \rightarrow q \equiv \neg p \vee q\).
- Prove by algebra: \(\neg(p \vee q) \equiv \neg p \wedge \neg q\).
- Prove by table: \(p \leftrightarrow q \equiv (p \wedge q) \vee (\neg p \wedge \neg q)\).
- Show \(p \rightarrow q \not\equiv q \rightarrow p\) with a counterexample row.
- Show the inverse \(\neg p \rightarrow \neg q \not\equiv p \rightarrow q\) (same counterexample family).
- Prove \(p \rightarrow (q \rightarrow r) \equiv (p \wedge q) \rightarrow r\) algebraically.
- Prove or disprove: \((p \rightarrow q) \rightarrow r \equiv p \rightarrow (q \rightarrow r)\).
- Prove \(p \wedge (p \rightarrow q) \equiv p \wedge q\) (algebra or table).
- Using replaceability, simplify \((p \leftrightarrow q) \wedge (p \vee \neg p)\).
- Express \(p \vee q\) using only \(\neg\) and \(\wedge\).
- Express \(p \rightarrow q\) using only \(\mathrm{NAND}\). (May be multi-step.)
- Prove \(\neg(p \leftrightarrow q) \equiv p \leftrightarrow \neg q\) (table recommended).
- Is \(\equiv\) the same as “provable from empty assumptions in some system”? One sentence on semantic vs syntactic views (awareness).
- Give three distinct formulas all equivalent to \(p \rightarrow q\).
- Prove \((p \vee q) \rightarrow r \equiv (p \rightarrow r) \wedge (q \rightarrow r)\).
- Disprove \((p \wedge q) \rightarrow r \equiv (p \rightarrow r) \wedge (q \rightarrow r)\).
- Show \(p \uparrow q \equiv q \uparrow p\) (NAND commutative).
- Write a full algebraic proof that \((p \wedge q) \vee (p \wedge \neg q) \equiv p\).
- Determine whether \((p \rightarrow q) \vee (q \rightarrow p)\) is a tautology (hence \(\equiv \mathbf{T}\)).
- If \(A \equiv B\) and \(A\) is a tautology, show \(B\) is a tautology.
- If \(A \equiv B\) and \(A\) is a contradiction, show \(B\) is a contradiction.
- Prove \(\neg(p \wedge q) \not\equiv \neg p \wedge q\) with a row.
- Functional completeness: explain why \(\{\wedge,\vee\}\) cannot express \(\neg p\).
- Build an equivalence proof that modus tollens formula \((\neg q \wedge (p\rightarrow q)) \rightarrow \neg p\) is a tautology (table or algebra).
- Replace inner formula: start from \(\neg\neg(p \wedge q)\) and reduce to \(p \wedge q\) with named steps.
CS connection
- Refactoring boolean conditions is equivalence-preserving transformation; tests that only check one branch miss inequivalent rewrites.
- Compiler IR canonicalizes boolean expressions (sometimes to BDD or CNF).
- Spec vs implementation: two preconditions may be equivalent yet one is clearer for humans.
- NAND-only libraries in hardware description; software rarely forces one connective but bit-twiddling uses De Morgan duals.
- Type-level and SMT solvers decide equivalence/entailment for fragments of logic.
- GitOps / feature flag cleanup: deleting a redundant clause requires equivalence or documented strengthening/weakening.
Common pitfalls
| Pitfall | What to do instead |
|---|---|
| Proving \(\equiv\) with one example row | Examples never prove equivalence |
| Disproving with a vague story | Give one concrete assignment |
| Converse = contrapositive | Only contrapositive preserves \(\equiv\) |
| Mixing \(\rightarrow\) tautology with \(\equiv\) | Entailment is one direction |
| Algebraic step without a law | Name the law or use a table |
| Thinking all complete bases are equally convenient | Completeness ≠ short formulas |
| Replacing \(A\) by \(B\) when only \(A\rightarrow B\) is tautology | That weakens/strengthens context-dependently—not free replaceability |
Checkpoint
- Define \(A \equiv B\) via tautology of \(A \leftrightarrow B\)
- Prove one equivalence by table and one by algebra
- Disprove an equivalence with a single row
- State contrapositive equivalence; reject converse
- Use replaceability inside a larger formula
- State functional completeness of \(\{\neg,\wedge\}\) and NAND (awareness)
- Distinguish entailment from equivalence
- Exercises completed or logged
Two takeaways:
- …
- …
Deep dive — equivalence as same boolean function
Two formulas are equivalent iff they define the same function \(\{T,F\}^n\to\{T,F\}\). There are \(2^{2^n}\) boolean functions on \(n\) vars; equivalence classes of formulas partition the huge set of syntactic expressions into \(2^{2^n}\) classes. CNF/DNF are normal representatives (not always unique).
Proof hygiene for \(\equiv\)
| Goal | Valid method | Invalid method |
|---|---|---|
| Prove \(A\equiv B\) | All \(2^n\) rows agree; or reversible law chain | Check 2–3 rows only |
| Disprove \(A\equiv B\) | One disagreeing assignment | “They look different” |
| Prove \(A\) entails \(B\) only | \(A\rightarrow B\) tautology | Claiming \(\equiv\) |
Replaceability worked carefully
If \(A\equiv B\), then \(C[A]\equiv C[B]\) for any context \(C[\cdot]\) built from connectives.
If only \(A\rightarrow B\) is a tautology, replacing \(A\) by \(B\) inside a larger formula can change truth (e.g. replace \(p\wedge q\) by \(p\) inside a negation).
More worked examples
Example 15 — Pierce’s law
\(((p\rightarrow q)\rightarrow p)\rightarrow p\) is a tautology (classical logic). Verify with a 4-row table.
Example 16 — Chain
\(p\rightarrow q \equiv \neg q\rightarrow\neg p \equiv \neg\neg q \vee \neg p \equiv q\vee\neg p \equiv \neg p\vee q\).
Example 17 — Inequivalent scopes
\(p\rightarrow(q\rightarrow r)\) vs \((p\rightarrow q)\rightarrow r\) revisited with full table of differences.
Example 18 — NAND complete sketch
\(\neg p = p\uparrow p\); \(p\wedge q = (p\uparrow q)\uparrow(p\uparrow q)\); then \(\vee\) via De Morgan.
Example 19 — Equivalence under substitution of atoms
If \(A(p,q)\equiv B(p,q)\), then \(A(r\vee s,q)\equiv B(r\vee s,q)\) by replaceability of atoms with formulas.
Additional exercises
- Prove Pierce’s law by table.
- Show \(\{\rightarrow\}\) alone is not functionally complete (monotone? or preserve T)—hint: implication preserves T when all inputs T.
- Prove \(p\leftrightarrow q \equiv \neg p\leftrightarrow\neg q\).
- Disprove \(p\leftrightarrow(q\leftrightarrow r) \equiv (p\leftrightarrow q)\leftrightarrow r\) or prove it (actually \(\leftrightarrow\) is associative—prove!).
- Write the shortest chain you can for \(\neg(p\vee(q\wedge\neg q))\equiv\neg p\).
Extended practice workshop
Prove or disprove (tables allowed for \(n\le 3\))
- \(p\rightarrow(q\rightarrow p)\)
- \((p\rightarrow q)\rightarrow p\)
- \(p\leftrightarrow\neg\neg p\)
- \((p\wedge q)\rightarrow(p\vee q)\)
- \(p\rightarrow q\) vs \(\neg p\rightarrow\neg q\)
Algebra chains (name every law)
- \(\neg(p\rightarrow\neg q)\) to \(p\wedge q\)
- \((p\rightarrow q)\wedge(p\rightarrow\neg q)\) simplify
- \(p\vee(p\rightarrow q)\) simplify
- \((p\leftrightarrow q)\wedge p\) simplify to involve \(q\)
Completeness sketches
- Express \(\vee\) with \(\neg,\wedge\).
- Express \(\rightarrow\) with NAND only (multi-step OK).
- Why \(\{\wedge,\vee\}\) cannot make \(\neg\): consider the all-T assignment.
Replaceability
- Since \(q\vee\neg q\equiv\mathbf{T}\), simplify \((p\rightarrow r)\wedge(q\vee\neg q)\).
- Show you cannot replace \(p\wedge q\) by \(p\) under an outer \(\neg\) freely.
Self-score table
| Block | Cold | Notes |
|---|---|---|
| 1–5 | ||
| 6–9 | ||
| 10–12 | ||
| 13–14 |
Flashcard: contrapositive
\[p\rightarrow q \;\equiv\; \neg q\rightarrow\neg p\]
Converse and inverse are equivalent to each other, not to the original.
Tomorrow
Day 26 — Predicates & quantifiers. Open sentences, universe of discourse, \(\forall\) and \(\exists\), free vs bound variables, negation rules for quantifiers.