Circuitos booleanos

Na teoria da complexidade computacional e , um circuito booliano é um modelo matemático para circuitos lógicos digitais. Uma linguagem formal pode ser decidida por uma família de circuitos boolianos, um circuito para cada comprimento de entrada possível. Circuitos boolianos também são usados em modelos formais para lógica combinacional em eletrônica digital. Circuitos boolianos são definidos em termos das portas lógicas que contém. Por exemplo, um circuito pode conter as funções binárias das portas AND e OR, e função unária da porta NOT, ou ser inteiramente descrita por portas binárias NAND. Cada porta corresponde a alguma função booliana que recebe um número fixo de bits como input e devolve um único bit como output. Circuitos boolianos provém um modelo para muitos componentes digitais usados em engenharia da computação, incluindo multiplexadores, , e unidades lógicas e aritméticas.