Shannon's expansion

In mathematics, Shannon's expansion or the Shannon decomposition is a method by which a Boolean function can be represented by the sum of two sub-functions of the original. While often credited to Claude Elwood Shannon, Boole proved this much earlier. Claude Shannon is credited with many other important aspects of Boolean algebra.

Expansion

The Shannon expansion develops the idea that Boolean functions can be reduced by means of the identity:

:$F\; =\; x\; cdot\; F\_x\; +\; x\text{'}\; cdot\; F\_\{x\text{'}\}$

where $F$ is any function and $F\_x$and $F\_\{x\text{'}\}$ are positive and negative Shannon cofactors of $F$, respectively. It is named for Claude Shannon.

A positive Shannon cofactor of function $F$ with respect to variable $x$ is defined as that function with all $x$’s set to $1$. A negative Shannon cofactor is the same, but sets all $x$’s to $0$.

The Shannon expansion theorem is an important idea in Boolean algebra. It paved the way for Binary decision diagrams, Satisfiability solvers, and many other techniques relevant for computer engineering and formal verification of digital circuits.

As presented in Jan.1948 paper, "The Synthesis of Two-Terminal Switching Circuits" [Bell System Technical Journal, vol.28, pp.59-98, original text.] . Simply stated as the expansion of a function as:

:$f(X\_1,\; X\_2,\; dots\; ,\; X\_n)\; =\; X\_1\; cdot\; f(1,\; X\_2,\; dots\; ,\; X\_n)\; +\; X\_1\text{'}\; cdot\; f(0,\; X\_2,\; dots\; ,\; X\_n)$

followed by the expansion for two variables, and noting that expansion can be continued for any number of variables.

Example

Rather than explain it pedantically, here is an example:

Take this as our function:

: $f\; =\; xyz\; +\; xy\text{'}z\; +\; x\text{'}y\text{'}z\; +\; x\text{'}yz\; +\; x\text{'}y\text{'}z\text{'}\; ,$

Now, notice that you can re-write the function in terms of any two variables — namely, a variable and its complement. Observe:

:$f\; =\; x\text{'}g\_x\text{'}\; +\; xg\_x\; ,$

Now, to make the final expression equivalent to our composition of functions, simply apply the distributive theorem to the function about "x":

:$f\; =\; x\text{'}(y\text{'}z\; +\; yz\; +\; y\text{'}z\text{'})\; +\; x(yz\; +\; y\text{'}z)\; ,$

Now have expanded the function "f" about the variable "x".

"x" Variables

In Shannon's expansion the term "x" is very significant but problems can arise in simple equations. What if there were no x variable in one or more of the terms? Problems here can lead to confusion. Dealing with no "x" variable in one or more of the terms can be simple. The solution is not always intuitive.

In Boolean algebra, you can "AND any literal or term with 1", and still achieve the same "truth value". With that in mind, let's look at this function:

:$f\; =\; yz\; +\; xyz\text{'}\; +\; x\text{'}y\text{'}z\; ,$

If we desire to expand around the variable x, we simply don't have enough information in the first term to accomplish this task. So, what do we do? Remember what was said above: AND the literal with 1, or, in this case $(x\text{'}\; +\; x)$.

:$f\; =\; yz(x\text{'}\; +\; x)\; +\; xyz\text{'}\; +\; x\text{'}y\text{'}z\; ,$

Expand:

:$f\; =\; x\text{'}yz\; +\; xyz\; +\; xyz\text{'}\; +\; x\text{'}y\text{'}z\; ,$

This function contains the variable about which we want to expand the expression, so now we should have no problem performing the expansion:

:$f\; =\; x\text{'}\; g\_x\text{'}\; +\; x\; g\_x\; ,$:$f\; =\; x\text{'}(yz\; +\; y\text{'}z)\; +\; x(yz\; +\; yz\text{'})\; ,$

The expansion is complete.

Of course, you can perform Shannon's Expansion about any variable you desire, so long as you can provide for that variable in the expression without changing the truth value of the expression. Also, you can perform multiple expansions of a single function (e.g. about "x", then about "y") or, you can even perform the expansion about many variables at once (e.g. about "xy"). The result is a functionally equivalent expression for the variables involved.

Expanding and minimizing

*You can expand a function
*You can minimize a function

Why make an expression larger? Is Boolean algebra all about minimizing functions?

Consider a logic device called a multiplexer. Multiplexers take "n" select inputs, and 2ⁿ data inputs, and give one output. Once you expand any boolean function about any number of variables, you can use the variables that the function was expanded about as the select inputs, and their respective composed functions as the corresponding data inputs.

References

External links

* [http://homepages.ius.edu/JFDOYLE/c421/html/Chapter6.htm Shannon’s Decomposition] Example with multiplexers.
* [http://www1.cs.columbia.edu/~sedwards/papers/soviani2007optimizing.pdf Optimizing Sequential Cycles Through Shannon Decomposition and Retiming (PDF)] Paper on application.

ee also

*Truth value
*Mathematics
*Boolean algebra (logic)
*Claude Elwood Shannon