Shannon expansion

The Shannon expansion (also called the Shannon decomposition or the Boole–Shannon expansion) is the fundamental recursive identity that decomposes any Boolean function into the contributions of a single variable: f(x₁,…,xₙ) = xᵢ · f|ₓᵢ=₁ + ¬xᵢ · f|ₓᵢ=₀. It is the algebraic engine beneath Binary Decision Diagrams, logic synthesis, and virtually all canonical representations of Boolean functions. The expansion is named for Claude Shannon, who formalized it in his 1938 master's thesis — though the identity itself was known to George Boole decades earlier. What Shannon recognized was not the formula but its computational utility: by recursively decomposing on variables, one turns an exponentially large truth table into a compact graph whose structure reveals the function's internal logic. The two sub-functions f|ₓᵢ=₁ and f|ₓᵢ=₀ are called cofactors, and their recursive decomposition is what gives ordered decision diagrams their canonical power.

The Shannon expansion is not merely a technical device. It encodes a deep epistemological assumption: that the complexity of a Boolean function can be understood by asking, variable by variable, what happens when each is fixed. This assumption is powerful when it holds and catastrophic when it does not — as in the case of integer multiplication, where no variable order yields compact cofactor structure. The expansion is thus not a universal key to Boolean complexity but a contingent one, whose applicability depends on whether the function's information is localized in individual variables or distributed across many.