Circuitos booleanos

En la teoría de la complejidad computacional y , un circuito booleano es un modelo matemático para circuitos lógicos digitales combinacionales. Una familia de circuitos booleanos puede decidir un lenguaje formal, un circuito para cada longitud de entrada posible. 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. Por ejemplo, un circuito puede contener compuertas AND y OR y compuertas NOT unarias, o estar completamente descrito por compuertas NAND binarias. 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. Son una abstracción que omite muchos aspectos relevantes para el diseño de circuitos lógicos digitales reales, como la , fan-out, glitches, consumo de energía y variabilidad de retardo de propagación .