A Boolean circuit is a finite acyclic digraph of logical gates that computes a Boolean function. Inputs are Boolean variables or constants, and each internal gate applies a specified Boolean operation to the values on its incoming wires. Its depth is the longest number of gate layers along an input-to-output path. Size and permitted gate arities must be specified when comparing circuits. A formula is the special case without shared subcomputations.
For depth-three OR-AND-OR circuits, let 
be the minimum total number of AND and OR gates needed
to compute 
exactly. All bottom gates and the output gate are counted; input negations are free,
and fan-in and fan-out are unrestricted.
