Shannon's expansion theorem

Shannon’s expansion theorem says any Boolean function can be decomposed around a single variable into two simpler functions. For variable $w_1$:

$f(w_1,w_2,\dots ,w_n)=\overline{w_1}\cdot f(0,w_2,\dots ,w_n)+w_1\cdot f(1,w_2,\dots ,w_n)$

Or, writing $f_{\overline{w_1}}=f(0,w_2,\dots )$ and $f_{w_1}=f(1,w_2,\dots )$ for the two cofactors:

$f=\overline{w_1}\cdot f_{\overline{w_1}}+w_1\cdot f_{w_1}$

The cofactor $f_{w_1}$ is what $f$ collapses to when $w_1=1$; $f_{\overline{w_1}}$ is what it collapses to when $w_1=0$. The expansion is just “split the function based on the value of $w_1$.”

Why this matters

Two practical uses:

1. MUX-based synthesis. Shannon expansion maps directly onto a Multiplexer: $w_1$ becomes the select line, and the two cofactors become the data inputs. So any function can be implemented as a MUX network where the leaves are simpler functions.

2. Recursive decomposition. Apply expansion repeatedly — first around $w_1$, then around $w_2$ inside each cofactor, and so on. This is how LUT-based synthesis decomposes a wide function into a tree of small LUTs.

Worked example

Decompose $f=\overline{w_1}{w}_3+w_2\overline{w_3}$ around different variables and compare:

Around $w_1$:

$f_{\overline{w_1}}=w_3+w_2\overline{w_3},f_{w_1}=w_2\overline{w_3}$

$f=\overline{w_1}(w_3+w_2\overline{w_3})+w_1(w_2\overline{w_3})$

Around $w_2$:

$f_{\overline{w_2}}=\overline{w_1}{w}_3,f_{w_2}=\overline{w_1}{w}_3+\overline{w_3}$

$f=\overline{w_2}(\overline{w_1}{w}_3)+w_2(\overline{w_1}{w}_3+\overline{w_3})$

Around $w_3$:

$f_{\overline{w_3}}=w_2,f_{w_3}=\overline{w_1}$

$f=\overline{w_3}(w_2)+w_3(\overline{w_1})$

The third decomposition is the cheapest — both cofactors collapsed to single literals. Choosing the right variable to expand around is a real optimization decision; a useful first heuristic is to pick the one that appears in the most product terms, since it’s likely to simplify both cofactors. The heuristic is not always optimal — finding the variable whose expansion gives the smallest combined cofactor cost is itself a search problem, and synthesis tools (Espresso, ABC) explore it systematically.

Procedure for finding cofactors

To compute $f_{w_1}$ from a Boolean expression in product form:

1. Take terms containing $w_1$: drop the $w_1$ literal (it’s now $1$) and keep the rest.
2. Take terms containing $\overline{w_1}$: drop them entirely (they’re now $0$).
3. Take terms with neither: keep them as-is.

To compute $f_{\overline{w_1}}$, swap the rules: drop $w_1$-containing terms, drop the $\overline{w_1}$ literal but keep the rest.

Applied recursively (4-to-1 MUX style)

For two control variables $(w_1,w_2)$ over four cases, you get a 4-to-1 MUX decomposition. Take $f=\overline{w_1}\overline{w_3}+w_1{w}_2+w_1{w}_3$:

$w_1$	$w_2$	Selected case	$f$ with values substituted
0	0	$\overline{w_1}\overline{w_2}$	$\overline{w_3}$
0	1	$\overline{w_1}{w}_2$	$\overline{w_3}$
1	0	$w_1\overline{w_2}$	$w_3$
1	1	$w_1{w}_2$	$1$

Implementing as a 4-to-1 MUX: $w_1,w_2$ are select lines; the data inputs are $\overline{w_3},\overline{w_3},w_3,1$. Three cases need just $w_3$ or its complement; the fourth is a constant. No complex AND/OR gates needed before the MUX — just inverters.

This is the route to “LUT-friendly” decomposition: the function reduces to simple expressions parameterized by the select variables.