Número mínimo de compuertas NAND necesarias para realizar la función EXOR

La implementación de 4 puertas de la función XOR requiere que la salida de una de las puertas se use dos veces. Que yo sepa, no hay una forma algorítmica directa para encontrar tales soluciones; deben ser "descubiertos".

En cierto sentido, tiene que "des-optimizar" la solución antes de optimizarla, y saber qué paso de desoptimización tiene sentido es una cuestión de intuición. En este caso, requiere la observación * que

$$ A \ cdot \ overline {B} = A \ cdot \ overline {(A \ cdot B)} $$

y

$$ \ overline {A} \ cdot B = \ overline {(A \ cdot B)} \ cdot B $$

y luego darse cuenta de que el término \ $ \ overline {(A \ cdot B)} \ $ para ambas expresiones de la mano derecha puede ser generado por la misma puerta.

* Los detalles:

Desde \ $ A \ cdot \ overline {A} = 0 \ $, puede agregar este término a cualquier expresión sin cambiarlo:

$$ A \ cdot \ overline {B} = A \ cdot \ overline {A} + A \ cdot \ overline {B} $$

Ahora, factoriza la A

$$ \ ldots = A \ cdot (\ overline {A} + \ overline {B}) $$

y aplique DeMorgan's:

$$ \ ldots = A \ cdot \ overline {(A \ cdot B)} $$