A circuit is a triplet (M, L, G), where • M is a set of values, • L is a set of gate labels, each of which is a function from M^{i} to M for some non-negative integer i (where i represents the number of inputs to the gate), and • G is a
labelled directed acyclic graph with labels from L. The vertices of the graph are called
gates. For each gate g of
in-degree i, the gate g can be labeled by an element \ell of L if and only if \ell is defined on M^{i}.
Terminology The gates of in-degree 0 are called
inputs or
leaves. The gates of out-degree 0 are called
outputs. If there is an edge from gate g to gate h in the graph G then h is called a
child of g. We suppose there is an order on the vertices of the graph, so we can speak of the kth child of a gate when k is less than or equal to the out-degree of the gate. The
size of a circuit is the number of nodes of a circuit. The
depth of a gate g is the length of the
longest path in G beginning at g up to an output gate. In particular, the gates of out-degree 0 are the only gates of depth 1. The
depth of a circuit is the maximum depth of any gate.
Level i is the set of all gates of depth i. A
levelled circuit is a circuit in which the edges to gates of depth i comes only from gates of depth i + 1 or from the inputs. In other words, edges only exist between adjacent levels of the circuit. The
width of a levelled circuit is the maximum size of any level.
Evaluation The exact value V(g) of a gate g with in-degree i and label l is defined recursively for all gates g. : V(g) = \begin{cases} l & \text{if } g \text{ is an input} \\ l(V(g_1), \dotsc, V(g_i)) & \text{otherwise,} \end{cases} where each g_j is a parent of g. The value of the circuit is the value of each of the output gates. == Circuits as functions ==