CHAP. 15] BOOLEAN ALGEBRA 377
Fig. 15-7EXAMPLE 15.9 We apply Algorithm 15.4 to the following expressionEwhich (by Example 15.8) is now
expressed as the sum of all its prime implicants:
E=x′z′+xy+x′y′+yz′Step 1. Express each prime implicant ofEas a complete sum-of-products to obtain:
x′z′=x′z′(y+y′)=x′yz′+x′y′z′
xy=xy(z+z′)=xyz+xyz′
x′y′=x′y′(z+z′)=x′y′z+x′y′z′
yz′=yz′(x+x′)=xyz′+x′yz′Step 2. The summands ofx′z′arex′yzandx′y′z′which appear among the other summands. Thus deletex′z′
to obtain
E=xy+x′y′+yz′
The summands of no other prime implicant appear among the summands of the remaining prime implicants, and
hence this is a minimal sum-of-products form forE. In other words, none of the remaining prime implicants is
superfluous, that is, none can be deleted without changingE.
15.10Logic Gates and Circuits
Logic circuits(also calledlogic networks) are structures which are built up from certain elementary circuits
calledlogic gates. Each logic circuit may be viewed as a machineLwhich contains one or more input devices
and exactly one output device. Each input device inLsends a signal, specifically, abit(binary digit),
0or1to the circuitL, andLprocesses the set of bits to yield an output bit. Accordingly, ann-bit sequence may be
assigned to each input device, andLprocesses the input sequences one bit at a time to produce ann-bit output
sequence. First we define the logic gates, and then we investigate the logic circuits.
Logic Gates
There are three basic logic gates which are described below. We adopt the convention that the lines entering
the gate symbol from the left are input lines and the single line on the right is the output line.
(a) OR Gate:Figure 15-8(a)shows an OR gate with inputsAandBand outputY=A+Bwhere “addition”
is defined by the “truth table” in Fig. 15-8(b). Thus the outputY=0 only when inputsA=0 andB=0.
Such an OR gate may, have more than two inputs. Figure 15-8(c)shows an OR gate with four inputs,A,B,
C,D, and outputY=A+B+C+D. The outputY=0 if and only if all the inputs are 0.