Representación de Lupanov
La representación ( k , s ) de Lupanov , llamada así por Oleg Lupanov , es una forma de representar circuitos booleanos para mostrar que el recíproco del efecto Shannon . Shannon había demostrado que casi todas las funciones booleanas de n variables necesitan un circuito de tamaño de al menos 2 n n −1 . El recíproco es que:
Todas las funciones booleanas de n variables se pueden calcular con un circuito de como máximo 2 n n −1 + o(2 n n −1 ) puertas.
La idea es representar los valores de una función booleana ƒ en una tabla de 2k filas, representando los posibles valores de las k primeras variables x 1 , ..., , x k , y 2 n − k columnas representando los valores de las otras variables.
Además, sea el conjunto de las columnas cuya intersección con es .
