THE DIGITAL LOGIC LEVEL - Structured Computer Organization - page 152

variable to indicate that its value is inverted. The absence of a bar means that it is
not inverted. Furthermore, we will use implied multiplication or a dot to mean the
Boolean A ND function and to mean the Boolean OR function. Thus, for ex-

am p le, A BC takes the value 1 only when A

+

= 1 and B = 0 and C = 1. Also,

0) . The four rows
of Fig. 3-3(a) producing 1 bits in the output are: ABC , ABC , ABC , and ABC . The
function, M , is true (i.e., 1) if any of these four conditions is true, so we can write
M

AB + BC is 1 only when ( A = 1 and B = 0) or ( B = 1 a nd C =

ABC
as a compact way of giving the truth table. A function of n variables can thus be
described by giving a ''sum'' of at most 2 n n -variable ''product'' terms. This for-
mulation is especially important, as we will see shortly, because it leads directly to
an implementation of the function using standard gates.
It is important to keep in mind the distinction between an abstract Boolean
function and its implementation by an electronic circuit. A Boolean function con-
sists of variables, such as A , B , and C , and Boolean operators such as AND, OR,
and NOT. A Boolean function is described by giving a truth table or a Boolean
function such as
F

= ABC + ABC + ABC +

ABC
A Boolean function can be implemented by an electronic circuit (often in many
different ways) using signals that represent the input and output variables and gates
such as AND , OR , and NOT . We will generally use the notation AND, OR, and NOT
when referring to the Boolean operators and AND , OR , and NOT when referring to
the gates, even though it is sometimes ambiguous as to whether we mean the func-
tions or the gates.

= ABC +

3.1.3 Implementation of Boolean Functions

As mentioned above, the formulation of a Boolean function as a sum of up to
2 n product terms leads directly to a possible implementation. Using Fig. 3-3 as an
example, we can see how this implementation is accomplished. In Fig. 3-3(b), the
inputs, A , B , and C , are shown at the left edge and the output function, M ,is
shown at the right edge. Because complements (inverses) of the input variables are
needed, they are generated by tapping the inputs and passing them through the
inverters labeled 1, 2, and 3. To keep the figure from becoming cluttered, we have
drawn in six vertical lines, of which three are connected to the input variables, and
three connected to their complements. These lines provide a convenient source for
the inputs to subsequent gates. For example, gates 5, 6, and 7 all use A as an input.
In an actual circuit these gates would probably be wired directly to A without using
any intermediate ''vertical'' wires.
The circuit contains four AND gates, one for each term in the equation for M
(i.e., one for each row in the truth table having a 1 bit in the result column). Each