Information Technology Reference
In-Depth Information
g
j
used in the design of a full adder (see Section
2.7
)
is a monotone function of the variables
p
j
,
c
j
,and
g
j
. Its set of implicants is
I
(
c
j
+
1
)=
{
The function
c
j
+
1
=(
p
j
∧
c
j
)
∨
p
j
∧
c
j
,
g
j
,
p
j
∧
g
j
,
c
j
∧
g
j
,
p
j
∧
c
j
∧
g
j
}
. If any one of these products has value 1 then so
does
c
j
+
1
. Its set of prime implicants is
PI
(
c
j
+
1
)=
I
(
c
j
+
1
)
because these
are the smallest products for which
c
j
+
1
has value 1. Thus,
c
j
+
1
is defined by
PI
(
c
j
+
1
)
and
represented as
c
j
+
1
=(
p
j
∧
{
p
j
∧
c
j
,
g
j
}⊆
g
j
.
We now present a replacement rule for monotone functions that captures the following
idea: if a function
g
computed by a gate of a monotone circuit has a monom
π
that is not a
monom of the function
f
computed by the complete circuit, then
π
can be removed from
g
without affecting the value of
f
. This idea is valid in monotone circuits because the absence
of negation provides only one way to eliminate extra monoms, namely, by
OR
ing them with
products containing a subset of their variables. Taking the
AND
of a monom with another
term creates a longer monom. Thus, since monoms that are not monoms of the function
f
computed by a circuit must be eliminated, there is no loss of generality in assuming that they
are not produced in the first place.
c
j
)
∨
DEFINITION
9.6.2
Let
f
:
B
n
n
be two monotone functions. Let
g
be
computed within a monotone circuit for
f
. The following is a replacement rule for
g
:
→B
and
g
:
B
→B
a) Let
π
1
∈
PI
(
g
)
and let
h
be defined by
PI
(
h
)=
PI
(
g
)
−{
π
}
.Replacethegatecomputing
for all monoms
π
(including the empty monom),
π
π
∈
g
by one computing
h
if
∧
PI
(
f
)
.
We now show that any monom
π
satisfying Rule (a) can be removed from
PI
(
g
)
because
it contributes nothing to the computation of
f
.
LEMMA
9.6.1
Let
f
:
B
n
n
→B
and
g
:
B
→B
be two monotone functions and let
π
∈
PI
(
g
)
be such that for all monoms
π
(including the empty monom),
π
π
∈
∧
PI
(
f
)
.Let
h
be defined
by
PI
(
h
)=
PI
(
g
)
.If
g
is computed in some monotone circuit for
f
,thecircuitobtained
by replacing
g
by
h
also computes
f
.
Proof
Let
−{
π
}
C
∗
be
C
denote a circuit for
f
within which the function
g
is computed. Let
the circuit obtained by replacing
g
by
h
under Rule (a). Since
h
≤
g
and the circuit is
monotone, the function
f
∗
computed by
C
∗
satisfies
f
∗
≤
f
. We suppose that
f
∗
=
f
and
show that a contradiction results.
If
f
∗
n
such that
f
∗
(
a
)=
0 but
f
(
a
)=
1.
Since the only change in the circuit occurred at the gate computing
g
, by monotonicity, on
this tuple
g
(
a
)=
1 but
h
(
a
)=
0. It follows that
π
(
a
)=
1. Let
π
be a prime implicant of
f
for which
π
(
a
)=
1. We show that
π
=
π
=
f
, there is some input
n
-tuple
a
∈B
∧
π
1
for some monom
π
1
, in contradiction
to the condition of the lemma.
Let
x
i
be any variable of
π
.Then
a
i
=
1since
π
(
a
)=
1. Define the
n
-tuple
b
by
b
i
=
0and
b
j
=
a
j
for
j
a
and
π
(
b
)=
0,
h
and
g
both have the same
value on
b
. Thus, both circuits compute the same value, which must be 0 by monotonicity
and the fact that
f
∗
=
0on
a
.Since
π
(
a
)=
1and
π
(
b
)=
0 but only one variable was
changed, namely
x
i
,
π
must contain
x
i
.Since
x
i
=
i
.Since
b
≤
is an arbitrary variable of
π
, it follows
that
π
contains
π
as a sub-monom.
This last result implies that if a function
f
has no prime implicants containing more than
l
variables, then any monoms containing more than
l
variables can be removed where they
Search WWH ::
Custom Search