Hardware Reference
In-Depth Information
result column of the truth table vertically. Thus,
NAND
is 1110,
NOR
is 1000,
AND
is 0001, and
OR
is 0111. Obviously, only 16 Boolean functions of two variables
exist, corresponding to the 16 possible 4-bit result strings. In contrast, ordinary
algebra has an infinite number of functions of two variables, none of which can be
described by giving a table of outputs for all possible inputs because each variable
can take on any one of an infinite number of possible values.
Figure 3-3(a) shows the truth table for a Boolean function of three variables:
M
f
(
A
,
B
,
C
). This function is the majority logic function, that is, it is 0 if a
majority of its inputs are 0 and 1 if a majority of its inputs are 1. Although any
Boolean function can be fully specified by giving its truth table, as the number of
variables increases, this notation becomes increasingly cumbersome. Instead, an-
other notation is frequently used.
=
A
BC A
B C
A
1
A
ABC
4
ABC
5
B
2
8
M
B
A B C
0
M
0
0
0
1
0
0
0
0
1
6
ABC
0
1
0
0
1
1
C
1
0
0
0
1
1
1
3
1
0
1
C
ABC
1
1
0
7
1
1
1
(a)
(b)
Figure 3-3.
(a) The truth table for the majority function of three variables.
(b) A circuit for (a).
To see how this other notation comes about, note that any Boolean function
can be specified by telling which combinations of input variables give an output
value of 1. For the function of Fig. 3-3(a) there are four combinations of input
variables that make
M
equal to 1. By convention, we will place a bar over an input
