Last updated: 3/18/03
Link back to course Welcome...

Worksheet: Logic Gates

The worksheet on Binary Arithmetic With Switches showed that simple mechanical switches can carry out arithmetic. While switches are easy to understand, and were actually used in some early computers, they are, however, slow. Even though switches are no longer used, computers are still built with these and similar functions. There have been many technologies used in computers to replace switches, including vacuum tubes, transistors and different generations of microchips. However, the basic functions have remained constant. Because the technology and construction details change while the function remains constant, it is very useful to have representation or symbols for the functions, independent of the technology used to implement the function. This set of representations or symbols is called logic gates. The logic part because they represent classical logical relationships, and gates because they can steer signals to different parts of a large circuit. Here are some examples of logical relationships:

1. "If you wash the dishes and clean your room, you can go to the party." Your kid has washed the dishes but not cleaned the room. Does your kid get to go to the party under this rule? (AND)
2. "I will let you go to the party if you wash the dishes or clean your room." Your kid has cleaned their room but the dishes are still dirty. Does your kid get to go to the party under this rule? (OR)
3. Same rule as #2, but your kid both washed the dishes and cleaned up their room - do they get to go? (Inclusive or, OR, includes cases where both conditions are true)
4. "I either aced that test (90 or above) or I bombed it (less than 70)." What are the chances of getting a grade that is 90 or above and below 70 at the same time? (Exclusive or, XOR, excludes case where both conditions are true)

Logic gates are drawn with

• a shape representing the function of the gate
• two input lines on the left-hand side (sometimes more, but not here), and letters to identify the inputs
• one output line on the right-hand side, and a letter to identify the output

The logical function is made explicit with a truth table. In the truth table, 0 represents false and 1 represents true.

Here are the most important examples. The name of the gate is its logical function that relates the inputs to the outputs. Take an AND gate, for example. Its output is true (1) if input A is true AND (2) input A is true. If you have taken Critical Thinking, you should recognize the logical functions. The difference is that here, we are considering them as actual hardware. The logical functions used here are:

• The output of an AND gate is true if (1) input A is true AND (2) input B is true, otherwise the output is false.
• The output of an OR gate is true if (1) input A is true OR (2) input B is true, otherwise the output is false (inclusive or).
• The output of an XOR gate is true if (1) input A is true XOR (2) input B is true, otherwise the output is false (exclusive or).

Notice that all of these can be summarized as follows (one thing to memorize instead of three):

• The output of an XXX gate is true if (1) input A is true XXX (2) input B is true, otherwise the output is false.

Also, the function goes with the shape of the drawing; you need to memorize this association.

Always start at the left with the inputs, and end at the right with the outputs.

1. AND gate. So named because the output is true if Input A is true and Input B is true. In the switch worksheet, this was the series connection. This function carries out binary multiplication.

2. OR gate. This is the normal inclusive or; the output is true if A is true, or if B is true, or if both are true. Inclusive means that the case where both inputs are true is included in making the output true.

3. Exclusive or, or XOR (pronounced "zor"); the output is true if A is true, or if B is true, but not if both are true. This function carries out binary addition, except for the carry in the case of 1 + 1.

More complicated circuits: combinations. The circuit below has two logic gates, an XOR and an AND. The drawing shows that the input at A is delivered without change to the top input of the XOR and the top input of the AND. Work from left to right, same as before.

4. Combining the XOR and AND gates carries out binary addition with the carry. Which bit (C or D) is the carry? Which one is the addition?

To illustrate the steering capabilities of gates, we need one more feature, inversion. Any signal line (an input or output) can be inverted by placing a circle on its connection to the body of the logic gate. The circle inverts the truth of that input. This means that it changes true to false or false to true, before it gets used by the gate itself.

5. Using the double inversion in the circuit above, complete the truth table.

Now, with the inversion function, we can see how gates can steer.

6. Fill in the truth table for this circuit. After you have finished, notice that bit A steers bit B from C to D. In this way, data can be steered from a multiplier to an adder; we can select which binary operation (multiplication or addition) to perform. Also, data can be steered to or from a particular memory location.

A more complicated problem. Work from left to right. Do not try to find the output of a gate before you have found both of its inputs, since the inputs cause the outputs.

7. Fill in the truth table for the circuit above. HINT: Make a bigger truth table off the side, to show the values in between the gates.

NOTE: On Quiz and the Final, the full truth table takes too long to fill out. More likely is a question giving a value for A and a value for B, as in A = 0 and B = 1. This amounts to doing a single row of the truth table.