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

then we write f ( x 1 , x 2 , ... , x n )=( y 1 , y 2 , ... , y m ) . This is illustrated by the function
f ( 3,2 )

example ( x 1 , x 2 , x 3 )=( y 1 , y 2 ) defined in Fig. 2.2 on page 39 .
A binary function is one whose domain and codomain are Cartesian products of

B

=

{ } B

0, 1 .A Boolean function is a binary function whose codomain consists of the set .In

other words, it has one output.
As we see in Section 2.3 , normal forms provide standard ways to construct circuits for
Boolean functions. Because a normal-form expansion of a function generally does not yield
a circuit of smallest size or depth, methods are needed to simplify the algebraic expressions
produced by these normal forms. This topic is discussed in Section 2.2.4 .
Before exploring the algebraic properties of simple Boolean functions, we define the basic
circuit complexity measures used in this topic.

2.2.3 Circuit Complexity Measures
We often ask for the smallest or most shallow circuit for a function. If we need to compute
a function with a circuit, as is done in central processing units, then knowing the size of the
smallest circuit is important. Also important is the depth of the circuit. It takes time for
signals applied to the circuit inputs to propagate to the outputs, and the length of the longest
path through the circuit determines this time. When central processing units must be fast,
minimizing circuit depth becomes important.
As indicated in Section 1.5 , the size of a circuit also provides a lower bound on the space-
time product needed to solve a problem on the random-access machine, a model for modern
computers. Consequently, if the size of the smallest circuit for a function is large, its space-time
product must be large. Thus, a problem can be shown to be hard to compute by a machine
with memory if it can be shown that every circuit for it is large.
We now define two important circuit complexity measures.

DEFINITION 2.2.3 The size of a logic circuit is the number of gates it contains. Its depth is the
number of gates on the longest path through the circuit. The circuit size , C Ω ( f ) ,and circuit
depth , D Ω ( f ) , of a Boolean function f :

m are defined as the smallest size and smallest
depth of any circuit, respectively, over the basis Ω for f .

n

B →B

Most Boolean functions on n variables are very complex. As shown in Sections 2.12 and
2.13 , their circuit size is proportional to 2 n /n and their depth is approximately n . Fortunately,
most functions of interest have much smaller size and depth. (It should be noted that the circuit
of smallest size for a function may be different from that of smallest depth.)

2.2.4 Algebraic Properties of Boolean Functions
Since the operations AND (

or )playavital
role in the construction of normal forms, we simplify the subsequent discussion by describing
their properties.
If we interchange the two arguments of AND , OR ,or EXCLUSIVE OR , it follows from their
definition that their values do not change. This property, called commutativity ,holdsforall
three operators, as stated next.

∧ ), OR ( ∨ ), EXCLUSIVE OR ( ⊕ ), and NOT ( ¬