18 1. Classical Computation

Ý½ Ý¼

Ü½ Ü¼

Þ¾ Þ½ Þ¼

¨ ¨

¨

¨

Fig. 2.1. Circuit over the basis {∧, ⊕} for the addition of two 2-digit

numbers: z2z1z0 = x1x0 + y1y0.

edge is linked to one of the function arguments. Some vertices are called

output vertices. Since the graph is acyclic, any value assignment to the

input variables can be extended (uniquely) to a consistent set of values for

all vertices. Therefore, the set of values at the output vertices is a function

of input values. This function is computed by a circuit. It is easy to see

that this representation of a circuit can be transformed into a sequence of

assignments, and vice versa. (We will not use this representation much, but

it explains the name “circuit”.)

A circuit for a Boolean function is called a formula if each auxiliary

variable, except the last one, is used (i.e., appears on the right-hand side of

an assignment) exactly once. The graph of a formula is a tree whose leaves

are labeled by input variables; each label may appear any number of times.

(In a general circuit an auxiliary variable may be used more than once, in

which case the out-degree of the corresponding vertex is more than 1.)

Why the name “formula”? If each auxiliary variable is used only once, we

can replace it by its definition. Performing all these “inline substitutions”,

we get an expression for f that contains only input variables, functions from

the basis, and parentheses. The size of this expression approximately equals

the total length of all assignments. (It is important that each auxiliary

variable is used only once; otherwise we would need to replace all occurrences

of each auxiliary variable by their definitions, and the size might increase

exponentially.)

A basis A is called complete if, for any Boolean function f, there is a

circuit over A that computes f. (It is easy to see that in this case any

function of type

Bn

→

Bm

can be computed by an appropriate circuit.)

The most common basis contains the following three functions:

NOT(x) = ¬x, OR(x1, x2) = x1 ∨ x2, AND(x1, x2) = x1 ∧ x2