Boole's expansion theorem, often referred to as the Shannon expansion or decomposition, is the identity:
is any Boolean function,
set equal to
respectively.
are sometimes called the positive and negative Shannon cofactors, respectively, of
with respect to
These are functions, computed by restrict operator,
(see valuation (logic) and partial application).
It has been called the "fundamental theorem of Boolean algebra".
[1] Besides its theoretical importance, it paved the way for binary decision diagrams (BDDs), satisfiability solvers, and many other techniques relevant to computer engineering and formal verification of digital circuits.
In such engineering contexts (especially in BDDs), the expansion is interpreted as a if-then-else, with the variable
being the condition and the cofactors being the branches (
is true and respectively
[2] A more explicit way of stating the theorem is: Repeated application for each argument leads to the Sum of Products (SoP) canonical form of the Boolean function
that would be Likewise, application of the dual form leads to the Product of Sums (PoS) canonical form (using the distributivity law of
): George Boole presented this expansion as his Proposition II, "To expand or develop a function involving any number of logical symbols", in his Laws of Thought (1854),[3] and it was "widely applied by Boole and other nineteenth-century logicians".
[4] Claude Shannon mentioned this expansion, among other Boolean identities, in a 1949 paper,[5] and showed the switching network interpretations of the identity.
In the literature of computer design and switching theory, the identity is often incorrectly attributed to Shannon.