Shannon expansion

Also called: Shannon's expansion theorem, Shannon expansion theorem, Boole's expansion theorem, cofactor expansion

The identity F = x'·F(x = 0) + x·F(x = 1), which splits any function on one variable. It is exactly what a 2:1 multiplexer computes.

Shannon expansion splits a Boolean function around one of its variables. Pick a variable x. Then:

F = x' · F(x = 0) + x · F(x = 1)

The two pieces are called cofactors:

F(x = 0) is F with 0 put in for x everywhere.
F(x = 1) is F with 1 put in for x.

Neither cofactor contains x any more. Why the identity holds: when x = 0 the second term vanishes and you're left with F(x = 0), which is F. When x = 1 the first term vanishes. Either way you get F back.

Now compare with a 2:1 MUX: Y = . Put x on S, F(x = 0) on I0 and F(x = 1) on I1, and the MUX is the expansion. That's why a MUX can build any function.

Expand again on a second variable and you get four cofactors, one per data input of a 4:1 MUX. Keep going and you reach the full truth table. The "0, 1, x or x'" rule of multiplexer implementation is just the cofactors of a 3-variable function after expanding on two variables.

The idea is also the basis of binary decision diagrams, which design tools use to represent large functions.

			F
0	0	0	1	1
0	0	1	0	0
0	1	0	1	1
0	1	1	1	1
1	0	0	0	0
1	0	1	0	0
1	1	0	1	1
1	1	1	1	1

Worked example

Example

Expanding F = AB + BC + A'C' on A

Find both cofactors, then check that the expansion matches F. The two columns in the diagram are the original and the expansion.

1.
F(A = 0): put A = 0, so = 1. F = 0 + BC + C' = = .
2.
F(A = 1): put A = 1, so = 0. F = B + BC + 0 = B.
3.
Expansion: F = .
4.
Check row 2 = 010: original = 0 + 0 + 1 = 1; expansion = 1 · 1 = 1. ✓
5.
As hardware: a 2:1 MUX with S = A, I0 = , I1 = B.

Common mistakes

Pairing x with F(x = 0). The complement x' goes with F(x = 0), and x goes with F(x = 1).
Leaving x inside a cofactor. Substitute it everywhere, primed copies included, so the cofactor has no x left.
Thinking the expansion simplifies F. It only rewrites F; the two forms are always equal.

Practice Shannon expansion

Interactive questions with instant feedback and a worked solution for every wrong answer.

Combinational Logic lesson full course

Practice exams

Learn it step by step

Shannon expansion is taught in Combinational Logic.

Combinational Logic →

All terms