Universal Gates for GATE: Realizing Any Function with Only NAND or Only NOR, and Counting the Minimum Gates

Most students can write a NAND truth table but pause when the question says "NAND gates only" or asks for the minimum number of 2-input gates. The conversion is not a guessing exercise. Once the Boolean expression is in the right form, bubble cancellation and a careful count do the work.

Why NAND and NOR are universal gates

A gate set is functionally complete when it can implement every Boolean function. Since any Boolean expression can be built from NOT, AND and OR, a gate that can construct all three is universal.

Using only 2-input NAND gates:

• NOT: A' = NAND(A,A). The two inputs are tied together, so this costs 1 NAND.

• AND: First form (AB)', then invert it: AB = NAND(NAND(A,B), NAND(A,B)). This costs 2 NANDs.

• OR: By De Morgan, A + B = (A'B')'. Therefore A + B = NAND(NAND(A,A), NAND(B,B)). This costs 3 NANDs.

NOR works by the dual construction. NOR(A,A) gives A'. An OR needs one NOR followed by a NOR inverter, so it costs 2. An AND is (A' + B')', so it needs two input inverters and a final NOR, costing 3.

Because NAND alone and NOR alone can each construct NOT, AND and OR, either one is a universal gate set.

The bubble-pushing recipe for two-level circuits

Minimise the expression before you draw anything, with Boolean algebra and K-map minimization, because every redundant product term you leave in becomes a physical gate you then have to count. Then take the minimised sum of products as a two-level circuit: each product term is formed by an AND at the first level, and the terms are combined by an OR at the second level.

Replace the first-level AND gates with NAND gates. Their outputs are now complemented product terms. Replace the final OR with a NAND. Its complemented inputs and complemented output apply De Morgan's law, so the paired inversion bubbles cancel. The result is the same function in NAND-NAND form.

The dual rule is just as useful:

• SOP, or AND-OR, maps naturally to NAND-NAND.

• POS, or OR-AND, maps naturally to NOR-NOR.

If an SOP has k product terms, each term fits one available NAND gate, and all required literal complements already exist, the count is k first-level NANDs plus 1 output NAND. Total: k + 1.

Those assumptions matter. If only uncomplemented inputs are available, each required complement costs another NAND. If a product has more literals than the allowed gate fan-in, a 2-input implementation needs decomposition and the simple k + 1 count no longer applies directly.

Worked NAND example: F = AB + CD

There are two product terms, so k = 2. Apply double negation and De Morgan's law:

F = AB + CD

F = ((AB + CD)')'

F = ((AB)' · (CD)')'

Therefore:

F = NAND(NAND(A,B), NAND(C,D))

Walk through the gates:

1. G1 = NAND(A,B) = (AB)'

2. G2 = NAND(C,D) = (CD)'

3. G3 = NAND(G1,G2) = ((AB)' · (CD)')' = AB + CD

The total is 3 two-input NAND gates, matching k + 1 = 2 + 1 = 3. A direct truth check confirms it. If either product AB or CD is 1, its first-level NAND output is 0, making the final NAND output 1. If both products are 0, both intermediate outputs are 1 and the final output is 0.

Now take the POS dual, F = (A+B)(C+D):

1. G1 = NOR(A,B) = (A+B)'

2. G2 = NOR(C,D) = (C+D)'

3. G3 = NOR(G1,G2) = ((A+B)' + (C+D)')' = (A+B)(C+D)

This uses 3 two-input NOR gates.

XOR, XNOR and the counts worth knowing

Gate type matters here, so do not memorise one number for both NAND and NOR.

These counts assume 2-input gates, uncomplemented inputs A and B, and reusable intermediate outputs.

The 4-NAND XOR is concrete, not a magic number:

P = NAND(A,B)
Q = NAND(A,P)
R = NAND(B,P)
XOR = NAND(Q,R)

Check the middle case A=0, B=1. Then P=1, Q=1, R=0, so the final output is 1. For equal inputs, the final output is 0. To obtain XNOR with NAND only, invert this XOR output using one more NAND with tied inputs. Total: 5.

The XOR figure of four is a genuine minimum, not just the size of the construction above. The output NAND has to give 0 when A=B=0 and again when A=B=1, so both of its inputs must be 1 at those two points. Neither A nor B qualifies, since each is 0 at A=B=0. The only signals one NAND can build from A and B are A', B' and (AB)', and every one of those is 0 at A=B=1. That leaves only the second gate, and feeding one signal into both inputs merely inverts it, so the second gate would itself have to be XNOR, which no single NAND over A, B and one earlier signal produces. Three gates cannot reach XOR.

The NOR dual produces XNOR in 4 gates:

P = NOR(A,B)
Q = NOR(A,P)
R = NOR(B,P)
XNOR = NOR(Q,R)

For A=B=0, P=1, both Q and R are 0, and the result is 1. For unequal inputs it is 0, and for A=B=1 it is again 1. One more NOR inverter converts it to XOR, giving 5 NOR gates.

Traps that eat the marks

• Do not count a NAND as an AND. A NAND output must be inverted when the target needs the uncomplemented product.

• Match form to gate type. NAND-NAND is natural for SOP; NOR-NOR is natural for POS.

• Check whether complemented literals are supplied. Generating A' from A costs one gate.

• Respect the stated fan-in. A drawn 3-input gate is not one 2-input gate.

• Count shared intermediate signals once. In the XOR construction, P feeds two gates but is generated only once.

• Do not say XNOR also needs 4 NAND gates. With only A, B and 2-input NANDs, XOR needs 4 and XNOR needs 5. The 4-gate result for XNOR belongs to NOR.

How GATE tests universal gates

Common questions ask for the minimum number of 2-input NAND gates, the function produced by an all-NAND diagram, or which gate sets are functionally complete. Work in this order: simplify the function, choose SOP or POS, match NAND-NAND or NOR-NOR, expose any missing literal complements, then count with the fan-in restriction. Reading an all-NAND diagram back into an expression is a recognition skill rather than a derivation, so drill it on mixed sets such as these Digital Electronics combinational-circuit MCQs.

A different IIT organises GATE each cycle and publishes that year's Digital Electronics syllabus in the official GATE brochure. Read the current brochure on the organising institute's GATE portal rather than an older PDF.

The short version and next step

NAND and NOR are universal because each can build NOT, AND and OR. SOP maps cleanly to NAND-NAND and POS to NOR-NOR. The k + 1 shortcut is valid only when each term fits one gate and its literals are already available.

Practise until you can read an all-NAND diagram without redrawing it as AND-OR first. The full route through Digital Electronics sits inside GATE Guidance by Sanchit Sir, and the GATE category connects it to the remaining subjects. KnowledgeGate's question bank carries about 1,500 Digital Electronics questions, and working through the realization and gate-count ones is what turns this method into recall.