Chapter 1 Basic Principles of Digital Systems outlin e 1

switch used as a logic switch. Briefly explain how it

works.

2.9 Refer to Figure 2.10 (logic pushbuttons). Should the normally

open pushbutton be considered an active HIGH or

active LOW device? Briefly explain your choice.

2.10 Should the normally closed pushbutton be considered an

active HIGH or active LOW device? Why?

LED and the current flowing through it. Why is a series

resistor required?

2.13 Draw a circuit showing how an OR-gate output will illuminate

an LED when the gate output is LOW. Assume the

required series resistor is 470 _.

Section 2.3 Derived Logic Functions

2.14 For a 4-input NAND gate with inputs A, B, C, and D and

output Y:

and rectangular-outline symbols.

NAND gate and a NOR gate.

NAND gate with inputs A, B, C, D, and E and output Y.

How many lines would the truth table of this gate have?

2.18 Repeat Problem 2.17 for a 5-input NOR gate.

2.19 A pump motor in an industrial plant will start only if the

temperature and pressure of liquid in a tank exceed a certain

level. The temperature sensor and pressure sensor,

shown in Figure 2.39 each produce a logic HIGH if the

measured quantities exceed this value. The logic circuit

interface produces a HIGH output to turn on the motor.

Draw the symbol and truth table of the gate that corresponds

to the action of the logic circuit.

activated by a logic LOW.

Problem 2.19: Temperature and Pressure Sensors

Problem 2.21: Circuit for Two-Way Switch

Problem 2.22: Logic Circuit

on a light from either the top or the bottom of the stairwell

and off at the other end. The circuit also allows anyone

coming along after you to do the same thing, no matter

which direction they are coming from.

The lamp is ON when the switches are in the same positions

and OFF when they are in opposite positions.

What logic function does this represent? Draw the truth

table of the function and use it to explain your reasoning.

2.41.

“Output is HIGH if one input is HIGH, but not both.”

This is not the best statement of the operation of a multiple-

input XOR gate. Look at the truth table derived in

Problem 2.22 and write a more accurate description of ninput

XOR operation.

Equivalence

the gate output in its active state.

stairwell. This is a common circuit that allows you to turn

of Logic Gates

when a square waveform is applied to one input and

truth table show output active states for the DeMorgan

equivalent form of the gate.

2.25 Refer to Figure 2.43. State which two gates of the three

shown are DeMorgan equivalents of each other. Explain

your choice.

A

B

Problem 2.28: Input Waveforms

Problem 2.29:Waveforms

How does this compare to the waveform that would

appear at the output of an Exclusive OR gate under the

same conditions?

2.27 Sketch the input waveforms represented by the following

32-bit sequences (use 1/4-inch graph paper, 1 square per

bit):

A: 0000 0000 0000 1111 1111 1111 1111 0000

B: 1010 0111 0010 1011 0101 0011 1001 1011

Assume that these waveforms represent inputs to a

logic gate. (Spaces are provided for readability only.)

Sketch the waveform for gate output Y if the gate function

is:

a. AND

b. OR

c. NAND

d. NOR

e. XOR

f. XNOR

2.28 Repeat Problem 2.27 for the waveforms shown in Figure

2.44.

to an OR gate. Complete the sketch by drawing the waveform

for output Y.

2.30 Repeat Problem 2.29 for a NOR gate.

2.31 Figure 2.46 shows a circuit that will make a lamp flash at

3 Hz when the gasoline level in a car’s gas tank drops below

a certain point. A float switch in the tank monitors

the level of gasoline. What logic level must the float

switch produce to make the light flash when the tank is

approaching empty? Why?

replaced by a NOR gate.

gate is replaced by an ExclusiveORgate?Whyorwhy not?

2.33. Indicate the high-impedence state by the notation

C B

A

Y

C B

Y

c.

A

Y

Problem 2.24: Logic Gates

X

Y

a. b. c.

Y

X

Problem 2.25: Logic Gates

B

A

Y

Answers to Section Review Problems 55

HIGH.” 2.2. OR: “A OR B OR C OR D must be HIGH to

make Y HIGH.”

Section 2.2

2.3 When the switch is open, it provides a logic HIGH because

of the pull-up resistor. A closed switch is LOW, due to the connection

to ground.

Section 2.3

2.4 XOR; 2.5 NAND; 2.6 NOR; 2.7 XNOR.

Section 2.4

2.8 Y _ A__B__C__D_

Section 2.5

2.9 An AND needs two HIGH inputs to make a HIGH output. If

the Control input is LOW, the output can never be HIGH; the

output remains LOW. An OR output is HIGH if one input is

HIGH. If the Control input is HIGH, the output is always HIGH,

regardless of the level at the Signal input. In both cases, the output

is “stuck” at one level, signifying that the gate is inhibited.

from you, pin 1 is on the left side at the far end. The pins are

numbered counterclockwise from that point.

“Hi-Z” How do the enable properties of these gates differ

from gates such as AND and NAND?

Section 2.6 Integrated Circuit Logic Gates

2.35 Name two logic families used to implement digital logic

functions. How do they differ?

NAND gate in low power Schottky TTL, CMOS, and

high-speed CMOS technologies.

2.37 Repeat Problem 2.36 for a quadruple 2-input NOR gate.

How does each numbering system differentiate between

the NAND and NOR functions?

2.38 List six types of packaging that a logic gate could

come in.

Problem 2.31: Gasoline Level Circuit

A N S W E R S T O S E C T I O N R E V I E W P R O B L E M S
57

❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚

❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚❘❙❚

C H A P T E R 3

Boolean Algebra and

Combinational Logic

O U T L I N E

Expressions, Logic

Diagrams, and Truth

Tables

(SOP) and Productof-

Sums (POS) Forms

3.3 Theorems of

Boolean Algebra

POS Expressions

the Karnaugh Map

Method

C H A P T E R O B J E C T I V E S

• Explain the relationship between the Boolean expression, logic diagram,

and truth table of a logic gate network and be able to derive any one from

either of the other two.

• Draw logic gate networks in such a way as to cancel out internal inversions

automatically (bubble-to-bubble convention).

• Write the sum of products (SOP) or product of sums (POS) forms of a

Boolean equation.

• Use rules of Boolean algebra to simplify the Boolean expressions derived

from logic diagrams and truth tables.

• Apply the Karnaugh map method to reduce Boolean expressions and logic

circuits to their simplest forms.

In Chapter 3, we will examine the rudiments of combinational logic. A combinational

logic circuit is one in which two or more gates are connected together to combine several

Boolean inputs. These circuits can be represented several ways, as a logic diagram,

truth table, or Boolean expression.

A Boolean expression for a network of logic gates is often not in its simplest form. In

such a case, we may be using more components than would be required for the job, so it is

of benefit to us if we can simplify the Boolean expression. Several tools are available to us,

such as Boolean algebra and a graphical technique known as Karnaugh mapping. We can

also simplify the Boolean expression by taking care to draw the logic diagrams in such a

way as to automatically eliminate inverting functions within the circuit. _

logic gates.

combination of inputs, independent of the order in which they are applied.

In Chapter 2, we examined the functions of single logic gates. However, most digital circuits

require multiple gates. When two or more gates are connected together, they form a

logic gate network. These networks can be described by a truth table, a logic diagram

(i.e., a circuit diagram), or a Boolean expression. Any one of these can be derived from any

other.

A digital circuit built from gates is called a combinational (or combinatorial) logic

inputs can be applied in any sequence and still produce the same result. For example, an

AND gate output will always be HIGH if all inputs are HIGH, regardless of the order in

which they became HIGH. This is in contrast to sequential logic, in which sequence matters;

a sequential logic output may have a different value with two identical sets of inputs

if those inputs were applied in a different order. We will study sequential logic in a later

chapter.

Boolean Expressions from Logic Diagrams

so that inverting outputs connect to inverting inputs and noninverting outputs connect

to noninverting inputs.

Order of precedence The sequence in which Boolean functions are performed,

unless otherwise specified by parentheses.

Writing the Boolean expression of a logic gate network is similar to finding the expression

for a single gate. The difference is that in a multiple gate network, the inputs will usually

not consist of single variables, but compound expressions that represent outputs of previous

gates.

In an OR gate, with inputs x and y, the output will always be x _ y regardless of

whether x and y are single variables (e.g., x _ A, y _ B, output _ A _ B) or compound expressions

(e.g., x _ AB, y _ AC, output _ AB _ AC).

Figure 3.1 shows a simple logic gate network, consisting of a single AND and a

single OR gate. The AND gate combines inputs A and B to give the output expression AB.

The OR combines the AND function and input C to yield the compound expression

AB _ C.

K E Y T E R M S

K E Y T E R M S

A AB

C

Y_AB_ C

Boolean Expression from a Gate Network

❘❙❚ EXAMPLE 3.1 Derive the Boolean expression of the logic gate network shown in Figure 3.2a.

A AB

CD

B

D

Y _ AB_CD

B

C

Y

a. Logic gate network

Example 3.1

Figure 3.2b shows the gate network with the output terms indicated for each gate. The

AND and NAND functions are combined in an OR function to yield the output expression:

❘❙❚

draw the NAND in its DeMorgan equivalent form. If we choose the gate symbols so that

outputs with bubbles connect to inputs with bubbles, we will not have bars over groups of

variables, except possibly one bar over the entire function. In a circuit with many inverting

functions (NANDs and NORs), this results in a cleaner notation and often a clearer idea of

the function of the circuit.We will followthis notation, which we will refer to as the bubbleto-

❘❙❚ EXAMPLE 3.2 Redraw the circuit in Figure 3.2 to conform to the bubble-to-bubble convention. Write the

Boolean expression of the new logic diagram.

Solution

A AB

C

D

C_D

Example 3.2

Using DeMorgan Equivalents to Simplify a Circuit

Figure 3.3 shows the new circuit. The NAND has been converted to its DeMorgan

equivalent so that its active-HIGH output drives an active-HIGH input on the OR gate. The

new Boolean expression is Y _ AB _ C_ _ D_. ❘❙❚

Boolean functions are governed by an order of precedence. Unless otherwise specified,

AND functions are performed first, followed by ORs. This order results in a form similar

to that of linear algebra, where multiplication is performed before addition, unless

otherwise specified.

Figure 3.4 shows two logic diagrams, one whose Boolean expression requires parentheses

and one that does not.

A AB

C

AB_ AC

A

B

(A _B

(A _B) _C)

A_B_ C

b. Parentheses required (OR, then AND)

FIGURE 3.4

Order of Precedence

The AND functions in Figure 3.4a are evaluated first, eliminating the need for parentheses

in the output expression. The expression for Figure 3.4b requires parentheses since

the ORs are evaluated first.

❘❙❚ EXAMPLE 3.3 Write the Boolean expression for the logic diagrams in Figure 3.5.

Example 3.5

Order of Precedence

A

B

S

C

P

Q

3

2

3

2

Gate 2: B _ C

Gate 3: Y _ Gate 1 _ Gate2 _ A_ _ B_ _ B _ C

Figure 3.5b: Gate 1: P_ _ Q_ _ P _ Q_

Gate 2: Q _ R_

Gate 3: S _ G_a_t_e_1_ _ G_a_t_e_2_ _ (P _ Q_)(Q _ R_) _ (P _ Q_)(Q _ R_)

3.1 • Boolean Expressions, Logic Diagrams and Truth Tables 61

Note that when two bubbles touch, they cancel out, as in the doubly inverted P input

or the connection between the outputs of gates 1 and 2 and the inputs of gate 3. In the resultant

Boolean expression, bars of the same length cancel; bars of unequal length do not.

❘❙❚

3.1 Write the Boolean expression for the logic diagrams in Figure 3.6, paying attention to

the rules of order of precedence.

A

B

CD

a.

W

X

Z

Y

FIGURE 3.6

Section Review Problem 3.1

Logic Diagrams from Boolean Expressions

to output of a logic gate network.

true and complement form.

Boolean equation or truth table.

We can derive a logic diagram from a Boolean expression by applying the order of precedence

rules. We examine an expression to create the first level of gating from the circuit inputs,

then combine the output functions of the first level in the second level gates, and so

forth. Input inverters are often not counted as a gating level, as we usually assume that each

variable is available in both true (noninverted) and complement (inverted) form. When input

variables are available to a circuit in true and complement form, we refer to them as

The first level usually will be AND gates if no parentheses are present, OR gates if

parentheses are used. (Not always, however; parentheses merely tell us which functions to

synthesize first.) Although we will try to eliminate bars over groups of variables by use of

DeMorgan’s theorems and the bubble-to-bubble convention, we should recognize that a

bar over a group of variables is the same as having those variables in parentheses.

Let us examine the Boolean expression Y _ AC _ BD _ AD. Order of precedence

tells us that we synthesize the AND functions first. This yields three 2-input AND gates,

with outputs AC, BD, and AD, as shown in Figure 3.7a. In the next step, we combine these

AND functions in a 3-input OR gate, as shown in Figure 3.7b.

K E Y T E R M S

When the expression has OR functions in parentheses, we synthesize the ORs first, as

for the expression Y _ (A _ B)(A _ C _ D)(B _ C). Figure 3.8 shows this process. In the

first step, we synthesize three OR gates for the terms (A _ B), (A _ C _ D), and (B _ C).

We then combine these terms in a 3-input AND gate.

FIGURE 3.7

Logic Diagram for

Y _AC _ BD _AD

A AC

AD

B

D

a. ANDs first

A

B

C

Y_ AC _BD _ AD

C

D

A

Y (A B)(A C

C

D

B

(A

_B)

C)

_ _ _ _D)(B _C)

_ _

Logic Diagram for Y _ (A _ B)

(A _ C _ D) (B _ C)

❘❙❚ EXAMPLE 3.4 Synthesize the logic diagrams for the following Boolean expressions:

1. P _ QR_S_ _ S_T

2. X _ (W _ Z _ Y)V_ _ (W_ _ V)Y_

Solution

1. Recall that a bar over two variables acts like parentheses. Thus the QR_S_ term is synthesized

from a NAND, then an AND, as shown in Figure 3.9a. Also shown is the second

AND term, S_T.