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
Previous Page Next Page