The mathematical language of all digital circuits. Master every law — from the basic identity and null rules to De Morgan's theorems and K-Map minimization — with interactive proof tools and a live K-Map builder.
Boolean Algebra, formalized by George Boole in 1847 and later adapted for circuit analysis by Claude Shannon in 1938, is the algebraic system that governs all digital logic. Unlike conventional algebra where variables hold any real number, Boolean variables hold exactly one of two states: 1 (True/HIGH) or 0 (False/LOW).
This binary constraint makes Boolean Algebra simultaneously simpler and stranger than regular algebra. Laws that seem wrong in arithmetic — like A + A = A — are fundamental truths in Boolean logic. Understanding this distinction is the first step toward writing correct, minimal logic.
Why it matters in VLSI: Every combinational circuit in a chip is ultimately an implementation of a Boolean expression. Minimizing that expression directly reduces gate count, silicon area, power consumption, and propagation delay.
E.V. Huntington's Postulates (1904) define the formal axioms. For a set K with operators + (OR) and · (AND) to be a Boolean Algebra:
Closure — results always stay within K (0 or 1)
Identity elements — 0 for OR, 1 for AND
Commutativity — order of operands doesn't matter
Distributivity — each operator distributes over the other
Complement — every element has a unique complement
Section 02
The Three Fundamental Operations
All Boolean logic is built from three primitive operations. Every gate in every chip is an implementation of one of these, or a combination:
Operation
Symbol
Gate
Output is 1 when…
CMOS Cost
AND (Conjunction)
A · B
AND
All inputs are HIGH
4 transistors
OR (Disjunction)
A + B
OR
At least one input is HIGH
4 transistors
NOT (Negation)
A' or Ā
Inverter
Input is LOW
2 transistors
NAND (Universal)
(A · B)'
NAND
Not all inputs are HIGH
2 transistors ★
NOR (Universal)
(A + B)'
NOR
All inputs are LOW
2 transistors ★
★ Why NAND/NOR are preferred in CMOS: A native CMOS gate is inherently inverting. NAND and NOR are implemented directly with 2 stacked transistors each — no extra inverter needed. AND and OR require 4 transistors (NAND + inverter). This is why most logic synthesis tools target NAND-NOR libraries.
Section 03 – 10
All Boolean Laws at a Glance
Each card below shows the law, its formula, and its practical significance. Click any card to highlight it.
Identity Law
A + 0 = A A · 1 = A
OR-ing with 0 or AND-ing with 1 leaves a variable unchanged. These are the "neutral elements" of Boolean algebra.
Identity
Null (Annulment) Law
A + 1 = 1 A · 0 = 0
OR with 1 always forces output high. AND with 0 always forces output low — the constant "dominates." Used to detect constant inputs in synthesis.
Null
Idempotent Law
A + A = A A · A = A
Combining a variable with itself yields the variable. This proves logic is not additive — wiring the same signal twice to an AND or OR gate is redundant silicon.
Idempotent
Complement Law
A + A' = 1 A · A' = 0
A variable OR its complement is always 1; AND is always 0. This is the Law of Excluded Middle and the Law of Contradiction — the twin pillars of binary logic.
Complement
Double Negation
(A')' = A
Inverting a signal twice restores the original. Two back-to-back inverters in a signal path are wasteful — synthesis tools remove them. Also used in driving high fan-out nets.
Involution
Commutative Law
A + B = B + A A · B = B · A
Input order to a gate doesn't affect the logical output. Physical wire routing may differ but the Boolean result is identical. Fundamental for place-and-route flexibility.
Commutative
Associative Law
(A+B)+C = A+(B+C) (A·B)·C = A·(B·C)
Grouping of terms doesn't change the result. Allows cascading 2-input gates to build 3+ input functions without logic change — crucial for gate-level netlist mapping.
Associative
Distributive Law
A·(B+C) = A·B + A·C A+(B·C) = (A+B)·(A+C)
The second form (OR over AND) has no equivalent in regular math. Used for factoring SOP expressions into POS form and for logic restructuring during optimization.
Distributive
Absorption Law
A + (A·B) = A A · (A+B) = A
The AB term is entirely "absorbed" by A. One of the most powerful simplification tools — in a K-Map, this eliminates covered cells. Directly reduces gate count.
Absorption
Redundancy Law
A + A'·B = A + B A · (A'+B) = A · B
The complement variable in the second term is redundant — B already covers what A'B adds. Used in logic hazard elimination and SOP simplification.
Redundancy
Section 08
De Morgan's Theorems
Proposed by Augustus De Morgan in 1847, these two theorems are the most consequential rules in all of digital electronics. They show that AND and OR are mathematically dual — you can always convert one to the other by complementing appropriately.
Theorem 1: (A + B)' = A' · B'
Theorem 2: (A · B)' = A' + B'
In plain English:
Theorem 1: The complement of a SUM equals the PRODUCT of the complements → NOR = Bubbled-AND
Theorem 2: The complement of a PRODUCT equals the SUM of the complements → NAND = Bubbled-OR
A
B
(A+B)'
A'·B'
Match?
(A·B)'
A'+B'
Match?
0
0
1
1
✓
1
1
✓
0
1
0
0
✓
1
1
✓
1
0
0
0
✓
1
1
✓
1
1
0
0
✓
0
0
✓
VLSI Application — Active-Low Logic: Most flip-flop reset and chip-select pins are active-low (labeled RST_N, CS_N). De Morgan's theorems let designers convert between active-high and active-low logic without adding inverters, by swapping gates and flipping input polarities on a schematic (bubble pushing).
Section 09
Consensus Theorem
The Consensus Theorem eliminates a redundant "consensus term" when a variable and its complement appear across different product terms:
AB + A'C + BC = AB + A'C
(A+B)·(A'+C)·(B+C) = (A+B)·(A'+C)
The term BC is the consensus of AB and A'C. Whenever B=1 and C=1, either A=1 (making AB=1) or A=0 (making A'C=1). So BC can never be the "only" 1 in the expression — it's always already covered. Eliminating it reduces the circuit.
Hazard Cover: Paradoxically, the consensus term is sometimes deliberately added (not removed) to eliminate static hazards — glitches that occur during signal transitions. The redundant term bridges the timing gap between the two covering terms.
Section 10
Principle of Duality
For every Boolean theorem, there exists a dual theorem obtained by:
Swapping every OR (+) with AND (·) and vice versa
Swapping every 0 with 1 and vice versa
Do NOT complement any variables
Original Law
Dual Law
A + 0 = A
A · 1 = A
A + 1 = 1
A · 0 = 0
A + A = A
A · A = A
A + A' = 1
A · A' = 0
A·(B+C) = AB+AC
A+(B·C) = (A+B)·(A+C)
Section 11
Karnaugh Map (K-Map) Minimization
A Karnaugh Map (K-Map), developed by Maurice Karnaugh in 1953, is a visual grid for minimizing Boolean expressions. It arranges truth table values so that adjacent cells differ by exactly one variable — which makes grouping of 1s (minterms) directly visible as simplified terms.
K-Map rules for grouping:
Groups must contain 1, 2, 4, 8… (powers of 2) adjacent 1-cells
Groups can wrap around edges (the K-Map is toroidal)
Make each group as large as possible — larger group = fewer literals
Every 1-cell must be covered by at least one group
Use the minimum number of groups that cover all 1s
Notice the Gray code ordering (00, 01, 11, 10) on the axes — adjacent cells differ by exactly one bit. Use the interactive K-Map builder below to practice grouping minterms.
Section 12
Boolean Algebra in VLSI Design
Boolean minimization is not a paper exercise — every law has a direct silicon cost:
Logic Synthesis
EDA tools like Synopsys Design Compiler parse RTL and internally apply Boolean minimization (Quine-McCluskey, ESPRESSO algorithm) to reduce gate count before technology mapping.
Gate-Level Optimization
Absorption and redundancy laws eliminate unnecessary gates. Every removed gate saves area (μm²), leakage current (nA), and switching energy (fJ) at 5nm/3nm nodes.
Active-Low Interfaces
De Morgan's theorems enable bubble-pushing: converting from positive to negative logic and back without adding inverters — critical for matching IP block interfaces.
Glitch Elimination
Static hazards in combinational paths cause unnecessary switching power. Adding the consensus term provides a steady path during transitions, eliminating glitches at the cost of one gate.
⚡ INTERACTIVE LAB — Boolean Algebra Workbench
Verify laws live, build K-Maps, and evaluate expressions with any input combination.
Select a Boolean law, set variable values with the toggle buttons, and watch both sides evaluate in real time.
A
B
C
Left Side (LHS)A + 0
Evaluates to
0
A = 0 A + 0 = 0
Right Side (RHS)A
Evaluates to
0
A = 0 Result = 0
✓ LAW HOLDS — LHS = RHS
Click the cells to toggle minterms (1s). The K-Map will automatically find groups and generate the minimized Sum of Products (SOP) expression.