Circuito (informática)

---

En informática teórica , un circuito es un modelo de cálculo en el que los valores de entrada proceden a través de una secuencia de puertas, cada una de las cuales calcula una función . Los circuitos de este tipo proporcionan una generalización de los circuitos booleanos y un modelo matemático para los circuitos lógicos digitales. Los circuitos se definen por las puertas que contienen y los valores que las puertas pueden producir. Por ejemplo, los valores en un circuito booleano son valores booleanos , y el circuito incluye puertas de conjunción , disyunción y negación . Los valores en un circuito entero son conjuntosde números enteros y las puertas calculan la unión de conjuntos, la intersección de conjuntos y el complemento de conjuntos , así como las operaciones aritméticas de suma y multiplicación .

Un circuito es un triple , donde${\ estilo de visualización (M, L, G)}$

Los vértices del gráfico se llaman puertas . Para cada puerta de entrada en grado , la puerta se puede etiquetar con un elemento de si y solo si está definido en .${\ estilo de visualización g}$ ${\ estilo de visualización i}$${\ estilo de visualización g}$${\ estilo de visualización \ ell}$${\ estilo de visualización L}$${\ estilo de visualización \ ell}$${\ estilo de visualización M ^ {i}}$

Las puertas de entrada en grado 0 se denominan entradas o hojas . Las puertas de grado 0 se llaman salidas . Si hay una arista de puerta a puerta en el gráfico , entonces se llama hijo de . Suponemos que hay un orden en los vértices del gráfico, por lo que podemos hablar del hijo de una puerta cuando es menor que el grado de salida de la puerta.${\ estilo de visualización g}$${\ estilo de visualización h}$${\ estilo de visualización G}$${\ estilo de visualización h}$${\ estilo de visualización g}$${\ estilo de visualización k}$${\ estilo de visualización k}$

El tamaño de un circuito es el número de nodos de un circuito. La profundidad de una puerta es la longitud del camino más largo desde el principio hasta una puerta de salida. En particular, las puertas de grado 0 son las únicas puertas de profundidad 1. La profundidad de un circuito es la profundidad máxima de cualquier puerta. ${\ estilo de visualización g}$${\ estilo de visualización G}$${\ estilo de visualización g}$

Nivel${\ estilo de visualización i}$ es el conjunto de todas las puertas de profundidad . Un circuito nivelado es un circuito en el que los bordes de las puertas de profundidad provienen solo de las puertas de profundidad o de las entradas. En otras palabras, los bordes solo existen entre niveles adyacentes del circuito. El ancho de un circuito nivelado es el tamaño máximo de cualquier nivel.${\ estilo de visualización i}$${\ estilo de visualización i}$${\ estilo de visualización i+1}$

---