Teorema de expansión de Shannon (o de Boole) en funciones booleanas

Actualizado el
El teorema de expansión de Shannon dice que cualquier función booleana se puede partir en dos casos según el valor de una de sus variables: lo que vale la función cuando esa variable es 1 y lo que vale cuando es 0. Sirve para simplificar expresiones, para implementar funciones con multiplexores y es la base de los diagramas de decisión binarios (BDD) que usan las herramientas de diseño de chips.
Aunque se le llama «de Shannon», el resultado ya estaba en George Boole, y por eso también se conoce como teorema de expansión de Boole o descomposición de Shannon.
Enunciado y fórmula
Sea f(x1, x2, …, xn) una función booleana. Para cualquier variable x1:
f(x1, …, xn) = x1 · f(1, x2, …, xn) + x1' · f(0, x2, …, xn)
Aquí «·» es el producto lógico (AND), «+» la suma lógica (OR) y x' la negación de x. Las funciones f(1, …) y f(0, …) se llaman cofactores de f respecto de x1; se suelen escribir fx y fx'.
Existe también la forma dual, con producto de sumas:
f = (x1 + f(0, x2, …, xn)) · (x1' + f(1, x2, …, xn))
Demostración
Basta comprobar los dos valores posibles de x1, porque una variable booleana solo puede valer 0 o 1.
- Si x1 = 1, entonces x1' = 0, y el lado derecho queda 1 · f(1, …) + 0 · f(0, …) = f(1, …), que es justo f con x1 = 1.
- Si x1 = 0, entonces x1' = 1, y queda 0 · f(1, …) + 1 · f(0, …) = f(0, …), que es f con x1 = 0.
En los dos casos ambos lados coinciden, así que la igualdad es cierta para todas las entradas. La forma dual se demuestra igual o aplicando el principio de dualidad del álgebra de Boole.
Ejemplos resueltos
Ejemplo 1: simplificar una expresión
Sea f(x, y, z) = xy + x'z + yz. Expandimos respecto de x:
- Cofactor con x = 1: f(1, y, z) = y + 0 + yz = y (por absorción, y + yz = y).
- Cofactor con x = 0: f(0, y, z) = 0 + z + yz = z.
Por el teorema, f = x · y + x' · z. El término yz sobraba: es el llamado término de consenso. Se puede comprobar con la tabla de verdad completa (8 filas): las dos expresiones dan la misma salida en todas.
Ejemplo 2: la función mayoría
La función mayoría de tres entradas vale 1 cuando al menos dos de ellas valen 1: M(a, b, c) = ab + ac + bc. Expandiendo respecto de a:
- M(1, b, c) = b + c + bc = b + c.
- M(0, b, c) = bc.
Resultado: M = a(b + c) + a'bc. Se lee así: si a vale 1, basta que otra entrada valga 1; si a vale 0, hacen falta las otras dos. La forma dual da M = (a + bc)(a' + b + c), que también coincide en las 8 filas.
Ejemplo 3: la puerta XOR
Para f(x, y) = x ⊕ y, los cofactores son f(1, y) = y' y f(0, y) = y. Por tanto x ⊕ y = xy' + x'y, la expresión de la puerta XOR en suma de productos.
Ejemplo 4: llegar a la forma canónica
Si se expande una y otra vez respecto de todas las variables, cada cofactor final es una constante (0 o 1) y se obtiene la suma de minitérminos. Para la mayoría:
M = a'bc + ab'c + abc' + abc
Son exactamente las cuatro filas de la tabla en las que M vale 1: (0,1,1), (1,0,1), (1,1,0) y (1,1,1). Con n variables, la expansión completa tiene como mucho 2n términos.
Aplicaciones en electrónica digital
Multiplexores
Un multiplexor de 2 a 1 con entrada de selección s calcula s' · I0 + s · I1, que es exactamente el lado derecho de la expansión. Por eso cualquier función se puede construir con multiplexores: se conecta x a la selección, el cofactor f(0, …) a I0 y el cofactor f(1, …) a I1. Repitiendo con los cofactores se obtiene un árbol de multiplexores que implementa cualquier función.
Diagramas de decisión binarios (BDD)
Un BDD representa una función como un árbol de preguntas «¿x vale 1?». Cada nodo es una expansión de Shannon: la rama del 1 lleva al cofactor fx y la del 0 al cofactor fx'. Al fusionar los nodos repetidos se obtienen representaciones compactas que se usan en la verificación formal de circuitos y en los resolutores SAT.
Tabla resumen
| Forma | Expresión | Uso |
|---|---|---|
| Suma de productos | f = x · fx + x' · fx' | Multiplexores, minitérminos |
| Producto de sumas (dual) | f = (x + fx') · (x' + fx) | Maxitérminos |
| Con XOR | f = x · fx ⊕ x' · fx' | Circuitos con puertas XOR |
La versión con XOR funciona porque los dos sumandos nunca valen 1 a la vez (uno lleva x y el otro x'), y en ese caso OR y XOR dan lo mismo.
Errores habituales
- Cambiar los cofactores: el que va con x es el de x = 1, no el de x = 0.
- Olvidar simplificar el cofactor antes de seguir expandiendo; la expansión es más útil cuanto más sencillos quedan fx y fx'.
- Confundirlo con las leyes de De Morgan, que sirven para negar expresiones, no para descomponerlas.
Historia y nombre
George Boole presentó la expansión como «Proposición II» en The Laws of Thought (1854), con el título «expandir o desarrollar una función que contiene cualquier número de símbolos lógicos». Claude Shannon la utilizó en 1949, en su artículo «The Synthesis of Two-Terminal Switching Circuits», donde mostró su lectura en redes de conmutación; de ahí que en electrónica se le atribuya a menudo solo a él.
No confundir con el teorema de Shannon-Hartley
Muchas búsquedas de «teorema de Shannon», «fórmula de Shannon» o «límite de Shannon» se refieren a otro resultado, de teoría de la información: la capacidad máxima de un canal con ruido, C = B · log2(1 + S/N), con B el ancho de banda en hercios y S/N la relación señal-ruido en potencia (no en decibelios). Por ejemplo, una línea de 3.000 Hz con S/N = 1.000 (30 dB) admite como mucho C = 3.000 · log2(1.001) ≈ 29.900 bit/s. No tiene relación con la expansión de funciones booleanas.
Si buscas otros resultados del mismo campo, en la lista de teoremas más importantes de las matemáticas hay un apartado de lógica.
Preguntas frecuentes
¿Cuál es la fórmula de la expansión de Shannon?
f = x · f(x=1) + x' · f(x=0). La forma dual es f = (x + f(x=0)) · (x' + f(x=1)).
¿Qué es un cofactor de Shannon?
Es la función que resulta de fijar una variable a 1 (cofactor positivo) o a 0 (cofactor negativo).
¿Es lo mismo que el teorema de Shannon-Hartley?
No. Shannon-Hartley da la capacidad de un canal con ruido, C = B · log2(1 + S/N). La expansión de Shannon descompone funciones booleanas.
¿Para qué sirve en electrónica?
Para implementar cualquier función con multiplexores, para simplificar expresiones y como base de los diagramas de decisión binarios usados en verificación de circuitos.
RELACIONADOS