Demo 4.5: Moving the Inversions
The previous demonstration left a gap. Every rule you used worked on expressions built from AND, OR and inversions of single signals, and not one of them could do anything with a bar drawn over a whole group of terms.
That is a serious limitation rather than a technicality. The gates you can actually buy have inverted outputs. A 7400 holds NAND gates, a 7402 holds NOR gates, and their expressions are full of exactly the long bars your rules cannot touch. If simplification stops the moment a bar covers more than one letter, it stops on almost every real circuit.
De Morgan’s theorems close the gap. They say what happens when a group complement is broken, and the consequence is that an inversion is never stuck where it was drawn. It can always be moved to the other side of a gate, so long as the gate changes from AND to OR, or from OR to AND, as the inversion passes through.
Once inversions can move freely, something else becomes possible. A circuit drawn in AND, OR and NOT can be rebuilt using nothing but NAND gates, or nothing but NOR gates, without changing what it does and usually without using any more gates than before.
How to use it
Section titled “How to use it”Three views along the top.
The theorems shows each equivalence three ways at once: as two gate symbols that turn out to be the same part, as two schematics you can drive from the same switches, and as a truth table. There is also a third form on offer that looks like a theorem and is false. Select it and see which rows give it away.
Breaking bars works like the simplification demonstration. You choose the rule at each step and the expression is rewritten when you get it right, with two levels of hint if you want them. This view also has a button labelled “What if I break both bars at once?”. Press it. It does not tell you off, it carries the illegal step out and shows you the circuit it produces alongside a truth table marking the rows where that circuit is wrong.
One gate type takes a finished circuit through three stages: as designed, with inversions inserted in pairs, and then with each pair absorbed into the gate next to it. The truth table carries all three stages side by side so you can confirm that only the parts list changed.
De Morgan's Theorems
Moving an inversion from the output of a gate to its inputs, and using that to build a circuit from one kind of part.
Walkthrough
Section titled “Walkthrough”Step 1: Two symbols for one part
Section titled “Step 1: Two symbols for one part”Open The theorems and select Bar over a product. At the top are two gate symbols with an equals sign between them: a NAND, which is an AND with a bubble on its output, and a Negative-OR, which is an OR with a bubble on each of its inputs.
They are the same part. Not similar, not usually interchangeable, the same. If you have a 7400 on the bench, both symbols describe what is inside it, and you are free to draw whichever one makes your circuit easier to read.
Click through the input combinations and watch both schematics. Then select Bar over a sum and do the same for NOR and Negative-AND.
The pattern to take away is a sentence rather than a formula. Break the bar, and the operation directly underneath the break changes: addition becomes multiplication, or multiplication becomes addition. The broken pieces of the bar stay over the terms they were covering.
Step 2: See the mistake before you make it
Section titled “Step 2: See the mistake before you make it”Still in the first view, select The tempting one.
The claim on offer is that a bar over A·B is the same as A inverted multiplied by B inverted. It is what almost everyone writes first, because it treats the bar the way a minus sign behaves in ordinary algebra, where it does distribute over what follows.
The truth table disagrees on two of the four rows and marks them in rose. Two rows is more than enough.
The reason is worth saying plainly. A bar is a grouping symbol, not an operator that spreads. A bar over A·B means “work out A·B, then invert the result”, which is a different instruction from “invert A, invert B, then multiply them”. If you break a bar and the operation underneath it has not changed, you have not broken the bar, you have copied it.
Step 3: Break one bar at a time, and find out why
Section titled “Step 3: Break one bar at a time, and find out why”Open Breaking bars and select Two bars. A NOR gate is being fed by a NAND gate, so there are two bars, one nested under the other.
Work the two steps. Break the longest bar first, which is the one covering everything, and notice what it leaves behind: A picks up a bar, and the term that was already barred picks up a second one. The double bar then cancels, because inverting something twice returns it unchanged, and three gates turn out to be one AND gate with a single inverted input.
Now go back and press What if I break both bars at once? before taking the first step.
You are shown the expression that shortcut produces, the circuit it describes, and a truth table comparing it against the circuit you actually started with. Some of those rows are wrong. That is the entire argument for the rule, and it is a much better argument than being told not to do it.
There is a distinction here that is easy to lose. Breaking one bar in several places at once is fine. Breaking two different bars in one step is not. The first is one operation applied across a term, the second is two operations pretending to be one.
Step 4: A circuit that collapses further than you expect
Section titled “Step 4: A circuit that collapses further than you expect”Select A whole circuit. Five gates and an inverter arrive, arranged so that two inverted-output gates feed a third.
Write down what it computes by labelling each gate output in turn, which is what the expression above the schematic is doing for you. Then work the six steps. De Morgan gets the expression out from under its bars, distributing opens it up, and then something unusual finishes it.
Look carefully at step five. One of the terms contains B and also contains B inverted. A product containing a signal alongside its own complement can never be high, whatever else is in it, because one of those two factors is always 0. The whole term collapses, and with it most of the circuit.
The answer is a single AND gate on A and B. Six parts reduced to one. If you had built the original from the schematic without doing this work, you would have paid for five gates you did not need and three levels of propagation delay instead of one.
Step 5: Build it from one kind of gate
Section titled “Step 5: Build it from one kind of gate”Open One gate type with NAND only selected. Stage one is a sum of products, which is the shape simplification usually leaves behind: two AND gates feeding an OR gate.
Stage two looks wasteful and is meant to. An inversion has been added to each AND output and a second one to the OR input it feeds. Each pair cancels, so the circuit still does exactly what it did, and the truth table at the bottom confirms it. Seven gates doing the work of three.
Stage three is the same drawing read differently. An AND with an inverted output is a NAND. An OR with inverted inputs is a Negative-OR, which by the first theorem is also a NAND. Three gates again, and now every one of them is the same part.
Switch to NOR only and watch the dual procedure on a product of sums. Bubbles go on every OR output and every AND input this time.
The gate count did not go up. That is what makes this worth doing rather than merely interesting: a board that needs one part number is cheaper to buy, cheaper to stock, easier to lay out and easier to repair than one that needs three.
Check your understanding
Section titled “Check your understanding”A bar is broken in a Boolean expression. What must change?
Which of these statements are true? Select all that apply.
Check the first theorem for yourself
Column 1 is a NAND gate. Column 2 inverts both inputs and ORs them. Column 3 inverts both inputs and ANDs them. Two of these three columns are identical. Fill all three and find out which.
Match each idea to what it lets you do
Why can a sum-of-products circuit be converted to NAND gates without needing more gates than before?
A student reduces a circuit and produces an expression that looks tidy but they are not certain of one De Morgan step. What settles it fastest?
Wrap-up
Section titled “Wrap-up”De Morgan’s theorems are one idea with two faces. Inverting the output of a gate is the same as inverting its inputs and swapping AND for OR. That is all.
What that buys you is mobility. Before this, an inversion drawn on a schematic was a fixed feature you had to work around. Now it is something you can move, and moving inversions until they meet and cancel is how a circuit built from the parts you can actually buy gets simplified.
Four things to carry forward.
- Break the bar, change the operation underneath. If the operator did not change, the bar was not broken.
- One bar per step. Breaking a single bar in several places is fine, and it is a different thing from breaking two bars at once, which produces a circuit that fails.
- A bar is a grouping symbol. When it comes off, whatever it was holding together needs to stay together, which usually means brackets.
- Inversions inserted in pairs cost nothing and change everything. That is what makes a whole circuit from one part number possible.
The last of those connects back to the universality demonstration. You saw there that NAND alone can produce every other gate, and you now have the procedure that makes the claim practical: take any circuit, insert inversions in pairs, absorb each pair into the gate beside it, and read off the result.
What is still missing is a way of finding the best expression to start from. Everything so far has depended on spotting the right rule at the right moment, and on knowing when to make an expression bigger before making it smaller. That is a skill, and skills are unreliable. Karnaugh maps come next, and they replace the judgement with a procedure that finds a minimal circuit without requiring you to be clever on the day.
© 2026 Derek Molloy, Dublin City University. All rights reserved.