En el primer capítulo de Elements of Computing Systems , se le pide al lector que implemente puertas lógicas básicas como No, Y, O, Xor, así como un multiplexor y des-multiplexor de 2 entradas. Los autores instruyen al lector para que construya sus puertas utilizando la puerta universal NAND como base.
Puedo construir todas las puertas solicitadas utilizando las puertas NAND sin problema. Al usar tablas de verdad y la ley de DeMorgan, he minimizado las puertas lo más posible (por ejemplo, Xor puede representarse mínimamente usando solo 4 puertas NAND, al igual que un chip Mux de 2 entradas).
En aras del rigor, decidí construir las puertas utilizando la otra puerta universal: NOR. Al hacerlo, noté que las representaciones de NAND y NOR están bastante ligadas en términos de complejidad. Por ejemplo, las puertas Y requieren 2 puertas NAND o 3 puertas NOR, pero esto es contrarrestado por puertas O que necesitan 2 puertas NOR o 3 puertas NAND.
Para las 16 funciones booleanas que existen para 2 entradas, NAND y NOR terminan vinculados. Ninguna de las dos puertas es superior en términos de minimizar la complejidad. Sin embargo, esto no parece mantenerse cuando se construye el chip Mux.
Puedo construir el chip Mux en 4 puertas NAND. El chip de multiplexor (DMux) se puede construir en 5 puertas NAND o 4 puertas NOR. El reconocimiento de patrones de mi cerebro quiere muy mal pensar que el chip Mux debe tener una representación NOR en solo 5 puertas, por lo que Mux y DMux son otro conjunto de pares atados, dejando las puertas NAND y NOR nuevamente atadas.
Pero por más que lo intente, no puedo encontrar una manera de implementar un chip Mux en menos de 7 NOR gates .
¿Me estoy perdiendo algún truco de minimización (como con las máscaras en NAND-Xor o NOR-Xnor)?