Universal gates (NAND - NOR completeness) — Hinglish notes

3.1.14 · Hardware › Boolean Algebra & Logic Gates

WHAT / WHY / HOW

WHAT — "Functional completeness" ka matlab hai ki gates ka ek set koi bhi truth table express kar sakta hai. Classic complete set hai ${AND, OR, NOT}$ . Agar ek single gate in teeno ko reproduce kar sake, toh woh gate akela complete = universal hai.

WHY ek hi gate kaafi kyun hoti hai? Kyunki AND/OR/NOT khud zyada primitive operations se bane hote hain, aur dono NAND aur NOR ke andar pehle se hi NOT hota hai. Jab ek baar NOT free mein mil jaye, toh aap un-invert karke AND aur OR tak pahunch sakte ho.

HOW — Strategy: dikhao ki NAND (ya NOR) se NOT, AND, OR bana sakte hain. Kyunki ${A N D, O R, N O T}$ jaana-maana complete set hai, isse transitively prove hota hai ki single gate complete hai.

Definitions

NAND se sab kuch derive karna (first principles se)

Maano $↑$ NAND denote karta hai, toh $A ↑ B = \overline{A B}$ .

Step 1 — NAND se NOT

Dono inputs ko ek saath joodo: $B = A$ set karo. $A ↑ A = \overline{A \cdot A} = \overline{A}$

Yeh step kyun? $A \cdot A = A$ (idempotence), toh $\overline{A \cdot A} = \overline{A}$ . Ab hamare paas inversion aa gayi.

Step 2 — NAND se AND

NAND pehle se $\overline{A B}$ deta hai; hum bas ise Step-1 wale NOT se invert karte hain: $\overline{(A ↑ B)} = (A ↑ B) ↑ (A ↑ B) = \overline{\overline{A B}} = A B$

Yeh step kyun? Double negation cancel hota hai: $\overline{\overline{A B}} = A B$ . Toh AND = NAND ke baad NAND-inverter (2 NANDs).

Step 3 — NAND se OR (De Morgan key hai)

De Morgan: $A + B = \overline{\overline{A} \cdot \overline{B}}$ . Woh right side exactly un dono inverted inputs ka NAND hai: $A + B = \overline{\overline{A} \cdot \overline{B}} = (A ↑ A) ↑ (B ↑ B)$

Yeh step kyun? Har input ko invert karo (Step 1 mein ek NAND each = 2 gates), phir unhe NAND karo (1 gate). OR = 3 NANDs.

Kyunki humne NOT, AND, OR produce kar liye — NAND universal hai. ∎

NOR se sab kuch derive karna (dual version)

Maano $↓$ NOR denote karta hai, toh $A ↓ B = \overline{A + B}$ . Duality ki wajah se har NAND result mein AND↔OR flip ho jaata hai:

Function	NOR se
NOT	$A ↓ A = \overline{A + A} = \overline{A}$
OR	$(A ↓ B) ↓ (A ↓ B) = \overline{\overline{A + B}} = A + B$
AND	$(A ↓ A) ↓ (B ↓ B) = \overline{\overline{A} + \overline{B}} = A B$

Swap kyun hota hai? NOR inputs ko OR-then-invert se group karta hai, isliye uski cheap operation OR hai (2 gates) jabki AND ko 3 gates chahiye — yeh NAND ka mirror image hai.

Figure — Universal gates (NAND - NOR completeness)

Worked examples

Common mistakes

Recall Feynman: ek 12-saal ke bachche ko samjhao

Socho tumhare paas sirf ek tarah ki LEGO brick hai, lekin yeh ek magic brick hai jo kehti hai "NOT both." Itni magic bricks ko snap karke tum koi bhi toy machine bana sakte ho — calculator, game, kuch bhi. Tumhe kabhi alag brick ki zaroorat nahi padegi. Trick yeh hai: magic brick pehle se "no" kehna jaanti hai (invert), aur jab ek baar "no" kehna aa jaye, toh baaki saari bricks (AND, OR, NOT) usi se rebuild kar sakte ho. NAND aur NOR wahi magic bricks hain.

Active-recall flashcards

#flashcards/hardware

Koi gate "universal" kyun kehlaata hai?

Kyunki tum har Boolean function (matlab NOT, AND, OR reproduce karna) sirf usi gate se bana sakte ho.

Kaunse single gates universal hain?

NAND aur NOR.

NAND se NOT kaise banate hain?

Dono inputs ko ek saath joodo:

A ↑ A = \overline{A}

NANDs se AND kaise banate hain, aur kitne?

Inputs ko NAND karo phir result invert karo; 2 NANDs:

(A ↑ B) ↑ (A ↑ B) = A B

NANDs se OR kaise banate hain, aur kitne?

Har input ko invert karo, phir unhe NAND karo; 3 NANDs:

(A ↑ A) ↑ (B ↑ B) = A + B

AND akela universal kyun nahi ho sakta?

AND monotonic hai aur invert nahi kar sakta (NOT produce nahi kar sakta); ek universal gate mein inversion honi chahiye.

OR-from-NAND mein kaunsi Boolean identity central hai?

De Morgan:

A + B = \overline{\overline{A} \cdot \overline{B}}

XOR ke liye kitne NAND gates chahiye?

NOR ke liye AND/OR mein se kaunsa cheaper hai (kam gates)?

OR cheaper hai (2 NORs); AND ko 3 NORs chahiye — NAND ka mirror.

NAND aur NOR ka formula?

\overline{A B}

aur

\overline{A + B}

Connections

Boolean Algebra & Logic Gates
De Morgan's Laws — OR/AND conversions ke peeche ka engine
Truth Tables — har construction verify karne ka tarika
Logic Gate Symbols
Combinational Circuits — jahan universal gates assemble hoti hain (adders, MUX)
CMOS Transistors — kyun NAND/NOR physically banane mein sabse sasti hain
Duality Principle — NAND↔NOR mirror ko explain karta hai