# Boole's expansion theorem

(Redirected from Shannon expansion)

Boole's expansion theorem, often referred to as the Shannon expansion or decomposition, is the identity: ${\displaystyle F=x\cdot F_{x}+x'\cdot F_{x}'}$, where ${\displaystyle F}$ is any Boolean function, ${\displaystyle x}$ is a variable, ${\displaystyle x'}$ is the complement of ${\displaystyle x}$, and ${\displaystyle F_{x}}$and ${\displaystyle F_{x}'}$ are ${\displaystyle F}$ with the argument ${\displaystyle x}$ equal to ${\displaystyle 1}$ and to ${\displaystyle 0}$ respectively.

The terms ${\displaystyle F_{x}}$ and ${\displaystyle F_{x}'}$ are sometimes called the positive and negative Shannon cofactors, respectively, of ${\displaystyle F}$ with respect to ${\displaystyle x}$. These are functions, computed by restrict operator, ${\displaystyle \operatorname {restrict} (F,x,0)}$ and ${\displaystyle \operatorname {restrict} (F,x,1)}$ (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, satisfiability solvers, and many other techniques relevant to computer engineering and formal verification of digital circuits.

## Statement of the 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})}$

Proof for the statement follows from direct use of mathematical induction, from the observation that ${\displaystyle f(X_{1})=X_{1}.f(1)+X_{1}'.f(0)}$ and expanding a 2-ary and n-ary Boolean functions identically.

## Variations and implications

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}}}

## Properties of Cofactors

Linear Properties of Cofactors:
For a boolean function H which is made up of two boolean functions F and G 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 H is a unate function and...
If H is positive unate then ${\displaystyle F=x\cdot F_{x}+F_{x}'}$
If H is negative unate then ${\displaystyle 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:
${\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}'}$

## 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),[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]

## Application to switching circuits

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.

## Notes

1. ^ Paul C. Rosenbloom, The Elements of Mathematical Logic, 1950, p. 5
2. ^ George Boole, An Investigation of the Laws of Thought: On which are Founded the Mathematical Theories of Logic and Probabilities, 1854, p. 72 full text at Google Books
3. ^ a b Frank Markham Brown, Boolean Reasoning: The Logic of Boolean Equations, 2nd edition, 2003, p. 42
4. ^ Claude Shannon, "The Synthesis of Two-Terminal Switching Circuits", Bell System Technical Journal 28:59–98, full text, p. 62