Circuitos booleanos

Los circuitos booleanos también se utilizan como modelo formal para la lógica combinacional en electrónica digital.Los circuitos booleanos se definen en términos de las compuertas lógicas que contienen.Cada compuerta corresponde a alguna función booleana que toma un número fijo de bits como entrada y genera un solo bit.Los circuitos booleanos proporcionan un modelo para muchos componentes digitales utilizados en ingeniería informática, incluidos multiplexores, sumadores y unidades lógicas aritméticas, pero excluyen la lógica secuencial.Un circuito booleano sobre una base B, con n entradas y m salidas, se define como un grafo acíclico dirigido finito.Cada vértice corresponde a una función base o a una de las entradas, y hay un conjunto de exactamente m nodos que están etiquetados como salidas.[1]​ Los bordes también deben tener algún orden, para distinguir entre diferentes argumentos de la misma función booleana.[2]​ Como un caso especial, una fórmula proposicional o expresión booleana es un circuito booleano con un solo nodo de salida en el que todos los demás nodos tienen fan-out de 1.Por lo tanto, un circuito booleano puede considerarse como una generalización que permite subformulas compartidas y salidas múltiples.Una base común para los circuitos booleanos es el conjunto { AND, OR, NOT }, que es funcionalmente completo, es decir, a partir de él se pueden construir todas las demás funciones booleanas.Un circuito en particular actúa solo en entradas de tamaño fijo.En cambio, un lenguaje está representado por una familia de circuitos.Se dice que una familia de circuitos decide un idiomaEn otras palabras, un lenguaje es el conjunto de cadenas que, cuando se aplican a los circuitos correspondientes a sus longitudes, se evalúan como 1.[3]​ Se pueden definir varias medidas de complejidad importantes en los circuitos booleanos, incluida la profundidad del circuito, el tamaño del circuito y el número de alternancias entre las compuertas AND y las compuertas OR.Se sigue directamente del hecho de que los lenguajes enAdemás, el caso es que la inclusión es adecuada (es decir, PAGSEn particular, es útil para investigar problemas relacionados con P versus NP.Por ejemplo, si hay algún lenguaje en NP que no está en P/poly entonces PDos subclases de P/poly que tienen propiedades interesantes por derecho propio son NC y AC .La clase NC es el conjunto de lenguajes que pueden ser resueltos por familias de circuitos que están restringidas no solo a tener un tamaño polinómico sino también a tener una profundidad poli-logarítmica .La clase AC se define de manera similar a NC, sin embargo, las compuertas pueden tener un fan-in ilimitado (es decir, las puertas AND y OR se pueden aplicar a más de dos bits).[6]​ Por lo tanto, este problema se considera "inherentemente secuencial" en el sentido de que probablemente no exista un algoritmo eficiente y altamente paralelo que resuelva el problema.