Related Concepts: 4.01 Digital Systems & Signal Propagation | 3.05 Karnaugh Map (K-Map) Optimization & Don’t Care States | 4.07 Logic Analysis, Switching Circuits & Positive-Negative Logic

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. Two-Level Implementation Geometry (Degenerate vs. Non-Degenerate)

When cascading gates to build multi-level networks, the logical operations performed at each level determine whether the circuit is useful or redundant.

If we analyze all two-level gate combinations using four basic gates (AND, OR, NAND, NOR), there are $4\times 4=16$ possible configurations:

Level 1 Gate	Level 2: AND	Level 2: OR	Level 2: NAND	Level 2: NOR
AND	Degenerate	AND-OR	AND-NAND	AND-NOR
OR	OR-AND	Degenerate	OR-NAND	OR-NOR
NAND	NAND-AND	NAND-OR	NAND-NAND	Degenerate
NOR	NOR-AND	NOR-OR	Degenerate	NOR-NOR

• Degenerate Forms (8 combinations): These are combinations where the second-level gate performs the exact same logical operation as the first-level gates (e.g., AND-AND, OR-OR, NAND-NOR). They are mathematically redundant because the entire two-level circuit simplifies (degenerates) into a single-level gate with multiple inputs.
• Non-Degenerate Forms (8 combinations): These configurations maintain two distinct levels of logic processing. The most important for hardware synthesis are:
  • NAND-NAND: Equivalent to AND-OR (implements Sum-of-Products).
  • NOR-NOR: Equivalent to OR-AND (implements Product-of-Sums).

3.1 Comparison: Degenerate vs. Non-Degenerate Logic Configurations

Feature	Degenerate Logic Configurations	Non-Degenerate Logic Configurations
Logic Levels	Collapses mathematically into a single level of logic.	Maintains two distinct levels of logic processing.
Algebraic Simplification	$F=(AB)(CD)=ABCD$ (simplifies to a single product/sum).	Cannot be simplified to a single-level operator.
Gate Count Reduction	Reduces to a single multi-input gate.	Requires both level-1 and level-2 gates.
Examples (out of 16)	AND-AND, OR-OR, NAND-NOR, NOR-NAND.	AND-OR, OR-AND, NAND-NAND, NOR-NOR.
Hardware Synthesis Value	Redundant. No practical value for multi-level logic design.	Fundamental. NAND-NAND and NOR-NOR are the standard methods for universal implementations.

---

4. Universal Gate Implementation (Bubble-Pushing Algorithm)

Bubble-pushing is a graphical method used to convert a standard AND-OR logic circuit into an all-NAND or all-NOR equivalent circuit without changing the logical function.

4.1 Theoretical Basis: Double Inversion

The mathematical foundation of gate conversion is the double negation rule:

$F=(F^{\prime \prime })=\overline{\overline{F}}$

By applying De Morgan’s theorem, we can convert product terms to sum terms and vice-versa.

4.2 NAND-NAND Conversion (Bubble-Pushing Steps)

To convert a standard two-level AND-OR circuit into a NAND-only circuit:

1. Draw the logic circuit in its standard AND-OR form.
2. Place a bubble (inversion circle) at the output of every first-level AND gate.
3. To compensate for these bubbles, place a bubble at every input of the second-level OR gate.
4. Redraw the bubbled-input OR gate as a NAND gate (since $(\overline{A}+\overline{B})=\overline{A\cdot B}$ by De Morgan’s Law).
5. If any single input goes directly to the second-level gate without passing through a first-level gate, insert a NOT gate (configured as a NAND inverter) on that line to compensate for the added bubble.

AND-OR to NAND-NAND Conversion Flow:
Step 1 (Original):   Inputs ---> [ AND ] ---> Output Gate [ OR ] ---> F
Step 2 (Bubble):     Inputs ---> [ AND ]o ---> o Output Gate [ OR ] ---> F
Step 3 (NAND Gate):  Inputs ---> [ NAND ] ---> [ NAND ] ---> F

---

5. Major Exam Proofs

Major PYQ Proof (PYQ 2015 — 11 marks; 2021 — 08 marks)

Question (verbatim): Show that the circuit in Fig. 3(a) is an Exclusive-OR.

The figure is the standard 5-gate NOR network. Since you cannot see the figure here, learn the node-by-node derivation below — the intermediate expressions $N_1\dots N_5$ let you reconstruct the answer from any equivalent drawing.

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 (PYQ 2015 — 11 marks)

Question (verbatim): Implement the following function using the don’t-care conditions. Assume that both the normal and complement inputs are available. $F=A^{\prime }{B}^{\prime }{C}^{\prime }+A{B}^{\prime }D+A^{\prime }{B}^{\prime }C{D}^{\prime }$, $d=ABC+A{B}^{\prime }{D}^{\prime }$, with no more than two NOR gates.

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! $■$

---

5.1 The 2021 Two-NOR Problem — a different function

PYQ Master Design (PYQ 2021 — 08 marks)

Question (verbatim): Implement the following Boolean function $F$ together with the don’t care conditions $d$, using no more than two NOR gates. Assume that both the normal and complement inputs are available. $F(A,B,C,D)=\sum (2,4,6,10,12)d(A,B,C,D)=\sum (0,8,9,13)$

Do not confuse this with the 2015 problem above — the wording is nearly identical but the function is completely different. The method, however, is exactly the same.

Step 1: Plot and identify the zeros

The 0 cells are everything that is neither a minterm nor a don’t care: $\{1,3,5,7,11,14,15\}$.

       CD
  AB \ 00   01   11   10
    +----+----+----+----+
 00 |  X |  0 |  0 |  1 |
    +----+----+----+----+
 01 |  1 |  0 |  0 |  1 |
    +----+----+----+----+
 11 |  1 |  X |  0 |  0 |
    +----+----+----+----+
 10 |  X |  X |  0 |  1 |
    +----+----+----+----+

Step 2: Group the zeros to obtain $F^{\prime }$

A NOR gate natively produces $(X+Y{)}^{\prime }$, so we simplify the complement and let the final NOR supply the inversion.

1. Octet — the whole $D=1$ half: cells $\{1,3,5,7,9,11,13,15\}$. Cells $m_9$ and $m_{13}$ are don’t cares used here as 0s. $⟹\mathbf{D}$
2. Pair $\{14,15\}$: $AB=11$, $CD=10,11⟹C$ constant. $⟹\mathbf{ABC}$

$F^{\prime }=D+ABC⟹F=(D+ABC{)}^{\prime }$

Step 3: Realise with two NOR gates

• NOR 1 — feed the complemented inputs $A^{\prime }$, $B^{\prime }$, $C^{\prime }$: ${\text{Out}}_1=(A^{\prime }+B^{\prime }+C^{\prime }{)}^{\prime }=ABC$
• NOR 2 — feed $D$ and ${\text{Out}}_1$: $F=(D+ABC{)}^{\prime }■$

Verification: $m_2$ (0010) gives $(0+0{)}^{\prime }=1$ ✓; $m_{14}$ (1110) gives $(0+1{)}^{\prime }=0$ ✓.

The universal recipe for "implement with $N$ NOR gates"

1. Expand the function to a minterm list and plot it, marking don’t cares as $\times$.
2. Group the 0s, not the 1s — this gives $F^{\prime }$ directly, and NOR gates produce complemented outputs.
3. Write $F=(\text{sum of those terms}{)}^{\prime }$.
4. Build inner product terms with a NOR fed by complemented inputs, since $(A^{\prime }+B^{\prime }+C^{\prime }{)}^{\prime }=ABC$ by De Morgan. This is why the question always says “both normal and complement inputs are available.”
5. The final NOR ORs everything together and supplies the outer inversion.

Both the 2015 and 2021 papers collapse to a two-term $F^{\prime }$ precisely so that two gates suffice. If your $F^{\prime }$ has three or more terms, you have mis-grouped — usually by not exploiting the don’t cares as 0s.

---

Past Year Questions (PYQs)

Question (as asked)	Years	Marks	Solved in
Define universal gate. Distinguish between canonical form and standard form of a Boolean function	2021, 2022	10	§Abstract, §1 (forms in 3.03 SOP, POS, Canonical & Standard Forms)
Show that the circuit in Fig. 3(a) / 3(b) is an Exclusive-OR (5-gate NOR network)	2015, 2021	8–11	§5
Implement $F=A^{\prime }{B}^{\prime }{C}^{\prime }+A{B}^{\prime }D+A^{\prime }{B}^{\prime }C{D}^{\prime }$, $d=ABC+A{B}^{\prime }{D}^{\prime }$, with no more than two NOR gates	2015	11	§5
Implement $F=\sum (2,4,6,10,12)$, $d=\sum (0,8,9,13)$, with no more than two NOR gates	2021	8	§5.1
Simplify and implement with two-level NOR gate circuits: (i) $F(w,x,y,z)=\sum (1,2,13,14)$, (ii) $F(x,y,z)=[(x+y)(x^{\prime }+z){]}^{\prime }$	2021	7	§2 B method
Implement the following function with NOR gates: $F=x^{\prime }y{z}^{\prime }+x{y}^{\prime }z$	2024	8	§5.2
Simplify the logic circuit of Fig. 2(c) and construct the simplified circuit using only NAND gates	2018	10	4.07 Logic Analysis, Switching Circuits & Positive-Negative Logic

Pattern to notice: NOR implementation appears in five of the last ten papers, worth 7–11 marks, and always with the same skeleton — simplify, then realise in NOR-only form. The gate-count constraint (“no more than two NOR gates”) is the examiner telling you that the complement $F^{\prime }$ simplifies to exactly two terms. Treat it as a hint, not an obstacle.

The recurring trap: grouping the 1s out of habit. For NOR implementation you group the 0s; for NAND implementation you group the 1s. Getting this backwards produces a correct simplification of the wrong function.

5.2 The 2024 NOR Implementation

Worked Exam Problem (PYQ 2024 — 08 marks)

Question (verbatim): Implement the following function with NOR gates: $F=x^{\prime }y{z}^{\prime }+x{y}^{\prime }z$.

$F=\sum m(2,5)$ over three variables, so $F^{\prime }=\sum m(0,1,3,4,6,7)$.

Grouping the 0s of $F$ (i.e. the 1s of $F^{\prime }$) into three pairs — $\{0,1\}$, $\{3,7\}$, $\{4,6\}$:

$F^{\prime }=x^{\prime }{y}^{\prime }+yz+x{z}^{\prime }$

$F=\overline{x^{\prime }{y}^{\prime }+yz+x{z}^{\prime }}=(x+y)(y^{\prime }+z^{\prime })(x^{\prime }+z)$

This POS form maps straight onto a two-level NOR-NOR circuit:

• Level 1 — three NOR gates producing $(x+y{)}^{\prime }$, $(y^{\prime }+z^{\prime }{)}^{\prime }$, $(x^{\prime }+z{)}^{\prime }$
• Level 2 — one NOR gate combining them, whose inversion restores the product

Total: four NOR gates. Verification: $m_2$ ($x=0,y=1,z=0$) gives $(1)(1)(1)=1$ ✓; $m_7$ gives $(1)(0)(1)=0$ ✓.