Shannon expansion
From Wikipedia, the free encyclopedia
 |
This article or section may be confusing or unclear for many readers. Please improve the article or discuss this issue on the talk page. This article has been tagged since December 2006. |
The Shannon expansion develops the idea that Boolean functions can be reduced by means of the identity:
- F = x * Fx + x' * Fx',
where F is any function and Fxand Fx' 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.
 |
This mathematics-related article is a stub. You can help Wikipedia by expanding it. |
