Boole's expansion theorem

A more explicit way of stating the theorem is: : f(X_1, X_2, \dots , X_n) = X_1 \cdot f(1, X_2, \dots , X_n) + X_1' \cdot f(0, X_2, \dots , X_n) == Variations and implications ==

; XOR-Form : The statement also holds when the disjunction "+" is replaced by the XOR operator: : f(X_1, X_2, \dots , X_n) = X_1 \cdot f(1, X_2, \dots , X_n) \oplus X_1' \cdot f(0, X_2, \dots , X_n) ; Dual form: There is a dual form of the Shannon expansion (which does not have a related XOR form): : f(X_1, X_2, \dots , X_n) = (X_1 + f(0, X_2, \dots , X_n)) \cdot (X_1' + f(1, X_2, \dots , X_n)) Repeated application for each argument leads to the Sum of Products (SoP) canonical form of the Boolean function f. For example for n=2 that would be :\begin{align} f(X_1, X_2) & = X_1 \cdot f(1, X_2) + X_1' \cdot f(0, X_2)\\ & = X_1 X_2 \cdot f(1, 1) + X_1 X_2' \cdot f(1, 0) + X_1' X_2 \cdot f(0, 1) + X_1' X_2' \cdot f(0, 0) \end{align} Likewise, application of the dual form leads to the Product of Sums (PoS) canonical form (using the distributivity law of + over \cdot): :\begin{align} f(X_1, X_2) & = (X_1 + f(0, X_2)) \cdot (X_1' + f(1, X_2))\\ & = (X_1 + X_2 + f(0, 0)) \cdot (X_1 + X_2' + f(0, 1)) \cdot (X_1' + X_2 + f(1, 0)) \cdot (X_1' + X_2' + f(1, 1)) \end{align} == Properties of cofactors ==

; Linear properties of cofactors: : For a Boolean function F which is made up of two Boolean functions G and H the following are true: : If F = H' then F_x = H'_x : If F = G \cdot H then F_x = G_x \cdot H_x : If F = G + H then F_x = G_x + H_x : If F = G \oplus H then F_x = G_x \oplus H_x ; Characteristics of unate functions: : If F is a unate function and... : If F is positive unate then F = x \cdot F_x + F_{x'} : If F is negative unate then F = F_x + x' \cdot F_{x'} == Operations with cofactors ==

; Boolean difference: : The Boolean difference or Boolean derivative of the function F with respect to the literal x is defined as: : \frac{\partial F}{\partial x} = F_x \oplus F_{x'} ; Universal quantification: : The universal quantification of F is defined as: : \forall x F = F_x \cdot F_{x'} ; Existential quantification: : The existential quantification of F is defined as: : \exists x F = F_x + F_{x'} ==History==

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), and it was "widely applied by Boole and other nineteenth-century logicians". Claude Shannon mentioned this expansion, among other Boolean identities, in a 1949 paper, 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. ==Application to switching circuits==

• Binary decision diagrams follow from systematic use of this theorem • Any Boolean function can be implemented directly in a switching circuit using a hierarchy of basic multiplexer by repeated application of this theorem. ==References==