Information can be represented and stored on a variety of electrical/mechanical
devices. In many cases, the information relates to measurable variables
such as elapsed time or total rainfall or accumulated electrical charge
(for which the hourglass, raingauge, and capacitor, respectively, are suitable
representation devices). But what about abstract information, such as quantities
in mathematics? Here we create an analogy between something that can be
stored and measured in an electrical/mechanical device and a mathematical
value. For example, we can assign an equivalence between mathematical value
and electrical charge. The extent to which we can operate on that electrical
charge via the capacitor and our measuring instruments is the degreee to
which we can perform analogous mathematical calculations.
There are problems, however, with relating mathematics to storable parameters
on physical devices. Two of the more important ones are 1) measuring instruments
are rarely more accurate than three decimal digits--so mathematics carried
out through these devices would have intrinsic limited accuracy; 2) there
is typically unrecoverable loss of information--a capacitor could leak
away part of its charge, i.e., its analogous mathematical value would arbitrarily
But there is a solution to these problems: store mathematical values
in discrete rather than analog form. Here one uses devices whose variations
are limited to discrete states--typically two, e.g., on or off, positive
or negative, closed or open. Then, by representing mathematical quantities
in a number system having only two digits--a binary number system--any
value can be represented with arbitrary accuracy by linking together a
sequence of two-state devices and setting the appropriate state for each
device. Information integrity in this discrete representation is better
than that of analog representation because here information loss requires
an arbitrary change of state of a device, not a drift in value. That is
much less likely, and there are ways to correct for it.
Computers are developed to store and mathematically manipulate quantitative
information. Earlier computers were analog--usually electrical or mechanical.
Circuits and mechanisms were built to represent fixed mathematical problems
with results appearing in the form of a final voltage or a rotation angle
of a gear. The electrical and mechanical equivalents of addition, multiplication,
integration, and differentiation were incorporated into these computers.
Complex problems could be solved, albeit with the accuracy problems mentioned
Then the digital computer emerged. Here the electrical and mechanical
analogies for mathematical operations are replaced by the digital manipulation
of 1's and 0's--the two possible states of binary devices storing information.
How does one carry out mathematics with binary devices? That is the topic
of this exercise.
The objective is to devise and to piece together a series of binary
logic elements to effect an ultimate mathematical operation such as addition,
or subtraction, or multiplication. It is necessary and sufficient to consider
logic elements for which there are two binary inputs and one binary output.
We consider three logic elements from which all binary logic may be constructed:
the AND, OR, and NOT gates.
Note: in the problems that follow, use the circuit
builder to develop your circuits. When you link to the circuit builder
you will be asked to specify the number of inputs and outputs--that will
be determined, of course, by the problem. You will then be presented with
the circuit display having the specified number of inputs and outputs.
To build your circuit, drag logic components into the circuit area. Inputs
(circles) may be connected to outputs (squares) by clicking first on one,
then dragging to the other and releasing the mouse button. (A single output
(square) may be connected to several inputs (circles), but only one output
may be connected to any input.) Once your circuit is completed you can
choose either single input or all inputs. With the single input option,
you can specify a particular bit configuration of inputs. Once these inputs
are specified, the state (1 or 0) of each logic line will be displayed.
This will give you an opportunity to find errors in your circuit. With
the "all possible inputs" option, outputs for all possible inputs
will be presented. This should be your final confirmation that your circuit
Click here to view the available logic elements,
their graphic representation, and their input/output tables.
1. Confirm that each of the elementary circuits behaves as advertised.
That is, use the circuit builder to establish the
logic behavior of AND, NOT, OR, NAND, NOR. These will all be two-input
and one output circuits (except for NOT, which will be one input and one
2. Using only the component NAND, create a circuit that is equivalent
to the logic of an AND gate. Do the same to emulate a NOT gate. Do the
same to emulate an OR gate. (If this is doable, it means that all binary
logic circuitry can ultimately be generated from the single logic element
3. Using only the component NOR, see if you can create circuits equivalent
to AND, OR, and NOT is you did in problem 2.
4. Using only AND, NOT, and OR produce a three-input AND circuit, i.e.,
the output is 0 unless all three inputs are a 1. (You don't have to use
all three circuit elements.)
5. Using only AND, NOT, and OR produce a three-input OR circuit, ie.,
the output is 1 if any of the inputs is 1.
6. Create a two-input "adder" with two outputs: the one-digit
result of the add, and the value of a "carry" bit. In binary
arithmetic, 1+1=0 with a carry=1.
7. One of the more interesting public works problems is the "Superbowl"
problem. At the beginning of halftime during the Superbowl, 35 million
toilets are flushed almost simultaneously. The resulting loss of water
pressure wreaks havoc on many municipal water systems. Here you will
solve the problem for a "three toilet" system. Devise a logic circuit
whose "1" inputs represent "flushes" and whose "1" outputs represent
opened water-feed valves.
If no more than one toilet is flushed, then that toilet's
water valve opens, the others remaining closed. If more than one toilet
is flushed, then all the water valves remain closed.
8. You are designing a robot to move toward a light source. Three
photosensors SL, SC, and SR are mounted
at the front of the robot pointing 45o to the left, straight
ahead, and 45o to the right, respectively. Two wheels
WL and WR are powered depending on the output
of the sensors. If SL detects light, the robot is pointing
too far to the right, and the right wheel WR must be powered
up to turn the robot to the left. The opposite is necessary if
SR receives light. If only the forward-pointing sensor
SC is lit, then both wheels WL and WR
should be powered to propel the robot forward. If one treats the sensors
as having binary outputs, i.e., either "on" or \off", and the powered
wheels as being "on" or "off", a simple logic circuit can be used to
actuate the wheels under each sensor condition. Create such a logic
circuit using only NAND gates, and using the least number of these.
9. This picture is a schematic
diagram of a 14-pin CMOS chip that
contains 4 NAND gates. Your task is to design a printed circuit board that
implements the robot circuit you produced in problem 8. Using as many
CMOS chips as necessary, and taking into consideration which pins
constitute inputs and outputs, create the circuit by connecting the
appropriate pins. But now, try to route the connections so that the
"wires" don't cross one another. This is a typical problem in printed
circuit design. The objective is to "etch" the circuit onto a single layer
of a copper-coated circuit board which contains pin holes to accommodate
the chips. (Note: this problem does not require the
use of the CIRCUIT BUILDER. Just sketch out the connections between the