Beta Phase: Square45 is currently in beta testing. Expect some features or content to be incomplete or missing.
45

Shannon's Expansion Theorem

A foundational theorem stating that any Boolean function f(x1,...,xn)f(x_1, ..., x_n) can be uniquely expanded as a sum of products (SOP) or a product of sums (POS).
📜

The statement of the theorem

Let f:{0,1}n→{0,1}f: \{0, 1\}^n \to \{0, 1\} be an arbitrary Boolean function. Then ff can be uniquely represented in the canonical Sum-of-Products (SOP) form, f(x)=∑I∈MmIf(\mathbf{x}) = \sum_{I \in M} m_I, where MM is the set of minterms xI\mathbf{x}_I such that f(xI)=1f(\mathbf{x}_I) = 1. Equivalently, ff can be uniquely represented in the Product-of-Sums (POS) form, f(x)=∏J∈M′(xJ+1)f(\mathbf{x}) = \prod_{J \in M'} (\mathbf{x}_J + 1), where M′M' is the set of maxterms xJ\mathbf{x}_J such that f(xJ)=0f(\mathbf{x}_J) = 0.
Source: Wikipedia