Related Concepts: 01 Digital Systems & Signal Propagation | 03 BJT as NOT Gate & Inverter Operation | 05 TTL Logic Families & Open Collector Bus Systems

4.02 Universal Logic Gates & 2-Level Implementations

What is a Universal Logic Gate?

A logic gate is classified as Universal if any arbitrary Boolean function or digital circuit can be constructed using only that single gate type, without requiring any other gate types.

Both NAND and NOR gates are Universal Gates.

graph TD
    subgraph 4-NAND Gate XOR Network
        InA[Input A] & InB[Input B] --> NAND1[NAND 1: Output N1 = AB']
        InA & NAND1 --> NAND2[NAND 2: Output N2 = A • N1 ']
        InB & NAND1 --> NAND3[NAND 3: Output N3 = B • N1 ']
        NAND2 & NAND3 --> NAND4[NAND 4: Output F = A ⊕ B]
    end

---

1. NAND & NOR Gate Realizations of Basic Gates

Target Gate	NAND Gates Required	NOR Gates Required
NOT	1 (inputs tied: $\overline{A\cdot A}=A^{\prime }$)	1 (inputs tied: $\overline{A+A}=A^{\prime }$)
AND	2 ($\overline{\overline{AB}}=AB$)	3 ($\overline{A^{\prime }+B^{\prime }}=AB$)
OR	3 ($\overline{A^{\prime }\cdot B^{\prime }}=A+B$)	2 ($\overline{\overline{A+B}}=A+B$)
XOR	4 (cascaded 4-NAND network)	5 (4-NOR XNOR + 1 NOR Inverter)
XNOR	5 (4-NAND XOR + 1 NAND Inverter)	4 (cascaded 4-NOR network)

---

2. Two-Level Gate Implementation Rules

A. Two-Level NAND-NAND Implementation (SOP)

• Rule: Any function in Sum of Products (SOP) form can be directly implemented using a 2-level NAND-NAND circuit.
• Proof: $F=AB+CD⟹F=((AB+CD{)}^{\prime }{)}^{\prime }=((AB{)}^{\prime }\cdot (CD{)}^{\prime }{)}^{\prime }$. This represents a final NAND gate taking inputs from two level-1 NAND gates.
• Direct Literals Rule: If a single literal (e.g., $E$) feeds directly into the second-level OR/NAND gate, it must be complemented ($E^{\prime }$) to cancel out the output gate’s inversion.

B. Two-Level NOR-NOR Implementation (POS)

• Rule: Any function in Product of Sums (POS) form can be directly implemented using a 2-level NOR-NOR circuit.
• Proof: $F=(A+B)(C+D)⟹F=(((A+B)(C+D){)}^{\prime }{)}^{\prime }=((A+B{)}^{\prime }+(C+D{)}^{\prime }{)}^{\prime }$. This represents a final NOR gate taking inputs from two level-1 NOR gates.

---

3. Major Exam Proofs

Major PYQ Proof: 5-Gate NOR XOR Circuit (2015, 2021 - 8 Marks)

Question: Show mathematically that a 5-gate NOR network acts as an Exclusive-OR (XOR) gate.

Proof Solution:

1. $N_1=\overline{A+B}$
2. $N_2=\overline{A+N_1}=\overline{A+(A+B{)}^{\prime }}=\overline{A+A^{\prime }{B}^{\prime }}=A^{\prime }\cdot (A+B)=A^{\prime }B$
3. $N_3=\overline{B+N_1}=\overline{B+(A+B{)}^{\prime }}=\overline{B+A^{\prime }{B}^{\prime }}=B^{\prime }\cdot (A+B)=A{B}^{\prime }$
4. $N_4=\overline{N_2+N_3}=\overline{A^{\prime }B+A{B}^{\prime }}=A\odot B\text{(XNOR)}$
5. $N_5=\overline{N_4}=\overline{A\odot B}=\mathbf{A}\oplus \mathbf{B}\text{(XOR)}■$

---

PYQ Master Design (2015): The 2-NOR Gate Limit Puzzle

Question: Implement $F=A^{\prime }{B}^{\prime }{C}^{\prime }+A{B}^{\prime }D+A^{\prime }{B}^{\prime }C{D}^{\prime }$, with don’t cares $d=ABC+A{B}^{\prime }{D}^{\prime }$, using no more than Two NOR gates. Assume normal and complement inputs are available.

Step 1: Expand into Minterms We translate the raw algebra into decimal minterms to safely plot a K-map:

• $A^{\prime }{B}^{\prime }{C}^{\prime }\to 000X\to 0,1$
• $A{B}^{\prime }D\to 10X1\to 9,11$
• $A^{\prime }{B}^{\prime }C{D}^{\prime }\to 0010\to 2$
• Minterms = $\Sigma m(0,1,2,9,11)$
• $ABC\to 111X\to 14,15$
• $A{B}^{\prime }{D}^{\prime }\to 10X0\to 8,10$
• Don’t Cares = $\Sigma d(8,10,14,15)$

Step 2: Group the Zeros ($F^{\prime }$) for NOR Logic Because a NOR gate generates inverted OR logic $(X+Y{)}^{\prime }$, we simplify for $F^{\prime }$ (the zeros on the K-map). The zeros are remaining cells: $3,4,5,6,7,12,13$.

• Grouping $(4,5,6,7)$ with $(12,13,14d,15d)$ creates an 8-cell block: $B$
• Grouping $(3)$ with $(7)$ creates a pair: $A^{\prime }CD$
• Simplified complement: $F^{\prime }=B+A^{\prime }CD$

Step 3: The 2-NOR Implementation Double complementing gives $F$: $F=(B+A^{\prime }CD{)}^{\prime }$

• NOR Gate 1: Feed $A,C^{\prime },$ and $D^{\prime }$ into the first NOR gate: ${\text{Output}}_1=(A+C^{\prime }+D^{\prime }{)}^{\prime }={\mathbf{A}}^{\prime }\mathbf{CD}$
• NOR Gate 2: Feed $B$ and ${\text{Output}}_1$ into the second NOR gate: ${\text{Output}}_2=(B+{\text{Output}}_1{)}^{\prime }=(\mathbf{B}+{\mathbf{A}}^{\prime }\mathbf{CD}{)}^{\prime }=\mathbf{F}$

Proof Complete: Implemented using exactly two NOR gates! $■$

---

Past Year Questions (PYQs)

• [PYQ 2021]: Prove NOR is a universal gate with basic gate implementations. (08 Marks)
• [PYQ 2015, 2021]: 5-gate NOR XOR circuit proof. (08 Marks)
• [PYQ 2015, 2021]: Implement $F=A^{\prime }{B}^{\prime }{C}^{\prime }+A{B}^{\prime }D+A^{\prime }{B}^{\prime }C{D}^{\prime }$ with no more than two NOR gates. (12 Marks)