The Laws of Boolean Algebra
Boolean Algebra & Digital Logic
Chapter 3 · The Laws of Boolean Algebra
Chapter 1's own finding-box already showed three of these laws holding on a real permissions bitmask, without naming them formally. This chapter names every law properly, proves each one, and introduces the one proof method that's unique to Boolean algebra: since every variable only has two possible values, an identity in n variables can be proved completely just by checking all 2ⁿ input combinations — no infinite case to worry about, unlike ordinary algebra over the real numbers.
The Standard Laws
| Law | Statement |
|---|---|
| Commutative | x+y = y+x, xy = yx |
| Associative | (x+y)+z = x+(y+z), (xy)z = x(yz) |
| Distributive | x(y+z) = xy+xz |
| Identity | x+0 = x, x·1 = x |
| Domination | x+1 = 1, x·0 = 0 |
| Complement | x+x' = 1, x·x' = 0 |
| Idempotent | x+x = x, x·x = x |
| Absorption | x+(xy) = x, x(x+y) = x |
x: x+x'=1 and x·x'=0 in both cases. Absorption law, all 4 combinations of x,y: x+(x·y) equals x in every single case.
A Genuinely Surprising Law: The Second Distributive Law
Ordinary arithmetic distributes multiplication over addition (x(y+z)=xy+xz) — but never the reverse; addition does not distribute over multiplication for real numbers. Boolean algebra is different: OR genuinely does distribute over AND, a law with no counterpart in ordinary arithmetic at all.
x+(y·z) = (x+y)·(x+z) — checked exhaustively, every single one of the 8 possible (x,y,z) combinations matches on both sides.
x=2, y=3, z=4: x+(y×z) = 2+12 = 14, but (x+y)×(x+z) = 5×6 = 30 — not equal. This law is a genuine property of the two-valued Boolean system, not a fact that happens to carry over from regular arithmetic just because the +/· notation looks the same.
De Morgan's Laws, Proved Algebraically
Discrete Mathematics Fundamentals introduced these as a logical equivalence between statements. Here they're the same two identities, proved the same exhaustive way as every other law in this chapter:
(x+y)' = x'·y' — matches on every input pair. (x·y)' = x'+y' — matches on every input pair. Same theorem, same truth values, now derived as algebra rather than restated as a logic rule.
The Duality Principle
Notice the laws above come in matched pairs. That's not a coincidence: swap every + with ·, and every 0 with 1, and any true Boolean law becomes another true Boolean law — its dual. The two distributive laws are duals of each other; so are the two De Morgan's laws, the two identity laws, and the two domination laws. Once one half of a pair is proved, the other is guaranteed true for free.
Real Relevance: Negating Compound Conditions Correctly
De Morgan's Laws are the exact tool for correctly inverting a compound condition in real code — not (a and b) is not the same as (not a) and (not b), a mistake that's easy to make under pressure. The correct inversion, straight from this chapter's own proof, is (not a) or (not b). Chapter 5 builds on every law in this chapter directly to simplify tangled real conditions down to their shortest equivalent form.
Hands-On Exercises
Using a full truth table (all 4 combinations of x,y), prove the commutative law for AND: xy = yx.
Using this chapter's own duality principle, state the dual of the identity law x·1 = x without checking a truth table first — then verify your answer is actually true for both values of x.
A piece of code needs to negate the condition is_admin or is_owner to correctly express "neither an admin nor the owner." Using De Morgan's Law from this chapter, write the correct negated form, and explain specifically what would go wrong if someone incorrectly wrote not is_admin or not is_owner instead.
Chapter 3 Quick Reference
- Every Boolean law can be completely proved by checking all
2ⁿinput combinations — a finite, exhaustive proof unique to two-valued algebra - Commutative, associative, distributive, identity, domination, complement, idempotent, absorption — the full standard law set, each verified exhaustively
- The second distributive law (
x+(yz)=(x+y)(x+z)) has no counterpart in ordinary arithmetic — confirmed to fail for real numbers - De Morgan's Laws, re-proved algebraically — same theorem as Discrete Mathematics Fundamentals Chapter 2, now derived rather than restated
- Duality: swap
+↔·and0↔1in any true law to get another true law, for free - Next chapter: Boolean functions and canonical forms