Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAP. 15] BOOLEAN ALGEBRA 379

Suppose, for instance, a NOT gate is asked to process the following three sequences:

A 1 = 110001 ,A 2 = 10001111 ,A 3 = 101100111000

The NOT gate changes 0 to 1 and 1 to 0. Thus

A′ 1 = 001110 ,A′ 2 = 01110000 ,A′ 3 = 010011000111

are the three corresponding outputs.

Logic Circuits

A logic circuitLis a well-formed structure whose elementary components are the above OR, AND, and
NOT gates. Figure 15-11 is an example of a logic circuit with inputsA,B,Cand outputY. A dot indicates a
place where the input line splits so that its bit signal is sent in more than one direction. (Frequently, for notational
convenience, we may omit the word from the interior of the gate symbol.) Working from left to right, we express
Yin terms of the inputsA,B,Cas follows. The output of the AND gate isA·B, which is then negated to yield
(A·B)′. The output of the lower OR gate isA′+C, which is then negated to yield(A′+C)′. The output of the
OR gate on the right, with inputs(A·B)′and(A′+C)′, gives us our desired representation, that is,

Y=(A·B)′+(A′+C)′

Fig. 15-11

Logic Circuits as a Boolean Algebra

Observe that the truth tables for the OR, AND, and NOT gates are respectively identical to the truth tables
for the propositionsp∨q(disjunction, “porq”),p∧q(conjunction, “p andq”), and¬p(negation, “notp”),
which appear in Section 4.3. The only difference is that 1 and 0 are used instead of T and F. Thus the logic circuits
satisfy the same laws as do propositions and hence they form a Boolean algebra. We state this result formally.

Theorem 15.12: Logic circuits form a Boolean Algebra.

Accordingly, all terms used with Boolean algebras, such as, complements, literals, fundamental products,

minterms, sum-of-products, and complete sum-of-products, may also be used with our logic circuits.

AND-OR Circuits

The logic circuitLwhich corresponds to a Boolean sum-of-products expression is called anAND-OR circuit.

Such a circuitLhas several inputs, where:

(1) Some of the inputs or their complements are fed into each AND gate.

(2) The outputs of all the AND gates are fed into a single OR gate.

(3) The output of the OR gate is the output for the circuitL.

The following illustrates this type of a logic circuit.