Logic Circuits - Models of Computation: Exploring the Power of Computing - page 38

logic circuits, the operations can include many functions other than the basic three mentioned
above.
As illustrated above, a straight-line program can be constructed for any circuit. Similarly,
given a straight-line program, a circuit can be drawn for it as well. We now formally define
straight-line programs, circuits, and characteristics of the two.

DEFINITION 2.2.1 A straight-line program is set of steps each of which is an input step ,de-
noted ( s READ x ) ,an output step , denoted ( s OUTPUT i ) ,ora computation step , denoted
( s OP i ... k ) .Here s is the number of a step, x denotes an input variable, and the keywords
READ , OUTPUT ,and OP identify steps in which an input is read, an output produced, and the
operation OP is performed. In the s th computation step the arguments to OP are the results produced
at steps i , ... , k . It is required that these steps precede the s th step; that is, s

i , ... , k .
A circuit is the graph of a straight-line program. (The requirement that each computation
step operate on results produced in preceding steps insures that this graph is a DAG.) The fan-in
of the circuit is the maximum in-degree of any vertex. The fan-out of the circuit is the maximum
outdegree of any vertex. A gate is the vertex associated with a computation step.
The basis Ω of a circuit and its corresponding straight-line program is the set of operations
that they use. The bases of Boolean straight-line programs and logic circuits contain only Boolean
functions. The standard basis , Ω 0 , for a logic circuit is the set

≥

{ }

AND , OR , NOT .

2.2.1 Functions Computed by Circuits
As stated above, each step of a straight-line program computes a function. We now define the
functions computed by straight-line programs, using the example given in Eq. ( 2.2 ).

DEFINITION 2.2.2 Let g s be the function computed by the s th step of a straight-line pro-
gram . fthe s th step is the input step ( s READ x ) ,then g s = x . f t sthecomputa ion
step ( s OP i ... k ) ,thefunctionis g s = OP ( g i , ... , g k ) ,where g i , ... , g k are the functions
computed at steps on which the s th step depends. If a straight-line program has n inputs and m
outputs, it computes a function f :

m . f s 1 , s 2 , ... , s m are the output steps, then
f =( g s 1 , g s 2 , ... , g s m ) . The function computed by a circuit is the function computed by the
corresponding straight-line program.

n

B →B

The functions computed by the logic circuit of Fig. 2.1 are given below. The expression
for g s is found by substituting for its arguments the expressions derived at the steps on which
it depends.

g 1 := x ; g 5 := x ∧ y ;

g 2 := y ; g 6 := x ∧ y ;

g 3 := x ; g 7 := ( x ∧ y ) ∨ ( x ∧ y );

g 4 := y ;

The function computed by the above Boolean straight-line program is f ( x , y )=( g 5 , g 7 ) .
The table of values assumed by f as the inputs x and y run through all possible values is shown
below. The value of g 7 is the EXCLUSIVE OR function.