Digital Logic & Microprocessor — Digital Logic, NEC licence examination syllabus (Nepal Engineering Council).
Boolean Algebra: simplifying before you build
Every gate you remove is silicon saved, power saved, and delay saved.
A logic expression straight from a truth table is almost always wasteful. Boolean algebra lets you prove that a 12-gate circuit and a 3-gate circuit do exactly the same thing — and then you build the cheap one. The laws look abstract, but each one corresponds to a physical simplification you can point at in a circuit diagram.
The laws
BASIC IDENTITIES
A + 0 = A A · 1 = A
A + 1 = 1 A · 0 = 0
A + A = A A · A = A (idempotent)
A + A' = 1 A · A' = 0 (complement)
(A')' = A (involution)
COMMUTATIVE A + B = B + A A·B = B·A
ASSOCIATIVE (A+B)+C = A+(B+C) (AB)C = A(BC)
DISTRIBUTIVE A(B+C) = AB + AC
A + BC = (A+B)(A+C) ← the surprising one
ABSORPTION A + AB = A
A(A+B) = A
A + A'B = A + B
A(A'+B) = AB
CONSENSUS AB + A'C + BC = AB + A'C
(the BC term is redundant)
De Morgan's theorems — the two most useful
(A + B)' = A' · B' "NOR = AND of complements"
(A · B)' = A' + B' "NAND = OR of complements"
Extends to any number of variables:
(A + B + C)' = A'B'C'
(ABC)' = A' + B' + C'
The mechanical rule: BREAK the bar, CHANGE the sign.
· break the overall complement
· swap every + with · and every · with +
· complement each individual variable
De Morgan is what makes NAND/NOR universality practical, and it's the single most-used theorem in the whole subject. The mnemonic worth memorising: "break the line, change the sign." Applying it also lets you convert any AND-OR circuit into all-NAND form, which is how real designs get built.
Worked numerical 1 — a full simplification
Simplify Y = A'BC + AB'C + ABC' + ABC.
Y = A'BC + AB'C + ABC' + ABC
Duplicate ABC (allowed: A + A = A) so it can pair twice:
Y = A'BC + ABC + AB'C + ABC + ABC' + ABC
Group into three pairs:
(A'BC + ABC) = BC(A' + A) = BC·1 = BC
(AB'C + ABC) = AC(B' + B) = AC·1 = AC
(ABC' + ABC) = AB(C' + C) = AB·1 = AB
Y = BC + AC + AB
Gate count comparison:
Original: 4 AND (3-input) + 1 OR (4-input) = 5 gates,
plus 3 inverters = 8
Simplified: 3 AND (2-input) + 1 OR (3-input) = 4 gates,
no inverters = 4
Halved the gate count, and removed all inverters.
Sanity check with A=1, B=1, C=0:
Original: 0 + 0 + (1·1·1) + 0 = 1
Simplified: 0 + 0 + 1 = 1 ✔
Worked numerical 2 — using De Morgan
Simplify Y = ((A + B')·(A' + C))' and implement using NAND gates only.
Apply De Morgan to the outer complement (product → sum):
Y = (A + B')' + (A' + C)'
Apply De Morgan to each term (sum → product):
Y = (A'·B) + (A·C')
Y = A'B + AC'
Verify with a truth table for a couple of rows:
A=0,B=1,C=0: A'B = 1·1 = 1 → Y = 1
Original: ((0+0)·(1+0))' = (0·1)' = 0' = 1 ✔
A=1,B=0,C=0: AC' = 1·1 = 1 → Y = 1
Original: ((1+1)·(0+0))' = (1·0)' = 0' = 1 ✔
NAND-only implementation of Y = A'B + AC':
Note that X + Z = (X'·Z')' — a NAND of the inverted terms.
A'B = (A'B)'' → NAND(A', B) then invert
AC' = NAND(A, C') then invert
Y = NAND( NAND(A',B) , NAND(A,C') )
Total: 2 inverters (for A' and C') + 3 NANDs = 5 gates,
all of one type.
Worked numerical 3 — the consensus theorem in action
Simplify Y = AB + A'C + BC and prove the third term is redundant.
By the consensus theorem, BC is redundant:
Y = AB + A'C
PROOF — expand BC using A + A' = 1:
BC = BC(A + A') = ABC + A'BC
Y = AB + A'C + ABC + A'BC
= AB(1 + C) + A'C(1 + B) [factoring]
= AB·1 + A'C·1 [since 1 + X = 1]
= AB + A'C ∎
Intuition: BC only matters when B=1 and C=1. But then
either A=1 (so AB=1 already) or A=0 (so A'C=1 already).
Either way the output is already 1 — BC never contributes
anything new.
Saved: one 2-input AND gate, and one input on the OR gate.
Worked numerical 4 — duality and complements
Find the complement and the dual of Y = A(B + C'D).
COMPLEMENT — apply De Morgan repeatedly:
Y' = [A(B + C'D)]'
= A' + (B + C'D)'
= A' + B'·(C'D)'
= A' + B'(C + D')
DUAL — swap · with + and 0 with 1, but do NOT complement
the variables:
Y = A(B + C'D)
Y_dual = A + (B · (C' + D))
Note the difference: the complement inverts variables, the
dual does not. Confusing the two is a common error.
Why duals matter: every Boolean theorem has a valid dual.
Prove A + AB = A and you get A(A+B) = A free.
💡 Exam angle: a guaranteed 6–8 mark simplification question. Show every step with the law named beside it — that's where the marks are, not the final answer. The most useful tactic is duplicating a term (A + A = A) so it can pair with two different terms, as in numerical 1. Always verify your answer on two or three truth-table rows; it costs 30 seconds and catches sign errors.
Syllabus points
Laws & theorems (De Morgan's)
Expression simplification (numerical)
Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.