Cambridge A-Level Computer Science (9618) · lesson 15 of 15 · 35 min
Boolean Algebra — A-Level Laws
Applying De Morgan’s to Circuit Design
De Morgan’s theorems are essential for converting between NAND-only and NOR-only implementations. Any Boolean function can be implemented using only NAND gates or only NOR gates — these are called universal gates.
Implement A AND B using only NAND gates
A AND B = NOT(NOT(A AND B)) = NOT(A NAND B)
= (A NAND B) NAND (A NAND B)
Two NAND gates: first computes A NAND B, second inverts it.
Implement NOT A using only NAND gates
NOT A = A NAND A (tie both inputs together)
A NAND A = NOT(A AND A) = NOT A ✓
Simplification Using Laws
Simplify: A’B + AB + A’B’
Group 1: A’B + AB = B(A’ + A) = B·1 = B (distributive + complement)
Remaining: B + A’B’
= B + A’ (absorption: B + A’B’ = B + A’ by consensus)
Result: A’ + B
Which gates are called “universal gates”?
- AND and OR
- NOT and AND
- NAND and NOR
- XOR and XNOR
Answer: NAND and NOR
NAND and NOR are universal — any Boolean function can be built from either one alone.
Apply De Morgan’s theorem to simplify NOT(A OR B):
- NOT A OR NOT B
- NOT A AND NOT B
- A AND B
- NOT A OR B
- Answer: 1
De Morgan: NOT(A OR B) = NOT A AND NOT B. Simplify A + A’B using absorption:
- A’B
- A + B
- AB
- A’
- Answer: 1
A + A’B = (A + A’)(A + B) = 1·(A + B) = A + B (distributive law).
Previous lesson: Virtual machines and emulation
Back to Cambridge A-Level Computer Science (9618)