De Morgan's laws

De Morgan's first and second law

Each law with its truth table proof. Two variables have four combinations, so checking all four proves the law.

The same laws in every notation

Textbooks, datasheets and programming languages write the same two laws in different symbols. Every row below is checked by this site's expression engines.

The bar form is read "break the line, change the sign": cut the bar over A · B into a bar over each letter, and the · under the cut becomes +. In the code rows, ≡ means the two sides always give the same result; it is not an operator you can type. Writing == between them would need brackets round each side, because == binds tighter than || and or.

Proof of De Morgan's theorem

The truth tables above are one proof: with two variables there are only four cases, and checking every case is a proof. The algebraic proof uses the fact that a value has exactly one complement. If ¬a ∨ ¬b ORed with a ∧ b always gives 1, and ANDed with it always gives 0, then ¬a ∨ ¬b is the complement of a ∧ b, which is ¬(a ∧ b).

So ¬(a ∧ b) = ¬a ∨ ¬b. The second law has the same proof with every AND and OR swapped and every 1 and 0 swapped, which is the duality principle of boolean algebra: any law stays true when you swap them.

How to apply De Morgan's law step by step

The rule is mechanical, and it is easiest to remember as three moves on the bracket:

1. Take the NOT off the bracket. The bracket no longer has a bar over it.
2. Negate every term inside. A term that was already negated now has two NOTs, which cancel.
3. 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.

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.

De Morgan's law for n 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.

The three and four variable forms, each proved by its full truth table of 8 or 16 rows. The test suite checks every width up to eight.

De Morgan's law in logic gates

On a schematic the laws are drawn rather than written. The small circle on a gate's pin, the bubble, means invert. Each law says that two drawings are the same part:

Put another way, 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. This is called bubble pushing.

• 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, and the logic gate symbols page has every gate in both drawing standards.

De Morgan's law for sets

The same two laws hold for sets, with intersection for AND, union for OR and the complement for NOT. An element is in A ∩ B when it is in A and in B, so the two subjects are one algebra in different symbols.

In words: whatever is not in both sets is missing from at least one of them, and whatever is in neither set is outside A and outside B. Worked out with U = {1, 2, 3, 4, 5, 6, 7, 8}, A = {1, 2, 3, 4} and B = {3, 4, 5, 6}:

(A ∩ B)ᶜ and Aᶜ ∪ Bᶜ are both {1, 2, 5, 6, 7, 8}, and the second law checks out the same way: (A ∪ B)ᶜ and Aᶜ ∩ Bᶜ are both {7, 8}.

See it shaded: the Venn diagram generator draws (A ∩ B)ᶜ and gives its shortest equivalent, and the set notation page explains every symbol used here.

Common mistakes

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.

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 Boole's 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 a formal statement within symbolic logic, and Boolean algebra then made it mechanical enough to build circuits with.