Information Technology Reference
In-Depth Information
An important relationship holds between the DNF and CNF representations for Boolean
functions. If DNF
(
f
)
and CNF
(
f
)
are the representations of
f
in the DNF and CNF expan-
sions, then the following identity holds (see Problem
2.6
):
CNF
(
f
)=
DNF
(
f
)
It follows that the CNF of the parity function
f
(
n
)
has 2
n−
1
maxterms.
⊕
m
can be expanded to its CNF or DNF and each can be
realized with circuits, the following result is immediate.
n
Since each function
f
:
B
→B
THEOREM
2.3.1
Every function
f
:
B
n
m
can be realized by a logic circuit.
→B
2.3.3 SOPE and POSE Normal Forms
The sum-of-products and product-of-sums normal forms are simplifications of the disjunctive
and conjunctive normal forms, respectively. These simplifications are obtained by using the
rules stated in Section
2.2.4
.
A
product
in the variab
le
s
x
i
1
,
x
i
2
,
...
,
x
i
k
is the
AND
of each of these variables or their
negations. For example,
x
2
x
5
x
6
is a product. A minterm is a product that contains each of
the variables of a function. A
product of a Boolean function
f
is a product in some of the
variables of
f
.A
sum-of-products expansion (SOPE)
of a Boolean function is the
OR
(the
sum) of products of
f
. Thus, the DNF is a special case of the SOPE of a function.
A SOPE of a Boolean function can be obtained by simplifying the DNF of a function
using the rules given in Section
2.2.4
. For example, the DNF given earlier and shown below
can be simplified to produce a SOPE.
y
1
(
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
x
2
x
3
∨
x
1
x
2
x
3
It is
easy to see that the first and second terms combine to give
x
1
x
3
, the first and third give
x
2
x
3
(we use the property that
g
∨
g
=
g
), and the last two give
x
1
x
3
.Thatis,wecanwrite
the following SOPE for
f
:
f
=
x
1
x
3
∨
x
1
x
3
∨
x
2
x
3
(2.3)
Clearly, we could have stopped before any one of the above simplifications was used and gen-
erated another SOPE for
f
. This illustrates the point that a Boolean function may have many
SOPEs but only one DNF.
A
sum
in the va
ri
ables
x
i
1
,
x
i
2
,
...
,
x
i
k
is the
OR
of each of these variables or their nega-
tions. For example,
x
3
x
7
is a sum. A maxterm is a product that contains each of the
variables of a function. A
sum of a Boolean function
f
is a sum in some of the variables of
f
.A
product-of-sum expansion (POSE)
of a Boolean function is the
AND
(the product) of
sums of
f
. Thus, the CNF is a special case of the POSE of a function.
A POSE of a Boolean function can be obtained by simplifying the CNF of a function
using
t
he r
u
les given i
n
Section
2.2.4
. For ex
a
mpl
e,
the conju
nc
tion of the two maxterms
x
1
∨
x
4
∨
∨
x
2
∨
x
3
and
x
1
∨
x
2
∨
x
3
,namely
(
x
1
∨
x
2
∨
x
3
)
∧
(
x
1
∨
x
2
∨
x
3
)
,canbereducedto
x
1
∨
x
2
by the application of rules of Section
2.2.4
, as shown below:
(
x
1
∨
x
2
∨
x
3
)
∧
(
x
1
∨
x
2
∨
x
3
)=
Search WWH ::
Custom Search