De Morgan, Bubble Pushing and Mixed Logic

Use De Morgan's theorems to move inversions through a circuit, and name active-low signals so a schematic reads as it works.

You Will Be Able To

  • Apply De Morgan's theorems to two and to n variables.
  • Complement a whole expression in one pass.
  • Push bubbles through a gate circuit without changing its function.
  • Name active-low signals and draw them bubble to bubble.
Lesson
G2.5
Time
25 min
Runs on
Your browser
Check
5 questions

A designer needed the NAND of two status bits and typed ~a & ~b. The board passed its first test, with both bits at 0. It failed in the field, when only one bit was 1.

NAND as Intended, Against the Line That Was TypedOne input row per step, ab from 00 to 11. The two outputs agree on the first and last rows only.
0123a b00011011~(a & b), intended~a & ~b, typedfirst difference
Scroll horizontally ↔
  1. Cycle 0

    Both bits are 0. Both forms give 1, so the first test passed.

  2. Cycle 1

    b is 1. NAND still gives 1, but ~a & ~b gives 0. The board misbehaves.

  3. Cycle 3

    Both bits are 1. Both forms give 0. Only the middle rows show the bug.

Computed from the two expressions and confirmed on Icarus. The typed line is NOR, not NAND.

De Morgan's Two Theorems

De Morgan's theorems say how to invert an AND or an OR. Break the bar over the expression, and change the operator under it.

ab(ab)'a' + b'(a + b)'a'b'
001111
011100
101100
110000

Proof by perfect induction: columns 3 and 4 are equal, and so are columns 5 and 6.

So a NAND gate is also an OR gate with inverted inputs. A NOR gate is also an AND gate with inverted inputs. Each gate has two symbols.

GateUsual symbolOther symbolRead it as
NANDAND with a bubble on the outputOR with bubbles on both inputsthe output is 1 when a is 0 or b is 0
NOROR with a bubble on the outputAND with bubbles on both inputsthe output is 1 when a is 0 and b is 0
ANDANDNOR with bubbles on both inputs(a' + b')' = ab
ORORNAND with bubbles on both inputs(a'b')' = a + b

A bubble is an inverter drawn as a small circle on a pin.

De Morgan for Many Variables

The theorems hold for any number of inputs. (abc)' = a' + b' + c', and (a + b + c)' = a'b'c'.

To complement a whole expression, use the theorems from the outside in. Every AND becomes an OR, every OR becomes an AND, and every literal is inverted.

StepExpressionWhat changed
0(ab + c')'the expression to complement
1(ab)'·(c')'De Morgan on the OR: the sum becomes a product of complements
2(a' + b')cDe Morgan on the AND, and (c')' = c

The last form is the complement of ab + c'. All three forms have the same column, checked on every row.

Keep the brackets. The complement of ab + c' is (a' + b')c, and a' + b'c is a different function.

Bubble Pushing

Bubble pushing redraws a circuit with De Morgan. Move a bubble from the output of a gate to all of its inputs, and swap AND with OR. Two bubbles on one wire cancel.

Three NAND Gates Become AND-ORArrows show the signal from the inputs to f. Each step moves bubbles. The function stays the same at every step.
  • I/O
  • Datapath
  • Data
CallValueReturnWaiting
Three NAND gates become AND-ORArrows show the signal from the inputs to f. Each step moves bubbles. The function stays the same at every step. io a, b inputs io c, d inputs datapath Gate 1 NAND, then AND datapath Gate 2 NAND, then AND datapath Gate 3 NAND, then OR io f ab + cd bubble at both endsbubble at both ends
  1. datapath Gate 1NAND, then AND
    • bubble at both ends → Gate 3
  2. datapath Gate 2NAND, then AND
    • bubble at both ends → Gate 3
  3. datapath Gate 3NAND, then OR
    • f
  4. io fab + cd
  5. io a, binputs
    • Gate 1
  6. io c, dinputs
    • Gate 2
  1. Three NAND gates

    Three NAND gates: two at the inputs and one at the output.

    Follow the calls, values and waits
    1. data ((ab)'(cd)')': Gate 3 → f
  2. Redraw the output gate

    The output NAND is drawn as an OR with bubbles on its inputs.

    Follow the calls, values and waits
    1. data (ab)'' + (cd)'': Gate 1 → Gate 3
  3. Cancel the pairs

    Each wire now has a bubble at both ends. Two bubbles cancel, so the circuit is AND-OR.

    Follow the calls, values and waits
    1. data ab + cd: Gate 3 → f
Read the diagram as text
  • a, b: inputs
  • c, d: inputs
  • Gate 1: NAND, then AND
  • Gate 2: NAND, then AND
  • Gate 3: NAND, then OR
  • f: ab + cd
  • a, b → Gate 1
  • c, d → Gate 2
  • Gate 1 → Gate 3: bubble at both ends
  • Gate 2 → Gate 3: bubble at both ends
  • Gate 3 → f

The output column of all three forms is 0001000100011111 for abcd = 0000 to 1111.

The NAND-NAND Form
abcdf
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
The NAND-NAND Formn3 · ANDn3=0n2 · NOTn2=1n5 · ANDn5=0n4 · NOTn4=1n1 · ANDn1=1n0 · NOTn0=0a=0b=0c=0d=0
a=0 b=0 c=0 d=0
n3 · ANDa=0, b=0 → n3=0
n2 · NOTn3=0 → n2=1
n5 · ANDc=0, d=0 → n5=0
n4 · NOTn5=0 → n4=1
n1 · ANDn2=1, n4=1 → n1=1
n0 · NOTn1=1 → n0=0
Read the connections
GateKindInputsOutput
n3ANDa, bn3
n2NOTn3n2
n5ANDc, dn5
n4NOTn5n4
n1ANDn2, n4n1
n0NOTn1n0

Outputs: n0. 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.

The circuit as written: two NAND gates feeding a third. Click the pins and compare the table with the next one.

AND-OR, Drawn as NAND-NAND
abcdf
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
AND-OR, Drawn as NAND-NANDg0 · NANDterm0=1g1 · NANDterm1=1g2 · NANDf=0a=0b=0c=0d=0
a=0 b=0 c=0 d=0
g0 · NANDc=0, d=0 → term0=1
g1 · NANDa=0, b=0 → term1=1
g2 · NANDterm0=1, term1=1 → f=0
Read the connections
GateKindInputsOutput
g0NANDc, dterm0
g1NANDa, bterm1
g2NANDterm0, 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.

The expression ab + cd, drawn with the NAND-NAND style. Switch the style to AND-OR to see the bubbles cancel.

This is why a sum of products maps straight onto NAND gates. Lesson G2.6 uses it to build any function from NAND alone.

Active-Low Signals and Mixed Logic

Lesson G2.1 chose one logic convention for a whole circuit. Here the choice is made for each signal: its active level.

A signal is active low when 0 means "yes". Reset, chip select and interrupt lines are often active low. Their names end in _n, and some books write a bar or a trailing L.

NameActive levelAsserted whenExample
readyhighthe wire is 1a data valid flag
ready_nlowthe wire is 0an open-drain line pulled low by any device
rst_nlowthe wire is 0the reset of most chips
cs_nlowthe wire is 0the chip select of a memory or SPI device

Asserted means the signal says "yes". The active level says which voltage does that.

Mixed logic draws each gate by the job it does. Draw a bubble on every pin that carries an active-low signal. Then bubbles meet bubbles, and the drawing reads as plain AND and OR.

Say busy must be asserted when req0_n or req1_n is asserted. Both requests are active low. The job is an OR of two requests, so draw an OR gate with bubbles on its inputs. The part on the board is a NAND.

One NAND Part, Drawn by Its JobArrows show the two requests reaching the busy flag. The steps redraw the same part: first as a NAND, then as an OR with bubbles on its inputs.
  • I/O
  • Datapath
  • Control
CallValueReturnWaiting
One NAND part, drawn by its jobArrows show the two requests reaching the busy flag. The steps redraw the same part: first as a NAND, then as an OR with bubbles on its inputs. io req0_n active low: 0 =request io req1_n active low: 0 =request datapath NAND part AND shape, bubble onthe output datapath Same part OR shape, bubbles onboth inputs io busy active high: 1 = busy NANDbubble meets _nbubble meets _nOR
  1. io req0_nactive low: 0 = request
    • NAND part
    • bubble meets _n → Same part
  2. io req1_nactive low: 0 = request
    • NAND part
    • bubble meets _n → Same part
  3. datapath NAND partAND shape, bubble on the output
    • NAND → busy
  4. io busyactive high: 1 = busy
  5. datapath Same partOR shape, bubbles on both inputs
    • OR → busy
  1. As the part is sold

    A NAND symbol: an AND shape with a bubble at the output. Read literally, it says busy = NOT (req0_n AND req1_n), which hides the job.

    Follow the calls, values and waits
    1. data (r0·r1)': NAND part → busy
  2. Drawn by its job

    By De Morgan the same part is an OR with bubbles on its inputs. Each bubble sits on an active-low wire, so bubble meets bubble.

    Follow the calls, values and waits
    1. data r0' + r1': Same part → busy
  3. Read it as plain logic

    Ignore each matched bubble pair and read the shape: busy = request 0 OR request 1. That is the job the designer wanted.

Read the diagram as text
  • req0_n: active low: 0 = request
  • req1_n: active low: 0 = request
  • NAND part: AND shape, bubble on the output
  • Same part: OR shape, bubbles on both inputs
  • busy: active high: 1 = busy
  • req0_n → NAND part
  • req1_n → NAND part
  • NAND part → busy: NAND
  • req0_n → Same part: bubble meets _n
  • req1_n → Same part: bubble meets _n
  • Same part → busy: OR

Both drawings are one NAND gate. Mixed logic picks the drawing whose bubbles match the active levels of the wires.

Asked in interviews
  1. State De Morgan's theorems.

    (ab)' = a' + b' and (a + b)' = a'b'. They hold for any number of variables. In words: invert each input and swap AND with OR.

  2. What is bubble pushing used for?

    It turns a NAND-NAND or NOR-NOR circuit into an AND-OR or OR-AND drawing that is easy to read. It also maps a sum of products onto NAND gates. The function never changes.

  3. Why are so many control signals active low?

    Shared lines are often open drain: any device pulls them low, and a resistor pulls them high, so 0 must mean "asserted". Inverting gates are also the fast and cheap ones. So classic decoder chips such as the 74x138 have active-low outputs.

Try It

The module run_spec writes the rule as given: run when the guard is closed, start is pressed and there is no fault. The whole AND is inverted, because run_n is active low.

The module run_pushed pushes that output bubble through the AND gate, which becomes an OR. But start_n already carried a bubble, so its two bubbles should cancel.

Change the line to assign run_n = ~guard_closed | start_n | ~fault_n; and run again. The bench prints equal on 8 of 8.

Try the wrong De Morgan as well: ~guard_closed & start_n & ~fault_n. Count the rows that still agree.

RUNIcarus Verilog · in your browser
Edit the code, then run it
Expected: differ at guard start_n fault_n = 101: spec 0, pushed 1 differ at guard start_n fault_n = 111: spec 1, pushed 0 equal on 6 of 8
Read included file: tb.sv
// tb.sv: the equivalence bench (read-only). It tries all 8 rows.
module tb;
  logic guard_closed, start_n, fault_n;
  logic spec_n, pushed_n;
  int   equal = 0;

  run_spec   u_spec   (.guard_closed(guard_closed), .start_n(start_n), .fault_n(fault_n), .run_n(spec_n));
  run_pushed u_pushed (.guard_closed(guard_closed), .start_n(start_n), .fault_n(fault_n), .run_n(pushed_n));

  initial begin
    for (int i = 0; i < 8; i++) begin
      {guard_closed, start_n, fault_n} = i[2:0];
      #1;
      if (spec_n === pushed_n) equal++;
      else $display("differ at guard start_n fault_n = %b%b%b: spec %b, pushed %b", guard_closed, start_n, fault_n, spec_n, pushed_n);
    end
    $display("equal on %0d of 8", equal);
  end
endmodule

Check Yourself

ConceptWhat is (a + b')' after De Morgan?
ConceptWhich symbol also draws a NOR gate?
ConceptWhat is the complement of ab + c'?
ConceptA wire runs from a gate output with a bubble to a gate input with a bubble. What does the pair of bubbles do?
Predict the outputThe program compares ~(a & b & c) with ~a | ~b | ~c on all eight rows. Predict the exact line.
module tb;
  logic a, b, c;
  int   equal = 0;
  initial begin
    for (int i = 0; i < 8; i++) begin
      {a, b, c} = i[2:0];
      if ((~(a & b & c)) === (~a | ~b | ~c)) equal++;
    end
    $display("equal on %0d of 8", equal);
  end
endmodule

Common Mistakes

Wrong Write ~(a & b) as ~a & ~b.

De Morgan changes the operator as well. ~a & ~b is NOR, and it differs from NAND on 2 of the 4 rows.

Fix Break the bar and change the sign: ~(a & b) = ~a | ~b.

Before
assign ok_n = ~a & ~b;    // NOR: 1000
After
assign ok_n = ~a | ~b;    // NAND: 1110

Wrong Complement only the variables of an expression.

The complement also swaps every AND with OR. Without that swap you get a different function.

Fix Swap AND with OR, and complement each literal: (ab + c')' = (a' + b')c.

Wrong Add a bubble at one end of a wire and forget the other end.

One bubble inverts the signal. Only a pair of bubbles on the same wire cancels.

Fix Push bubbles in pairs, or add an inverter where a single bubble is left.

Wrong Read the name ready_n as "ready is 1".

The suffix _n marks an active-low signal. ready_n = 0 means "ready".

Fix Read the suffix first. An active-low signal is asserted at 0.

Remember

  • (ab)' = a' + b' and (a + b)' = a'b', for any number of variables.
  • To complement an expression, swap AND with OR and invert every literal. Keep the brackets.
  • A NAND is also an OR with bubbled inputs. A NOR is also an AND with bubbled inputs.
  • Bubble pushing moves inversions without changing the function. Two bubbles on one wire cancel.
  • An active-low signal, named with _n, is asserted at 0. Draw it with a bubble so bubbles meet.

Practice

Report a problem with this page