Circuiti booleani

Un circuito booleano è un modello matematico di computazione usato nello studio della teoria della complessità computazionale. Questi circuiti sono principalmente oggetto di studi nella complessità dei circuiti e sono dei tipi speciali di circuiti; un linguaggio formale può essere deciso da una famiglia di circuiti booleani, un circuito per ogni possibile lunghezza di input. In aggiunta, essi sono usati come modello formale per in elettronica digitale. I circuiti booleani sono definiti in termini di che essi contengono. Ad esempio, un circuito potrebbe contenere porte AND e OR e porte NOT , o essere interamente descritti da binarie. Ogni porta corrisponde a qualche funzione booleana che prende k bit di input e invia in output un singolo bit.