BOOLEAN ALGEBRA & LOGIC GATES — COMPLETE EXAM-READY GUIDE

Aditya, yeh chapter Computer Architecture ka backbone hai. Government exams

mein isse 3 se 5 questions guaranteed aate hain — IBPS SO IT, SSC CGL, NIELIT,
DSSSB, sab mein. Toh isko poora khatam karte hain, zero se hero tak, ek hi
response mein. Chal shuru karte hain!

PHASE 1 — WHY BOOLEAN ALGEBRA EXISTS? (Intuition

Building)
Real-life analogy: Dekh, computer ke andar sirf electricity chalti hai — ON ya
OFF. Koi "maybe" nahi hota. Jaise tubelight ka switch — ON (1) ya OFF (0). Ab
agar tujhe 10 switches ko aapas mein connect karke koi decision lena ho —
"agar switch A ON hai AUR switch B OFF hai TOH fan chale" — toh tujhe ek
mathematical system chahiye jo sirf 0 aur 1 mein kaam kare.

Yahi system hai Boolean Algebra — jo 1854 mein George Boole ne banaya tha.

Exam Fact: Boolean Algebra was invented by George Boole in 1854. Yeh almost
har exam mein pucha jaata hai!

Formal Definition: Boolean Algebra ek mathematical system hai jo sirf two

values — 0 (FALSE) aur 1 (TRUE) — ke saath kaam karta hai, aur isme teen basic
operations hain: AND, OR, NOT.

Logic Gates = Boolean operations ko electronically implement karne ke liye jo

circuits bante hain, unhe Logic Gates kehte hain.

Real World Boolean Algebra

────────── ───────────────
Switch ON → 1 (TRUE)
Switch OFF → 0 (FALSE)
"AND" condition → A · B (AND)
"OR" condition → A + B (OR)
"NOT" (opposite) → A̅ or A' (NOT)

PHASE 2 — CLASSIFICATION TREE (Full Hierarchy)

┌──────────────────────┐
│ LOGIC GATES │
└──────────┬───────────┘
│
┌──────────────────────┼──────────────────────┐
│ │ │
┌────────▼────────┐ ┌─────────▼─────────┐ ┌─────────▼─────────┐
│ BASIC GATES │ │ UNIVERSAL GATES │ │ SPECIAL GATES │
│ (Fundamental) │ │ (Can make ANY gate)│ │ (Derived) │
└────────┬────────┘ └─────────┬─────────┘ └─────────┬─────────┘
│ │ │
┌──────┼──────┐ ┌────┼────┐ ┌─────┼─────┐
│ │ │ │ │ │ │
┌─▼─┐ ┌─▼──┐ ┌─▼──┐ ┌─▼───┐ ┌──▼──┐ ┌──▼──┐ ┌──▼───┐
│AND│ │ OR │ │NOT │ │NAND │ │ NOR │ │ XOR │ │ XNOR │
└───┘ └────┘ └────┘ └─────┘ └─────┘ └─────┘ └──────┘
 Total Gates = 7
Basic = 3 (AND, OR, NOT)
Universal = 2 (NAND, NOR)
Special = 2 (XOR, XNOR)

Yaad rakh: Total 7 gates hain. 3 Basic + 2 Universal + 2 Special = 7

PHASE 3 — BASIC GATES (AND, OR, NOT)

3.1 — AND GATE

Real-life analogy: Soch, tere ghar mein ek room ka darwaza kholne ke liye dono
locks ka key chahiye. Agar dono keys hain (1 AND 1) — darwaza khulega (1).
Agar ek bhi key missing hai — darwaza band (0).

Definition: AND Gate ka output 1 hota hai SIRF jab ALL inputs 1 hon.

Symbol & Notation:

A ───┐
│ AND
B ───┤────── Y = A · B (ya A AND B)
│
Symbol:

A ──────┐
|D──── Y = A · B
B ──────┘

Shape: Flat back, curved front (D-shape)

Truth Table (2-input AND):

┌─────┬─────┬───────────┐
│ A │ B │ Y = A · B │
├─────┼─────┼───────────┤
│ 0 │ 0 │ 0 │
│ 0 │ 1 │ 0 │
│ 1 │ 0 │ 0 │
│ 1 │ 1 │ 1 │ ← Sirf yahi 1 hai
└─────┴─────┴───────────┘

Exam Point: AND gate mein output 1 hota hai ONLY when ALL inputs are 1.
Trick: AND = "sab 1 ho toh 1, warna 0" — bahut strict hai, ek bhi 0 aaya toh
output 0. ⭐⭐ Identity: A · 1 = A and A · 0 = 0

3.2 — OR GATE

Real-life analogy: Soch ek room mein 2 doors hain. Agar koi bhi ek door khula
ho, toh tu room mein ja sakta hai. Sirf jab dono band hon, toh nahi ja sakta.

Definition: OR Gate ka output 1 hota hai jab koi bhi ek ya zyada inputs 1 hon.

Symbol & Notation:

 A ───┐
│ OR
B ───┤────── Y = A + B (ya A OR B)
│
Symbol:

A ──────\
)──── Y = A + B
B ──────/

Shape: Curved back, pointed front

Truth Table (2-input OR):

┌─────┬─────┬───────────┐
│ A │ B │ Y = A + B │
├─────┼─────┼───────────┤
│ 0 │ 0 │ 0 │ ← Sirf yahi 0 hai
│ 0 │ 1 │ 1 │
│ 1 │ 0 │ 1 │
│ 1 │ 1 │ 1 │
└─────┴─────┴───────────┘

Exam Point: OR gate mein output 0 hota hai ONLY when ALL inputs are 0.
Trick: OR = "koi bhi 1 ho toh 1" — bahut lenient hai. ⭐⭐ Identity: A + 0 = A
and A + 1 = 1

3.3 — NOT GATE (Inverter)

Real-life analogy: Yeh ek ulta mirror hai. Jo bhi input de — output uska
opposite aata hai. 0 diya → 1 aaya. 1 diya → 0 aaya.

Definition: NOT Gate input ko invert (ulta) karta hai. Single input gate hai.

Symbol & Notation:

A ───▷○──── Y = A' = Ā = NOT A

(Triangle with small circle at output)

Circle = inversion (bubble)

Truth Table:

┌─────┬──────────┐
│ A │ Y = A' │
├─────┼──────────┤
│ 0 │ 1 │
│ 1 │ 0 │
└─────┴──────────┘

Exam Point: NOT gate is the only single-input gate. Baaki sab minimum 2-
input hain. NOT ko represent karte hain: A' ya Ā (A-bar) ya ¬A ⭐⭐ Double
NOT: (A')' = A (double inversion = original)

⭐ BASIC GATES — COMPARISON TABLE

┌──────────┬─────────────┬───────────────┬──────────────────────────┐
│ Gate │ Notation │ Output = 1 │ Output = 0 │
│ │ │ When? │ When? │
├──────────┼─────────────┼───────────────┼──────────────────────────┤
│ AND │ A · B │ ALL inputs=1 │ ANY input=0 │
│ OR │ A + B │ ANY input=1 │ ALL inputs=0 │
│ NOT │ A' / Ā │ Input = 0 │ Input = 1 │
├──────────┼─────────────┼───────────────┼──────────────────────────┤
│ Inputs │ AND=2+ │ OR=2+ │ NOT=1 (only single-input)│
└──────────┴─────────────┴───────────────┴──────────────────────────┘

PHASE 4 — UNIVERSAL GATES (NAND, NOR)

4.1 — NAND GATE (NOT + AND)

Real-life analogy: NAND = AND ka ulta bhai. Jahan AND 1 bolta, NAND 0 bolta.
Jahan AND 0 bolta, NAND 1 bolta.

Definition: NAND = NOT of AND. Output 0 hota hai ONLY when ALL inputs 1 hon.
Baaki sab cases mein 1.

Symbol:

A ──────┐
|D──○── Y = (A · B)' = NOT(A AND B)
B ──────┘

(AND shape + bubble ○ at output)

Truth Table:

┌─────┬─────┬──────────────┐
│ A │ B │ Y = (A·B)' │
├─────┼─────┼──────────────┤
│ 0 │ 0 │ 1 │
│ 0 │ 1 │ 1 │
│ 1 │ 0 │ 1 │
│ 1 │ 1 │ 0 │ ← Sirf yahi 0 hai
└─────┴─────┴──────────────┘

NAND = AND ki EXACTLY opposite truth table Trick: NAND mein sirf "1,1 →
0", baaki sab 1.

4.2 — NOR GATE (NOT + OR)

Real-life analogy: NOR = OR ka ulta bhai. Jahan OR 1 bolta, NOR 0 bolta.

Definition: NOR = NOT of OR. Output 1 hota hai ONLY when ALL inputs 0 hon.

Symbol:

A ──────\
)──○── Y = (A + B)' = NOT(A OR B)
B ──────/

(OR shape + bubble ○ at output)

Truth Table:
┌─────┬─────┬──────────────┐
│ A │ B │ Y = (A+B)' │
├─────┼─────┼──────────────┤
│ 0 │ 0 │ 1 │ ← Sirf yahi 1 hai
│ 0 │ 1 │ 0 │
│ 1 │ 0 │ 0 │
│ 1 │ 1 │ 0 │
└─────┴─────┴──────────────┘

NOR = OR ki EXACTLY opposite truth table Trick: NOR mein sirf "0,0 → 1",
baaki sab 0.

⭐⭐⭐ WHY ARE NAND & NOR CALLED "UNIVERSAL GATES"?

Real-life analogy: Jaise LEGO blocks se tu koi bhi shape bana sakta hai — car,
house, robot — waise hi NAND ya NOR gate se tu koi bhi doosra gate (AND, OR,
NOT, XOR, XNOR) bana sakta hai!

SUPER IMPORTANT EXAM FACT: NAND and NOR are called Universal Gates
because ANY Boolean function can be implemented using ONLY NAND gates or ONLY
NOR gates.

Proof — Making all gates from NAND only:

1) NOT from NAND:

A ──┬──┐
│ |D──○── A'
A ──┘

Connect BOTH inputs to same signal A.

NAND(A,A) = (A·A)' = A' ✅

2) AND from NAND:

A ──┐
|D──○── (A·B)' ──┬──┐
B ──┘ │ |D──○── A·B ✅
(A·B)'─┘

Two NAND gates: First NAND, then NOT(using NAND) = AND

3) OR from NAND:
A ──┬──┐
|D──○── A' ──┐
A ──┘ |D──○── A+B ✅
B ──┬──┐ │
|D──○── B' ──┘
B ──┘

Three NAND gates: NOT A, NOT B, then NAND(A', B') = A+B

Proof — Making all gates from NOR only:

1) NOT from NOR:

A ──┬──\
│ )──○── A'
A ──┘──/

NOR(A,A) = (A+A)' = A' ✅

2) OR from NOR:
NOR(A,B) → then NOT using NOR = (A+B)'' = A+B ✅
Two NOR gates.
3) AND from NOR:
NOR(A,A)=A', NOR(B,B)=B', then NOR(A',B') = (A'+B')' = A·B ✅
Three NOR gates (uses De Morgan's)

Exam mein seedha puchte hain: "Minimum NAND gates to implement AND?" → 2
"Minimum NAND gates to implement OR?" → 3 "Minimum NOR gates to implement OR?"
→ 2 "Minimum NOR gates to implement AND?" → 3

⭐⭐ NAND/NOR — Gates Required Count Table

┌─────────────────┬──────────────────┬──────────────────┐
│ Gate to Make │ Using NAND only │ Using NOR only │
├─────────────────┼──────────────────┼──────────────────┤
│ NOT │ 1 │ 1 │
│ AND │ 2 │ 3 │
│ OR │ 3 │ 2 │
│ XOR │ 4 │ 5 │
│ XNOR │ 5 │ 4 │
└─────────────────┴──────────────────┴──────────────────┘

Pattern dekh: NAND se AND banana easy (2), OR mushkil (3). NOR se OR easy
(2), AND mushkil (3). Yeh logic hai kyunki NAND = NOT-AND, NOR = NOT-OR.

PHASE 5 — SPECIAL GATES (XOR, XNOR)

5.1 — XOR GATE (Exclusive OR)

Real-life analogy: Soch do dost hain — ek hi party mein sirf ek ja sakta hai.
Dono jaye ya dono na jaye — toh output 0. Sirf ek jaye — output 1. "Exclusive"
matlab "sirf ek ko choose karo."

Definition: XOR gate ka output 1 hota hai jab inputs DIFFERENT (alag) hon. Jab
SAME hon toh output 0.

Symbol & Notation:

A ──────\
⊕)──── Y = A ⊕ B (XOR symbol = ⊕)
B ──────/

(OR shape with extra curved line at input side)

Boolean Expression: A ⊕ B = A'B + AB' = A·B' + A'·B

Truth Table:

┌─────┬─────┬─────────────┐
│ A │ B │ Y = A ⊕ B │
├─────┼─────┼─────────────┤
│ 0 │ 0 │ 0 │ ← Same → 0
│ 0 │ 1 │ 1 │ ← Different → 1
│ 1 │ 0 │ 1 │ ← Different → 1
│ 1 │ 1 │ 0 │ ← Same → 0
└─────┴─────┴─────────────┘
 XOR = "Odd number of 1s" detector Trick: XOR — "Different = 1, Same = 0"
⭐⭐ XOR is used in: Half Adder, Parity Checker, Parity Generator, Error
Detection

5.2 — XNOR GATE (Exclusive NOR)

Real-life analogy: XNOR = XOR ka ulta. Yeh "equality checker" hai. Dono same
hain → 1. Dono different hain → 0.

Definition: XNOR gate ka output 1 hota hai jab inputs SAME hon. Jab DIFFERENT
hon toh 0.

Symbol & Notation:

A ──────\
⊕)──○── Y = (A ⊕ B)' = A⊙B
B ──────/

(XOR shape + bubble at output)

Boolean Expression: A ⊙ B = AB + A'B'

Truth Table:

┌─────┬─────┬──────────────┐
│ A │ B │ Y = A ⊙ B │
├─────┼─────┼──────────────┤
│ 0 │ 0 │ 1 │ ← Same → 1
│ 0 │ 1 │ 0 │ ← Different → 0
│ 1 │ 0 │ 0 │ ← Different → 0
│ 1 │ 1 │ 1 │ ← Same → 1
└─────┴─────┴──────────────┘

XNOR = "Even number of 1s" detector (including 0 ones) Trick: XNOR —

"Same = 1, Different = 0" ⭐⭐ XNOR is used in: Equality comparator circuits

⭐⭐ SPECIAL GATES — COMPARISON TABLE

┌────────┬────────────────┬─────────────────┬───────────────────┐
│ Gate │ Output = 1 │ Output = 0 │ Use Case │
├────────┼────────────────┼─────────────────┼───────────────────┤
│ XOR │ Inputs DIFFER │ Inputs SAME │ Adder, Parity │
│ XNOR │ Inputs SAME │ Inputs DIFFER │ Equality checker │
├────────┼────────────────┼─────────────────┼───────────────────┤
│ │ XOR & XNOR are COMPLEMENTS of each other │
└────────┴────────────────┴─────────────────┴───────────────────┘

PHASE 6 — COMPLETE 7-GATE MASTER COMPARISON TABLE

┌────────┬─────────┬──────────────────┬──────────────────┬───────────────┐
│ Gate │ Symbol │ Expression │ Output = 1 When │ Output=0 When │
├────────┼─────────┼──────────────────┼──────────────────┼───────────────┤
│ AND │ A·B │ A · B │ All inputs = 1 │ Any input = 0 │
│ OR │ A+B │ A + B │ Any input = 1 │ All inputs= 0 │
│ NOT │ A' │ A' │ Input = 0 │ Input = 1 │
│ NAND │ (A·B)' │ (A · B)' │ Any input = 0 │ All inputs =1 │
│ NOR │ (A+B)' │ (A + B)' │ All inputs = 0 │ Any input = 1 │
│ XOR │ A⊕B │ A'B + AB' │ Odd no. of 1s │ Even no. of 1s│
│ XNOR │ A⊙B │ AB + A'B' │ Even no. of 1s │ Odd no. of 1s │
└────────┴─────────┴──────────────────┴──────────────────┴───────────────┘

Yeh table ratta maar le — direct questions aate hain isse.

PHASE 7 — BOOLEAN ALGEBRA LAWS (Complete Set)

Real-life analogy: Jaise maths mein a+b = b+a (commutative law) hota hai,
waise Boolean Algebra ke bhi fixed rules hain jo expressions ko simplify karne
mein kaam aate hain.

⭐⭐⭐ ALL BOOLEAN ALGEBRA LAWS — COMPLETE TABLE

┌─────┬────────────────────┬───────────────────────┬────────────────────────┐
│ No. │ LAW NAME │ AND Form │ OR Form │
├─────┼────────────────────┼───────────────────────┼────────────────────────┤
│ 1 │ Identity Law │ A · 1 = A │ A + 0 = A │
│ 2 │ Null/Dominance Law │ A · 0 = 0 │ A + 1 = 1 │
│ 3 │ Idempotent Law │ A · A = A │ A + A = A │
│ 4 │ Complement Law │ A · A' = 0 │ A + A' = 1 │
│ 5 │ Commutative Law │ A · B = B · A │ A + B = B + A │
│ 6 │ Associative Law │ (A·B)·C = A·(B·C) │ (A+B)+C = A+(B+C) │
│ 7 │ Distributive Law │ A·(B+C) = A·B + A·C │ A+(B·C) = (A+B)·(A+C) │
│ 8 │ Absorption Law │ A·(A+B) = A │ A + A·B = A │
│ 9 │ Involution Law │ (A')' = A │ (double NOT = original)│
│ 10 │ De Morgan's Law 1 │ (A·B)' = A' + B' │ (Break AND, flip to OR)│
│ 11 │ De Morgan's Law 2 │ (A+B)' = A' · B' │ (Break OR, flip to AND)│
└─────┴────────────────────┴───────────────────────┴────────────────────────┘

SABSE ZYADA IMPORTANT: De Morgan's Laws, Absorption Law, Distributive Law —

yeh simplification mein sabse zyada use hote hain.

Special Useful Identities (Exam ke liye extra)

┌──────────────────────────────────────────┐
│ A + A'B = A + B (Redundancy Law) │
│ A'+ AB = A'+ B (Redundancy Law) │
│ A(A'+B) = AB (Simplification) │
│ A ⊕ 0 = A │
│ A ⊕ 1 = A' │
│ A ⊕ A = 0 │
│ A ⊕ A' = 1 │
│ A ⊕ B = A'B + AB' │
│ A ⊙ B = AB + A'B' (XNOR) │
└──────────────────────────────────────────┘

PHASE 8 — DE MORGAN'S THEOREM (Detailed)

Real-life analogy: De Morgan's Theorem ek translator hai. Yeh AND ko OR mein
aur OR ko AND mein badal deta hai — saath mein sab variables ko invert kar
deta hai.

Soch aise: "Dono nahi aaye" (NOR) = "Pehla nahi aaya AND doosra nahi aaya"
⭐⭐⭐ Two Theorems:

┌─────────────────────────────────────────────────────────┐
│ │
│ THEOREM 1: (A · B)' = A' + B' │
│ │
│ "NOT of AND = OR of NOTs" │
│ "Break the AND, change to OR, invert each variable" │
│ │
│──────────────────────────────────────────────────────── │
│ │
│ THEOREM 2: (A + B)' = A' · B' │
│ │
│ "NOT of OR = AND of NOTs" │
│ "Break the OR, change to AND, invert each variable" │
│ │
└─────────────────────────────────────────────────────────┘

Memory Trick: "Break the line, change the sign" Jab bar (NOT) todke neeche
laao → AND ↔ OR badal jaata hai, aur har variable pe individually NOT lag
jaata hai.

Step-by-step Verification (Theorem 1):

A │ B │ A·B │ (A·B)' │ A' │ B' │ A'+B'

──┼───┼─────┼────────┼────┼────┼──────
0 │ 0 │ 0 │ 1 │ 1 │ 1 │ 1 ✅ Match
0 │ 1 │ 0 │ 1 │ 1 │ 0 │ 1 ✅ Match
1 │ 0 │ 0 │ 1 │ 0 │ 1 │ 1 ✅ Match
1 │ 1 │ 1 │ 0 │ 0 │ 0 │ 0 ✅ Match

✅ (A·B)' = A'+B' — Proved!

Solved Example — Apply De Morgan's:

Q: Simplify (A·B·C)' = ? A: A' + B' + C' ✅ (Break AND, change to OR, invert
each)

Q: Simplify (A + B + C)' = ? A: A' · B' · C' ✅ (Break OR, change to AND,

invert each)

Q: Simplify ((A·B)' + C)' = ?

Step 1: Let X = (A·B)', so expression = (X + C)'

Step 2: Apply DeMorgan: X' · C'
Step 3: X' = ((A·B)')' = A·B (double NOT cancels)
Step 4: Answer = A·B·C' ✅

PHASE 9 — BOOLEAN EXPRESSION SIMPLIFICATION

(Step-by-Step Examples)
Example 1: Simplify F = AB + AB'

F = AB + AB'
= A(B + B') ← Factor out A (Distributive)
= A(1) ← Complement Law: B + B' = 1
= A ← Identity Law: A·1 = A ✅
Example 2: Simplify F = A + AB

F = A + AB
= A(1 + B) ← Factor out A
= A(1) ← Null Law: 1 + B = 1
= A ← This is Absorption Law ✅

Example 3: Simplify F = (A + B)(A + B')

F = (A + B)(A + B')
= A·A + A·B' + B·A + B·B' ← Distribute
= A + AB' + AB + 0 ← A·A=A, B·B'=0
= A + A(B' + B) ← Factor
= A + A(1)
= A + A
= A ✅

Example 4: Simplify F = A'B'C + A'BC + AB'C + ABC

F = A'B'C + A'BC + AB'C + ABC

= C(A'B' + A'B + AB' + AB) ← Factor out C
= C((A'(B'+B) + A(B'+B))) ← Factor inside
= C(A' + A)
= C(1)
= C ✅

PHASE 10 — CANONICAL FORMS (SOP & POS)

Real-life analogy:

Jaise address likhne ka ek standard format hota hai (Name, Street, City, PIN),
waise Boolean expression likhne ke bhi 2 standard formats hain — SOP aur POS.

SOP — Sum of Products (Minterms)

Definition: Sab product terms (AND) ko OR se jodo.

F = A'BC + AB'C + ABC ← SOP form

└─┬─┘ └─┬─┘
Product Product
(minterm) (minterm)

Products (AND terms) summed by OR

Minterm: Ek product term jismein SARE variables present hain (complemented ya

uncomplemented).

For 2 variables A, B → Minterms:

┌─────┬─────┬──────────┬───────────┐
│ A │ B │ Minterm │ Notation │
├─────┼─────┼──────────┼───────────┤
│ 0 │ 0 │ A'B' │ m₀ │
│ 0 │ 1 │ A'B │ m₁ │
│ 1 │ 0 │ AB' │ m₂ │
│ 1 │ 1 │ AB │ m₃ │
└─────┴─────┴──────────┴───────────┘

Notation: F = Σm(1,3,5,7) means "OR of minterms 1,3,5,7"

 Minterm mein: Variable = 1 → uncomplemented, Variable = 0 → complemented.

POS — Product of Sums (Maxterms)

Definition: Sab sum terms (OR) ko AND se jodo.

F = (A+B+C)(A+B'+C)(A'+B+C) ← POS form

└──┬──┘
Sum term
(maxterm)

Sums (OR terms) multiplied by AND

Maxterm: Ek sum term jismein SARE variables present hain.

For 2 variables A, B → Maxterms:

┌─────┬─────┬──────────┬───────────┐
│ A │ B │ Maxterm │ Notation │
├─────┼─────┼──────────┼───────────┤
│ 0 │ 0 │ A+B │ M₀ │
│ 0 │ 1 │ A+B' │ M₁ │
│ 1 │ 0 │ A'+B │ M₂ │
│ 1 │ 1 │ A'+B' │ M₃ │
└─────┴─────┴──────────┴───────────┘

Notation: F = ΠM(0,2,4,6) means "AND of maxterms 0,2,4,6"

Maxterm mein: Variable = 0 → uncomplemented, Variable = 1 → complemented.

(OPPOSITE of minterms!)

⭐⭐ Conversion between SOP ↔ POS:

┌──────────────────────────────────────────────────────┐
│ If F = Σm(1,3,5,7) for 3 variables (0 to 7) │
│ Then F = ΠM(0,2,4,6) │
│ │
│ RULE: Minterms NOT in SOP → become Maxterms of POS │
│ (Just take the REMAINING numbers) │
└──────────────────────────────────────────────────────┘

Exam Pattern: "Convert Σm(1,4,5,6) into POS for 3 variables" Answer:

ΠM(0,2,3,7) — jo numbers SOP mein nahi hain woh POS mein hain.

PHASE 11 — KARNAUGH MAP (K-MAP) — Complete Guide

Real-life analogy: Samajh, boolean simplification algebra se karna — jaise ek

jungle mein bina map ke raasta dhundna. K-Map ek visual shortcut hai — tu
boxes mein 1 bhar, grouping kar, aur simplified expression nikal. No algebra
needed!

Definition: Karnaugh Map ek graphical method hai Boolean expressions ko

simplify karne ka, jo truth table ko 2D grid mein organize karta hai.

K-Map was introduced by Maurice Karnaugh in 1953.

 11.1 — 2-Variable K-Map

Structure:

B
0 1
┌─────┬─────┐
A 0 │ m₀ │ m₁ │ m₀ = A'B' m₁ = A'B
├─────┼─────┤
1 │ m₂ │ m₃ │ m₂ = AB' m₃ = AB
└─────┴─────┘

Solved Example: Simplify F = Σm(1,2,3)

Step 1: Fill K-Map with 1s at positions 1, 2, 3

B
0 1
┌─────┬─────┐
A 0 │ 0 │ 1 │ (m₁)
├─────┼─────┤
1 │ 1 │ 1 │ (m₂, m₃)
└─────┴─────┘

Step 2: Make groups of adjacent 1s (power of 2: 1,2,4,8...)

Group 1: m₁ + m₃ (column B=1) → B

Group 2: m₂ + m₃ (row A=1) → A

B
0 1
┌─────┬─────┐
A 0 │ 0 │ [1] │ ← Group1 (vertical pair)
├─────┼─────┤
1 │ [1] │ [1] │ ← Group2 (horizontal pair)
└─────┴─────┘

Step 3: F = A + B ✅

11.2 — 3-Variable K-Map

Structure (GRAY CODE order — dhyan de!):

BC
00 01 11 10 ← GRAY CODE! (not 00,01,10,11)
┌─────┬─────┬─────┬─────┐
A 0 │ m₀ │ m₁ │ m₃ │ m₂ │
├─────┼─────┼─────┼─────┤
1 │ m₄ │ m₅ │ m₇ │ m₆ │
└─────┴─────┴─────┴─────┘

CRITICAL: Column order is 00, 01, 11, 10 (Gray Code — sirf ek bit change
hoti hai). Students yahan GALTI karte hain exam mein! 10 aur 11 ka position
swap hai compared to normal binary!

Minterm positions:

m₀ = A'B'C' (000) m₄ = AB'C' (100)

m₁ = A'B'C (001) m₅ = AB'C (101)
m₂ = A'BC' (010) m₆ = ABC' (110)
m₃ = A'BC (011) m₇ = ABC (111)
Solved Example: Simplify F(A,B,C) = Σm(0,2,4,5,6)

Step 1: Fill 1s at m₀, m₂, m₄, m₅, m₆

BC
00 01 11 10
┌─────┬─────┬─────┬─────┐
A 0 │ 1 │ 0 │ 0 │ 1 │ m₀, m₂
├─────┼─────┼─────┼─────┤
1 │ 1 │ 1 │ 0 │ 1 │ m₄, m₅, m₆
└─────┴─────┴─────┴─────┘

Step 2: Grouping (remember: K-Map wraps around!)

Group 1 (Quad): m₀, m₂, m₄, m₆ → corners = column 00 + column 10

BC
00 01 11 10
┌─────┬─────┬─────┬─────┐
A 0 │ [1] │ 0 │ 0 │ [1] │ ← left+right columns wrap!
├─────┼─────┼─────┼─────┤
1 │ [1] │ 1 │ 0 │ [1] │
└─────┴─────┴─────┴─────┘

In this group: B changes, C changes, but C=0 throughout

Constant: C' (C is always 0)
→ Group 1 = C' (B' is not constant, A is not constant)

Wait, let me re-check. m₀(000), m₂(010), m₄(100), m₆(110)

A: 0,0,1,1 → changes
B: 0,1,0,1 → changes
C: 0,0,0,0 → constant 0 → C'
→ Group 1 = C' ✅

Group 2 (Pair): m₄, m₅ → AB'C' + AB'C = AB'

m₄(100), m₅(101): A=1, B=0, C changes
→ Group 2 = AB' ✅

Step 3: F = C' + AB' ✅

11.3 — 4-Variable K-Map

Structure:

CD
00 01 11 10 ← Gray Code
┌──────┬──────┬──────┬──────┐
AB 00 │ m₀ │ m₁ │ m₃ │ m₂ │
├──────┼──────┼──────┼──────┤
01 │ m₄ │ m₅ │ m₇ │ m₆ │
├──────┼──────┼──────┼──────┤
11 │ m₁₂ │ m₁₃ │ m₁₅ │ m₁₄ │
├──────┼──────┼──────┼──────┤
10 │ m₈ │ m₉ │ m₁₁ │ m₁₀ │
└──────┴──────┴──────┴──────┘

Row order: 00, 01, 11, 10 (Gray Code)

Column order: 00, 01, 11, 10 (Gray Code)

Both rows AND columns follow Gray Code! Row order: 00, 01, 11, 10 (NOT 00,
01, 10, 11)

⭐⭐⭐ K-MAP GROUPING RULES:

┌──────────────────────────────────────────────────────────┐
│ RULE 1: Groups must have 1, 2, 4, 8, 16 cells │
│ (ONLY powers of 2) │
│ │
│ RULE 2: Groups must be RECTANGULAR (no L-shape, no │
│ diagonal, no irregular shapes) │
│ │
│ RULE 3: Larger groups = simpler expression │
│ (always make the BIGGEST possible group) │
│ │
│ RULE 4: Every 1 must be covered by at least one group │
│ │
│ RULE 5: Groups CAN OVERLAP (same 1 in multiple groups) │
│ │
│ RULE 6: K-Map WRAPS AROUND: │
│ - Left edge connects to Right edge │
│ - Top edge connects to Bottom edge │
│ - All 4 corners are adjacent! │
│ │
│ RULE 7: 0s are NEVER included in groups │
│ │
│ RULE 8: Fewer groups = better (minimize total groups) │
└──────────────────────────────────────────────────────────┘

MOST COMMON EXAM MISTAKE: Students forget wrap-around — first column is

adjacent to last column, first row is adjacent to last row.

Group to Expression Conversion:

┌────────────┬──────────────────────────────────────┐
│ Group Size │ Variables that DROP OUT │
├────────────┼──────────────────────────────────────┤
│ 1 cell │ No variable drops → 4 variables │
│ 2 cells │ 1 variable drops → 3 variables │
│ 4 cells │ 2 variables drop → 2 variables │
│ 8 cells │ 3 variables drop → 1 variable │
│ 16 cells │ All drop → F = 1 (always true) │
└────────────┴──────────────────────────────────────┘

RULE: Variable that CHANGES in the group → drops out

Variable that stays CONSTANT → remains in expression
(constant at 1 → uncomplemented, constant at 0 → complemented)

Solved Example (4-variable): F(A,B,C,D) = Σm(0,1,2,4,5,6,8,9,12,13,14)

Step 1: Fill K-Map

CD
00 01 11 10
┌──────┬──────┬──────┬──────┐
AB 00 │ 1 │ 1 │ 0 │ 1 │ m₀,m₁,m₂
├──────┼──────┼──────┼──────┤
01 │ 1 │ 1 │ 0 │ 1 │ m₄,m₅,m₆
├──────┼──────┼──────┼──────┤
11 │ 1 │ 1 │ 0 │ 1 │ m₁₂,m₁₃,m₁₄
├──────┼──────┼──────┼──────┤
10 │ 1 │ 1 │ 0 │ 0 │ m₈,m₉
└──────┴──────┴──────┴──────┘

Step 2: Grouping

Group 1 (8-cell): Column CD=00 (all 4 rows) + Column CD=01 (all 4 rows)
→ m₀,m₁,m₄,m₅,m₈,m₉,m₁₂,m₁₃
These 8 cells: A changes, B changes, C=0 constant, D changes
Wait — let me check: CD columns 00 and 01 → C=0 in both, D changes.
Actually: CD=00 → C=0,D=0 and CD=01 → C=0,D=1. So C=0 always, D changes.
A changes (all rows), B changes (all rows).
→ Group 1 = C' (only C stays constant at 0)
 Group 2 (4-cell): m₂,m₆,m₁₄,m₁₀... wait m₁₀ is 0.
Let me recheck: m₂(0010)=1, m₆(0110)=1, m₁₄(1110)=1, m₁₀(1010)=0
So column CD=10 has: 1,1,1,0 (row 10 is 0)

Group 2 (vertical pair): m₂, m₆ → AB=00,01 CD=10

A=0 in both, wait no: m₂ → A=0,B=0. m₆ → A=0,B=1. A=0 constant, B changes.
C=1, D=0 constant.
→ Group 2 = A'C D'... Hmm, let me reconsider.

Actually, better grouping:

m₂(0010), m₆(0110), m₁₄(1110): these 3 can't form a group (not power of 2).

m₂+m₆: A'CD', m₁₄+m₆: BCD', m₂+m₁₄ not adjacent.

Group 2 (4-cell, wrapping): m₂, m₆, m₁₄, m₁₀ → but m₁₀=0. Can't use.

So: Group 2 (pair): m₂ + m₆ → row 00,01 col 10

A: 0,0 → A'; B: 0,1 → changes(drops); C:1,1→C; D:0,0→D'
→ A'CD'

Group 3 (pair): m₆ + m₁₄ → row 01,11 col 10

A: 0,1 → changes; B:1,1→B; C:1,1→C; D:0,0→D'
→ BCD'

Group 2+3 better: m₂,m₆,m₁₂,m₁₄?

m₂=0010, m₆=0110, m₁₂=1100, m₁₄=1110
Check adjacency in K-Map:
m₂ is row00 col10, m₆ is row01 col10, m₁₄ is row11 col10, m₁₂ is row11 col00
m₁₂ is NOT in col10, so this doesn't work as a rectangular group.

Let me try: m₂(row00,col10), m₆(row01,col10), m₁₄(row11,col10)

Only 3 → can't group.

Better approach:
Group 2 (quad, wrap-around): m₀,m₂,m₄,m₆ → CD=00 and CD=10 in rows 00,01
Wait these are already covered by Group 1 (m₀,m₄ are in Group1).

OK let me simplify. The remaining uncovered cells after Group 1 (C') are:
m₂, m₆, m₁₄ (in column CD=10, except m₁₀ which is 0)

Group 2 (pair): m₂ + m₆ → A'CD'

Group 3 (pair): m₆ + m₁₄ → BCD'

But m₁₄ alone: can we get a bigger group?

m₁₂(1100)+m₁₃(1101)+m₁₄(1110)... m₁₂ and m₁₃ already in Group1.

Actually, simplest: after Group 1 = C', remaining = m₂, m₆, m₁₄

Group 2: m₂+m₆ pair in col CD=10, rows 00,01 → A'CD' (but wait, let me keep it simpler)

Hmm, I'm overcomplicating this. Let me pick a cleaner example.

Let me redo with a cleaner example.

F(A,B,C,D) = Σm(0,1,2,5,8,9,10)

CD
00 01 11 10
┌──────┬──────┬──────┬──────┐
AB 00 │ 1 │ 1 │ 0 │ 1 │ m₀,m₁,m₂
├──────┼──────┼──────┼──────┤
01 │ 0 │ 1 │ 0 │ 0 │ m₅
├──────┼──────┼──────┼──────┤
11 │ 0 │ 0 │ 0 │ 0 │
├──────┼──────┼──────┼──────┤
10 │ 1 │ 1 │ 0 │ 1 │ m₈,m₉,m₁₀
└──────┴──────┴──────┴──────┘
Groups:
Group 1 (Quad, wrap-around rows 00+10, cols 00+01):
m₀, m₁, m₈, m₉
A:0,0,1,1→changes; B:0,0,0,0→B'=constant; C:0,0,0,0→C'...
wait: m₀=0000, m₁=0001, m₈=1000, m₉=1001
A changes, B=0 always, C=0 always, D changes → B'C'

Group 2 (Quad, wrap-around rows 00+10, cols 00+10):

m₀, m₂, m₈, m₁₀
m₀=0000, m₂=0010, m₈=1000, m₁₀=1010
A changes, B=0 always, C changes, D=0 always → B'D'

Group 3 (pair): m₁, m₅

m₁=0001, m₅=0101 → A=0 both, B changes, C=0 both, D=1 both → A'C'D

F = B'C' + B'D' + A'C'D ✅

OK this is also getting complicated for a teaching example. Let me use a simpler classic one.

Let me use a cleaner, classic exam example instead:

Solved Example (4-variable): Simplify F(A,B,C,D) = Σm(0, 1, 3, 5, 7, 8, 9, 11,

13, 15)

Step 1: Fill K-Map with 1s

CD
00 01 11 10
┌──────┬──────┬──────┬──────┐
AB 00 │ 1 │ 1 │ 1 │ 0 │ m₀, m₁, m₃
├──────┼──────┼──────┼──────┤
01 │ 0 │ 1 │ 1 │ 0 │ m₅, m₇
├──────┼──────┼──────┼──────┤
11 │ 0 │ 1 │ 1 │ 0 │ m₁₃, m₁₅
├──────┼──────┼──────┼──────┤
10 │ 1 │ 1 │ 1 │ 0 │ m₈, m₉, m₁₁
└──────┴──────┴──────┴──────┘

Step 2: Identify Groups

Group 1 (8-cell — entire columns 01 and 11):

m₁,m₃,m₅,m₇,m₉,m₁₁,m₁₃,m₁₅
→ All where D=1. A,B,C all change.
→ Group 1 = D

Group 2 (Quad — wrap-around rows 00+10, col 00):

m₀, m₈
Plus we need 4... m₀,m₁,m₈,m₉ (row 00+10, col 00+01)
→ already covered by Group 1 (m₁,m₉). But m₀,m₈ not yet covered.

Group 2 (pair, wrap): m₀ + m₈

m₀=0000, m₈=1000 → A changes, B=0, C=0, D=0 → B'C'D'

F = D + B'C'D' ✅

Shortcut: 8-cell group in 4-variable K-Map = single variable. 4-cell = 2

variables. 2-cell = 3 variables. 1-cell = 4 variables.

11.4 — DON'T CARE CONDITIONS (X)

Real-life analogy: Kabhi kabhi kuch input combinations possible hi nahi hoti
(jaise BCD mein 1010 to 1111). In impossible cases mein output se koi farak
nahi padta — "don't care" hai. K-Map mein inhe X se mark karte hain aur
grouping mein convenience ke liye 1 ya 0 maan lete hain.

┌───────────────────────────────────────────────────┐
│ Don't Care (X): │
│ • Mark as X in K-Map │
│ • Can be treated as 1 OR 0 for grouping │
│ • Use as 1 if it helps make a BIGGER group │
│ • Use as 0 if it doesn't help │
│ • Notation: d(2,5,7) means don't care at 2,5,7 │
└───────────────────────────────────────────────────┘

Exam mein don't care wale questions zaroor aate hain!

PHASE 12 — SPECIAL CONCEPTS & CROSS-TOPIC LINKS

⭐ Half Adder & Full Adder (Preview — Digital Circuits chapter se link)

┌─────────────────────────────────────────────────────┐
│ HALF ADDER: │
│ Sum = A ⊕ B (XOR gate) │
│ Carry = A · B (AND gate) │
│ Uses: 1 XOR + 1 AND gate │
│ │
│ FULL ADDER: │
│ Sum = A ⊕ B ⊕ Cin │
│ Carry = AB + BCin + ACin │
│ Uses: 2 XOR + 2 AND + 1 OR gate │
└─────────────────────────────────────────────────────┘

Half Adder aur Full Adder mein XOR gate kaafi important role play karta hai
— yeh cross-link yaad rakh Digital Circuits topic ke liye.

⭐ Parity Bit Connection

XOR gate → used to GENERATE parity bit

XOR gate → used to CHECK/DETECT parity errors

Even Parity: Total 1s (including parity bit) = EVEN

Odd Parity: Total 1s (including parity bit) = ODD

Cross-link: Error Detection topic (Computer Networks / Data Communication)

mein parity bit ka concept aayega.

⭐ Dual & Complement of Boolean Expression

┌─────────────────────────────────────────────────────┐
│ DUAL: Replace AND↔OR, replace 0↔1. │
│ Variables remain SAME. │
│ │
│ COMPLEMENT: Replace AND↔OR, replace 0↔1, │
│ AND complement EACH variable (A→A', B→B') │
│ │
│ Example: │
│ F = AB + C │
│ Dual(F) = (A+B) · C │
│ Complement(F) = (A'+B') · C' │
└─────────────────────────────────────────────────────┘
 PHASE 13 — COMPLETE FORMULA SHEET
╔══════════════════════════════════════════════════════════════╗
║ BOOLEAN ALGEBRA — FORMULA SHEET ║
╠══════════════════════════════════════════════════════════════╣
║ ║
║ BASIC OPERATIONS: ║
║ AND: A · B OR: A + B NOT: A' / Ā ║
║ ║
║ IDENTITY: A·1 = A A+0 = A ║
║ NULL/DOMINANCE: A·0 = 0 A+1 = 1 ║
║ IDEMPOTENT: A·A = A A+A = A ║
║ COMPLEMENT: A·A'= 0 A+A'= 1 ║
║ INVOLUTION: (A')' = A ║
║ COMMUTATIVE: A·B = B·A 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 ║
║ REDUNDANCY: A+A'B=A+B A'(A+B)=A'B ║
║ ║
║ DE MORGAN'S: ║
║ (A·B)' = A'+B' (A+B)' = A'·B' ║
║ ║
║ XOR: A⊕B = A'B+AB' XNOR: A⊙B = AB+A'B' ║
║ A⊕0=A A⊕1=A' A⊕A=0 A⊕A'=1 ║
║ ║
║ K-MAP GROUP SIZES: ║
║ 2-var: max 4 cells 3-var: max 8 4-var: max 16 ║
║ Groups must be powers of 2: 1,2,4,8,16 ║
║ ║
║ MINTERMS & MAXTERMS: ║
║ n variables → 2ⁿ minterms/maxterms ║
║ F(SOP) = Σm(...) ↔ F(POS) = ΠM(remaining) ║
║ ║
║ GATE COUNTS: ║
║ Total gates: 7 (AND,OR,NOT,NAND,NOR,XOR,XNOR) ║
║ Basic: 3 Universal: 2 Special: 2 ║
║ NAND gates for AND=2, OR=3, NOT=1 ║
║ NOR gates for OR=2, AND=3, NOT=1 ║
║ ║
║ HALF ADDER: Sum=A⊕B, Carry=A·B ║
║ FULL ADDER: Sum=A⊕B⊕Cin, Carry=AB+BCin+ACin ║
║ ║
╚══════════════════════════════════════════════════════════════╝

PHASE 14 — EXAM-ORIENTED QUICK FACTS (25 One-

liners)
1. Boolean Algebra was invented by George Boole in 1854.
2. Boolean Algebra deals with only two values: 0 and 1.
3. Three basic operations: AND (·), OR (+), NOT (').
4. AND gate output is 1 only when ALL inputs are 1.
5. OR gate output is 0 only when ALL inputs are 0.
6. NOT is the only single-input gate.
7. NAND and NOR are called Universal Gates.
8. Any Boolean function can be implemented using only NAND or only NOR
gates.
9. NAND = NOT of AND; NOR = NOT of OR.
10. XOR gives 1 when inputs are different; XNOR gives 1 when inputs are
same.
11. XOR is also called "odd function" (detects odd number of 1s).
12. XNOR is also called "even function" or "equivalence gate".
13. De Morgan's: (A·B)' = A'+B' and (A+B)' = A'·B'.
 14. Absorption Law: A+AB = A and A(A+B) = A.
15. A⊕0 = A, A⊕1 = A', A⊕A = 0, A⊕A' = 1.
16. K-Map was introduced by Maurice Karnaugh in 1953.
17. K-Map uses Gray Code ordering (only 1 bit changes between adjacent
cells).
18. K-Map groups must be powers of 2 (1, 2, 4, 8, 16).
19. K-Map wraps around — first & last columns are adjacent, first & last
rows are adjacent.
20. Don't care conditions (X) can be treated as 0 or 1 in K-Map for
larger groups.
21. In SOP (Sum of Products), we use minterms (Σ notation).
22. In POS (Product of Sums), we use maxterms (Π notation).
23. n variables → 2ⁿ minterms and 2ⁿ maxterms.
24. Half Adder uses XOR (sum) and AND (carry) gates.
25. To convert SOP to POS: take the remaining minterm numbers not in the
SOP.

PHASE 15 — PROBABLE EXAM QUESTIONS (25 MCQs

with Answers)

Q1. Boolean Algebra was developed by: (a) Claude Shannon (b) George Boole (c)
Maurice Karnaugh (d) Augustus De Morgan ✅ (b) George Boole

Q2. Which of the following is a Universal Gate? (a) AND (b) OR (c) XOR (d)
NAND ✅ (d) NAND — NAND and NOR are universal gates.

Q3. The output of AND gate is 1 only when: (a) Any input is 1 (b) All inputs
are 0 (c) All inputs are 1 (d) Any input is 0 ✅ (c) All inputs are 1

Q4. NOT gate is also called: (a) Buffer (b) Inverter (c) Amplifier (d)
Converter ✅ (b) Inverter

Q5. The complement of (A + B) according to De Morgan's theorem is: (a) A' + B'
(b) A · B (c) A' · B' (d) (AB)' ✅ (c) A' · B'

Q6. A ⊕ A = ? (a) A (b) 1 (c) 0 (d) A' ✅ (c) 0

Q7. A ⊕ 1 = ? (a) A (b) 0 (c) 1 (d) A' ✅ (d) A'

Q8. How many minimum NAND gates are needed to implement an OR gate? (a) 1 (b)
2 (c) 3 (d) 4 ✅ (c) 3

Q9. XNOR gate output is 1 when: (a) Inputs are different (b) Inputs are same
(c) All inputs are 1 (d) All inputs are 0 ✅ (b) Inputs are same

Q10. Karnaugh Map was introduced by: (a) George Boole (b) Claude Shannon (c)
Maurice Karnaugh (d) De Morgan ✅ (c) Maurice Karnaugh

Q11. In K-Map, the column ordering follows: (a) Binary sequence (b) Octal
sequence (c) Gray Code (d) ASCII Code ✅ (c) Gray Code
Q12. Simplify: A + A'B = ? (a) A (b) B (c) A + B (d) AB ✅ (c) A + B
(Redundancy Law)

Q13. Which gate acts as an equality detector? (a) XOR (b) XNOR (c) NAND (d)
NOR ✅ (b) XNOR

Q14. The maximum number of groups in a 4-variable K-Map is: (a) 4 (b) 8 (c) 16
(d) 32 ✅ (c) 16 (2⁴ = 16 cells)

Q15. A · 0 = ? (a) A (b) 1 (c) 0 (d) A' ✅ (c) 0 (Null/Dominance Law)

Q16. A + 1 = ? (a) A (b) 0 (c) A' (d) 1 ✅ (d) 1 (Null/Dominance Law)

Q17. How many minterms exist for 3 variables? (a) 3 (b) 6 (c) 8 (d) 16 ✅ (c)
8 (2³ = 8)

Q18. Which law states A + AB = A? (a) Identity (b) Commutative (c) Absorption
(d) Distributive ✅ (c) Absorption Law

Q19. NOR gate is equivalent to: (a) OR + NOT (b) AND + NOT (c) OR followed by
NOT (d) NOT followed by OR ✅ (c) OR followed by NOT — NOR = NOT(A OR B)

Q20. In a K-Map, don't care conditions are represented by: (a) 0 (b) 1 (c) X
(d) D ✅ (c) X (also sometimes 'd')

Q21. The dual of expression AB + C is: (a) A'B' + C' (b) (A+B)·C (c) (A+B)+C
(d) A'B'C' ✅ (b) (A+B)·C — Swap AND↔OR, variables stay same.

Q22. Total number of logic gates is: (a) 3 (b) 5 (c) 7 (d) 9 ✅ (c) 7 — AND,
OR, NOT, NAND, NOR, XOR, XNOR

Q23. XOR gate is used in which circuit? (a) Multiplexer (b) Decoder (c) Half
Adder (d) Flip-Flop ✅ (c) Half Adder (Sum = A ⊕ B)

Q24. (A')' = ? (a) 0 (b) 1 (c) A (d) A' ✅ (c) A — Involution Law (double NOT
cancels)

Q25. If F = Σm(1,3,5,7) for 3 variables, the POS form is: (a) ΠM(1,3,5,7) (b)
ΠM(0,2,4,6) (c) Σm(0,2,4,6) (d) ΠM(0,1,2,3) ✅ (b) ΠM(0,2,4,6) — Remaining
numbers from 0-7 not in SOP.

COMPLETE REVISION CHART (One-Page Summary)

╔════════════════════════════════════════════════════════════════════════╗
║ BOOLEAN ALGEBRA & LOGIC GATES ║
║ COMPLETE REVISION CHART ║
╠════════════════════════════════════════════════════════════════════════╣
║ ║
║ GATES: Basic(3): AND OR NOT ║
║ Universal(2): NAND NOR Special(2): XOR XNOR ║
║ Total = 7 gates ║
║ ║
║ AND: All 1→1 OR: Any 1→1 NOT: Inverts (Single-input) ║
║ NAND: NOT-AND NOR: NOT-OR (Universal—can make any gate) ║
║ XOR: Diff→1 XNOR: Same→1 (Complements of each other) ║
║ ║
║ NAND gates: NOT=1, AND=2, OR=3 ║
║ NOR gates: NOT=1, OR=2, AND=3 ║
║ ║
║ KEY LAWS: ║
║ 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 ║
║ Absorption: A+AB=A Redundancy: A+A'B=A+B ║
║ Involution: (A')'=A ║
║ De Morgan: (AB)'=A'+B' (A+B)'=A'·B' ║
║ ║
║ XOR IDENTITIES: A⊕0=A, A⊕1=A', A⊕A=0, A⊕A'=1 ║
║ ║
║ CANONICAL FORMS: ║
║ SOP = Σm (Sum of Minterms — AND terms ORed) ║
║ POS = ΠM (Product of Maxterms — OR terms ANDed) ║
║ Convert: remaining numbers become the other form ║
║ n variables → 2ⁿ minterms/maxterms ║
║ ║
║ K-MAP: ║
║ Inventor: Maurice Karnaugh (1953) ║
║ Order: Gray Code (00,01,11,10) ║
║ Groups: powers of 2 only, rectangular, wrap-around allowed ║
║ Bigger group = simpler term. Don't cares (X) = flexible. ║
║ 2-var: 4 cells, 3-var: 8 cells, 4-var: 16 cells ║
║ ║
║ APPLICATIONS: Half/Full Adder, Parity, Comparator, MUX, Decoder ║
║ ║
╚════════════════════════════════════════════════════════════════════════╝