Information Technology Reference
In-Depth Information
DEFINITION
9.4.1
Given two disjoint subsets
A
,
B ⊆{
0, 1
}
n
of the set of the Boolean
n
-tuples,
the
neighborhood
of
A
and
B
,
N
(
A
,
B
)
,isthesetof pairsof tuples
(
x
,
y
)
,
x
∈
A
and
y
∈
B
,suchthat
x
and
y
agree in all but one position.
The neighborhood of
A
=
{
}
and
B
=
{
}
N
(
A
,
B
)=
{
}
0
1
is the pair
(
0, 1
)
.Also,
the neighborhood of
A
=
{
}
and
B
=
{
}
N
(
A
,
B
)=
000, 101
111, 010
is the set of pairs
{
(
000, 010
)
,
(
101, 111
)
}
.
,weusethenotation
f
−
1
(
0
)
and
f
−
1
(
1
)
to denote the sets
of
n
-tuples that cause
f
to assume the values 0 and 1, respectively.
n
Given a function
f
:
B
→B
THEOREM
9.4.2
For any
f
:
B
n
f
−
1
(
0
)
and
B
f
−
1
(
1
)
, the following
→B
and any
A
⊆
⊆
inequality holds over the standard basis
Ω
0
:
≥
|N
(
A
,
B
)
|
2
L
Ω
0
(
f
)
|
Proof
Consider a circuit for
f
of fan-out 1 over the standard basis that has the mini-
mal number of leaves, namely
L
Ω
0
(
f
)
. Since the fan-in of each gate is either 1 or 2, by
Lemma
9.2.1
the number of leaves is one more than the number of gates of fan-in 2. Each
fan-in-2 gate is an
AND
or
OR
gate with suitable negation on its inputs and outputs.
Consider a minimal formula for
f
. Assume without loss of generality that the formula
is written over the basis
|
A
||
B
. We prove the lower bound by induction, the base case
being that of a function on one variable. If the function is constant,
{∧
,
¬}
=
0and
its formula size is also 0. If the function is non-constant, it is either
x
or
x
.(If
f
(
x
)=
x
,
f
−
1
(
1
)=
|N
(
A
,
B
)
|
and
f
−
1
(
0
)=
{
1
}
{
0
}
.) In both cases,
|N
(
A
,
B
)
|
=
1 since the neighborhood
has only one pair. (In the first case
N
(
A
,
B
)=
{
(
0, 1
)
}
.) Also,
|
A
|
=
1and
|
B
|
=
1,
thereby establishing the base case.
The inductive hypothesis is that
L
Ω
0
(
f
∗
)
for any function
f
∗
≥|N
(
A
,
B
)
|
/
|
A
||
B
|
whose formula size
L
Ω
0
(
f
∗
)
2. Since the occurrences of
NOT
do not affect the formula size of a function, apply DeMorgan's theorem as necessary so that
the output gate of the optimal (minimal-depth) formula for
f
is an
AND
gate. Then we can
write
f
=
g
≤
L
0
−
1forsome
L
0
≥
h
,where
g
and
h
are defined on the variables appearing in their formulas.
Since the formula for
f
is optimal, so are the formulas for
g
and
h
.
Let
A
∧
f
−
1
(
0
)
and
B
f
−
1
(
1
)
.Thus,
f
(
x
)=
0for
x
∈
⊆
⊆
A
and
f
(
x
)=
1for
x
∈
B
.Since
f
=
g
∧
h
,if
f
(
x
)=
1, then both
g
(
x
)=
1and
h
(
x
)=
1. That is,
f
−
1
(
1
)
g
−
1
(
1
)
and
f
−
1
(
1
)
h
−
1
(
1
)
.(SeeFig.
9.7
.) It follows that
B
g
−
1
(
1
)
and
⊆
⊆
⊆
h
−
1
(
1
)
.Let
B
1
=
B
2
=
B
.Let
A
1
=
A
g
−
1
(
0
)
(which implies
A
1
⊆
g
−
1
(
0
)
)
B
⊆
∩
and let
A
2
=
A
−
A
1
.Since
f
(
x
)=
0for
x
∈
A
, but
g
(
x
)=
1for
x
∈
A
2
, as suggested
h
−
1
(
0
)
.(Since
f
=
g
in Fig.
9.7
, it follows that
A
2
⊆
∧
h
,
f
(
x
)=
0, and
g
(
x
)=
1, it
follows that
h
(
x
)=
0.) Finally, observe that
N
(
A
1
,
B
1
)
and
N
(
A
2
,
B
2
)
are disjoint (
A
1
and
A
2
have no tuples in common) and that
|N
(
A
,
B
)
|
=
|N
(
A
1
,
B
1
)
|
+
|N
(
A
2
,
B
2
)
|
.
Given the inductive hypothesis, it follows from the above that
≥
|N
(
A
1
,
B
1
)
|
2
+
|N
(
A
2
,
B
2
)
|
2
L
Ω
0
(
f
)=
L
Ω
0
(
g
)+
L
Ω
0
(
h
)
|
A
1
||
B
1
|
|
A
2
||
B
2
|
|N
(
A
1
,
B
1
)
|
2
+
|N
(
A
2
,
B
2
)
|
2
1
=
|
B
|
|
A
1
|
|
A
2
|
Search WWH ::
Custom Search