Boolean Algebra & K-Map Minimization

Why Boolean Algebra?

Analogy: A light switch is either ON (1) or OFF (0). A computer is made of billions of tiny switches (transistors). Boolean algebra is the math of these two-state systems — it tells us how to combine switches to build any circuit.

The Basic Gates — Building Blocks

AND gate:  output = 1 only when ALL inputs = 1
           A · B    (like "both A AND B must be true")
           0·0=0  0·1=0  1·0=0  1·1=1

OR gate:   output = 1 when AT LEAST ONE input = 1
           A + B    (like "A OR B or both")
           0+0=0  0+1=1  1+0=1  1+1=1

NOT gate:  output = opposite of input
           A'   or   Ā
           0'=1   1'=0

NAND gate: output = NOT(A AND B) = A' + B'
NOR gate:  output = NOT(A OR B) = A' · B'
XOR gate:  output = 1 when inputs DIFFER = A⊕B
           0⊕0=0  0⊕1=1  1⊕0=1  1⊕1=0

Boolean Laws — The Algebra Rules

Law	AND form	OR form
Identity	A · 1 = A	A + 0 = A
Null	A · 0 = 0	A + 1 = 1
Idempotent	A · A = A	A + A = A
Complement	A · A' = 0	A + A' = 1
Double complement	(A')' = A
Commutative	AB = BA	A+B = B+A
Associative	(AB)C = A(BC)	(A+B)+C = A+(B+C)
Distributive	A(B+C) = AB+AC	A+BC = (A+B)(A+C)
Absorption	A(A+B) = A	A+AB = A

De Morgan's Theorems (critically important):

(A · B)' = A' + B'   "NAND = NOT-AND = OR of complements"
(A + B)' = A' · B'   "NOR = NOT-OR = AND of complements"

Practical use: to implement NAND using OR gates, or NOR using AND gates.
To apply De Morgan: flip the operation (AND↔OR) AND complement each variable.

Canonical Forms — The Standard Representations

Every Boolean function can be written in two canonical forms:

SOP (Sum of Products) = sum of MINTERMS = Σm(...)
POS (Product of Sums) = product of MAXTERMS = ΠM(...)

For 3 variables (A, B, C):
  Minterm m₅ (binary 101): A · B' · C   ← 1=uncomplemented, 0=complemented
  Maxterm M₅ (binary 101): A' + B + C'  ← 0=uncomplemented, 1=complemented
  (Opposite rules!)

Relationship: if f = Σm(1,3,5) then f = ΠM(0,2,4,6,7)
  (minterms not in SOP become maxterms in POS)

Example: f(A,B,C) = A'B + BC

Truth table:
A B C | f
0 0 0 | 0   (m0)
0 0 1 | 0   (m1)
0 1 0 | 1   (m2) ← A'B when C=0
0 1 1 | 1   (m3) ← A'B when C=1, also BC
1 0 0 | 0   (m4)
1 0 1 | 0   (m5)
1 1 0 | 0   (m6)
1 1 1 | 1   (m7) ← BC when A=1

f = Σm(2,3,7)
f = ΠM(0,1,4,5,6)

Karnaugh Map (K-Map) — Visual Minimisation

Analogy: Grouping 1s in a K-map is like grouping adjacent houses in a city to be served by one power line. Bigger groups = simpler circuit.

K-map layout (Gray code order — only 1 bit changes between adjacent cells):

3-variable K-map (A,B on rows, C on columns):
       C=0   C=1
AB=00 | m0  | m1  |
AB=01 | m2  | m3  |
AB=11 | m6  | m7  |
AB=10 | m4  | m5  |
      ↑ Gray code order: 00,01,11,10 (not binary order!)

Grouping rules:

1. Groups must be rectangular (including wrap-around)
2. Group size MUST be a power of 2: 1, 2, 4, 8, 16
3. Wrap-around is allowed: top↔bottom, left↔right, corners
4. Make groups as LARGE as possible (prime implicants)
5. Every 1-cell MUST be covered by at least one group
6. Don't-cares (×) can be included to enlarge, but don't need to be covered

Each group of size 2^k eliminates k variables:
  Group of 2  → 1 variable eliminated
  Group of 4  → 2 variables eliminated
  Group of 8  → 3 variables eliminated

Reading a group: Variables that have the SAME value throughout the group → keep them. Variables that CHANGE → eliminate them.

Example: Group covers cells where A=1,B=0 in all cells, C varies (0 and 1)
  A stays 1 → write A
  B stays 0 → write B'
  C varies  → eliminate C
  Result: A · B'

Prime Implicants and Essential PIs

Prime Implicant (PI): a group that CANNOT be enlarged further
  (Any larger valid grouping that includes all cells of this group exists → PI is not maximal)

Essential PI: a PI that covers at least one minterm NOT covered by any other PI
  → MUST be included in the minimal cover

Algorithm:
  1. Find ALL prime implicants
  2. Identify essential PIs (check each minterm — which PIs cover it?)
  3. Include all essential PIs
  4. Cover remaining minterms with minimum additional PIs

Worked Example: f(A,B,C,D) = Σm(0,1,2,4,5,10,11,14,15)

4-variable K-map:
      CD: 00  01  11  10
AB:00 |  1 |  1 |  0 |  0 |
AB:01 |  1 |  1 |  0 |  0 |
AB:11 |  0 |  0 |  1 |  1 |
AB:10 |  0 |  0 |  1 |  1 |

Identify groups:
Group 1: m0,m1,m4,m5 (first two rows, CD=00,01) → A'D'  (A=0,D=0, BC varies)
  Wait — more carefully: A=0, D varies... let me re-read.
  Cells: (00,00),(00,01),(01,00),(01,01) — A=0 in all, D=0 in all → A'D'?
  No: rows 00,01 (A=0,B=0/1), columns 00,01 (C=0/1,D=0 in col00; D=1 in col01)
  → B varies, C varies, A=0, D varies — need to recheck.

For GATE: practice K-maps on paper, step by step.
General approach: box the 1s, find largest valid groups, read the product term.

SOP vs POS Minimisation

SOP minimisation: group the 1s → gives minimal Sum of Products
POS minimisation: group the 0s → gives minimal Product of Sums
                  (each group of 0s = one SUM term in POS)

Don't-care cells: treat as 1 for SOP, treat as 0 for POS

Quick Check

Q1. Apply De Morgan: simplify (A'B + C')'

= (A'B)' · (C')'     [De Morgan: (X+Y)' = X'Y']
= (A+B') · C         [De Morgan: (XY)' = X'+Y'; and (C')' = C]
= AC + B'C

Q2. What is minterm m₆ for variables A, B, C?

6 in binary = 110
m₆ = A · B · C'    (1→uncomplemented, 0→complemented)

Q3. In a 3-variable K-map, what is the maximum group size? Answer: 8 (all cells = 2^3). A group of 8 = 0 variables → constant function f=1.

Key Points