Information Technology Reference
In-Depth Information
DISTRIBUTIVITY
x
1
∧
(
x
2
∨
x
3
)=(
x
1
∧
x
2
)
∨
(
x
1
∧
x
3
)
x
1
∧
(
x
2
⊕
x
3
)=(
x
1
∧
x
2
)
⊕
(
x
1
∧
x
3
)
x
1
∨
(
x
2
∧
x
3
)=(
x
1
∨
x
2
)
∧
(
x
1
∨
x
3
)
We often write
x
∧
y
as
xy
. The operator
∧
∨
⊕
has precedence over the operators
and
,which
means that parentheses in
(
x
z
may be dropped.
The above rules are illustrated by the following formula:
∧
y
)
∨
z
and
(
x
∧
y
)
⊕
(
x
∧
(
y
⊕
z
))
∧
(
x
∨
y
)=(
x
∨
(
y
⊕
z
))
∧
(
x
∨
y
)
=(
x
∨
(
y
⊕
z
))
∧
(
x
∨
y
)
=
x
∨
(
y
∧
(
y
⊕
z
))
=
x
∨
((
y
∧
y
)
⊕
(
y
∧
z
))
=
x
∨
(
0
⊕
y
∧
z
)
=
x
∨
(
y
∧
z
)
DeMorgan's second rule is used to simplify the first term in the first equation. The last
rule on substitution of constants is used twice to simplify the second equation. The third
distributivity rule and commutativity of
areusedtosimplifythethirdone. Thesecond
distributivity rule is used to expand the fourth equation. The fifth equation is simplified by
invoking the third absorption rule. The final equation results from the commutativity of
∧
⊕
and application of the rule
x
1
⊕
0
=
x
1
. When there is no loss of clarity, we drop the operator
symbol
∧
between two literals.
2.3
Normal-Form Expansions of Boolean Functions
Normal forms are standard ways of constructing circuits from the tables defining Boolean
functions. They are easy to apply, although the circuits they produce are generally far from
optimal. They demonstrate that every Boolean function can be realized over the standard basis
as well as the basis containing
AND
and
EXCLUSIVE OR
.
In this section we define five normal forms: the disjunctive and conjunctive normal forms,
the sum-of-products expansion, the product-of-sums expansion, and the ring-sum expansion.
2.3.1 Disjunctive Normal Form
A
minterm
in the varia
b
les
x
1
,
x
2
,
.
..
,
x
n
is the
AND
of each variable or its negation. For
example, when
n
=
3,
x
1
∧
x
2
∧
x
3
is a minterm. It has value 1 exactly when each variable
has value 0.
x
1
∧
x
3
is another minterm; it has value 1 exactly when
x
1
=
1,
x
2
=
0and
x
3
=
1. It follows that a minterm on
n
variables has
va
lue 1 for exactly one of the 2
n
points
in its domain. Using the notation
x
1
=
x
and
x
0
=
x
, we see that the above minterms can
be written as
x
1
x
2
x
3
and
x
1
x
2
x
3
, respectively, when we drop the use of the
AND
operator
x
2
∧
.
Thus,
x
1
x
2
x
3
=
1when
x
=(
x
1
,
x
2
,
x
3
)=(
0, 0, 0
)
and
x
1
x
2
x
3
=
1when
x
=(
1, 0, 1
)
.
That is, the minterm
x
(
c
)
=
x
c
1
∧
x
c
2
2
x
c
n
has value 1 exactly when
x
=
c
where
c
=
(
c
1
,
c
2
,
...
,
c
n
)
.A
minterm of a Boolean function
f
is a minterm
x
(
c
)
that contains all the
variables of
f
and for which
f
(
c
)=
1.
The word “disjunction” is a synonym for
OR
,andthe
disjunctive normal form (DNF)
of
a Boolean function
f
:
∧
∧···∧
1
n
B
→B
is the
OR
of the minterms of
f
.Thus,
f
has value 1 when
Search WWH ::
Custom Search