De Morgan’s Laws
Mastering logic transformation: The bridge between AND and OR operations.
Logic Transformation
De Morgan’s laws allow us to convert AND logic to OR logic and vice versa. In VLSI, this is the “Secret Sauce” for mapping high-level logic to physical CMOS gates.
change the sign.”
Interactive Logic Transformer
Select a law to see the transformation in action
Practical Use in VLSI
NAND/NOR-Only Design
Since NAND and NOR are universal gates, De Morgan’s laws are used to convert Standard Sum of Products (SOP) into forms that can be implemented purely with NAND gates.
CMOS Logic Synthesis
In CMOS, the Pull-Up Network (PMOS) is the dual of the Pull-Down Network (NMOS). De Morgan’s laws help designers determine the PMOS topology from the NMOS logic.
Simplification Example
Given Expression
Apply De Morgan’s Law to $\overline{(A+B)}$
Final Simplified Result
VLSI Interview: The XOR-to-NAND Challenge
A common interview question is to implement an XOR gate using only NAND gates. Since NAND is a universal gate, we can use De Morgan’s laws to transform the expression until every term is a NAND operation.
XOR Expression (SOP)
Start with the standard Sum of Products form.
Apply Double Inversion
Adding two bars over the entire expression doesn’t change its value (Involution Law).
Apply De Morgan to the Bottom Bar
“Break the bar, change the sign.”
This expression represents a NAND of two NANDs. Specifically:
1. NAND(A, NOT B)
2. NAND(NOT A, B)
3. NAND these two results together.