Convierta de forma óptima (pequeña) expresiones booleanas en la forma NOR a mano

2

¿Hay una manera de convertir fácilmente una expresión booleana con solo unas pocas variables en una forma NOR?

Tomemos el medio sumador como ejemplo:

a b | sum
---------
0 0 | 0
0 1 | 1
1 0 | 1
1 1 | 0

La suma de productos es: $$ sum = \ overline {a} b + a \ overline {b} $$

Si lo convierto a una forma que solo involucra puertas NAND con 2 entradas, obtengo:

$$ sum = \ overline {a} b + a \ overline {b} = \ overline {\ overline {\ overline {a} b + a \ overline {b}}} = \ overline {\ overline {\ overline {a} b + a \ overline {b}} + 0} = \ overline {\ overline {\ overline {a + \ overline {b + 0}} + \ overline {\ overline {a + 0} + b} } + 0} $$

Cuento con 6 puertas NOR.

Sin embargo, si primero escribo la expresión booleana como un producto de sumas: $$ sum = (a + b) \ cdot (\ overline {a} + \ overline {b}) = \ overline {\ overline {a + b} + \ overline {\ overline {a} + \ overline {b} }} = \ overline {\ overline {a + b} + \ overline {\ overline {a + 0} + \ overline {b + 0}}} $$

Ahora, solo hay 5 puertas NOR.

Supongo que este es un problema de optimización considerable (como sugiere este documento , me gustaría preguntar si hay una manera de 'optimizarlo' en pequeñas expresiones booleanas (por ejemplo, < 3 variables).

Además, me gustaría una respuesta con respecto a la misma pregunta con NAND, así como el mismo problema que aparece allí también.

    
pregunta CMOS

1 respuesta

1

Cuestiono el valor real de su pregunta, ya que nadie tiene solo NOR gates simples para trabajar en la práctica. Hay algoritmos para encontrar soluciones minimizadas casi óptimas para expresiones menos triviales. enlace

La fuerza bruta es el mejor enfoque para un problema pequeño, me temo.

    
respondido por el Sean Houlihane

Lea otras preguntas en las etiquetas