Shannon Expansion

boolean-algebra

Definition

Shannon Expansion

Shannon expansion, named after Claude Shannon, is a method for decomposing Boolean function into simpler components.

For a given Boolean function $f(x_1,x_2,\dots ,x_n)$ and a selected variable $x_i$, the Boolean function $f$ can be expressed as:

$$f=(x_i\wedge f_{x_i=1})\vee (\neg x_i\wedge f_{x_i=0})$$

where $f_{x_i=1}$ is a positive cofactor and $f_{x_i=0}$ is a negative Cofactor of $f$.

By recursively applying the Shannon expansion to each variable, a Boolean function can be broken down into a disjunctive of conjunctions or a conjunctions of disjunctions.

Example

1. Example:

$$\begin{array}{rlr}f& =a\cdot b+\neg a\cdot c& \\ ⟹f_{a=1}& =1\cdot b+0\cdot c& =b\\ ⟹f_{a=0}& =0\cdot b+1\cdot c& =c\\ f& =a\cdot f_{a=1}+\neg a\cdot f_{a=0}& \\ & =a\cdot b+\neg a\cdot c& \end{array}$$

2. Example:

$$\begin{array}{rl}f& =(\neg a\wedge b\wedge \neg c)\vee (\neg a\wedge b\wedge c)\vee (a\wedge \neg b\wedge c)\vee (a\wedge b\wedge c)\\ f_{a=1}& =\underset{=0}{\underbrace{(0\wedge b\wedge \neg c)}}\vee \underset{=0}{\underbrace{(0\wedge b\wedge c)}}\vee \underset{=\neg b\wedge c}{\underbrace{(1\wedge \neg b\wedge c)}}\vee \underset{=b\wedge c}{\underbrace{(1\wedge b\wedge c)}}\\ & =\cancel{0\vee 0\vee }(\neg b\wedge c)\vee (b\wedge c)\\ & =(\neg b\wedge c)\vee (b\wedge c)\\ f_{a=0}& =\underset{=b\wedge \neg c}{\underbrace{(1\wedge b\wedge \neg c)}}\vee \underset{b\wedge c}{\underbrace{(1\wedge b\wedge c)}}\vee \underset{=0}{\underbrace{(0\wedge \neg b\wedge c)}}\vee \underset{=0}{\underbrace{(0\wedge b\wedge c)}}\\ & =(b\wedge \neg c)\vee (b\wedge c)\cancel{\vee 0\vee 0}\\ & =(b\wedge \neg c)\vee (b\wedge c)\\ f_{a=1,b=1}& =\underset{=0}{\underbrace{(0\wedge c)}}\vee \underset{=c}{\underbrace{(1\wedge c)}}\\ & =0\vee c\\ & =c\\ f_{a=1,b=0}& =\underset{=c}{\underbrace{(1\wedge c)}}\vee \underset{=0}{\underbrace{(0\wedge c)}}\\ & =c\vee 0\\ & =c\\ f_{a=0,b=1}& =\underset{=\neg c}{\underbrace{(1\wedge \neg c)}}\vee \underset{=c}{\underbrace{(1\wedge c)}}\\ & =\neg c\vee c\\ & =1\\ f_{a=0,b=0}& =\underset{=0}{\underbrace{(0\wedge \neg c)}}\vee \underset{=0}{\underbrace{(0\wedge c)}}\\ & =0\vee 0\\ & =0\end{array}$$

By applying the Shannon expansion iteratively, a pattern emerges that can be represented using the If-Then-Else function:

$$f=\text{ITE}(a,\text{ITE}(b,c,c),\text{ITE}(b,1,0))$$

which can be simplified to:

$$f=\text{ITE}(a,c,b)$$

which can then be back-translated to:

$$f=\text{ITE}(a,c,b)=(a\wedge c)\vee (\neg a\wedge b)$$