Logic Gates & Gate-Level Design
Complete Guide for GATE CS — AND/OR/NOT/NAND/NOR/XOR/XNOR, Universal Gates, Gate-Level Implementation & Timing
Last Updated: April 2026
📌 Key Takeaways
- Basic gates: AND (output 1 only if ALL inputs 1), OR (output 1 if ANY input 1), NOT (inverts input). These form a complete set.
- NAND = NOT-AND; NOR = NOT-OR. Both are universal gates — any Boolean function can be built using only NAND gates (or only NOR gates).
- XOR: Output 1 when inputs DIFFER. A⊕B=A’B+AB’. Key: odd number of 1-inputs → output 1. Used for parity, adders, comparators.
- XNOR: Output 1 when inputs are SAME. Equality checker. (A⊕B)’.
- NAND-only implementation: Invert AND-OR (SOP) expression — each AND gate becomes NAND, replace final OR with NAND.
- NOR-only implementation: Invert OR-AND (POS) expression — each OR gate becomes NOR, replace final AND with NOR.
- Critical path determines circuit delay — minimise gate levels for speed; 2-level (SOP/POS) is fastest but may need more gates.
1. Basic Logic Gates — Truth Tables & Expressions
| Gate | Symbol | Expression | Output Rule | Truth Table (A,B→Y) |
|---|---|---|---|---|
| AND | D-shape with flat input | Y = A·B (or AB) | 1 only if ALL inputs are 1 | 00→0, 01→0, 10→0, 11→1 |
| OR | Curved D-shape | Y = A+B | 1 if ANY input is 1 | 00→0, 01→1, 10→1, 11→1 |
| NOT (Inverter) | Triangle with bubble | Y = A’ | Inverts input | 0→1, 1→0 |
| BUFFER | Triangle, no bubble | Y = A | Passes input unchanged (used for driving) | 0→0, 1→1 |
2. Derived Gates — NAND, NOR, XOR, XNOR
| Gate | Expression | Output Rule | Truth Table (A,B→Y) | Key Property |
|---|---|---|---|---|
| NAND | Y = (A·B)’ | 0 only if ALL inputs are 1 | 00→1, 01→1, 10→1, 11→0 | Universal gate |
| NOR | Y = (A+B)’ | 1 only if ALL inputs are 0 | 00→1, 01→0, 10→0, 11→0 | Universal gate |
| XOR | Y = A⊕B = A’B+AB’ | 1 if inputs are DIFFERENT (odd #1s) | 00→0, 01→1, 10→1, 11→0 | Parity, adder sum |
| XNOR | Y = (A⊕B)’ = AB+A’B’ | 1 if inputs are SAME | 00→1, 01→0, 10→0, 11→1 | Equality checker |
XOR Extended Properties
A ⊕ 0 = A | A ⊕ 1 = A’ | A ⊕ A = 0 | A ⊕ A’ = 1
XOR is commutative and associative: A⊕B⊕C = (A⊕B)⊕C
n-input XOR: Output = 1 iff ODD number of inputs are 1 (parity generator)
n-bit parity: Even parity = XOR of all bits = 0 if even count of 1s
3. Universal Gates — NAND and NOR
A gate is universal if any Boolean function can be implemented using only that gate type. Both NAND and NOR are universal because they can each implement NOT, AND, and OR — a functionally complete set.
Implementing Basic Gates Using Only NAND
NOT A: NAND(A, A) = (A·A)’ = A’
AND(A,B): NAND(NAND(A,B), NAND(A,B)) = ((AB)’)’ = AB [3 NAND gates total: 1 for NAND, 2 for inverting]
Shortcut: NOT(NAND(A,B)) → tie NAND output to another NAND’s both inputs
OR(A,B): NAND(NAND(A,A), NAND(B,B)) = NAND(A’, B’) = (A’·B’)’ = A+B [De Morgan]
Implementing Basic Gates Using Only NOR
NOT A: NOR(A, A) = (A+A)’ = A’
OR(A,B): NOR(NOR(A,B), NOR(A,B)) = ((A+B)’)’ = A+B
AND(A,B): NOR(NOR(A,A), NOR(B,B)) = NOR(A’, B’) = (A’+B’)’ = AB [De Morgan]
3.1 NAND-NAND vs AND-OR-INVERT
A two-level SOP implementation (AND-OR) can be directly converted to NAND-NAND with the same number of gates:
- Replace each AND gate with a NAND gate
- Replace the OR gate with a NAND gate
- The double inversions (from two NAND levels) cancel: (AB)’·(CD)’) = (AB)” + (CD)” = AB+CD ✓ — Wait, use De Morgan correctly. Let me re-state:
NAND(NAND(A,B), NAND(C,D)) = ((AB)’)·((CD)’)’ = (AB)+(CD) by De Morgan. ✓ Same function as AND-OR implementation.
4. Implementing Boolean Functions with Gates
4.1 SOP → AND-OR → NAND-NAND
Steps: (1) Minimize using K-map → obtain SOP. (2) Draw AND gates for each product term. (3) Connect all AND outputs to a single OR gate. (4) For NAND-NAND: replace AND gates + OR gate with NAND gates at both levels.
4.2 POS → OR-AND → NOR-NOR
Steps: (1) Minimize → obtain POS. (2) Draw OR gates for each sum term. (3) Connect to a final AND gate. (4) For NOR-NOR: replace OR gates + AND gate with NOR gates.
4.3 Gate Count for Common Functions
| Function | AND-OR Gates | NAND-only Gates | Levels |
|---|---|---|---|
| F = AB + CD | 2 AND + 1 OR = 3 | 3 NAND | 2 |
| F = A (single variable) | 0 gates (wire) | 0 | 0 |
| Full adder sum bit | 4 XOR + AND/OR | ~9 NAND | ~4 |
| 2-to-1 MUX | 2 AND + 1 OR + 1 NOT = 4 | 4 NAND | 2 |
5. Propagation Delay, Fan-In & Fan-Out
Propagation Delay
tpd = propagation delay of a single gate
Critical path delay = sum of gate delays along the longest input-to-output path
Maximum frequency = 1 / (critical path delay)
2-level SOP/POS implementations have delay = 2 × tpd (plus NOT for complements), regardless of the number of variables. Multi-level implementations may reduce gate count but increase delay.
| Parameter | Definition | Effect of Violation |
|---|---|---|
| Fan-in | Maximum number of inputs a gate can have | Too many inputs → increased delay, may not be logically possible |
| Fan-out | Maximum number of gate inputs a single output can drive | Exceeding fan-out → output voltage degrades below valid logic level |
| Noise margin | Voltage difference between output level and input threshold | Low noise margin → glitches and incorrect logic |
6. Worked Examples (GATE CS Level)
Example 1 — Gate-Level Expressions
Problem: (a) Express F = (A+B)’C + AB’ using only NAND gates, specifying the minimal gate circuit. (b) A 4-input NAND gate has output Y = (ABCD)’. What is Y when A=1,B=0,C=1,D=1?
(a) Converting F = (A+B)’C + AB’ to NAND:
First simplify: (A+B)’ = A’B’ (De Morgan). So F = A’B’C + AB’.
F = B'(A’C + A) = B'(A+C) using absorption (A’C+A = A+C).
This is now 2-level: F = B'(A+C). Convert to NAND: F = NAND(NAND(B,B), NAND(A,C)) — but we need AND inside OR:
Actually: F = (A+C)B’. AND-OR: (A OR C) AND (NOT B). NAND form:
F = NAND(NAND(A,C), … ) — better to use: F = ((A+C)’)’ · B” = NAND(NOR(A,C), B) — uses NOR.
Simplified: F = B'(A+C). NAND implementation requires NOT(B), OR(A,C), AND. Total: ~4 NAND gates: NOT(B)=NAND(B,B); NAND(A,A) and NAND(C,C) to get A’ and C’; then NAND(A’,C’)=A+C; finally NAND(NAND(B,B), NAND(NAND(A,A),NAND(C,C))) = NAND(B’, A+C) = (B'(A+C))’ — one more NOT needed.
(b) 4-input NAND(1,0,1,1):
NAND outputs 0 only if ALL inputs are 1. Since B=0, NOT all inputs are 1.
Y = (1·0·1·1)’ = (0)’ = 1
Example 2 — NAND-Only Implementation
Problem: Implement F = AB + A’C using only NAND gates. How many NAND gates are needed? What is the gate delay if each gate has delay t?
F = AB + A’C is in SOP form. Convert to NAND-NAND:
Step 1: F = ((AB)’·(A’C)’)’ — double complement
Step 2: First level NAND: NAND(A,B) and NAND(A’,C)
Step 3: Second level NAND: NAND(NAND(A,B), NAND(A’,C))
Step 4: Need A’ — requires NAND(A,A)
Gates needed: NAND(A,A) for A’ (1), NAND(A,B) (1), NAND(A’,C) (1), final NAND (1) = 4 NAND gates
Critical path: A → NAND(A,A) → NAND(A’,C) → NAND(out) = 3t delay
Note: the A→NAND(A,B)→NAND(out) path = 2t, so critical path is 3t
Example 3 — Circuit Analysis & Timing
Problem: A combinational circuit has the following structure: inputs A, B, C. Layer 1: G1 = NAND(A,B), G2 = NOT(C). Layer 2: G3 = AND(G1, G2). Layer 3: G4 = OR(G3, B). Find the Boolean expression for G4 and the critical path delay if AND=OR=1ns, NAND=0.8ns, NOT=0.5ns.
G1 = (AB)’; G2 = C’
G3 = G1·G2 = (AB)’·C’
G4 = G3 + B = (AB)’C’ + B
Simplify: (AB)’C’ + B = (A’+B’)C’ + B = A’C’ + B’C’ + B = A’C’ + B’C’ + B
= A’C’ + B(1 + B’C’… wait: B’C’ + B = B + B’C’ = (B+B’)(B+C’) = B+C’ (absorption variant)
G4 = A’C’ + B + C’ = C'(A’+1) + B = C’ + B
G4 = B + C’
Critical path (longest): A→G1(NAND,0.8ns)→G3(AND,1ns)→G4(OR,1ns) = 2.8 ns
Path B→G4 = 1ns; Path C→G2(0.5ns)→G3(1ns)→G4(1ns) = 2.5ns; Path A→G1→G3→G4 = 2.8ns (critical)
7. 5 Common Mistakes in Logic Gates
Mistake 1 — Thinking NAND and NOR Are NOT Associative
What happens: Students treat NAND(A,B,C) as NAND(NAND(A,B),C), getting wrong results.
Root cause: NAND and NOR are NOT associative. NAND(NAND(A,B),C) ≠ NAND(A,B,C). NAND(A,B,C) = (ABC)’; NAND(NAND(A,B),C) = ((AB)’)·C)’ = (AB) + C’ ≠ (ABC)’.
Correct approach: Always treat NAND/NOR as a single multi-input gate, not as cascaded 2-input gates.
Mistake 2 — Confusing XOR with OR
What happens: Students write “XOR outputs 1 if any input is 1” — same as OR. Then get XOR(1,1)=1 wrong (it should be 0).
Root cause: XOR = Exclusive OR — it’s 1 ONLY when inputs differ. Both 1 → output 0 (they are the same).
Correct approach: XOR = “different inputs.” For n-input XOR: output = 1 iff ODD number of inputs are 1. XOR(1,1,1) = 1; XOR(1,1,0) = 0.
Mistake 3 — Wrong Gate Count in NAND-NAND Conversion
What happens: For SOP with complemented variables like A’, students forget the inverter (NAND(A,A)) needed to generate A’.
Root cause: The NAND-NAND conversion only replaces AND/OR gates. Complemented inputs require additional NOT (= NAND with tied inputs) gates that are not part of the 2-level structure.
Correct approach: Count all NAND gates including those needed to generate complemented inputs from uncomplemented ones.
Mistake 4 — Miscalculating Critical Path
What happens: Students add delays of ALL gates instead of finding the longest path.
Root cause: Critical path is the LONGEST path from any input to any output, not the sum of all gate delays.
Correct approach: Trace all possible input-to-output paths, sum delays along each path, take the maximum.
Mistake 5 — Applying De Morgan Incorrectly for Multi-Input NAND/NOR
What happens: For 3-input NAND(A,B,C), students write output = A’·B’·C’ instead of A’+B’+C’.
Root cause: Extending De Morgan’s theorem to multiple inputs requires De Morgan applied to the entire AND/OR, not to each input separately.
Correct approach: NAND(A,B,C) = (A·B·C)’ = A’+B’+C’ (De Morgan: complement of product = sum of complements). NOR(A,B,C) = (A+B+C)’ = A’·B’·C’.
8. Frequently Asked Questions
Q1. Why are NAND and NOR called universal gates?
NAND and NOR are “universal” because any Boolean function can be implemented using exclusively one or the other. This works because NOT, AND, and OR form a functionally complete set — you can build any function with just these three. NAND can implement all three: NOT(A)=NAND(A,A); AND(A,B)=NOT(NAND(A,B)); OR(A,B)=NAND(NOT(A),NOT(B)). Similarly for NOR. Practical significance: IC manufacturers can produce a single chip type (e.g., 7400 quad NAND) and designers can build any circuit from it. Also, NAND/NOR require fewer transistors than AND/OR in CMOS technology.
Q2. What is the difference between XOR and XNOR gates?
XOR (Exclusive OR): output = 1 when inputs are DIFFERENT. A⊕B = A’B+AB’. A 2-input XOR outputs 1 for 01 and 10, outputs 0 for 00 and 11. Extended: n-input XOR = 1 iff ODD number of inputs are 1 — makes it a natural parity generator. XNOR: complement of XOR. Output = 1 when inputs are the SAME. Natural equality checker: A XNOR B = 1 means A = B. For n-bit equality: AND of XNORs for each bit position tells if two numbers are equal.
Q3. What is propagation delay in logic gates?
Propagation delay (tpd) is the time between a change at the input and the corresponding change at the output. There are two values: tpHL (delay for output going from High to Low) and tpLH (output Low to High). The specified tpd is usually the maximum of both. For a multi-gate circuit, the total delay is the sum of delays along the critical path — the longest input-to-output signal path. Minimizing the number of gate levels (2-level SOP/POS) minimizes delay but may increase the gate count and power consumption.
Q4. What are fan-in and fan-out in digital logic?
Fan-in is the maximum number of inputs a gate supports — beyond this limit, the gate’s internal design doesn’t account for more connections. Fan-out is the maximum number of subsequent gate inputs a single gate output can drive reliably. This is limited by the drive current capacity of the output: each connected input draws (or supplies) a certain current, and the driving gate can only supply a finite total current while maintaining valid logic levels. In standard TTL: fan-out ≈ 10. In CMOS: much higher because CMOS inputs are capacitive, not resistive — fan-out is limited by speed (capacitance), not DC current.