Shannon decomposition
Table of contents
Boole’s expansion theorem
The Shannon expansion or decomposition theorem, also known as Boole’s expansion theorem is an identity which allow the expansion of any logic function to broken down in parts. One consequence of this theorem is the possibility to implement any logic function using multiplexers.
The expansion can take any of these three variations:
$\begin{aligned} f(x_1,x_2,\ldots,x_n)&= x_1 \cdot f(1,x_2,\ldots,x_n) + \overline{x_1}\cdot f(0,x_2,\ldots,x_n) \\\\ &= \bigl(x_1+f(0,x_2,\ldots,x_n)\bigr)\cdot \bigl(\overline{x_1}+f(1,x_2,\ldots,x_n)\bigr) \\\\ &= x_1 \cdot f(1,x_2,\ldots,x_n) \oplus \overline{x_1}\cdot f(0,x_2,\ldots,x_n) \end{aligned}$
More details can be found in Section 1.9 “Shannon’s Expansion Theorem” in [1] and in Section 3.2 “Switching functions” in [2].
References
- [1]G. Donzellini, L. Oneto, D. Ponta, and D. Anguita, Introduction to Digital Systems Design. Springer International Publishing, 2018 [Online]. Available at: https://books.google.cl/books?id=va1qDwAAQBAJ
- [2]Z. Kohavi and N. K. Jha, Switching and Finite Automata Theory. Cambridge University Press, 2010 [Online]. Available at: https://books.google.cl/books?id=jZIxam8Rb9AC