Circuit Complexity
Circuit complexity is a measure of how hard it is to express or compute a boolean function.
Boolean Functions
Boolean functions can be classified according to the size or depth of the Boolean circuits that compute them.
A Boolean circuit with $n$ input bits is a directed acyclic graph in which every node is either an input node labelled by one of the $n$ input bits, an AND gate, an OR gate, or a NOT gate. The input node has in-degree 0, the AND gate has in-degree 2,