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.
- Cycle 0
Both bits are 0. Both forms give 1, so the first test passed.
- Cycle 1
b is 1. NAND still gives 1, but ~a & ~b gives 0. The board misbehaves.
- 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.
| a | b | (ab)' | a' + b' | (a + b)' | a'b' |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 | 0 |
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.
| Gate | Usual symbol | Other symbol | Read it as |
|---|---|---|---|
| NAND | AND with a bubble on the output | OR with bubbles on both inputs | the output is 1 when a is 0 or b is 0 |
| NOR | OR with a bubble on the output | AND with bubbles on both inputs | the output is 1 when a is 0 and b is 0 |
| AND | AND | NOR with bubbles on both inputs | (a' + b')' = ab |
| OR | OR | NAND 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.
| Step | Expression | What 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')c | De 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.
- I/O
- Datapath
- Data
- Three NAND gates
Three NAND gates: two at the inputs and one at the output.
Follow the calls, values and waits
- data ((ab)'(cd)')': Gate 3 → f
- Redraw the output gate
The output NAND is drawn as an OR with bubbles on its inputs.
Follow the calls, values and waits
- data (ab)'' + (cd)'': Gate 1 → Gate 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
- 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.
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.
| Name | Active level | Asserted when | Example |
|---|---|---|---|
ready | high | the wire is 1 | a data valid flag |
ready_n | low | the wire is 0 | an open-drain line pulled low by any device |
rst_n | low | the wire is 0 | the reset of most chips |
cs_n | low | the wire is 0 | the 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.
- I/O
- Datapath
- Control
- 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
- data (r0·r1)': NAND part → busy
- 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
- data r0' + r1': Same part → busy
- 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
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.
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.
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.
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 8Read 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
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.
assign ok_n = ~a & ~b; // NOR: 1000assign ok_n = ~a | ~b; // NAND: 1110Wrong 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.