Lecture 2: Boolean Circuits

Boolean circuit

A Boolean circuit with \(n\) inputs and \(1\) output is a directed acyclic graph that consists of the following kind of nodes:

• Input nodes, labeled \(1,\ldots,n\), without ingoing edges (sources).
• Any number of gates, labeled with \({\mathrm{\scriptstyle NOT}}\), \({\mathrm{\scriptstyle AND}}\), \({\mathrm{\scriptstyle OR}}\).
  • All \({\mathrm{\scriptstyle AND}}\), \({\mathrm{\scriptstyle OR}}\) gates have two incoming edges.
  • All \({\mathrm{\scriptstyle NOT}}\) gates have one incoming edge.
• One output gate, without outgoing edges (sink). (All other gates have at least one outgoing edge.)

Circuit computation

Suppose we assign Boolean values \(x_1,\ldots,x_n\) to the input nodes of a circuit. Then, we can propagate these values through the gates of the circuit by applying the corresponding Boolean operations.

More formally, we would process the gates of the circuit in topological order. To process a gate \(u\) labeled with a Boolean operation \(T\in \{ {\mathrm{\scriptstyle NOT}},{\mathrm{\scriptstyle AND}},{\mathrm{\scriptstyle OR}}\}\), we apply the operation \(T\) to the values assigned to the ancestors of \(u\) and we assign the output of this operation to \(u\). (Since we process nodes in topological order, the ancestors of \(u\) have already been processed at the time we process \(u\).)

We say a Boolean circuit \(C\) with \(n\) inputs and \(1\) output computes an \(n\)-bit Boolean function \(f{\colon}\{0,1\}^n\to\{0,1\}\) if for every input \(x=(x_1,\ldots,x_n)\in\{0,1\}^n\), the function value \(f(x)\) is equal to the value propagated to the output gate of \(C\) when we assign \(x_1,\ldots,x_n\) to the input nodes of \(C\).

One can show (e.g., by induction) that a circuit computes only one function. In particular, the function does not depend on the order we process the gates. We write \(f_C\) to denote the function computed by a circuit \(C\).

Example: parity

Consider the following \(n\)-bit Boolean function \[ {\mathrm{\scriptstyle PARITY}}_n(x) := \begin{cases} 1 & \text{ if $x_1+\ldots+x_n$ is an odd number,}\\ 0 & \text{ otherwise.} \end{cases} \] For \(n=2\), we can express \({\mathrm{\scriptstyle PARITY}}\) in terms of \({\mathrm{\scriptstyle NOT}},{\mathrm{\scriptstyle AND}},{\mathrm{\scriptstyle OR}}\) as follows \[{\mathrm{\scriptstyle PARITY}}_2(x_1,x_2)= (x_1 \land \neg x_2) \lor (\neg x_1 \land x_2)\] The parity of \(2\) bits is called exclusive-or. A common notation for \({\mathrm{\scriptstyle PARITY}}_2(x_1,x_2)\) is \(x_1\oplus x_2\).

If \(n\) is a power of \(2\), we can construct a circuit for \({\mathrm{\scriptstyle PARITY}}\) recursively based on the following identity \[ {\mathrm{\scriptstyle PARITY}}_n(x) = {\mathrm{\scriptstyle PARITY}}_{n/2}(x_1,\ldots,x_{n/2}) \oplus {\mathrm{\scriptstyle PARITY}}_{n/2}(x_{n/2+1},\ldots,x_n). \]

Circuit complexity

For a given Boolean functions, there could be many ways of computing it by a circuit. But some circuits are better than others.

We measure the efficiency of a circuit \(C\) by its size \[ {\mathrm{size}}(C) := \text{the number of gates of $C$}. \] For a Boolean function \(f\), we define its size as the minimum size of circuit that computes \(f\).

Another measure for the efficiency of a circuit is its depth \[ {\mathrm{depth}}(C) := \text{length of longest path from an input node to the output gate} \]

Generic upper bound

Theorem: For every \(n\)-bit Boolean function \(f\) there exists a circuit of size at most \(10\cdot 2^n-10\) to compute it.

Proof: We will use induction on \(n\). If we fix one of input bit of the function \(f\), then we are left with an \(n-1\)-bit Boolean function.

For \(n=1\), the theorem is true because for every \(1\)-bit function, we can find a circuit of size at most \(10\). Suppose \(n>1\). Let \(f_0\) and \(f_1\) be the two \(n-1\) bit functions obtained by fixing the first bit of \(f\), i.e., \[ f_0(x_2,...,x_n)=f(0,x_2,...,x_n), \] \[ f_1(x_2,...,x_n)=f(1,x_2,...,x_n). \] Both \(f_0\) and \(f_1\) are \(n-1\) bit functions. The following identity allows us to express the original function \(f\) in terms of \(f_0\) and \(f_1\) as well as a few basic operations \[ f =(\neg x_1 \land f_0) \lor (x_1 \land f_1). \] Therefore, we can construct a circuit for \(f\) from a circuit for \(f_0\) and a circuit for \(f_1\) as well as \(4\) additional gates (one \({\mathrm{\scriptstyle NOT}}\) gate, one \({\mathrm{\scriptstyle OR}}\) gate, and two \({\mathrm{\scriptstyle AND}}\) gates). It follows that \({\mathrm{size}}(f)\le {\mathrm{size}}(f_0)+{\mathrm{size}}(f_1)+4\). By induction hypothesis, both \({\mathrm{size}}(f_0)\) and \({\mathrm{size}}(f_1)\) are at most \(10\cdot 2^{n-1}-10\). By combining these bound, we get \[ {\mathrm{size}}(f) \le 10 \cdot 2^{n}-20+4 = 10 \cdot 2^{n}-16 \le 10 \cdot 2^n-10. \]