Boolean Circuit

Definition

A Boolean circuit C “computes” a (finite) function $f:\{0,1{\}}^n\mapsto \{0,1{\}}^m$ over De Morgan basis
A circuit ensembles is an infinite family of circuits $\mathcal{A}=\{A_n{\}}_{n\in N}$. $A_n$ has n input bits, $\mathcal{A}$ has m bit output, if each $A_n$ has $m(n)$ output bits (i.e., m is a function from N to N, might be constant, e.g., m(n) = 1). Circuit ensemble can handle any input length, i.e., compute any (even infinite) functions, but the description size is infinite!.