11/8/06

7:26 PM

Page S1

3.7 Switching Networks: A Problem-Solving Tool

S1

G START

Computer Circuits

D

GE

IN

E

TT

3.7 Switching Networks: A Problem-Solving Tool

Do you know how a computer works? All computers use a logic system devised by George Boole. The switches inside a computer chip can be arranged into a switching network, or a system of gates, delivering logical results (see Figure 1).

The most fundamental logic gates are called AND, OR, and NOT gates. The application of logic to electric circuits was pioneered by Claude E. Shannon of the Massachusetts Institute of Technology and Bell Telephone Laboratories. The idea is to simplify circuits as much as possible by finding equivalent circuits in much the same way as we find equivalent statements. At Bell Laboratories, after several days’ work, a group of engineers once produced a circuit with 65 contacts. Then an engineer, trained in symbolic logic, designed an equivalent circuit with 47 contacts in only three hours. In this section you will learn about these circuits and simplify several yourself in problems 16–20 of Exercises 3.7.

FIGURE 1

This logic diagram shows the inputs and outputs for a series of logic gates. From left to right, the gates shown are a NOT gate, two AND gates, and an OR gate. The lines that connect the gates represent the physical wires that connect “decision-making” devices on a circuit board or in an integrated circuit. For more information on logic gates see the

Discovery section of Exercises 3.7. ᭤

A. Switching Networks

FIGURE 2

FIGURE 3

Switches in series.

FIGURE 4

Switches in parallel.

The theory of logic discussed in this chapter can be used to develop a theory of simple switching networks. A switching network is an arrangement of wires and switches that connects two terminals. A closed switch permits the flow of current, whereas an open switch prevents the flow. One can also think of a switch as a drawbridge over a river controlling the flow of traffic along a road (see Figure 2).

Two switches can be connected in series (in a line from left to right), as in

Figure 3. In this network, the current flows between terminals A and B only if both switches P and Q are closed.

Can we use logic to describe circuits? In considering such a problem, let p be the statement “Switch P is closed” and let q be the statement “Switch Q is closed.” If p is true, then the switch is closed, and current flows. If p is false, then the switch is open, and current does not flow. Thus, the circuit of Figure 2 can be associated with the statement p.

When two switches are connected in series, as in Figure 3, the current will flow only when both switches are closed. Thus, the circuit is associated with the statement p ٙ q. On the other hand, in Figure 4, current will flow when either switch P or switch Q is closed. The switches are connected in parallel and the statement corresponding to this circuit is p ٚ q. What about the statement ϳp?

This statement corresponds to PЈ, a switch that is open if P is closed and vice versa. Switches P and PЈ are called complementary.

304470_Bello_ch03_sec7_web

S2

11/8/06

7:26 PM

Page S2

3 Logic

Series and parallel circuits can be combined to form more complicated networks, as shown in Figure 5. The network there corresponds to the statement

( p ٙ q) ٚ r. If we think of the switches as drawbridges, we can see that we are able to go from A to B when both P and Q are down (closed) or when R is down

(closed). Now, all compound statements can be represented by switching networks. When switches open and close simultaneously, the switches will be represented by the same letter and will be called equivalent.

FIGURE 5

P R O B L E M

S O L V I N G

Switching Networks

Construct a network corresponding to the statement ( p ٚ q) ٙ r.

➊ Read the problem and select

Design a circuit starting at A, ending at B, and corresponding to ( p ٚ q) ٙ r.

the unknown.

➋ Think of a plan.

Find the components