12.1 Axioms of Boolean Algebra

A Boolean algebra is a set B = {0, 1} with operations + (OR), · (AND), and ' (complement) satisfying the Huntington postulates:

Note the shock for ordinary algebra: both distributive laws hold, including + over ·. Also, 1 + 1 = 1 (idempotence), not 2 — Boolean + is OR, not addition.

Duality principle: any theorem remains valid after swapping + ↔ · and 0 ↔ 1 simultaneously. Prove one law and its dual comes free. Example pair: x + x·y = x (absorption) and its dual x·(x + y) = x.

12.2 Fundamental Theorems (with a Sample Proof)

Idempotent (x + x = x), Domination (x + 1 = 1), Involution ((x')' = x), Absorption (x + xy = x), De Morgan ((x + y)' = x'·y' and (x·y)' = x' + y').

Algebraic proof of absorption: x + xy = x·1 + x·y = x(1 + y) = x·1 = x. ∎ (Each step: identity, distributive, domination, identity.)

12.3 Boolean Functions, Minterms and Canonical Forms

A minterm of n variables is a product containing each variable once (plain or complemented); minterm m_i is 1 on exactly one input row. Any function is the OR of its 1-rows' minterms — the canonical Sum of Products (SOP), written F = Σm(...). Dually, the Product of Sums (POS) ANDs the maxterms of the 0-rows.

Worked Example 1 — algebraic simplification. Simplify F = xy + xy' + x'y.

1. xy + xy' = x(y + y') = x·1 = x.
2. F = x + x'y = (x + x')(x + y) = 1·(x + y) = x + y.

Step 2 used the other distributive law — the one that feels illegal in ordinary algebra. Gate cost dropped from three 2-input ANDs + OR to a single OR gate.

12.4 Karnaugh Maps (K-Maps)

A K-map arranges the truth table so that adjacent cells differ in one variable (Gray-code order 00, 01, 11, 10), letting the eye apply x + x' = 1. Rules:

1. Group 1s into rectangles of size 1, 2, 4, 8 (powers of 2).
2. The map wraps around: leftmost and rightmost columns are adjacent, as are the top and bottom rows.
3. Make groups as large as possible, as few as possible; overlaps are allowed.
4. A group of 2^k cells eliminates k variables. Don't-care cells (×) may join any group when convenient.

12.5 Worked Example 2 — 3-Variable K-Map

Minimize F(A, B, C) = Σm(0, 2, 4, 5, 6).

           BC=00  BC=01  BC=11  BC=10
    A=0      1      0      0      1
    A=1      1      1      0      1

1. Columns BC=00 and BC=10 are wrap-adjacent, so {m0, m2, m4, m6} form a quad. Inside it A and B both vary; C = 0 is constant → term C'.
2. Cells m4 (A=1, BC=00) and m5 (A=1, BC=01) form a pair: A = 1, B = 0 constant, C varies → term AB'.
3. F = C' + AB'. Verify m5 (1,0,1): C' = 0, AB' = 1 → F = 1 ✔; m7 (1,1,1): both terms 0 → F = 0 ✔.

The unsimplified SOP needed five 3-input AND gates plus a 5-input OR; the minimal form needs one inverter, one AND, one OR. For 4 variables the map is 4×4 with both axes in Gray order (rows AB = 00, 01, 11, 10; columns CD likewise); corner cells are mutually adjacent by double wrap-around.

12.6 Logic Gates

NAND universality: NOT x = NAND(x, x); AND = NOT(NAND); OR x + y = NAND(x', y') by De Morgan. Hence any circuit — an entire CPU — can be manufactured from one gate type, which simplifies fabrication. A half-adder is XOR (sum) + AND (carry): Boolean algebra is literally what arithmetic hardware is made of.

12.7 Common Mistakes

• Grouping counts other than powers of 2 (a group of 3 or 6 is invalid).
• Missing wrap-around adjacencies and corner quads.
• Simplifying with ordinary-algebra reflexes: x + x = x (not 2x); there is no subtraction or division in Boolean algebra — never "cancel" terms.
• For POS, group the 0s and complement, or read maxterms directly.

🎯 Exam Focus

1. State the Huntington postulates and explain the principle of duality with an example.
2. Prove algebraically: (a) x + x'y = x + y, (b) (x + y)(x + y') = x.
3. Express F(A, B, C) = A + B'C in canonical SOP (Σm) form.
4. Minimize F(A, B, C, D) = Σm(0, 1, 2, 4, 5, 6, 8, 9, 12, 13, 14) using a K-map.
5. Prove NAND is a universal gate by constructing NOT, AND, OR from it.
6. Draw the logic circuit of the minimized function in Q4 using AND-OR-NOT gates, then using NAND gates only.