Skip to content
Tutorials Center
My learning

Topics

Lesson 16 of 57 · Boolean Algebra

De Morgan's Theorems and Bubble Pushing

Learn De Morgan's theorems, prove them by exhaustive check in Python, use bubble pushing to redraw circuits, and convert AND-OR logic to NAND-only form.

Two of the most useful sentences in digital design were written down in the 1800s by Augustus De Morgan. They tell you what happens when you invert a group of signals, and they are the reason that circuits can be rebuilt from NAND or NOR gates alone. If you have ever wondered why "not (A and B)" is not the same as "not A and not B", this lesson settles it.

You will learn both theorems, prove them by checking every input, see how a drawing trick called bubble pushing applies them to circuit diagrams, and use them to turn an AND-OR circuit into a faster NAND-only version.

The two theorems

First theorem: the complement of an AND is the OR of the complements.

NOT(a · b) = a′ + b′

Second theorem: the complement of an OR is the AND of the complements.

NOT(a + b) = a′ · b′

In words: break the bar, change the sign. When you move a NOT across an AND or an OR, you complement each input and swap the operator. Both theorems extend to any number of variables: NOT(a·b·c) = a′ + b′ + c′.

Everyday language shows the idea. "It is not true that you are both tired and hungry" means "you are not tired, or you are not hungry (or both)". Negating the AND gives an OR of negations.

You can read the theorems as gate equivalences as well:

  • A NAND gate equals an OR gate with inverted inputs.
  • A NOR gate equals an AND gate with inverted inputs.

Both views are the same gate. The two ways of drawing it are chosen to make the meaning of a circuit obvious.

De Morgan in two lines

NOT of AND Equals the OR of the NOTs.
NOT of OR Equals the AND of the NOTs.

Break the bar, change the sign.

1 / 2

Proof by exhaustive check

Boolean variables take only two values, so a theorem about two variables needs only four checks. A truth table for the first theorem:

a b a·b NOT(a·b) a′ b′ a′ + b′
0 0 0 1 1 1 1
0 1 0 1 1 0 1
1 0 0 1 0 1 1
1 1 1 0 0 0 0

The columns NOT(a·b) and a′ + b′ are identical, which proves the theorem. The program below does this for both theorems with 2, 3 and 4 variables and then shows the most common wrong version of the rule.

Python Checking De Morgan's theorems

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both theorems hold for 2, 3 and 4 variables, and the "wrong rule" prints False. The truth table at the end shows that NAND matches a′ + b′ row by row, and NOR matches a′·b′.

Bubble pushing

In circuit diagrams, a small circle (a bubble) on a gate input or output means inversion. Bubble pushing is the practice of applying De Morgan's theorems graphically. The rules are short:

  1. Pick a gate, and move a bubble from its output to all its inputs (or from all its inputs to its output).
  2. Change the gate shape: AND becomes OR, and OR becomes AND.
  3. Two bubbles on the same wire cancel each other.

Example: take the circuit Y = NOT(a · b) · c, written as a NAND feeding an AND.

TEXT
Before:  a ─┐
            NAND ──┐
         b ─┘      AND ── Y
                c ─┘

Push the bubble from the NAND output back to its inputs and the NAND turns into an OR gate with bubbles on a and b. The circuit now reads "(a′ + b′) AND c", with no ambiguity about where the inversions are.

Why do designers care? Because the drawing should tell the reader what the circuit means. If a signal is "active low" (it does its job when it is 0), you draw bubbles on the pins that use it, and a well-drawn schematic is read left to right as a plain sentence.

Converting AND-OR logic to NAND-only

A sum-of-products circuit has a layer of AND gates feeding one OR gate. In CMOS, NAND gates are smaller and faster than AND and OR gates, so we convert it to two layers of NAND gates. Bubble pushing proves it works:

  1. Start with f = ab + cd as AND gates feeding an OR.
  2. Add a pair of bubbles on each wire between the two layers. The two bubbles cancel, so the function does not change.
  3. A bubble on an AND output turns it into a NAND. The bubbles on the OR inputs turn it into a NAND by De Morgan.
  4. The result is f = NAND( NAND(a, b), NAND(c, d) ).

The same trick with the roles swapped converts an OR-AND circuit (product of sums) into two layers of NOR gates: f = (a + b)(c + d) = NOR( NOR(a, b), NOR(c, d) ).

The next program turns this into a reusable tool. It takes a sum of products written as a list of terms, builds the two-level NAND-NAND version automatically, and compares it with the original over all inputs. A complemented input is made with a NAND whose inputs are tied together.

Python NAND-NAND conversion with a checker

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

All three functions match. The program also reports the number of gates in the two NAND layers (one per product term plus one for the final gate); inverters for complemented inputs are extra.

A NAND-only circuit is not always smaller than an AND-OR circuit. The gain is uniformity and speed: with one gate type in two layers, the delay is two gate delays, and the layout is easier. Each first-layer gate with many inputs may still need a tree of smaller gates, because real gates have a limited fan-in.

Check your understanding

Quick check · 5 questions

of 5 answered You scored / 5 · perfect!

  1. 1. Which expression equals NOT(a + b)?

    By the second De Morgan theorem, the complement of an OR is the AND of the complements.
  2. 2. A NAND gate is equivalent to which gate?

    NOT(a·b) = a′ + b′, which is an OR of the complemented inputs.
  3. 3. What happens to two bubbles on the same wire?

    Inverting a signal twice returns it to the original value, so the two bubbles can be removed.
  4. 4. A two-level AND-OR circuit becomes which circuit when all gates are replaced by NAND?

    Adding a pair of bubbles on each connecting wire changes nothing, and moving one bubble into each gate turns the ANDs into NANDs and the OR into a NAND.
  5. 5. Which line is NOT a correct use of De Morgan's theorem?

    The operator must change when the bar is broken, so NOT(a·b) is a′ + b′, not a′·b′.

Summary

  • De Morgan: NOT(a·b) = a′ + b′ and NOT(a + b) = a′·b′; break the bar, change the sign.
  • A NAND is an OR with inverted inputs, and a NOR is an AND with inverted inputs.
  • Bubble pushing moves inversion bubbles across gates, swapping AND and OR, and two bubbles on one wire cancel.
  • AND-OR (sum of products) circuits convert into NAND-NAND; OR-AND circuits convert into NOR-NOR.
  • Exhaustive checking proves these identities and verifies every conversion.

Next: Sum of Products and Product of Sums.