Shannon decomposition

The Shannon decomposition or Shannon expansion (named after Claude Elwood Shannon ) is a way of representing Boolean functions using their so-called cofactors. The mathematical statement about this decomposition is also called Shannon's expansion theorem. Although the phrase is named after Shannon, who first used it in 1949, it was created by George Boole about a hundred years earlier .

statement

Any Boolean function can be broken down as follows: ${\displaystyle F(x_{1},x_{2},\ldots ,x_{n})}$

${\displaystyle F(x_{1},x_{2},\ldots ,x_{n})=x_{i}F(x_{1},\ldots ,x_{i-1},1,x_{i+1},\ldots ,x_{n})\vee {\overline {x}}_{i}F(x_{1},\ldots ,x_{i-1},0,x_{i+1},\ldots ,x_{n})}$

or shorter using the so-called cofactors:

${\displaystyle F(x_{1},x_{2},\ldots ,x_{n})=x_{i}F_{x_{i}}\vee {\overline {x}}_{i}F_{{\overline {x}}_{i}}}$

The cofactors and are determined by partial evaluation of , i. H. Insertion of the variable defined: ${\displaystyle F_{x_{i}}}$ ${\displaystyle F_{{\overline {x}}_{i}}}$ ${\displaystyle F(x_{1},\ldots ,x_{n})}$ ${\displaystyle x_{i}}$

${\displaystyle {\begin{aligned}F_{x_{i}}&\equiv F(x_{1},\ldots ,x_{i-1},1,x_{i+1},\ldots ,x_{n})\\[3pt]F_{{\overline {x}}_{i}}&\equiv F(x_{1},\ldots ,x_{i-1},0,x_{i+1},\ldots ,x_{n})\\\end{aligned}}}$

This decomposition is also known as If-then-Else normal form (INF). It is also said that the function is " developed". If one repeats the application of the theorem for any function to all of its n parameters, one arrives at a representation of the function which exclusively uses the operators ∧, ∨ and ¬. The recursive application of the Shannon decomposition thus provides a proof that every Boolean function can be expressed using the operators ∧, ∨ and ¬. ${\displaystyle f}$ ${\displaystyle x_{i}}$ ${\displaystyle f}$

This decomposition led, among other things, to the development of binary decision diagrams and thus to one of the possibilities for processing the satisfiability problem of propositional logic . In addition, the expansion theorem can be used to derive expressions without brackets.

example

The Boolean function is given . ${\displaystyle y=f(x_{1},x_{2},x_{3})=x_{1}x_{2}{\overline {x_{3}}}\vee {\overline {x_{1}}}x_{2}\vee {\overline {x_{2}}}x_{3}}$

This should first be developed gradually , then gradually and finally : ${\displaystyle x_{1}}$ ${\displaystyle x_{2}}$ ${\displaystyle x_{3}}$

${\displaystyle y}$	${\displaystyle =x_{1}[x_{2}{\overline {x_{3}}}\vee {\overline {x_{2}}}x_{3}]\vee {\overline {x_{1}}}[x_{2}\vee {\overline {x_{2}}}x_{3}]}$		(Development after ) ${\displaystyle x_{1}}$
	${\displaystyle =x_{1}[x_{2}({\overline {x_{3}}})\vee {\overline {x_{2}}}(x_{3})]\vee {\overline {x_{1}}}[x_{2}(1)\vee {\overline {x_{2}}}(x_{3})]}$		(Development after ) ${\displaystyle x_{2}}$
	${\displaystyle =x_{1}[x_{2}({\overline {x_{3}}})\vee {\overline {x_{2}}}(x_{3})]\vee {\overline {x_{1}}}[x_{2}(x_{3}\vee {\overline {x_{3}}})\vee {\overline {x_{2}}}(x_{3})]}$		(Development after ) ${\displaystyle x_{3}}$
	${\displaystyle =x_{1}x_{2}{\overline {x_{3}}}\vee x_{1}{\overline {x_{2}}}x_{3}\vee {\overline {x_{1}}}x_{2}x_{3}\vee {\overline {x_{1}}}x_{2}{\overline {x_{3}}}\vee {\overline {x_{1}}}{\overline {x_{2}}}x_{3}}$		(Application of the distributive law)

Representation as a diagram

The conversion can also be understood as a multiplexer consisting of a non-gate, two ANDs and an OR gate. The signal according to which the decomposition is carried out is the control signal for the multiplexer. The two outputs of the duplicated logic are multiplexed, whereby a “1” is applied to one logic at the developed input, while a “0” is applied to the other. Shown as a diagram, it looks like this:

Individual evidence

1. ^ CE Shannon: The synthesis of two-terminal switching circuits . In: Bell System Technical Journal . tape 28 , no. 1 , 1949, p. 59-98 .
2. ↑ G. Boole: The calculus of logic . In: Cambridge and Dublin Mathematical Journal . tape 3 , no. 1848 , 1848, pp. 183–198 ( PDF [accessed November 26, 2012]).