Función booleana y circuitos lógicos

-1

Tengo a mi disposición: 2 entradas AND & O puertas lógicas y 1 entrada NO puertas lógicas.

Necesito probar (o refutar) que:

1) Cada función booleana en 3 variables (todas las 256 de ellas) se puede representar en un circuito lógico con máximo de 10 puertas lógicas (AND, OR y amp; NO)

2) Cada función booleana en n variables (todas \ $ 2 ^ {(2 ^ n)} \ $ de ellas) se pueden representar en un circuito lógico con máx. de \ $ 3 \ times 2 ^ n \ $ puertas lógicas

¿Desde dónde debo empezar? La ayuda sería muy apreciada.

    
pregunta Thea Chaos

2 respuestas

1

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.

    
respondido por el pserra
0

Para el primero, puedes intentar crear el peor caso posible en la tabla de Karnaugh.

  

como \ $ \ bar A * B * C + A * \ bar B * C + A * B * \ bar C + \ bar A * \ bar B * \ bar C \ $

  

Esta función ya no se puede simplificar, pero no tengo una prueba formal. Todos los factores son independientes entre sí. Esta expresión requiere al menos 3 NOTs, 8 ANDs y 3 ORs, por lo que 14 puertas.

    
respondido por el pserra

Lea otras preguntas en las etiquetas