Day 25 — Logical equivalence

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

1. List all atoms in \(A\) or \(B\).
   
2. Build columns for \(A\), \(B\), and optionally \(A \leftrightarrow B\).
   
3. 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

1. Prove by table: \(p \rightarrow q \equiv \neg p \vee q\).
   
2. Prove by algebra: \(\neg(p \vee q) \equiv \neg p \wedge \neg q\).
   
3. Prove by table: \(p \leftrightarrow q \equiv (p \wedge q) \vee (\neg p \wedge \neg q)\).
   
4. Show \(p \rightarrow q \not\equiv q \rightarrow p\) with a counterexample row.
   
5. Show the inverse \(\neg p \rightarrow \neg q \not\equiv p \rightarrow q\) (same counterexample family).
   
6. Prove \(p \rightarrow (q \rightarrow r) \equiv (p \wedge q) \rightarrow r\) algebraically.
   
7. Prove or disprove: \((p \rightarrow q) \rightarrow r \equiv p \rightarrow (q \rightarrow r)\).
   
8. Prove \(p \wedge (p \rightarrow q) \equiv p \wedge q\) (algebra or table).
   
9. Using replaceability, simplify \((p \leftrightarrow q) \wedge (p \vee \neg p)\).
   
10. Express \(p \vee q\) using only \(\neg\) and \(\wedge\).
    
11. Express \(p \rightarrow q\) using only \(\mathrm{NAND}\). (May be multi-step.)
    
12. Prove \(\neg(p \leftrightarrow q) \equiv p \leftrightarrow \neg q\) (table recommended).
    
13. Is \(\equiv\) the same as “provable from empty assumptions in some system”? One sentence on semantic vs syntactic views (awareness).
    
14. Give three distinct formulas all equivalent to \(p \rightarrow q\).
    
15. Prove \((p \vee q) \rightarrow r \equiv (p \rightarrow r) \wedge (q \rightarrow r)\).
    
16. Disprove \((p \wedge q) \rightarrow r \equiv (p \rightarrow r) \wedge (q \rightarrow r)\).
    
17. Show \(p \uparrow q \equiv q \uparrow p\) (NAND commutative).
    
18. Write a full algebraic proof that \((p \wedge q) \vee (p \wedge \neg q) \equiv p\).
    
19. Determine whether \((p \rightarrow q) \vee (q \rightarrow p)\) is a tautology (hence \(\equiv \mathbf{T}\)).
    
20. If \(A \equiv B\) and \(A\) is a tautology, show \(B\) is a tautology.
    
21. If \(A \equiv B\) and \(A\) is a contradiction, show \(B\) is a contradiction.
    
22. Prove \(\neg(p \wedge q) \not\equiv \neg p \wedge q\) with a row.
    
23. Functional completeness: explain why \(\{\wedge,\vee\}\) cannot express \(\neg p\).
    
24. Build an equivalence proof that modus tollens formula \((\neg q \wedge (p\rightarrow q)) \rightarrow \neg p\) is a tautology (table or algebra).
    
25. 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:

1. …
   
2. …

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

26. Prove Pierce’s law by table.
    
27. Show \(\{\rightarrow\}\) alone is not functionally complete (monotone? or preserve T)—hint: implication preserves T when all inputs T.
    
28. Prove \(p\leftrightarrow q \equiv \neg p\leftrightarrow\neg q\).
    
29. Disprove \(p\leftrightarrow(q\leftrightarrow r) \equiv (p\leftrightarrow q)\leftrightarrow r\) or prove it (actually \(\leftrightarrow\) is associative—prove!).
    
30. 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\))

1. \(p\rightarrow(q\rightarrow p)\)
   
2. \((p\rightarrow q)\rightarrow p\)
   
3. \(p\leftrightarrow\neg\neg p\)
   
4. \((p\wedge q)\rightarrow(p\vee q)\)
   
5. \(p\rightarrow q\) vs \(\neg p\rightarrow\neg q\)

Algebra chains (name every law)

6. \(\neg(p\rightarrow\neg q)\) to \(p\wedge q\)
   
7. \((p\rightarrow q)\wedge(p\rightarrow\neg q)\) simplify
   
8. \(p\vee(p\rightarrow q)\) simplify
   
9. \((p\leftrightarrow q)\wedge p\) simplify to involve \(q\)

Completeness sketches

10. Express \(\vee\) with \(\neg,\wedge\).
    
11. Express \(\rightarrow\) with NAND only (multi-step OK).
    
12. Why \(\{\wedge,\vee\}\) cannot make \(\neg\): consider the all-T assignment.

Replaceability

13. Since \(q\vee\neg q\equiv\mathbf{T}\), simplify \((p\rightarrow r)\wedge(q\vee\neg q)\).
    
14. 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.