Expansión Shannon

En matemáticas , la descomposición de Shannon o descomposición de Shannon en una variable es un método para representar una función booleana de variables como una suma de dos subfunciones de otras variables. Aunque este método a menudo se atribuye a Claude Shannon , Boole lo demostró mucho antes, y la posibilidad misma de tal expansión en cualquiera de las variables se deriva directamente de la posibilidad de definir cualquier función booleana utilizando la tabla de verdad . $x_{yo}$ $norte$ $(n-1)$

Descomposición

La expansión de Shannon en términos de una variable se basa en el hecho de que la tabla de verdad para una función booleana de variables binarias se puede dividir en dos partes, de modo que la primera parte contiene solo aquellas combinaciones de entrada en las que la variable siempre toma el valor , y la segunda parte contiene solo aquellas combinaciones de entrada combinaciones en las que la variable siempre toma el valor (y su valor invertido toma el valor ). Como resultado, se vuelve válida la siguiente identidad , llamada expansión de Shannon: $x_{yo}$ $norte$ $x_{yo}$ $una$ $x_{yo}$ ${\ estilo de visualización 0}$ ${\sobrelínea {x_{i))}$ $una$

f(x)=x_{i}\cdot f_{x_{i}}(x)+{\overline {x_{i}}}\cdot f_{\overline {x_{i}}}(x )=({\overline {x_{i}}}+f_{x_{i}}(x))\cdot ({x_{i}}+f_{\overline {x_{i}}}(x))

donde es la función booleana a expandir, y son los valores no invertidos e invertidos de la variable con respecto a la cual se realiza la expansión, y y son respectivamente el complemento positivo y negativo de la función con respecto a la variable . En la expansión de Shannon, los símbolos y denotan las operaciones de conjunción ("Y", Y) y disyunción ("O", O), respectivamente, pero la identidad sigue siendo válida cuando se reemplaza la disyunción por disyunción estricta (adición módulo 2, exclusiva " OR", XOR), ya que los términos nunca toman el valor verdadero al mismo tiempo (porque el complemento positivo se combina por conjunción con , y el complemento negativo se combina por conjunción con su inverso ). $f(x)$ $x_{yo}$ ${\sobrelínea {x_{i))}$ ${\ Displaystyle f_ {x_ {i}} (x)}$ $f_{\overline {x_{i))}(x)$ $f(x)$ $x_{yo}$ $\cdot$ $+$ ${\ Displaystyle f_ {x_ {i}} (x)}$ $x_{yo}$ $f_{\overline {x_{i))}(x)$ ${\sobrelínea {x_{i))}$

El complemento positivo está determinado por la parte de la tabla de verdad en la que la variable siempre toma un valor (y su valor invertido toma el valor de ): ${\ Displaystyle f_ {x_ {i}} (x)}$ $x_{yo}$ $una$ ${\sobrelínea {x_{i))}$ ${\ estilo de visualización 0}$

f_{x_{i}}(x)=f(x_{1},...,x_{i-1},1,x_{i+1},...,x_{n})

El complemento negativo lo determina el resto de la tabla, donde la variable siempre toma un valor (y el valor invertido toma un valor de ): $f_{\overline {x_{i))}(x)$ $x_{yo}$ ${\ estilo de visualización 0}$ ${\sobrelínea {x_{i))}$ $una$

f_{\overline {x_{i}}}(x)=f(x_{1},...,x_{i-1},0,x_{i+1},...,x_ {norte})

El teorema de descomposición de Shannon, a pesar de su obviedad, es una idea importante en el álgebra booleana para representar funciones booleanas como diagramas de decisión binarios , resolver el problema de la satisfacibilidad de las fórmulas booleanas e implementar muchas otras técnicas relacionadas con la ingeniería informática y la verificación formal de circuitos digitales. .

En el artículo "La síntesis de circuitos de conmutación de dos terminales" [1] , Shannon describió la descomposición de una función con respecto a una variable como: $x_{1}$

f(x_{1},x_{2},\puntos,x_{n})=x_{1}\cdot f(1,x_{2},\puntos,x_{n})+{\ superponer {x_{1}}}\cdot f(0,x_{2},\dots,x_{n})

seguido de expansión en dos variables, y señaló que la expansión podría continuar en cualquier número de variables.

Ejemplo de descomposición

Sea una función booleana de tres variables , y , dada como una forma normal disyuntiva perfecta , es decir, como una disyunción de conjunciones elementales, cada una de las cuales contiene cada variable o su complemento (inversión) en el mismo orden: $X$ $y$ $z$

f=x\cdot y\cdot z+x\cdot {\overline {y}}\cdot z+{\overline {x}}\cdot {\overline {y}}\cdot z+{\overline {x }}\cdot y\cdot z+{\overline {x}}\cdot {\overline {y}}\cdot {\overline {z}}

Para la expansión en una variable, esta función se puede reescribir como una suma: $X$

f=x\cdot g_{x}+{\overline {x}}\cdot g_{\overline {x}}

habiendo obtenido la expansión de una función booleana en una variable simplemente aplicando la propiedad distributiva para una variable y su complemento (inversión) : $F$ $X$ $X$ $X'$

f=x(y\cdot z+{\overline {y}}\cdot z)+{\overline {x}}({\overline {y}}\cdot z+y\cdot z+{\overline { y))\cdot {\overline {z)))

De igual forma, la expansión de la función en términos de la variable o se realiza : $F$ $y$ $z$

f=y(x\cdot z+{\overline {x}}\cdot z)+{\overline {y}}(x\cdot z+{\overline {x}}\cdot z+{\overline {x ))\cdot {\overline {z)))

f=z(x\cdot y+x\cdot {\overline {y}}+{\overline {x}}\cdot {\overline {y}}+{\overline {x}}\cdot { \overline {y)))+{\overline {z}}({\overline {x}}\cdot {\overline {y}})

A su vez, para cada una de las funciones restantes en un número menor de variables, se puede continuar la expansión en una de las variables restantes.

Generalización

La variable en la expansión de una función booleana puede ser no solo variables individuales incluidas en esta función, sino cualquier condición de multiplexación. Por ejemplo, se sabe expansión por expresión (x > y) y su negación.

Véase también

Notas

↑ Shannon, Claude E. La síntesis de los circuitos de conmutación de dos terminales // Boletín técnico del Bell System : diario. — vol. 28 . - Pág. 59-98 .

Enlaces

Ejemplo de descomposición de Shannon con multiplexores.
Optimización de ciclos secuenciales a través de la descomposición y reprogramación de Shannon (PDF) Documento sobre la solicitud.