Teorema de expansión de Boole

El teorema de expansión de Boole , a menudo denominado expansión de Shannon o descomposición de Shannon , es la identidad${\displaystyle F=x\cdot F_{x}+x'\cdot F_{x'}}$, dónde${\displaystyle F}$es cualquier función booleana ,${\displaystyle x}$es una variable,${\displaystyle x'}$es el complemento de${\displaystyle x}$, y${\displaystyle F_{x}}$y${\displaystyle F_{x'}}$son${\displaystyle F}$con el argumento${\displaystyle x}$establecer igual a${\displaystyle 1}$y a${\displaystyle 0}$respectivamente.

Los términos${\displaystyle F_{x}}$y${\displaystyle F_{x'}}$a veces se les llama cofactores de Shannon positivo y negativo , respectivamente, de${\displaystyle F}$con respecto a${\displaystyle x}$Estas son funciones, calculadas por el${\displaystyle \operatorname {restrict} }$operador,${\displaystyle \operatorname {restrict} (F,x,0)}$y${\displaystyle \operatorname {restrict} (F,x,1)}$.

El teorema ha sido denominado el "teorema fundamental del álgebra booleana". ^{[ 1 ]} Además de su importancia teórica, allanó el camino para los diagramas de decisión binarios (BDD), los solucionadores de satisfacibilidad y muchas otras técnicas relevantes para la ingeniería informática y la verificación formal de circuitos digitales. En tales contextos, particularmente en los BDD, la expansión se interpreta como un if-then-else , con la variable${\displaystyle x}$siendo la condición y los cofactores las ramas (${\displaystyle F_{x}}$cuando${\displaystyle x}$es cierto y respectivamente${\displaystyle F_{x'}}$cuando${\displaystyle x}$es falso). ^{[ 2 ]}

Una forma más explícita de enunciar el teorema es:

${\displaystyle 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})}$

Forma XOR

La afirmación también se cumple cuando la disyunción "+" se reemplaza por el operador XOR :

${\displaystyle f(X_{1},X_{2},\dots ,X_{n})=X_{1}\cdot f(1,X_{2},\dots ,X_{n})\oplus X_{1}'\cdot f(0,X_{2},\dots ,X_{n})}$

Forma dual

Existe una forma dual de la expansión de Shannon (que no tiene una forma XOR relacionada):

${\displaystyle f(X_{1},X_{2},\dots ,X_{n})=(X_{1}+f(0,X_{2},\dots ,X_{n}))\cdot (X_{1}'+f(1,X_{2},\dots ,X_{n}))}$

La aplicación repetida para cada argumento conduce a la forma canónica de suma de productos (SoP) de la función booleana.${\displaystyle f}$Por ejemplo, para${\displaystyle n=2}$eso sería

${\displaystyle {\begin{aligned}f(X_{1},X_{2})&=X_{1}\cdot f(1,X_{2})+X_{1}'\cdot f(0,X_{2})\\&=X_{1}X_{2}\cdot f(1,1)+X_{1}X_{2}'\cdot f(1,0)+X_{1}'X_{2}\cdot f(0,1)+X_{1}'X_{2}'\cdot f(0,0)\end{aligned}}}$

Asimismo, la aplicación de la forma dual conduce a la forma canónica Producto de Sumas (PoS) (utilizando la ley de distributividad de${\displaystyle +}$encima${\displaystyle \cdot }$):

${\displaystyle {\begin{aligned}f(X_{1},X_{2})&=(X_{1}+f(0,X_{2}))\cdot (X_{1}'+f(1,X_{2}))\\&=(X_{1}+X_{2}+f(0,0))\cdot (X_{1}+X_{2}'+f(0,1))\cdot (X_{1}'+X_{2}+f(1,0))\cdot (X_{1}'+X_{2}'+f(1,1))\end{aligned}}}$

Propiedades lineales de los cofactores:

Para una función booleana F compuesta por dos funciones booleanas G y H, se cumplen las siguientes condiciones:

Si${\displaystyle F=H'}$entonces${\displaystyle F_{x}=H'_{x}}$

Si${\displaystyle F=G\cdot H}$entonces${\displaystyle F_{x}=G_{x}\cdot H_{x}}$

Si${\displaystyle F=G+H}$entonces${\displaystyle F_{x}=G_{x}+H_{x}}$

Si${\displaystyle F=G\oplus H}$entonces${\displaystyle F_{x}=G_{x}\oplus H_{x}}$

Características de las funciones no saturadas:

Si F es una función no neutra y...

Si F es positivo entonces${\displaystyle F=x\cdot F_{x}+F_{x'}}$

Si F es negativo entonces${\displaystyle F=F_{x}+x'\cdot F_{x'}}$

Diferencia booleana:

La diferencia booleana o derivada booleana de la función F con respecto al literal x se define como:

${\displaystyle {\frac {\partial F}{\partial x}}=F_{x}\oplus F_{x'}}$

Cuantificación universal:

La cuantificación universal de F se define como:

${\displaystyle \forall xF=F_{x}\cdot F_{x'}}$

Cuantificación existencial:

La cuantificación existencial de F se define como:

${\displaystyle \exists xF=F_{x}+F_{x'}}$

George Boole presentó esta expansión como su Proposición II, "Expandir o desarrollar una función que involucre cualquier número de símbolos lógicos", en sus Leyes del Pensamiento (1854), ^{[ 3 ]} y fue "ampliamente aplicada por Boole y otros lógicos del siglo XIX". ^{[ 4 ]}

Claude Shannon mencionó esta expansión, entre otras identidades booleanas, en un artículo de 1949, ^{[ 5 ]} y mostró las interpretaciones de la identidad en el contexto de las redes de conmutación. En la literatura sobre diseño de computadoras y teoría de la conmutación, la identidad se atribuye a menudo erróneamente a Shannon. ^{[ 6 ] [ 4 ]}

1. Los diagramas de decisión binaria se derivan del uso sistemático de este teorema.
2. Cualquier función booleana puede implementarse directamente en un circuito de conmutación utilizando una jerarquía de multiplexores básicos mediante la aplicación repetida de este teorema.

• expansión de Reed-Müller

• Ejemplo de descomposición de Shannon con multiplexores.
• Optimización de ciclos secuenciales mediante descomposición de Shannon y reajuste de tiempos (PDF). Documento sobre la aplicación.