Nel dare una definizione formale di circuiti Booleani, [[Heribert Vollmer|Vollmer]] comincia definendo un setinsieme base di funzioni Booleane ''B'', corrispondenti alle porte accettabili nel modello del circuito. Un circuito Booleano su una base ''B'', con ''n'' input e ''m'' output, è definita come un [[grafo aciclico diretto]] finito. Ogni vertice corrisponde o ad una funzione base o ad un input, e c'è un set di esattamente ''m'' nodi che sono etichettati come output.<ref>Vollmer 1999, p. 8.</ref> Gli archi devono anche essere in qualche modo ordinati, per distinguere tra differenti argomenti per la stessa funzione Booleana.<ref>Vollmer 1999, p. 9.</ref>
