4.2 Boolean Laws: The Algebraic Identities That Simplify Circuits
State and correctly apply the core Boolean identity laws (identity, null, idempotent, complement, and double-negation laws), and recognize where ordinary arithmetic intuition does not carry over.
Boolean laws are the small set of algebraic identities that let you rewrite a Boolean expression into an equivalent, often simpler, form without changing what it computes — they are to Boolean algebra what rules like 'x + 0 = x' or 'x · 1 = x' are to ordinary algebra, except that Boolean algebra's two-valued domain produces some identities, like A + 1 = 1, that have no arithmetic counterpart at all. These laws matter because they are the actual mechanism behind circuit simplification: every time a real digital design is optimized to use fewer gates, less silicon area, or less power, that optimization is ultimately justified by a chain of these exact identities (or the more systematic Boolean-simplification and K-map techniques built on top of them in Modules 4.9 and 5).
Core Concept: The Nine Laws Grouped by Behavior
The spec lists nine important laws, and they fall naturally into a few behavioral groups. The identity laws — A + 0 = A and A · 1 = A — state that OR-ing with 0 or AND-ing with 1 leaves a variable unchanged, exactly mirroring the role that 0 and 1 play as identity elements in ordinary addition and multiplication respectively. The null (dominance) laws — A + 1 = 1 and A · 0 = 0 — are Boolean algebra's most distinctly non-arithmetic identities: OR-ing anything with 1 always produces 1 no matter what the other operand is, and AND-ing anything with 0 always produces 0, which has no equivalent in ordinary arithmetic (there is no number that 'dominates' addition the way 1 dominates Boolean OR).
The idempotent laws — A + A = A and A · A = A — state that combining a variable with itself, via either operator, just returns the same variable; these were used directly and by name in Module 3.4 and 3.5 to justify why tying both inputs of a NAND or NOR gate together produces a plain inverter. The complement laws — A + A' = 1 and A · A' = 0 — capture the fact that a variable and its own complement, combined with OR, always covers every possibility (hence 1), while combined with AND, always contradicts itself (hence 0). Finally, the involution law — (A')' = A — states that double complementation returns the original value, already introduced in Module 3.1's discussion of chained inverters.
• Identity laws: A + 0 = A, A · 1 = A — 0 and 1 act as 'do nothing' elements for OR and AND respectively. • Null laws: A + 1 = 1, A · 0 = 0 — these have no ordinary-arithmetic equivalent; they are pure Boolean-domain facts. • Idempotent laws: A + A = A, A · A = A — combining a variable with itself changes nothing. • Complement laws: A + A' = 1, A · A' = 0 — a variable and its complement always resolve to a fixed constant. • Involution law: (A')' = A — double complementation cancels out.
Step-by-Step: Proving Each Law from the Truth Table
Every one of these nine laws can be verified mechanically by checking it against the underlying truth tables of AND, OR, and NOT for both possible values of A — since a Boolean law claims to hold for every value a variable can take, and a variable can only take 0 or 1, checking both cases is a complete proof. For A + A = A: if A=0, then 0+0=0 (matches A); if A=1, then 1+1=1 by the OR truth table's both-inputs-1 row (matches A). For A · A' = 0: if A=0, then A'=1, and 0·1=0 (matches the claimed constant); if A=1, then A'=0, and 1·0=0 (matches again) — both cases confirm the law.
This exhaustive-case-check method (sometimes called 'perfect induction' since it checks literally every possible case rather than a general argument) is the standard way to verify any claimed Boolean identity involving a small number of variables, and it is exactly the technique you should fall back on any time you're unsure whether a proposed simplification is actually valid — if it holds for every row of the truth table, it's a valid law; if even one row breaks it, it is not.
• Step 1: Identify every value the variable(s) in the law can take (just 0 and 1 for a single-variable law). • Step 2: Substitute each case into both sides of the claimed identity. • Step 3: Confirm both sides match for every case — this is a complete proof by perfect induction over {0,1}.
Practical and Real-World Application: Gate-Count Reduction
These laws are the literal justification every time a real circuit is simplified to use fewer gates. If a designer's derived expression contains a subexpression like B + 1 somewhere, the null law A+1=1 (with B substituted for A) immediately tells them that entire subexpression collapses to the constant 1, and any gates that would have computed B in the first place can potentially be removed from the circuit entirely if B feeds nothing else — fewer gates means less silicon area, lower power consumption, and often less propagation delay, all of which are direct engineering costs in real chip design.
The idempotent laws in particular have already shown up as load-bearing facts earlier in this course: Module 3.4's proof that A NAND A = A' depends specifically on A·A=A, and Module 3.5's mirror proof that A NOR A = A' depends specifically on A+A=A. Recognizing these laws by name, rather than just intuiting that 'tying inputs together must do something useful', is what lets you extend the same reasoning to new circuits you haven't seen worked out before.
Common Mistake and the Tricky Concept
The spec's tricky point is a blanket warning worth taking seriously: do not apply ordinary arithmetic laws blindly, because Boolean algebra follows its own algebraic identities. The clearest example is the null law A + 1 = 1 — read with arithmetic intuition, 'anything plus 1' should keep growing or at least change with the other operand, but in Boolean algebra it is a constant, fixed result regardless of A's value. Similarly, A + A = A looks like it violates 'normal' addition (where x + x = 2x, not x) — but Boolean OR has no concept of magnitude or 2, only true/false, so 'true or true' is still just 'true'.
A second, subtler trap is assuming every arithmetic-looking law automatically holds. Some do carry over by coincidence of structure (commutativity, A+B=B+A and A·B=B·A, and associativity both hold in Boolean algebra exactly as in arithmetic), but you should never assume an unlisted identity is valid just because its arithmetic analogue is — always verify with the perfect-induction method shown above before relying on a Boolean identity you haven't seen explicitly stated.
The Nine Boolean Laws
These are exactly the nine laws the spec lists under 'Important Laws'. Null laws (A+1=1, A·0=0) have no ordinary-arithmetic equivalent — they are pure Boolean-domain facts.
Identity laws: A + 0 = A A · 1 = A
Null laws: A + 1 = 1 A · 0 = 0
Idempotent laws: A + A = A A · A = A
Complement laws: A + A' = 1 A · A' = 0
Involution law: (A')' = ACode Examples
Because a single Boolean variable can only be 0 or 1, checking both cases exhaustively is a complete proof. The A=1 case is the one that trips up arithmetic intuition: under Boolean OR, 1+1 is still just 1 (per the OR truth table established in Module 3.3), not 2, which is exactly why this idempotent law holds despite looking unusual next to ordinary addition.
A + A = A, verified for both A=0 and A=1 Any Boolean subexpression OR'd with the constant 1 collapses to 1 immediately, by the null law A+1=1 — it does not matter what B·C evaluates to, because ORing it with 1 always produces 1. In a real circuit, this tells a designer the gates computing B·C could potentially be removed entirely if their only use was feeding this OR.
Anything + 1 = 1, regardless of the other operand's complexity
Case A=0: A + A = 0 + 0 = 0 ✓ matches A
Case A=1: A + A = 1 + 1 = 1 ✓ matches A (OR truth table: 1+1=1, not 2)
Both cases confirmed → A + A = A holds for all A.F = B·C + 1
Apply null law (with the substitution X=1 for A+1=1, here X = B·C):
F = 1
Result: the entire B·C term is irrelevant — F is always 1.Important Rules
A + 0 = A and A · 1 = A (identity laws — 0/1 as 'do nothing' elements).
A + 1 = 1 and A · 0 = 0 (null/dominance laws — no arithmetic equivalent).
A + A = A and A · A = A (idempotent laws — self-combination changes nothing).
A + A' = 1 and A · A' = 0 (complement laws — a variable and its complement resolve to a constant).
(A')' = A (involution law — double complementation cancels).
Gate-Count and Power Reduction in Real Circuits
Every one of these nine laws is a justified, provable rewrite rule that real circuit designers (and automated logic-synthesis tools) apply to reduce the number of gates in a circuit, directly lowering silicon area, power consumption, and propagation delay — the idempotent laws specifically already underpinned the NAND/NOR tied-input inverter constructions from Module 3.4 and 3.5.
Reading A + 1 = 1 with arithmetic intuition and expecting the result to depend on A, the way ordinary addition would.
Treat A + 1 = 1 as an absolute Boolean identity: OR with the constant 1 always produces 1, regardless of A's value — this is a dominance law with no arithmetic counterpart.
The spec warns explicitly: 'Do not apply ordinary arithmetic laws blindly. Boolean algebra follows its own algebraic identities.' A + 1 = 1 is the clearest example of a law that looks wrong under arithmetic intuition but is fully correct and constantly used in Boolean algebra.
[tricky-problem] Why does the spec warn against applying 'ordinary arithmetic laws blindly' to Boolean algebra, using A + 1 = 1 as the key example? A. Because Boolean algebra doesn't actually support the '+' symbol. B. Because A + 1 always equals 1 regardless of A's value, unlike arithmetic addition where the result depends on both operands — this null-law behavior has no arithmetic counterpart. C. Because A + 1 equals 0 in Boolean algebra, the opposite of arithmetic. D. Because Boolean algebra requires all variables to be positive.
B. Because A + 1 always equals 1 regardless of A's value, unlike arithmetic addition where the result depends on both operands — this null-law behavior has no arithmetic counterpart. — The null law A + 1 = 1 is a purely Boolean-domain fact: OR-ing with the constant 1 always dominates and forces the result to 1, no matter what A is. This directly contradicts arithmetic intuition, where a sum's result generally does depend on both addends — exactly the kind of blind-application trap the spec's tricky problem warns about.
[interview] Which Boolean law directly justifies the earlier claim (Module 3.4) that A NAND A = A'? A. The null law, A · 0 = 0 B. The idempotent law, A · A = A, which collapses the tied-input AND stage to a plain A before NAND's built-in inversion is applied C. The complement law, A · A' = 0 D. The identity law, A · 1 = A
B. The idempotent law, A · A = A, which collapses the tied-input AND stage to a plain A before NAND's built-in inversion is applied — Tying both NAND inputs to A produces (A·A)'. The idempotent law A·A=A reduces the inner AND to just A, leaving (A)' = A' — a plain inverter. This is the exact algebraic justification underlying the NAND-based (and, via A+A=A, the NOR-based) tied-input inverter construction.
Simplify the expression H = (A + A') · (B + 0) using only the laws from this lesson. Show which law justifies each step.
A + A' = 1 (complement law). B + 0 = B (identity law). So H = 1 · B = B (identity law, A·1=A applied with B in place of A).
Simplify each parenthesized group independently before combining them.