Boole's expansion theorem

A more explicit way of stating the theorem is:

${\displaystyle 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})}$

XOR-Form

The statement also holds when the disjunction "+" is replaced by the XOR operator:

${\displaystyle 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):

${\displaystyle 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 ${\displaystyle f}$. For example for ${\displaystyle n=2}$ that would be

${\displaystyle {\begin{aligned}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{aligned}}}$

Likewise, application of the dual form leads to the Product of Sums (PoS) canonical form (using the distributivity law of ${\displaystyle +}$ over ${\displaystyle \cdot }$):

${\displaystyle {\begin{aligned}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{aligned}}}$

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 ${\displaystyle F=H'}$ then ${\displaystyle F_{x}=H'_{x}}$

If ${\displaystyle F=G\cdot H}$ then ${\displaystyle F_{x}=G_{x}\cdot H_{x}}$

If ${\displaystyle F=G+H}$ then ${\displaystyle F_{x}=G_{x}+H_{x}}$

If ${\displaystyle F=G\oplus H}$ then ${\displaystyle F_{x}=G_{x}\oplus H_{x}}$

Characteristics of unate functions:

If F is a unate function and...

If F is positive unate then ${\displaystyle F=x\cdot F_{x}+F_{x'}}$

If F is negative unate then ${\displaystyle F=F_{x}+x'\cdot F_{x'}}$

Boolean difference:

The boolean difference or boolean derivative of the function F with respect to the literal x is defined as:

${\displaystyle {\frac {\partial F}{\partial x}}=F_{x}\oplus F_{x'}}$

Universal quantification:

The universal quantification of F is defined as:

${\displaystyle \forall xF=F_{x}\cdot F_{x'}}$

Existential quantification:

The existential quantification of F is defined as:

${\displaystyle \exists xF=F_{x}+F_{x'}}$

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),[2] and it was "widely applied by Boole and other nineteenth-century logicians".[3]

Claude Shannon mentioned this expansion, among other Boolean identities, in a 1948 paper,[4] 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.[3]

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

• Reed–Muller expansion

• Shannon’s Decomposition Example with multiplexers.
• Optimizing Sequential Cycles Through Shannon Decomposition and Retiming (PDF) Paper on application.