Harman Patil (Editor)

Boole's expansion theorem

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

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

Contents

The terms F x and F x ′ are sometimes called the positive and negative Shannon cofactors, respectively, 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". 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 ( X 1 , X 2 , … , X n ) = X 1 ⋅ f ( 1 , X 2 , … , X n ) + X 1 ′ ⋅ f ( 0 , X 2 , … , X n )

Proof for the statement follows from direct use of mathematical induction, from the observation that f ( X 1 ) = X 1 . f ( 1 ) + X 1 ′ . f ( 0 ) and expanding a 2-ary and n-ary Boolean functions identically.

History

George Boole introduced this expansion in his "Laws of Thought" (1854) as Proposition II, titled "To expand or develop a function involving any number of logical symbols." This methodology was extensively utilized by Boole and other logicians throughout the nineteenth century.

Claude Shannon mentioned this expansion, among other Boolean identities, in a 1948 paper, 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.

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.

References

Boole's expansion theorem Wikipedia
(Text) CC BY-SA