El teorema de la expansión de Boole , a menudo denominado expansión o descomposición de Shannon , es la identidad :, dónde es cualquier función booleana , es una variable, es el complemento de , y y están con el argumento establecer igual a y para respectivamente.
Los términos y a veces se denominan cofactores positivos y negativos de Shannon , respectivamente, de con respecto a . Estas son funciones, calculadas por el operador de restricción , y (ver valoración (lógica) y aplicación parcial ).
Se le ha llamado el "teorema fundamental del álgebra de Boole". [1] Además de su importancia teórica, allanó el camino para los diagramas de decisión binaria (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 de ingeniería (especialmente en BBD), la expansión se interpreta como un si-entonces-si no , con la variable siendo la condición y los cofactores siendo las ramas ( Cuándo es cierto y respectivamente Cuándo Es falso). [2]
Declaración del teorema
Una forma más explícita de enunciar el teorema es:
Variaciones e implicaciones
- Formulario XOR
- La declaración también es válida cuando la disyunción "+" es reemplazada por el operador XOR :
- Forma dual
- Hay una forma dual de la expansión de Shannon (que no tiene una forma XOR relacionada):
La aplicación repetida para cada argumento conduce a la forma canónica de suma de productos (SoP) de la función booleana. Por ejemplo para eso sería
Asimismo, la aplicación de la forma dual conduce a la forma canónica del Producto de Sumas (PoS) (usando la ley de distributividad de encima ):
Propiedades de los cofactores
- Propiedades lineales de cofactores:
- Para una función booleana F que se compone de dos funciones booleanas G y H, se cumple lo siguiente:
- Si luego
- Si luego
- Si luego
- Si luego
- Características de las funciones de unte:
- Si F es una función única y ...
- Si F es positivo unte entonces
- Si F es negativo unte entonces
Operaciones con cofactores
- Diferencia booleana:
- La diferencia booleana o derivada booleana de la función F con respecto al literal x se define como:
- Cuantificación universal:
- La cuantificación universal de F se define como:
- Cuantificación existencial:
- La cuantificación existencial de F se define como:
Historia
George Boole presentó esta expansión como su Proposición II, "Para expandir o desarrollar una función que involucre cualquier número de símbolos lógicos", en sus Laws of Thought (1854), [3] y fue "ampliamente aplicada por Boole y otros lógicos ". [4]
Claude Shannon mencionó esta expansión, entre otras identidades booleanas, en un artículo de 1949, [5] y mostró las interpretaciones de la red de conmutación de la identidad. En la literatura sobre el diseño de computadoras y la teoría del cambio, la identidad a menudo se atribuye incorrectamente a Shannon. [6] [4]
Aplicación a circuitos de conmutación.
- Los diagramas de decisión binarios se derivan del uso sistemático de este teorema.
- Cualquier función booleana se puede implementar directamente en un circuito de conmutación utilizando una jerarquía de multiplexor básico mediante la aplicación repetida de este teorema.
Referencias
- ^ Rosenbloom, Paul Charles (1950). Los elementos de la lógica matemática . pag. 5.
- ^ GD Hachtel y F. Somezi (1996), Síntesis lógica y algoritmos de verificación , p. 234
- ^ Boole, George (1854). Una investigación de las leyes del pensamiento: sobre las cuales se basan las teorías matemáticas de la lógica y las probabilidades . pag. 72.
- ^ a b Brown, Frank Markham (2012) [2003, 1990]. Razonamiento booleano - La lógica de las ecuaciones booleanas (reedición de la 2ª ed.). Mineola, Nueva York: Dover Publications, Inc. p. 42. ISBN 978-0-486-42785-0. [1]
- ^ Shannon, Claude (enero de 1949). "La síntesis de circuitos de conmutación de dos terminales" (PDF) . Revista técnica de Bell System . 28 : 59–98 [62]. doi : 10.1002 / j.1538-7305.1949.tb03624.x . ISSN 0005-8580 .
- ^ Perkowski, Marek A .; Grygiel, Stanislaw (1995-11-20), "6. Panorama histórico de la investigación sobre la descomposición" , Estudio de la literatura sobre la descomposición de funciones , Versión IV, Grupo de descomposición funcional, Departamento de Ingeniería Eléctrica, Universidad de Portland, Portland, Oregón Estados Unidos, pág. 21, CiteSeerX 10.1.1.64.1129 (188 páginas)
Ver también
- Expansión Reed-Muller
enlaces externos
- 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 aplicación.