Esta es la respuesta completa para la segunda, así que no leas el spoiler si aún no quieres todo.
Puedes hacerlo por inducción. Vamos a demostrar que esto es posible con \ $ 5 \ times2 ^ {n-1} -4 \ $ gates, y que esto es mejor que \ $ 3 \ times2 ^ n \ $ gates.
- Puede realizar cualquier circuito lógico de 1 variable con 1 compuertas (una compuerta NO, o no una compuerta NO), y esto es menor o igual a \ $ 5 \ times2 ^ {1-1} -4 = 1 \ $.
- Suponga que puede realizar cualquier función de las variables \ $ n \ $ con \ $ 5 \ times2 ^ {n-1} -4 \ $ gates, anotadas \ $ F (n \ var) \ $. Desea agregar una variable \ $ X \ $. \ $ X \ $ es \ $ 0 \ $ o \ $ 1 \ $, por lo que la siguiente expresión:
\ $ [F_a (n \ var) AND (NOT \ X)] O [(F_b (n \ var) AND \ X] \ $
cubre todas las funciones posibles. Esa función utiliza el siguiente número de puertas:
\ $ 5 \ times2 ^ {n-1} -4 + 1 + 1 + 1 + 5 \ times2 ^ {n-1} -4 + 1 = 5 \ times2 \ times2 ^ n-4 = 5 \ times2 ^ {(n + 1) -1} -4 \ $ para todos \ $ n \ $ mayor que \ $ 0 \ $.
Esto es cierto para \ $ n + 1 \ $.
- Por inducción, la propiedad es verdadera para todos \ $ n \ $, por lo que podemos realizar cualquier función con \ $ 5 \ times2 ^ {n-1} -4 \ $ gates.
- por último,
\ $ 3 \ times2 ^ {n} = 6 \ times2 ^ {n-1} \ gt 5 \ times2 ^ {n-1} \ gt 5 \ times2 ^ {n-1} -4 \ $ para todos \ $ n \ $ mayor que \ $ 0 \ $.
En un punto de vista del circuito, puede ver esta solución como una pirámide de MUX de 2 entradas, con la primera variable en la base de todos los MUX de la primera capa y una fila de MUX por variables adicionales.
editar: formando
edit2: error matemático corregido, probando para \ $ 5 \ times2 ^ {n-1} -4 \ $ en su lugar.