Universal Gates: NAND-Only and NOR-Only Logic

Build NOT, AND, OR and XNOR from one kind of gate, and count the gates each one needs.

You Will Be Able To

  • Build NOT, AND and OR from NAND gates and from NOR gates.
  • Turn a sum of products into NAND-NAND and a product of sums into NOR-NOR.
  • Build XNOR from four NOR gates.
  • Count the gates of a one-kind netlist against the known minimum.
Lesson
G2.6
Time
25 min
Runs on
Your browser
Check
5 questions

A test chip has room for one kind of logic cell: a two-input NAND. The block still needs OR, XOR and a majority vote. Three NAND gates make an OR.

OR from Three NAND Gates, One Input Row per StepThe first two gates invert a and b. The third gate is a NAND of the two inverted inputs.
0123a b00011011(aa)' = a'(bb)' = b'(a'b')' = y
Scroll horizontally ↔
  1. Cycle 0

    Both inputs are 0. Both inverters give 1, and the NAND of 1 and 1 is 0.

  2. Cycle 1

    b is 1, so b' is 0. A NAND with a 0 input gives 1.

  3. Cycle 3

    The output column is 0111: the column of OR.

Computed from the three gates and confirmed by the lab below on Icarus.

One Gate Is Enough

A set of gates is complete when it can build every function. AND, OR and NOT together are complete. So a gate that can build those three is complete on its own. NAND and NOR are such universal gates.

From One NAND Gate to Every FunctionArrows show what each step builds from the one before. The last box stands for every truth table.
  • Datapath
  • Structure
CallValueReturnWaiting
From one NAND gate to every functionArrows show what each step builds from the one before. The last box stands for every truth table. datapath NAND the only cell datapath NOT inputs tied: 1 cell datapath AND NAND then NOT: 2cells datapath OR NOT on each input,then NAND: 3 cells datapath Any function a sum of products tie inputsinvert a NANDinvert the inputsproductssum
  1. datapath NANDthe only cell
    • tie inputs → NOT
  2. datapath NOTinputs tied: 1 cell
    • invert a NAND → AND
    • invert the inputs → OR
  3. datapath ANDNAND then NOT: 2 cells
    • products → Any function
  4. datapath ORNOT on each input, then NAND: 3 cells
    • sum → Any function
  5. datapath Any functiona sum of products
  1. NOT

    Tie both inputs of a NAND to a. The output is (aa)' = a'.

    Follow the calls, values and waits
    1. data (aa)' = a': NAND → NOT
  2. AND and OR

    AND is a NAND followed by NOT. OR is a NAND of the two inverted inputs.

    Follow the calls, values and waits
    1. data ab: NOT → AND
    2. data a + b: NOT → OR
  3. Every function

    With AND, OR and NOT you can write any truth table as a sum of products. So NAND alone builds it.

Read the diagram as text
  • NAND: the only cell
  • NOT: inputs tied: 1 cell
  • AND: NAND then NOT: 2 cells
  • OR: NOT on each input, then NAND: 3 cells
  • Any function: a sum of products
  • NAND → NOT: tie inputs
  • NOT → AND: invert a NAND
  • NOT → OR: invert the inputs
  • AND → Any function: products
  • OR → Any function: sum

NOR works the same way with the roles of AND and OR swapped.

FunctionFrom NANDFrom NOR
NOT a(aa)'(a + a)'
a AND b((ab)')' : a NAND, then a NAND used as NOT(a' + b')' : NOR of the two inverted inputs
a OR b(a'b')' : NAND of the two inverted inputs((a + b)')' : a NOR, then a NOR used as NOT

Tie the two inputs of a NAND or a NOR together and it is an inverter.

FunctionFewest NAND2 gatesFewest NOR2 gates
NOT11
AND23
OR32
NAND14
NOR41
XOR45
XNOR54
majority of three66
half adder: sum and carry together55

Found by trying every netlist of two-input gates, smallest first. The inputs are available only in true form.

The table has a pattern. Swap NAND with NOR and AND with OR, and the counts swap too. That is duality again: a NAND circuit for f becomes a NOR circuit for the dual of f.

AND-OR Is NAND-NAND, OR-AND Is NOR-NOR

A sum of products is a level of AND gates feeding one OR gate. Push a pair of bubbles onto every wire between the levels. Every gate becomes a NAND, and the function stays the same.

A product of sums is OR gates feeding one AND gate. The same move makes every gate a NOR.

One Function, Three Drawings
abcf
000
001
010
011
100
101
110
111

Minimum SOP

~a & c | a & b

2 terms · 4 literals

Minimum POS

(a | c) & (~a | b)

2 sum terms · 4 literals

One Function, Three Drawingsg0 · NOTinv_a=1g1 · NANDterm0=1g2 · NANDterm1=1g3 · NANDf=0a=0b=0c=0
a=0 b=0 c=0
g0 · NOTa=0 → inv_a=1
g1 · NANDinv_a=1, c=0 → term0=1
g2 · NANDa=0, b=0 → term1=1
g3 · NANDterm0=1, term1=1 → f=0
Read the connections
GateKindInputsOutput
g0NOTainv_a
g1NANDinv_a, cterm0
g2NANDa, bterm1
g3NANDterm0, term1f

Outputs: f. MUX inputs: d0, d1, select. Latch/flip-flop inputs: data, enable/clock. Unknown values are marked x; high impedance is folded into x in this model.

f = ab + a'c, drawn as NAND-NAND. Switch the style to AND-OR and to NOR-NOR. The truth table never changes.

XNOR from Four NOR Gates

XNOR is 1 when its two inputs are equal. With NOR gates alone it needs four, and no netlist does it with three.

XNOR From Four NOR Gates
XNOR From Four NOR Gatesg1 · NORn1=0g2 · NORn2=1g3 · NORn3=0g4 · NORy=0a=0b=1
a=0 b=1
g1 · NORa=0, b=1 → n1=0
g2 · NORa=0, n1=0 → n2=1
g3 · NORb=1, n1=0 → n3=0
g4 · NORn2=1, n3=0 → y=0
Read the connections
GateKindInputsOutput
g1NORa, bn1
g2NORa, n1n2
g3NORb, n1n3
g4NORn2, n3y

Outputs: y. MUX inputs: d0, d1, select. Latch/flip-flop inputs: data, enable/clock. Unknown values are marked x; high impedance is folded into x in this model.

Gate delay 24. Settled after 24 gate delays from t = 0.

Output values at each gate delay0123456789101112131415161718192021222324yxxx1111110000000111111110
Scroll horizontally ↔
Every computed frame
Timey
0x
1x
2x
31
41
51
61
71
81
90
100
110
120
130
140
150
161
171
181
191
201
211
221
231
240

  1. Step 4 · Both inputs 0. n1 = (a + b)' is 1. Both middle gates see a 1, so n2 and n3 are 0, and y is 1: the inputs are equal.
  2. Step 12 · a rises. n1 falls to 0. Now n2 = (a + n1)' is 0 and n3 = (b + n1)' is 1, so y falls to 0.
  3. Step 20 · b rises too. Both inputs are 1. n1, n2 and n3 are all 0, so y is 1 again.
  4. Step 28 · a falls. Now only b is 1. n2 becomes 1 and y falls to 0.

Every gate takes one gate delay. Press Next to step one delay at a time, or click a pin.

Read the middle gates as products. n2 = a'b and n3 = ab', so y = (a'b + ab')', the complement of XOR.

Asked in interviews
  1. Why are NAND and NOR called universal gates?

    Each one alone can build NOT, AND and OR, and those three build every function. Tie both inputs together for NOT, then add bubbles for AND and OR.

  2. How many NAND gates does an XOR need?

    Four. An exhaustive search over every netlist of two-input NAND gates shows that three are not enough. XNOR needs five: an XOR plus an inverter is five, and the search finds nothing smaller.

  3. Why do standard-cell libraries favour NAND over NOR?

    In CMOS a NAND has its NMOS in series and its PMOS in parallel. A NOR stacks the slower PMOS in series, so it needs wider transistors for the same speed. Lesson G9.2 measures it.

Try It

The cell library in cells.sv has six cells. Each one adds itself to a counter in the bench, so the bench can report what a netlist uses.

AND takes two NAND cells and OR takes three. The bench prints both columns and the count, 5.

Change or_n to the wrong guess: NAND2 u1 (t, a, b); followed by NAND2 u2 (y, t, t);. The OR column becomes 0001.

Build NOR from NAND cells in a third module. The exhaustive search says four cells is the fewest. The bench counts yours.

RUNIcarus Verilog · in your browser
Edit the code, then run it
Expected: AND from NAND2: 0001 OR from NAND2: 0111 NAND2 cells: 5, other cells: 0
Read included file: cells.sv
// cells.sv: the cell library (read-only). Every cell takes 2 time units.
// Ports are (y, inputs...): output first. Each cell adds 1 to its own counter in the bench.
// While the bench sets poison to 1, every cell output is x.
module INV   (output wire y, input wire a);               wire g; not #2 (g, a);           assign y = tb.poison ? 1'bx : g; initial tb.n_inv++; always @(tb.recount) tb.n_inv++; endmodule
module NAND2 (output wire y, input wire a, b);            wire g; nand #2 (g, a, b);       assign y = tb.poison ? 1'bx : g; initial tb.n_nand2++; always @(tb.recount) tb.n_nand2++; endmodule
module NOR2  (output wire y, input wire a, b);            wire g; nor #2 (g, a, b);        assign y = tb.poison ? 1'bx : g; initial tb.n_nor2++; always @(tb.recount) tb.n_nor2++; endmodule
module NAND3 (output wire y, input wire a, b, c);         wire g; nand #2 (g, a, b, c);    assign y = tb.poison ? 1'bx : g; initial tb.n_nand3++; always @(tb.recount) tb.n_nand3++; endmodule
module NOR3  (output wire y, input wire a, b, c);         wire g; nor #2 (g, a, b, c);     assign y = tb.poison ? 1'bx : g; initial tb.n_nor3++; always @(tb.recount) tb.n_nor3++; endmodule
module XOR2  (output wire y, input wire a, b);            wire g; xor #2 (g, a, b);        assign y = tb.poison ? 1'bx : g; initial tb.n_xor2++; always @(tb.recount) tb.n_xor2++; endmodule
Read included file: tb.sv
// tb.sv: the bench (read-only). It prints the output columns and counts the cells.
module tb;
  int n_inv, n_nand2, n_nor2, n_nand3, n_nor3, n_xor2;   // the cells add themselves here
  logic poison = 0;                                // 1 forces every cell output to x
  event recount;                                   // makes every cell add itself again
  logic a, b;
  wire  y_and, y_or;
  string col_and = "", col_or = "";

  and_n u_and (.a(a), .b(b), .y(y_and));
  or_n  u_or  (.a(a), .b(b), .y(y_or));

  initial begin
    for (int i = 0; i < 4; i++) begin
      {a, b} = i[1:0];
      #10;                                  // five cell delays: enough to settle
      col_and = {col_and, y_and ? "1" : "0"};
      col_or  = {col_or,  y_or  ? "1" : "0"};
    end
    $display("AND from NAND2: %s", col_and);
    $display("OR  from NAND2: %s", col_or);
    $display("NAND2 cells: %0d, other cells: %0d", n_nand2, n_inv + n_nor2 + n_nand3 + n_nor3 + n_xor2);
  end
endmodule

Check Yourself

ConceptHow do you make an inverter from a two-input NAND gate?
ConceptA sum of products is drawn with two levels. Which one-kind form has the same function, gate for gate?
ConceptWhat is the fewest number of two-input NOR gates that builds AND?
ConceptEvery NAND gate in a circuit for f is replaced by a NOR gate. What does the new circuit compute?
Predict the outputFour NAND primitives are wired as shown. The program prints y for ab = 00, 01, 10 and 11. Predict the exact line.
module tb;
  logic a, b;
  wire  na, nb, t, y;
  nand g1 (na, a, a);
  nand g2 (nb, b, b);
  nand g3 (t, na, nb);      // (a'b')' = a + b
  nand g4 (y, t, t);        // an inverter
  initial begin
    for (int i = 0; i < 4; i++) begin
      {a, b} = i[1:0];
      #1 $write("%b", y);
    end
    $display("");
  end
endmodule

Common Mistakes

Wrong Map AND-OR to NOR-NOR, or OR-AND to NAND-NAND.

Bubble pushing pairs AND-OR with NAND-NAND, and OR-AND with NOR-NOR. The other pairing gives the dual function.

Fix A sum of products becomes NAND-NAND. A product of sums becomes NOR-NOR.

Wrong Forget the inverter for a single input that enters the second level.

In NAND-NAND, a lone literal x feeds the output NAND. That gate inverts it, so it needs x' at its input.

Fix Feed a single literal through a NAND with its inputs tied, or use its complement directly.

Wrong Build OR as NAND followed by an inverter.

NAND then NOT is AND. OR needs the inverters on the inputs: (a'b')' = a + b.

Fix Invert each input with a NAND, then NAND the two results: three gates.

Before
NAND2 u1 (t, a, b);
NAND2 u2 (y, t, t);     // AND: 0001
After
NAND2 u1 (na, a, a);
NAND2 u2 (nb, b, b);
NAND2 u3 (y, na, nb);   // OR: 0111

Wrong Count only the gates of the textbook drawing.

An inverter made from a NAND is one more NAND. Every gate in the netlist counts.

Fix Count every instance. The exhaustive search gives the minimum to compare with.

Remember

  • NAND alone and NOR alone are each complete. Tie the inputs together for NOT.
  • AND-OR becomes NAND-NAND, and OR-AND becomes NOR-NOR, by bubble pushing.
  • Fewest gates: OR from NAND 3, AND from NOR 3, XOR from NAND 4, XNOR from NOR 4.
  • Swapping NAND with NOR gives the dual function, and dual circuits have the same size.

Practice

Report a problem with this page