Digital Design / Module 1: Numbers and logic
3. Boolean algebra and De Morgan
Simplify logic before spending gates on it.
See it move
The idea
Every gate costs area, power and delay. Boolean algebra lets you rewrite a function into a cheaper one with exactly the same . Synthesis tools do this automatically, yet you still need the skill, to read logic, spot bugs and answer interview questions.
The rules you actually use
- Identity:
A + 0 = A,A·1 = A - Annihilator:
A + 1 = 1,A·0 = 0 - Complement:
A + A' = 1,A·A' = 0 - Absorption:
A + AB = A - Redundancy:
A + A'B = A + B
De Morgan's laws
(AB)' = A' + B' and (A + B)' = A'B'. As a recipe: invert each input, swap AND with OR, and invert the output. In hardware terms, a NAND is the same as an OR with inverted inputs. This matters because CMOS gates naturally invert, so real circuits are full of these conversions.
Worked example
Simplify F = AB + AB' + A'B.
- Factor the first two terms:
A(B + B') + A'B - Since
B + B' = 1:A + A'B - By the redundancy rule:
A + B
Three AND terms have become a single OR gate. The animation lets you confirm this across all four rows of the truth table.
Common mistake
Treating a shorter expression as automatically better. Removing a "redundant" term can bring back a : the consensus term in AB + A'C + BC adds nothing logically, yet it holds the output steady while A changes. In the Barrel shifters and glitches lesson, you can watch this happen.
Key ideas
- De Morgan: invert the inputs, swap AND and OR, invert the output.
- Absorption removes redundant terms: A + AB = A.
- Consensus terms can matter when removing hazards.
Your exercise
Interview questions
coreSimplify A + A'B.
A + B.
coreState De Morgan for (AB)'.
A' + B'.
basicSimplify A(A + B).
It is A. Expanding gives A·A + A·B = A + AB, and absorption reduces A + AB to A. In words, if A is 1 the product is 1, and if A is 0 the product is 0, so B never matters.
basicApply De Morgan to (A + B')'.
Invert each term, swap OR for AND, and drop the outer inversion: the result is A'·B, since inverting B' gives B. It is 1 only when A is 0 and B is 1.
coreShow that AB + A'C + BC equals AB + A'C. Why might a designer keep the BC term anyway?
Whenever BC is 1, A is either 1, which makes AB true, or 0, which makes A'C true, so BC never adds a 1 of its own; it is the consensus term. Logically it is redundant. In a gate-level circuit, though, BC holds the output at 1 while A changes with B = C = 1, covering the moment when AB has turned off and A'C has not yet turned on. Equal truth tables do not mean equal glitch behaviour.
coreRewrite F = AB + CD so that it uses only NAND gates.
F = ((AB)'·(CD)')'. That is two NANDs for the products feeding a third NAND. By De Morgan, a NAND with inverted inputs is an OR, and the inversions at the outputs of the first-level NANDs supply exactly those inputs. Any two-level AND-OR circuit converts to NAND-NAND this way.
coreThe comment says what the designer wanted. What does the code actually build, and how do you fix it?
// y should be 1 only when a and b are both 0 assign y = ~a | ~b;
By De Morgan, ~a | ~b equals ~(a & b), so this is a NAND: it is 0 only when both inputs are 1. The intent is a NOR, which is 1 only when both are 0, so write ~(a | b) or ~a & ~b. The mistake is inverting the inputs without also swapping the operator.
coreIn ordinary arithmetic, a + bc does not equal (a + b)(a + c). Is A + BC = (A + B)(A + C) true in Boolean algebra?
Yes. Expanding the right side gives A + AC + AB + BC, and A absorbs AC and AB, leaving A + BC. Boolean algebra has both distributive laws, OR over AND as well as AND over OR, which ordinary arithmetic does not. This form is handy for converting between sum-of-products and product-of-sums.
advancedWhat is the dual of the identity A + A'B = A + B, and is the dual also true?
Swap AND with OR (and 0 with 1, though there are none here) to get A·(A' + B) = A·B. It is true: expanding gives AA' + AB, and AA' is 0. Every Boolean identity has a valid dual, so learning one form of each rule gives you the other for free.
advancedSimplify F = (A + B)(A' + C) to a sum of products.
Expanding gives AA' + AC + A'B + BC. AA' is 0, and BC is the consensus of AC and A'B, so it drops out, leaving F = AC + A'B. Checking: when A is 1, F follows C; when A is 0, F follows B. That is a 2:1 mux with A as select.