Boolean circuit

Definition

Let $n, m \ge 1$. A Boolean circuit with $n$ inputs and $m$ outputs is a finite directed graph $C$ without directed cycles, with the following labels.

1. Each vertex of in-degree $0$ is an input vertex labelled by a variable $x_1, \dots, x_n$ or by a constant $0$ or $1$.
2. Each other vertex is a gate labelled $\wedge$ or $\vee$ with in-degree $2$, or $\neg$ with in-degree $1$.
3. A list of $m$ vertices is marked as the outputs.

For $a \in \set{0,1}^n$, each vertex $v$ gets a value $v(a) \in \set{0, 1}$, defined along the edges since there are no cycles. An input vertex labelled $x_i$ gets $a_i$, and a constant gets its own value. A gate gets the conjunction, disjunction or negation of the values of its in-neighbours. The circuit computes the Boolean function $f_C \colon \set{0,1}^n \to \set{0,1}^m$ whose value at $a$ is the list of values of the outputs. The size of $C$ is the number of gates, and the depth is the largest number of edges on a directed path.