Day 24 — Boolean algebra

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

1. Eliminate \(\rightarrow\) and \(\leftrightarrow\) via rewrites.
   
2. Push \(\neg\) inward with De Morgan + double negation until negations hit only atoms (negation normal form).
   
3. Distribute to reach a target shape (DNF or CNF).
   
4. Drop dominated/idempotent/absorbing junk with identity, complement, absorption.
   
5. 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.

1. Verify De Morgan \(\neg(p \wedge q) \equiv \neg p \vee \neg q\) with a \(4\)-row table.
2. Simplify \(\neg(\neg p \wedge \neg q)\) fully.
3. Simplify \(p \wedge (p \vee q) \wedge (q \vee \mathbf{T})\).
4. Simplify \((p \rightarrow q) \wedge p\) to a short equivalent (use \(\rightarrow\) rewrite).
5. Show algebraically: \(\neg(p \rightarrow q) \equiv p \wedge \neg q\).
6. Expand \(p \vee (q \wedge r)\) and write the dual expansion of \(p \wedge (q \vee r)\).
7. Put \(p \rightarrow (q \rightarrow r)\) into an equivalent form using only \(\neg,\vee\) (no \(\rightarrow\)).
8. Find a DNF for \((p \vee q) \rightarrow r\) by table or algebra.
9. Find a CNF for \(p \leftrightarrow q\).
10. Simplify \((p \wedge q) \vee (p \wedge \neg q) \vee (\neg p \wedge q)\).
11. Prove absorption \(p \vee (p \wedge q) \equiv p\) using distributivity, complement/identity (or table).
12. Dualize the identity \(p \vee \mathbf{T} \equiv \mathbf{T}\).
13. Simplify \(\neg p \vee (p \wedge q)\) .
14. Show \((p \wedge q) \vee (p \wedge \neg q) \vee (\neg p \wedge q) \vee (\neg p \wedge \neg q) \equiv \mathbf{T}\).
15. Circuit: how many two-input AND/OR gates does unsimplified \((A\wedge B)\vee(A\wedge\neg B)\) need vs simplified \(A\)?
16. Is \(p \wedge (q \vee \neg q)\) equivalent to \(p\)? Justify with laws.
17. Push all negations in: \(\neg\bigl((p \rightarrow q) \wedge r\bigr)\).
18. Simplify \((p \vee q) \wedge (p \vee \neg q) \wedge (\neg p \vee q)\) as far as you can.
19. Write XOR \(p \oplus q\) in DNF and in CNF.
20. True or false: every formula has a unique shortest DNF. (Think; one sentence.)
21. 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.
22. Prove \(p \rightarrow (q \wedge r) \equiv (p \rightarrow q) \wedge (p \rightarrow r)\) by algebra or table.
23. Prove \(p \rightarrow (q \vee r)\) is not equivalent to \((p \rightarrow q) \vee (p \rightarrow r)\) with a counterexample assignment.
24. 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:

1. …
   
2. …

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

25. Simplify \(((p\rightarrow q)\rightarrow p)\rightarrow p\) (Law of Clavius / related)—table or algebra.
    
26. Prove dual of absorption from dual principle + one absorption law.
    
27. Convert \((p\leftrightarrow q)\rightarrow r\) to CNF (may be multi-clause).
    
28. Show \(p \wedge (q \vee (p \wedge r)) \equiv (p \wedge q) \vee (p \wedge r)\) and name laws.
    
29. Circuit: reduce \((A\vee B)\wedge(A\vee \neg B)\wedge(\neg A\vee B)\) gate count after algebra.
    
30. 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).