Lesson 13 — Intermediate

Boolean Algebra & K-Map

Boolean algebra 0 aur 1 ki maths hai — isi se digital circuits aur logic gates bante hain. Is lesson mein seekhenge basic laws, De Morgan, expression simplification, aur K-Map se visual tarike se circuit chhota karna. GATE CS aur electronics dono mein ye section aata hai.

Boolean algebra kya hai

Boolean algebra aur propositional logic ek hi cheez ke do naam hain — bas yahan variables ki jagah 0/1 ki values hoti hain. Isliye commutative, distributive, De Morgan — sab wahi laws yahan bhi lagti hain.

Basic laws (identity, idempotent, De Morgan)

Basic laws (A, B Boolean variables):

Identity     : A ∨ 0 = A        A ∧ 1 = A
Idempotent   : A ∨ A = A        A ∧ A = A
Complement   : A ∨ ¬A = 1       A ∧ ¬A = 0
Domination   : A ∨ 1 = 1        A ∧ 0 = 0
Double neg.  : ¬(¬A) = A
Distributive : A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C)
Absorption   : A ∨ (A ∧ B) = A   A ∧ (A ∨ B) = A

DE MORGAN (sabse important):
  ¬(A ∧ B) = ¬A ∨ ¬B
  ¬(A ∨ B) = ¬A ∧ ¬B

De Morgan mein ek hi rule yaad rakho: bar toda, sign badla — NOT ke andar jaakar AND ↔ OR badal jaata hai. Do NOT laga kar wapas bhi aa sakte ho (double negation).

Expression simplification — worked example

Ab ek expression simplify karte hain — ye hi kaam K-Map bhi karta hai, bas haath se:

F = A′B + AB′ + AB   simplify karo

Step 1: A common lo (do terms mein)
        F = A′B + A(B′ + B)
Step 2: B′ + B = 1 (complement law)
        F = A′B + A
Step 3: A + A′B = A + B  (redundancy rule)
        F = A + B

Cross-check (truth table):
A B | A′B | AB′ | AB | F
0 0 |  0  |  0  | 0  | 0
0 1 |  1  |  0  | 0  | 1
1 0 |  0  |  1  | 0  | 1
1 1 |  0  |  0  | 1  | 1
→ F = 1 jab A=1 ya B=1  →  F = A + B ✓

K-Map (Karnaugh Map)

K-Map ek visual truth table hai — adjacent 1s ko group karke sabse chhota expression milta hai:

K-MAP RULES:
  Cells = 2^variables  (2-var → 4,  3-var → 8)
  Group size = power of 2  (1, 2, 4, 8...)
  Group BADA ho = expression CHHOTA
  Wrap-around allowed (leftmost column = rightmost)
  Har 1 covered hona chahiye, overlap chalega

3-variable: F(A,B,C) = Σm(1, 3, 5, 7)
         BC
  A  00 01 11 10
   0 [ 0  1  1  0 ]
   1 [ 0  1  1  0 ]
  Column 01 aur 11 mein sab 1 → dono ka matlab C = 1
  Group of 4  ⇒  F = C  ✓

2-variable: F(A,B) = Σm(0, 1, 2)
   B  0  1
 A 0 [ 1  1 ]
  1 [ 1  0 ]
  Group (00,01) = A′ ;  Group (00,10) = B′
  F = A′ + B′ = ¬(A ∧ B)  ✓

• Group ka rule: 1, 2, 4, 8 cells hi group ho sakte hain — 3, 5, 6 cells wala group invalid hai.
• Prime implicant: aisa group jo kisi bade group se cover na ho — final answer mein wahi chahiye.
• X cells (dont-care): output jahan matter nahi karta — group mein daal kar bada banao, expression chhota hoga.
• Wrap-around: leftmost aur rightmost column ek doosre ke neighbour hain — yahan se group ban sakta hai.

Exercise

Common mistakes

• De Morgan mein sign nahi badalna: ¬(A∧B) = ¬A ∨ ¬B — AND zaroor OR ban jaata hai. Sirf bars laga kar sign chhod diya toh answer galat.
• K-Map mein 3 ya 5 cells ka group: Group hamesha 2 ki power (1,2,4,8...) hona chahiye. Odd size ka group kisi valid expression ko represent hi nahi karta.
• Wrap-around bhool jaana: K-Map circular hai — leftmost aur rightmost column adjacent hain. Wahan ka group miss karoge toh answer chhota nahi hoga (ya galat bhi).

A, B = do switches (0 = off, 1 = on),  F = bulb
A B | F
0 0 | 0   (dono off → bujha)
0 1 | 1   (alag-alag state → ON)
1 0 | 1
1 1 | 0   (dono same → phir se bujha)
F = A XOR B = A′B + AB′  (two-way switch circuit)