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.

**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.