Information Technology Reference
In-Depth Information
x
1
x
2
x
3
f
0001
0010
0101
0110
1001
1011
1100
1111
x
1
x
2
x
3
f
0001
0010
0101
0110
1001
1011
1100
1111
(a)
(b)
Figure 2.3
Truth tables illustrating the disjunctive and conjunctive normal forms.
exactly one of its minterms has value 1 and has value 0 otherwise. Consider the function whose
tableisgiveninFig.
2.3
(a). Its disjunctive normal form (or minterm expansion) is given by
the following formula:
f
(
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
The
parity
function
f
(
n
)
⊕
n
on
n
inputs has value 1 when an odd number of
inputs is 1 and value 0 otherwise. It can be realized by a circuit containing
n
:
B
→B
−
1 instances of
the
EXCLUSIVE OR
operator; that is,
f
(
n
)
⊕
(
x
1
,
...
,
x
n
)=
x
1
⊕
x
2
⊕···⊕
x
n
. However, the
DNF of
f
(
n
)
contains 2
n−
1
minterms, a number exponential in
n
. The DNF of
f
(
3
)
is
⊕
⊕
f
(
3
)
⊕
(
x
,
y
,
z
)=
x yz
∨
xyz
∨
x y z
∨
xyz
Here we use the standard notation for a variable and its complement.
2.3.2 Conjunctive Normal Form
A
maxterm
in the
va
riables
x
1
,
x
2
,
...
,
x
n
is the
OR
of each variable or its negation. For
exam
pl
e,
x
1
∨
x
2
∨
x
3
is a maxterm. It has value 0 exactly when
x
1
=
x
2
=
0and
x
3
=
1.
x
1
∨
x
3
is another maxterm; it has value 0 exactly when
x
1
=
0and
x
2
=
x
3
=
1.
It follows that a maxterm on
n
variables has value 0 for exactly one of the 2
n
points in its
domain. We see that the above maxterms can be written as
x
1
∨
x
2
∨
x
2
∨
x
3
and
x
1
∨
x
2
∨
x
3
,
respectively. Thus,
x
1
∨
x
2
∨
x
3
=
0when
x
=(
x
1
,
x
2
,
x
3
)=(
0, 0, 1
)
a
nd
x
1
∨
x
2
∨
x
3
=
0
when
x
=(
0, 1, 0
)
. That is, the maxterm
x
(
c
)
=
x
c
1
1
x
c
2
2
x
c
n
∨
∨···∨
has value 0 exactly
when
x
=
c
.A
maxterm of a Boolean function
f
is a maxterm
x
(
c
)
that contains all the
variables of
f
and for which
f
(
c
)=
0.
The word “conjunction” is a synonym for
AND
,andthe
conjunctive normal form (CNF)
of a Boolean function
f
:
n
is the
AND
of the maxterms of
f
.Thus,
f
has value 0
when exactly one of its maxterms has value 0 and has value 1 otherwise. Consider the function
whose table is given in Fig.
2.3
(b). Its conjunctive normal form (or maxterm expansion) is
given by the following formula:
f
(
x
1
,
x
2
,
x
3
)=(
x
1
∨
B
→B
x
2
∨
x
3
)
(
x
1
∨
x
2
∨
x
3
)
(
x
1
∨
x
2
∨
x
3
)
∧
∧
Search WWH ::
Custom Search