Laning and Zierler system: Difference between revisions

From formulasearchengine
Jump to navigation Jump to search
No edit summary
 
en>Derek farn
m Missing opening [
 
Line 1: Line 1:
The author's name is Christy Brookins. To perform lacross is 1 of the things she enjoys most. I am an invoicing officer and I'll be promoted quickly. Some time in the past he chose to live in North Carolina and he doesn't strategy on changing it.<br><br>Also visit my web blog: psychic solutions by lynne ([https://www-ocl.gist.ac.kr/work/xe/?document_srl=605236 Learn Alot more Here])
'''Boole's expansion theorem''', often referred to as the '''Shannon expansion''' or '''decomposition''', is the [[Identity (mathematics)|identity]]: <math>F = x \cdot F_x + x' \cdot F_x'</math>, where <math>F</math> is any [[Boolean function]] and <math>F_x</math>and <math>F_x'</math> are <math>F</math> with the argument <math>x</math> equal to <math>1</math> and to <math>0</math> respectively.
 
The terms <math>F_x</math> and <math>F_x'</math> are sometimes called the positive and negative '''Shannon cofactors''' of <math>F</math> with respect to <math>x</math>. These are functions, computed by '''restrict''' operator, <math>restrict(F, x, 0)</math> and <math>restrict(F, x, 1)</math> (see [[valuation (logic)]] and [[partial application]]).
 
It has been called the "fundamental theorem of Boolean algebra".<ref>Paul C. Rosenbloom, ''The Elements of Mathematical Logic'', 1950, p. 5</ref> Besides its theoretical importance, it paved the way for [[binary decision diagram]]s, [[Boolean satisfiability problem|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:
 
: <math>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)</math>
 
==History==
[[George Boole]] presented this expansion as his Proposition II, "To expand or develop a function involving any number of logical symbols", in his ''[[The Laws of Thought|Laws of Thought]]'' (1854),<ref>George Boole, ''An Investigation of the Laws of Thought: On which are Founded the Mathematical Theories of Logic and Probabilities'', 1854, p. 72 [http://books.google.com/books?id=SWgLVT0otY8C&pg=PA73&dq=to+expand+or+develop+a+function full text at Google Books]</ref> and it was "widely applied by Boole and other nineteenth-century logicians".<ref name="brown">Frank Markham Brown, ''Boolean Reasoning: The Logic of Boolean Equations'', 2nd edition, 2003, p. 42</ref>
 
[[Claude Shannon]] mentioned this expansion, among other Boolean identities, in a 1948 paper,<ref>Claude Shannon, "The Synthesis of Two-Terminal Switching Circuits", ''Bell System Technical Journal'' '''28''':59–98, [http://www3.alcatel-lucent.com/bstj/vol28-1949/articles/bstj28-1-59.pdf full text], p. 62</ref> and showed the switching network interpretations of the identity.  In the literature of computer design and switching theory, it is often attributed to Shannon.<ref name="brown" />
 
==Application to switching circuits==
 
It can be implemented directly in a [[switching circuit theory|switching circuit]] using a [[multiplexer]].
 
==Notes==
<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.
 
[[Category:Boolean algebra]]

Latest revision as of 03:43, 4 October 2013

Boole's expansion theorem, often referred to as the Shannon expansion or decomposition, is the identity: F=x⋅Fx+x′⋅Fx′, where F is any Boolean function and Fxand Fx′ are F with the argument x equal to 1 and to 0 respectively.

The terms Fx and Fx′ are sometimes called the positive and negative Shannon cofactors of F with respect to x. These are functions, computed by restrict operator, restrict(F,x,0) and 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:

f(X1,X2,…,Xn)=X1⋅f(1,X2,…,Xn)+X1′⋅f(0,X2,…,Xn)

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, it is often attributed to Shannon.[3]

Application to switching circuits

It can be implemented directly in a switching circuit using a multiplexer.

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. ↑ 3.0 3.1 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

External links

Retrieved from "https://en.formulasearchengine.com/index.php?title=Laning_and_Zierler_system&oldid=11025"