Boole's expansion theorem

The Shannon decomposition or Shannon expansion (named after Claude Elwood Shannon) represents a way to represent Boolean functions using their so-called cofactors. The mathematical statement of this decomposition is also referred to as a development set of Shannon. Although the set is named after Shannon, who first used it in 1949, he was about a hundred years previously set by George Boole.

Statement

Any Boolean function can be written as follows:

The so-called co-factors of the function may be used, which are defined as follows:

  • Is the original function where the variable is substituted with the value 1.
  • Is the original function where the variable is substituted with the value 0.

This decomposition is also known as if-then -else normal form ( INF). It is also said that the function " developed by ". Repeating the application of the theorem for an arbitrary function to all its n parameters, we arrive at a representation of the function, which uses only the ∧, ∨ and ¬ operators. The recursive application of the Shannon decomposition thus provides evidence that each Boolean function by means of the operators ∧, ∨ and ¬ can be expressed.

This decomposition result was the development of binary decision diagrams, and thus one of the ways of handling the satisfiability of propositional logic. In addition, the development kit can be used to derive about clip free expressions.

Example

Consider the Boolean function.

This is according to first, then after and finally developed:

View as chart

One can understand the transformation as a multiplexer of a non- gate, two AND and an OR gate. The signal according to which the separation is carried out, the control signal for the multiplexer. Are multiplexed, the two outputs of duplicated logic, wherein the logic of the developed input with a "1 " is applied, while the other is loaded with a "0". Represented as a graph, it looks like this:

309719
de