De Morgan's Laws

In electronics, NAND and NOR gates are much cheaper and faster to manufacture than AND and OR gates. But what if your circuit design requires an AND? This is where De Morgan's laws save the day.

Augustus De Morgan, a 19th-century British mathematician, discovered two elegant transformations:

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

What does this mean in practice? Take the first law. The left side is a NAND gate. The right side is: invert A, invert B, then OR them together. So a NAND is equivalent to an OR with inverted inputs! Similarly, a NOR is equivalent to an AND with inverted inputs. And by adding another inverter, you can turn a NAND into an AND, or a NOR into an OR.

Practical example. You have only NAND gates available (this is a common constraint in chip design because NANDs are the cheapest transistor structure). You need an OR gate. Apply De Morgan: OR(A,B) = NOT(NAND(NOT(A), NOT(B))). Build two NOTs (using NANDs with tied inputs), feed them into a NAND, and add one more NOT at the output. You just built an OR gate from three NANDs — with zero AND or OR gates used.