Information Technology Reference
In-Depth Information
values. Furthermore, for each variable x i there is a value c i such that the subfunction of f obtained
by assigning x i the value c i is in Q ( n− 1 )
.
2,3
The class Q ( n )
2,3 contains the function f ( n )
mod 3, c :
B
n
→B
,asweshow.Here z mod a is
the remainder of z after removing all multiples of a .
LEMMA 9.3.1 For n ≥ 3 and c ∈{ 0, 1, 2 } ,thefunction f ( n )
B
n
→B
mod 3, c :
defined below is
in Q ( n )
2,3 :
f ( n )
mod 3, c ( x 1 , x 2 , ... , x n )=(( y + c )mod 3 )mod 2
where y = i = 1 x i and and + denote integer addition.
Proof We show that the functions f ( n )
mod 3, c , c
∈{
}
,arealldistinctwhen n
1.
When n = 1, the functions are different because f ( 1 mod 3,0 ( x 1 )= x 1 , f ( 1 mod 3,1 ( x 1 )=
x 1 ,and f ( 1 )
0, 1, 2
.Becausethe
functions f ( 2 mod 3,0 ( x 1 , x 2 ) , f ( 2 mod 3,1 ( x 1 , x 2 ) ,and f ( 2 mod 3,2 ( x 1 , x 2 ) have value 1 only when
y = x 1 + x 2 = 1, 0, 2, respectively, the three functions are different.
The proof of membership of f ( n )
mod 3, c
mod 3,2 ( x 1 )= 0. For n = 2, y can assume values in
{
0, 1, 2
}
in Q ( n )
2,3 is by induction. The base case is n = 3,
which holds, as shown in the next paragraph. The inductive hypothesis is that for each
c
, f ( n− 1 )
Q ( n− 1 )
2,3
∈{
0, 1, 2
}
mod 3, c
.
3, f ( n )
To s h ow t h a t f o r n
mod 3, c has at least three distinct subfunctions as any two of its
variables range over all values, let y be the sum of the n
2 variables that are not fixed and
let c be the sum of c and the values of the two variables that are fixed. Then the value of the
function is (( y + c )mod 3 )mod 2 = ((( y mod 3 )+( c mod 3 )) mod 3 )mod 2.
Since ( y mod 3 ) and ( c mod 3 ) range over the values 0, 1, and 2, the three functions are
different, as shown in the first paragraph of this proof.
To show that for any variable x i there is an assignment c i such that f ( n )
mod 3, c
is in
Q ( n− 1 )
2,3
,let c = 0.
We now derive a lower bound on the circuit size of functions in the class Q ( n )
2,3 .
THEOREM 9.3.2 Over the basis of all Boolean functions on two inputs, Ω ,if f ∈ Q ( n )
2,3
for
n
3 ,then
C Ω ( f )
2 n
3
Proof We show tha t f depends on each of its variables. Suppose it does not depend on
x i .Then,pick x i and a second variable x j and let them range over all four possible values.
Since the value of x i has no effect on f , f has at most two subfunctions as x i and x j range
over all values, contradicting its definition.
We now show that some input vertex x i of a circuit for f has fan-out of 2 or more.
Consider a gate g in a circuit for f whose longest path to the output gate is longest. (See
Fig. 9.4 .) Since the circuit does not have loops and no other vertex is farther away from the
output, both of g 's input edges must be attached to input vertices. Let x i and x j be the two
inputs to this gate. If the fan-out of both of these input vertices is 1, they influence the value
of f only through the one gate to which they are connected. Since this gate has at most two
Search WWH ::




Custom Search