The two rules

Negating a group flips the operator and negates each member:

The pattern is called bubble pushing: moving an inversion bubble from an output to the inputs (or the reverse) while switching AND to OR. It extends to any number of inputs.

Read each row left to right: the orange circles are the inversions, and both sides of the equals sign compute the same y for every input.

• Top row: the bubble leaves the NAND output, lands on both inputs, and the AND body becomes an OR.

• Middle row: the same move on a NOR turns the OR body into an AND.

• Bottom row: a NAND with its inputs tied is an inverter, so na and nb are a′ and b′; the last NAND is the top-row OR with inverted inputs, so y = a | b with three gates.

Everything from NAND

NAND is universal: any Boolean function can be built from NAND alone. Tying both inputs together turns a NAND into an inverter, and the rest follows from De Morgan.

Standard-cell libraries are rich in NAND and NOR gates, so mapping converts AND/OR equations into these forms with De Morgan.

1
2
3
4
5
6
7
8
9
10
11
12

module and_from_nand (input wire a, b, output wire y);
  wire n1;
  nand g1 (n1, a, b);      // ~(a & b)
  nand g2 (y,  n1, n1);    // inverter: ~~(a & b) = a & b
endmodule

module or_from_nand (input wire a, b, output wire y);
  wire na, nb;
  nand g1 (na, a, a);      // inverter: ~a
  nand g2 (nb, b, b);      // inverter: ~b
  nand g3 (y,  na, nb);    // ~(~a & ~b) = a | b   (De Morgan)
endmodule

Active-low signals

In the gate primitives above, terminals are output first: nand g3(y, na, nb) means y = ~(na & nb). Push a bubble through an AND gate by changing it to OR and inverting both inputs: (a·b)′ = a′+b′. Pushing through OR gives the dual rule. Do not invert the output twice when moving between the two forms.

A signal named en_n is asserted when it is 0. Active-low signals appear in almost every interface.

Suppose a block is selected only when two active-low enables are both asserted. The condition “both asserted” is ~en_a_n & ~en_b_n, and De Morgan turns that into a single NOR:

1
2
3
4
5
6
7
8

module select_two_enables (
  input  wire en_a_n,    // active low
  input  wire en_b_n,    // active low
  output wire sel        // active high
);
  // sel = (~en_a_n) & (~en_b_n) = ~(en_a_n | en_b_n)
  assign sel = ~(en_a_n | en_b_n);
endmodule

Related topics

• The identity toolkit

• Verilog operators and types