Shannon expansion & binary decision diagrams
Shannon expansion factors any Boolean function about a variable: f = x·f|ₓ₌₁ + x′·f|ₓ₌₀, where the cofactors are f with x fixed. Applying it recursively builds a binary decision diagram — a branching structure whose leaves are 0 and 1. Merging identical subtrees and skipping redundant tests yields the reduced ordered BDD, which is a canonical form: two functions are equal iff their ROBDDs are identical.
✓ Unlimited questions · marked criterion by criterion · no card needed
Method: how to approach it
The order below is what examiners expect to see, and each step carries its own marks.
- Pick a variable and compute both cofactorsf|ₓ₌₁ substitutes x = 1 and simplifies; f|ₓ₌₀ substitutes x = 0.
- Write the expansionf = x·f|ₓ₌₁ + x′·f|ₓ₌₀. Verify by checking both branches against the truth table.
- Recurse to build the BDDExpand each cofactor on the next variable in a FIXED order, until reaching constants.
- ReduceMerge isomorphic subgraphs and delete any node whose two branches lead to the same place. The result is canonical for that variable order.
Worked example
Apply Shannon expansion to f = xy + x′z about the variable x.
- Cofactor at x = 1: substitute x = 1, x′ = 0, giving 1·y + 0·z = y.
- Cofactor at x = 0: substitute x = 0, x′ = 1, giving 0·y + 1·z = z.
- Expansion: f = x·y + x′·z.
- As a BDD: test x; the 1-branch tests y, the 0-branch tests z; each then leads to the constants.
Answer. f = x·y + x′·z, a three-node BDD testing x, then y or z — this function is exactly a 2-to-1 multiplexer with select x.
Where marks get dropped
These are the specific errors that cost credit on shannon expansion & binary decision diagrams questions — QED's rubric penalises each of them separately.
- Changing the variable order between branches. An ORDERED BDD requires one global order, and canonicity depends on it.
- Forgetting to simplify the cofactors. Leaving x in a cofactor defeats the purpose of the expansion.
- Expecting all variable orders to give the same size. Some functions have linear BDDs under one order and exponential ones under another.
Practise this until it is automatic
Unlimited fresh questions
QED generates new shannon expansion & binary decision diagrams problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.
Marked like an examiner
Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.
Answer in real notation
A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.
Saved to your library
Every question you generate is kept and re-takeable as a timed exam, and your Boolean Algebra mastery is tracked so you know when this is exam-ready.
Shannon expansion & binary decision diagrams — frequently asked questions
Why are ROBDDs canonical?
Because for a fixed variable order the reduction rules produce a unique minimal graph. Equivalence checking becomes a pointer comparison, which is why BDDs powered early hardware verification.
Does variable ordering matter much?
Enormously. The middle-bit output of a multiplier has exponential BDD size under every order, while many practical circuits are small under a good one. Finding the optimal order is NP-hard.
How does this relate to multiplexers?
Shannon expansion is exactly a multiplexer: x selects between the two cofactors. Recursive expansion is therefore a direct recipe for a multiplexer-based implementation.
The rest of Boolean Algebra
Axioms, laws, simplification and Boolean functions. Each subtopic below has its own method, worked example and mark-losing traps.
- 1Boolean axioms & laws
- 2The duality principle
- 3Simplifying Boolean expressions
- 4Boolean functions & truth tables
- 5Boolean algebra, logic & set algebra
- 6Sum-of-products & product-of-sums
- 7Karnaugh maps & minimal expressions
- 8Logic gates & translating circuits
- 9NAND / NOR universality
- 10Don’t-care conditions in minimisation
- 11Quine–McCluskey minimisation
- 12Half adders, full adders & multiplexers
- 13Shannon expansion & binary decision diagrams
Ready to make shannon expansion & binary decision diagrams exam-proof?
Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.
Start practising free →