Information Technology Reference
In-Depth Information
=
x
1
∨
(
x
2
∨
x
3
)
∧
(
x
2
∨
x
3
)
{
}
3rd distributivity rule
=
x
1
∨
x
2
∨
(
x
3
∧
x
3
)
{
}
3rd distributivity rule
=
x
1
∨
x
2
∨
{
}
0
6th absorption rule
=
x
1
∨
x
2
{
}
1st rule on substitution of constants
It is easily shown that the POSE of the parity function is its CNF. (See Problem
2.8
.)
2.3.4 Ring-Sum Expansion
The
ring-sum expansion (RSE)
of a function
f
is the
EXCLUSIVE OR
(
⊕
) of a constant
∧
) of unnegated variables of
f
. For example, 1
⊕
x
1
x
3
⊕
x
2
x
4
is an RSE.
and products (
⊕
∧
B
=
{
}
The operations
constitute a ring. (Rings are examined in
Section
6.2.1
.) Any two instances of the same product in the RSE can be eliminated since they
sum to 0.
The RSE of a Boolean function
f
:
and
over the set
0, 1
n
B
→B
can be constructed from its DNF, as we
show. Since a minterm of
f
has value 1 on exactly one of the 2
n
points in its domain, at
most one minterm in the DNF for
f
has value 1 for any point in its domain. Thus, we
can combine minterms
wi
th
EXCLUSIVE OR
instead of
OR
without ch
an
ging the value of the
function. Now replace
x
i
with
x
i
⊕
1 in each minterm containing
x
i
and then apply the
second distributivity rule. We simplify the resulting formula by usin
g
commutativity
a
nd the
abso
rption rule
x
i
⊕
x
i
=
0. For example, since the minterms of
(
x
1
∨
x
2
)
x
3
are
x
1
x
2
x
3
,
x
1
x
2
x
3
,and
x
1
x
2
x
3
, we construct the RSE of this function as follows:
(
x
1
∨
x
2
)
x
3
=
x
1
x
2
x
3
⊕
x
1
x
2
x
3
⊕
x
1
x
2
x
3
=(
x
1
⊕
1
)
x
2
x
3
⊕
(
x
1
⊕
1
)(
x
2
⊕
1
)
x
3
⊕
x
1
x
2
x
3
=
x
2
x
3
⊕
x
1
x
2
x
3
⊕
x
3
⊕
x
1
x
3
⊕
x
2
x
3
⊕
x
1
x
2
x
3
⊕
x
1
x
2
x
3
=
x
3
⊕
x
1
x
3
⊕
x
1
x
2
x
3
The third equation follows by applying the second distributivity rule and commutativity. The
fourth follows by applying
x
i
⊕
x
i
=
0 and commutativity. The two occurrences of
x
2
x
3
are
canceled, as are two of the three instances of
x
1
x
2
x
3
.
As this example illustrates, the RSE of a function
f
:
n
is the
EXCLUSIVE OR
of
a Boolean constant
c
0
and one or more products of unnegated variables of
f
. Since each of
the
n
variables of
f
can be present or absent from a product, there are 2
n
products, including
the product that contains no variables; that is, a cons
tant whose v
alue is 0 or 1. For example,
1
B
→B
⊕
x
3
⊕
x
1
x
3
⊕
x
1
x
2
x
3
is the RSE of the function
(
x
1
∨
x
2
)
x
3
.
2.3.5 Comparison of Normal Forms
It is easy to show that the RSE of a Boolean function is unique (see Problem
2.7
). However, the
RSE is not necessarily a compact representation of a function. For example, the RSE of the
OR
of
n
variables,
f
(
n
)
, includes every product term except for the constant 1. (See Problem
2.9
.)
It is also true that some functions have large size in some normal forms but small size in
others. For example, the parity function has exponential size in the DNF and CNF normal
forms but linear size in the RSE. Also,
f
(
n
)
∨
has exponential size in the RSE but linear size in
∨
the CNF and SOPE representations.
Search WWH ::
Custom Search