Shannon's Expansion Theorem

Mux implementations of logic functions require that a given function be decomposed with respect to the variables that are used as the select inputs

^ i.e. Split f(w1...) into w1*f(1,...) + w1'*f(0,...)

  • Terms without the cofactor appear in both complemented and uncomplemented forms


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

  • Cofactors are denoted $f_{\overline{w_1}}$
    • $f = \overline{w_1}f_{\overline{w_1}} + w_1 f_{w_1}$

Multiple variable implementation

We can expand multiple variables simultaneously, making $2^n$ different terms.

When all variables are expanded, a canonical sum of products is formed