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 splits the function based on the value of $w_1$.

Why this matters

Two 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 isn’t always optimal. Finding the variable whose expansion gives the smallest combined cofactor cost is itself a search problem, and synthesis tools (Espresso, ABC) work through 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.