De Morgan's laws
Two rules for moving a NOT through a bracket. Negate an AND and you get an OR of negations; negate an OR and you get an AND of negations. Negate every term, swap the operator. That is the whole of it, and it is the most used identity in digital logic.
The two laws
The negation of an AND is the OR of the negations.
A NAND gate is an OR gate with both inputs inverted.
Proof
| a | b | ¬(a ∧ b) | ¬a ∨ ¬b |
|---|---|---|---|
| 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
Both columns match on all 4 rows, so the identity holds.
The negation of an OR is the AND of the negations.
A NOR gate is an AND gate with both inputs inverted.
Proof
| a | b | ¬(a ∨ b) | ¬a ∧ ¬b |
|---|---|---|---|
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 |
Both columns match on all 4 rows, so the identity holds.
In engineering notation the same two lines read (A·B)' = A' + B' and (A+B)' = A'·B'. In code, !(a && b) is !a || !b, which is the form most programmers meet first.
How to apply them
The rule is mechanical, and it is easiest to remember as three moves on the bracket:
- Take the NOT off the bracket. The bracket no longer has a bar over it.
- Negate every term inside. A term that was already negated now has two NOTs, which cancel.
- Swap the operator. Every AND between those terms becomes OR, and every OR becomes AND.
When brackets are nested, work from the outside in. The outer NOT sees the inner bracket as one term, so it gets a NOT of its own and waits. Then apply the law to that inner bracket in turn. The older mnemonic is "break the line, change the sign": the overbar breaks into pieces, and the operator under the break flips.
Worked examples
Six derivations, each one a step at a time with the law named at every line. Every step is checked against the starting expression by the same engine that runs the tools on this site.
A NOT over an AND
The basic move, followed by the tidy-up that nearly always comes with it.
- ¬(a ∧ ¬b)
- ¬a ∨ ¬¬b De Morgan: negate each term, AND becomes OR
- ¬a ∨ b Double negation: ¬¬b is b
A NOT over a longer OR
With three terms the rule is the same: every term is negated and every operator is swapped.
- ¬(a ∨ ¬b ∨ c)
- ¬a ∧ ¬¬b ∧ ¬c De Morgan: negate each term, OR becomes AND
- ¬a ∧ b ∧ ¬c Double negation
Nested brackets, outside in
Apply the law to the outermost NOT first. The inner bracket comes along as one term, and gets its own turn.
- ¬((a ∧ b) ∨ c)
- ¬(a ∧ b) ∧ ¬c De Morgan on the outer OR; the bracket is a single term
- (¬a ∨ ¬b) ∧ ¬c De Morgan on the inner AND
The complement of a function
Negating a sum of products gives a product of sums. This is how you write ¬F when you already have F.
- ¬((a ∧ b) ∨ (¬a ∧ c))
- ¬(a ∧ b) ∧ ¬(¬a ∧ c) De Morgan on the OR
- (¬a ∨ ¬b) ∧ (¬¬a ∨ ¬c) De Morgan on each AND
- (¬a ∨ ¬b) ∧ (a ∨ ¬c) Double negation
An OR gate from NAND gates
Read backwards, the law turns an OR into a NAND with inverted inputs, which is how NAND builds everything.
- a ∨ b
- ¬¬(a ∨ b) Double negation, added on purpose
- ¬(¬a ∧ ¬b) De Morgan on the inner NOT: one NAND fed by two inverters
Clearing a negated bracket before simplifying
Simplification needs the NOTs on single variables. De Morgan pushes them there; then the ordinary laws apply.
- ¬(¬a ∨ (b ∧ ¬c))
- a ∧ ¬(b ∧ ¬c) De Morgan on the OR, with ¬¬a written as a
- a ∧ (¬b ∨ c) De Morgan on the remaining AND
- (a ∧ ¬b) ∨ (a ∧ c) Distributive law, into sum of products form
Want to see one on your own expression? The boolean algebra calculator shows every law it applies, and can confirm that any two of the lines above are equivalent.
More than two variables
The laws hold for any number of terms, because a ∧ b ∧ c is just (a ∧ b) ∧ c and the two-variable law can be applied twice. In practice you treat the whole chain at once: negate every term, swap every operator.
A three input NAND is a three input OR with every input inverted.
Proof
| a | b | c | ¬(a ∧ b ∧ c) | ¬a ∨ ¬b ∨ ¬c |
|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 |
Both columns match on all 8 rows, so the identity holds.
A three input NOR is a three input AND with every input inverted.
Proof
| a | b | c | ¬(a ∨ b ∨ c) | ¬a ∧ ¬b ∧ ¬c |
|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 |
Both columns match on all 8 rows, so the identity holds.
In circuits: bubble pushing
On a schematic the laws are drawn rather than written. The small circle on a gate's pin means invert, and De Morgan says you may move a bubble from the output of a gate to all of its inputs as long as you swap the gate's shape at the same time.
- A NAND gate, an AND with a bubbled output, is the same part as an OR with both inputs bubbled: ¬(a ∧ b) = ¬a ∨ ¬b.
- A NOR gate, an OR with a bubbled output, is an AND with both inputs bubbled: ¬(a ∨ b) = ¬a ∧ ¬b.
- Two bubbles on one wire cancel, so a NAND driving a gate with bubbled inputs can be redrawn as a plain AND driving a plain gate.
Engineers use this to make a schematic read the way the design was thought about, with active-low signals shown as bubbles rather than as extra inverters. It is also why NAND and NOR are universal: the OR that NAND seems to lack is a NAND with its inputs inverted, which is the "OR gate from NAND gates" example above. The NAND and NOR converter applies the laws to a whole expression and counts the gates.
The common mistake
The error nearly everyone makes once is to push the NOT inside the bracket and leave the operator alone, writing ¬(a ∧ b) as ¬a ∧ ¬b. The table shows where it goes wrong.
| a | b | ¬(a ∧ b) | ¬a ∧ ¬b |
|---|---|---|---|
| 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
The two differ on 2 of 4 rows. "Not both a and b" is true whenever either one is missing; "not a and not b" needs both to be missing. The first is an OR of the negations, and only the OR is right.
Where the name comes from
Augustus De Morgan (1806–1871) was a British mathematician and logician, a contemporary and correspondent of George Boole, and he stated the laws formally in his Formal Logic of 1847; the algebraic notation used here came with the Boolean algebra that followed. The observation itself is much older: medieval logicians knew it, and William of Ockham wrote out the same rule in words in the fourteenth century. What De Morgan added was the algebra, which is what makes the rule mechanical enough to build circuits with.
Questions about De Morgan's laws
What are De Morgan's laws?
Two identities in boolean algebra that say how a NOT moves through a bracket. Negating an AND gives the OR of the negated terms: ¬(a ∧ b) = ¬a ∨ ¬b. Negating an OR gives the AND of the negated terms: ¬(a ∨ b) = ¬a ∧ ¬b. In short, negate every term and swap AND for OR.
What is De Morgan's theorem in digital electronics?
The same two laws read as gates: a NAND gate is an OR gate with both inputs inverted, and a NOR gate is an AND gate with both inputs inverted. That is what lets any circuit be rebuilt from NAND gates alone or from NOR gates alone, and what engineers are doing when they push inversion bubbles around a schematic.
How do you apply De Morgan's law step by step?
Find the NOT that covers a bracket. Remove it, put a NOT on every term inside the bracket instead, and swap the operator between the terms: AND becomes OR, OR becomes AND. If a term was already negated it now has two NOTs, which cancel. Work from the outermost bracket inwards, treating any inner bracket as a single term until it is its own turn.
Do De Morgan's laws work for more than two variables?
Yes. ¬(a ∧ b ∧ c) = ¬a ∨ ¬b ∨ ¬c, and the same for OR, for any number of terms. It follows from applying the two-variable law repeatedly, since a ∧ b ∧ c is (a ∧ b) ∧ c. The tables on this page prove the three-variable forms directly.
Why is ¬(a ∧ b) not the same as ¬a ∧ ¬b?
Take a = 1 and b = 0. Then a ∧ b is 0, so ¬(a ∧ b) is 1; but ¬a ∧ ¬b is 0 ∧ 1, which is 0. The NOT cannot simply be distributed inside the bracket; the operator has to flip as well. "Not both" means "at least one is missing", which is an OR.
Who was De Morgan?
Augustus De Morgan, a British mathematician and logician, who stated the laws formally in 1847, alongside George Boole's work. The idea itself is older: medieval logicians, William of Ockham among them, had written out the same rule in words.