CPSC 100, Spring 1997:
Answers to Quiz #2

This is the second quiz from the course Computer Science 100: Principles of Computer Science, taught by David Eck. The answers that are included here are sample answers only. There might be many other answers to a given problem that would also receive full credit. See the home page for the text, The Most Complex Machine, for more information about the course.


Question 1:

Define the term logic gate.

Answer: A logic gate is a simple circuit that is meant to compute the result of a simple logical operation such as AND, OR, or NOT. For example, an AND gate has two inputs and one output. Its output is on if its first input is on AND its second input is on.

Note: A logic gate can be built from just a few transistors. Logic gates can be combined to produce larger, more complex circuits. The association between gates and logic is useful because logic can be used as a tool for building and understanding circuits.


Question 2:

Consider the following circuit. Write down the logical expression that expresses the output of the circuit in terms of the three inputs, A, B, and C.

(image of circuit)

Answer: (A or (not B)) and (not (B or C))

Note: This formula is obtained by working from left to right and finding a formula for the output of each logic gate in the diagram. The leftmost NOT gate computes the value of the expression (not B). The top OR gate combines this value with A to compute (A and (not) B). And so on.


Question 3:

Add the following two binary numbers:

                    1 0 0 1 1 1 1 0 0 1
                      1 0 0 1 1 0 0 1 1
                 -----------------------

Answer:Here is the sum shown with the answer and the carry from each column to the next shown in red:

                    0 0 1 1 1 0 0 1 1
                    1 0 0 1 1 1 1 0 0 1
                      1 0 0 1 1 0 0 1 1
                 -----------------------
                    1 1 1 0 1 0 1 1 0 0

Question 4:

Explain briefly: (1) What is the purpose of a full-adder circuit; and (2) How can a circuit for adding two 16-bit binary numbers be built from full adders.

Answer:A full adder is a circuit that computes the sum of three bits and gives a two-bit answer. A circuit for adding two 16-bit numbers can be built from 16 full-adder circuits. Each full-adder does one column of the sum. The full adder for a given column adds two bits from the input numbers together with a one-bit carry from the previous column to the right. The adder produdes a two-bit answer; one of these bits is used as a carry into the next column.


Question 5:

Explain what is meant by a feedback loop in a logic circuit, and draw an example circuit that contains a feedback loop.

Answer: In a feedback loop, the output of a logic gate is fed back, either directly or though a sequence of other gates, into and input of the same gate. The circuit contains a loop of wires and gates. The pictures below show two feedback loops. In the fist, the output of a NOT gate is fed directly back into the input of the gate. In the second, there are two gates in the loop.

(circuits with feedback loops)


David Eck, 18 April 1997