Boolean Algebra & K-Maps

Boolean algebra lets you simplify logic before building it. Learn the laws (identity, complement, distributive, absorption), De Morgan's theorems, SOP and POS forms, minterms and maxterms, Karnaugh maps with don't-cares, and how simplification saves gates, power and delay.

A logic function can be written in many equivalent ways. Simplifying it reduces the number of gates, chip area, power and delay. Karnaugh maps give a visual method for up to 4–5 variables; software (Espresso, synthesis tools) handles larger ones.

An analogy

Boolean simplification is like simplifying fractions: 6/8 and 3/4 are equal, but the simpler form is cheaper to work with.

Laws

Commutative, associative, distributive (including A + BC = (A + B)(A + C)), idempotent (A + A = A), involution ((A′)′ = A). De Morgan converts between AND/OR forms — essential for NAND/NOR implementations.

Canonical forms

Sum of products (SOP) = OR of AND terms, built from minterms where F = 1. Product of sums (POS) = AND of OR terms from maxterms where F = 0. SOP maps directly to NAND–NAND logic.

Karnaugh maps

Cells are ordered in Gray code so neighbours differ by one variable. Group 1s in rectangles of 1, 2, 4, 8… (wrapping around edges); each group eliminates variables. Use don't-cares (x) to make larger groups.

Hazards and automation

Minimal SOP can create static hazards (glitches) — adding a redundant consensus term removes them. Quine–McCluskey and Espresso algorithms minimise large functions; synthesis tools optimise for area, delay and power.

Formulas

• Identity & complement: A + 0 = A, A·1 = A, A + A′ = 1, A·A′ = 0
• Absorption: A + AB = A, A(A + B) = A
• De Morgan: (A·B)′ = A′ + B′, (A + B)′ = A′·B′
• Consensus: AB + A′C + BC = AB + A′C

Worked example: Algebraic simplification

Given: F = AB + AB′ + A′B

Find: Minimal form.

• AB + AB′ = A(B + B′) = A
• F = A + A′B = A + B (absorption)

Answer: F = A + B

Worked example: K-map

Given: F(A,B,C) = Σm(1,3,5,6,7)

Find: Minimal SOP.

• Group m1, m3, m5, m7 → C
• Group m6, m7 → AB

Answer: F = C + AB (2 terms instead of 5)

Common mistakes

• Wrong: Not wrapping K-map edges. — Right: Edges and corners are adjacent.
• Wrong: Forgetting don't-cares. — Right: Use x cells to enlarge groups.

Applications

• Control logic: Minimal decoding for enables and alarms.
• FPGA/ASIC synthesis: Automatic Boolean optimisation.
• Verification: Equivalence checking of logic.

Key takeaways

• Use laws and De Morgan to simplify.
• SOP from minterms, POS from maxterms.
• K-maps: group powers of two, wrap edges.
• Simpler logic = fewer gates, less power.

Going further

• Quine–McCluskey: Tabular minimisation.
• Hazard-free design: Consensus terms prevent glitches.
• BDDs: Binary decision diagrams for large functions.