De Morgan's Laws

Sometimes in circuit design you run into a funny situation: you need a particular gate, say, OR, but the "factory" only has NAND gates and NOT inverters available. Can you get by? Yes! And that's where mathematics comes to the rescue — specifically, the laws of Augustus De Morgan.

De Morgan proved a beautiful rule: the negation of a logical OR is equivalent to a logical AND of the negations. It sounds like an incantation, but in practice it's very clear.

Imagine that we take an ordinary AND gate, put inverters (NOT) on both of its inputs, and then one more inverter on its output. This whole construction magically starts working exactly like an OR gate!

Two formulas

There are two laws, and they are symmetric:

NOT (A AND B)  = (NOT A) OR (NOT B)
NOT (A OR B)   = (NOT A) AND (NOT B)

The left side of the first law is the NAND gate, and the right side is an OR with inverted inputs. So a NAND is equivalent to an OR with flipped inputs.

Proof with a truth table

Let's check the first law for all four input combinations:

The "NOT (A AND B)" column and the "(NOT A) OR (NOT B)" column match in all four rows — so the expressions are indeed equivalent.

Numeric example: A = 1, B = 0

Let's work through the first law step by step for A = 1 and B = 0:

1. First the left side: A AND B = 1 AND 0 = 0. Invert it: NOT (A AND B) = NOT 0 = 1.

2. Now the right side: NOT A = NOT 1 = 0, and NOT B = NOT 0 = 1. OR them: 0 OR 1 = 1.

3. Compare: the left side gives 1, and the right side gives 1 as well. The equality holds.

Try running the remaining three combinations yourself — the results will always match.

OR from three NANDs

Now let's apply the law in practice. We only have NANDs. To get OR(A, B), we need to realize the formula NOT (NOT A AND NOT B). First build two inverters by tying both NAND inputs together:

// Inverter from NAND: both inputs tied
NAND n1 (a, a, nA);   // nA = NOT a
NAND n2 (b, b, nB);   // nB = NOT b

// OR from three NANDs
NAND n3 (nA, nB, or); // or = NOT (nA AND nB) = a OR b

Done: an OR gate from three NANDs — with zero ready-made OR or AND gates used. The third NAND already outputs the OR: by De Morgan's law NOT (NOT a AND NOT b) = a OR b, so no extra inverter is needed on the output.

NAND — the universal gate

All basic elements can be built from NAND alone:

• NOT: NAND(A, A) — both inputs tied together.
• AND: NAND(A, B) plus an inverter on the output — two NANDs in a row.
• OR: inverters on the inputs plus a NAND — three NANDs.

Real processors, including your smartphone, are built mostly from NAND gates: producing dozens of different gate types on a single chip is expensive and technologically difficult, while the universal NAND is cheap and compact.

Why it matters in the game: level 1.4

In level 1.4 "At least one" you need to build an OR gate, but you only have a NAND and the gates you've already built. De Morgan's law suggests the solution: build an AND from a NAND (via an inverter), then plug it into the formula OR = NOT (NOT A AND NOT B) — or build the OR directly from three NANDs. Both paths lead to the same truth table.

De Morgan's identities are easy to check in the truth table generator: build tables for NOT(A AND B) and (NOT A) OR (NOT B) — they match row for row.

Summary

1. NOT (A AND B) = (NOT A) OR (NOT B) — negating an AND turns it into an OR of negations.

2. NOT (A OR B) = (NOT A) AND (NOT B) — negating an OR turns it into an AND of negations.

3. A NAND is equivalent to an OR with flipped inputs, and a NOR to an AND with flipped inputs.

4. NOT, AND, and OR can all be built from NAND — that's why NAND is called the universal gate.

5. De Morgan's laws let you build any circuit from a limited set of parts.

In level 1.4 you will build an OR gate using De Morgan's law, with the AND and NOT gates you've already constructed. To learn more about AND, OR, and NOT gates, read "Logic Gates — AND, OR, NOT", and next up is the XOR gate, which will become the sum bit of your future adder.