De Morgan's Laws

De Morgan’s laws state how to push a negation through a parenthesis: the negation of an OR becomes an AND of negations, and the negation of an AND becomes an OR of negations.

$\overline{X\vee Y}=\overline{X}\wedge \overline{Y}$

$\overline{X\wedge Y}=\overline{X}\vee \overline{Y}$

In the parallel set-theory version, the complement of a union is the intersection of complements, and vice versa.

These laws extend to any number of variables: $\overline{x_1+x_2+\dots +x_n}=\overline{x_1}\overline{x_2}\cdots \overline{x_n}$.

Why they matter

Three reasons you’ll keep reaching for these laws:

1. Converting between gate types. A NAND gate is $\overline{xy}$ which by De Morgan equals $\overline{x}+\overline{y}$ — an OR of inverted inputs. That equivalence is exactly what makes NAND a universal gate.

2. Distributing a NOT. When you complement a long expression, De Morgan’s laws push the bar inward step by step until each variable carries its own negation.

3. NAND-NAND and NOR-NOR synthesis. Converting an SOP expression into an all-NAND implementation relies on De Morgan to rewrite each AND-then-OR as a chain of NANDs.

The diagram above shows the same logic implemented three ways: as a NAND, as inverted inputs into an OR, and as a NOR with bubbles on the output. They’re all the same circuit, just drawn with the negation in a different place — De Morgan in pictures.

Worked example

Complement $f=(\overline{A}B+C)$.

Applying De Morgan to the outer OR:

$\overline{f}=\overline{(\overline{A}B)}\cdot \overline{C}$

Then to the AND inside:

$\overline{f}=(A+\overline{B})\cdot \overline{C}$

Distributing:

$\overline{f}=A\overline{C}+\overline{B}\overline{C}$

The original expression and its complement use opposite combinations of operators — every AND in the first becomes an OR in the second and vice versa, with each variable individually negated. That’s De Morgan’s signature.