The Digital Domain: Logic Gates

MF: lightly clean up to make the text more concise

Do we have any interest in salvaging the logic gates/XOR project that Selim and I worked on? --MF, 3/25/19

On this page, you review three Boolean operators (and, or, and not) and learn how they relate to electronic circuitry.

In a circuit with billions of transistors, or even thousands of transistors, hardware designers can't think about each individual transistor. Just as programmers use abstraction, hardware architects use abstractions, in which a group of transistors and other circuit elements are considered as a single thing. What kinds of things? There are basically two kinds, one for memory and one for computation.

Learn more about memory.

Memory is made out of flip-flops. A flip-flop is a circuit that has two stable states, on and off. An input signal can tell it to turn on, turn off, or change whatever it's state is. Once that happens, the flip-flop stays in the new state until it gets another signal. It has an output that reflects its state: on if the flip-flop is on, off if it's off.

Boolean Operators

The circuits to do computation are more interesting. They compute functions, just like reporters in Snap!. Since computers do a lot of arithmetic, you might think that the basic circuit functions would be addition, subtraction, multiplication, and division, but that's not the case. Of course there are circuits to do those things, but they're made out of logic gates: circuits that compute Boolean functions: and, or, and not.

The reason that Boolean functions are considered more fundamental is that their inputs and outputs can be represented with a single wire going into or out from the circuit. That's not true about arithmetic functions. If you consider a voltage on a wire as meaning 1, and no voltage as meaning 0, then you have to see that an adder will have three possible output values, because 1+1=2, which is neither 0 nor 1. By contrast, if you consider a voltage on a wire as meaning True, and no voltage as meaning False, then the output from a Boolean function of two inputs can still only be True or False, so only one output wire is needed.

You saw some examples in Unit 2 Lab 3: Making Decisions by Using Predicates: AND, OR, and NOT:
(true) AND (true) reporting true (true) AND (false) reporting false (false) AND (false) reporting false (true) OR (true) reporting true (true) OR (false) reporting true (false) OR (false) reporting false NOT (true) reporting false NOT (false) reporting true

Some other ways to think about Boolean operators: It is possible to emulate Boolean operations electronically and these operations are sometimes represented as truth tables (either with true/false or ones/zeros).

Logic Gates

Inside a computer, Boolean operations are implemented in physical circuitry using logic gates. (A single gate implements one of the basic functions and, or, or not.) Logic circuits are often represented with drawings that help engineers see how the information will flow through a circuit. For example, the following diagram of a logic circuit with two gates represents the Boolean expression A or (A and B). Can you see how?

logic gate diagram of (A or (A and B))
  1. Talk with Your Partner Look at the logic circuit drawn above. For what values of A and B will the output be true?
On the previous page, you learned about tungsten and tin, and here we're talking about Boolean functions. In what sense is this less abstract? From the point of view of the chip designer, logic gates are the fundamental building blocks of a digital circuit. (The actual physical chip fabrication is at an even lower level of abstraction, in the analog domain.) diagram of computer abstraction hierarchy showing three levels of decreasing abstraction: software domain (including applications, programming languages, libraries, and operating systems), digital domain (including architecture, components, integrated circuits, and logic gates), and analog domain (including transistors); there is a dividing line between the software and digital domains labeled 'program abstraction barrier' and a dividing line between the digital and analog domains labeled 'digital abstraction barrier;' there is a vertical double-headed arrow on the right indicating that the items listed first on the list (and their sub-lists) have a 'high level of abstraction' and those lower on the list have a 'low level of abstraction'
  1. Which of the following expressions will report true?
    1. (T and F) and (not (T and F))
    2. (not (T or F)) or (T or F)
    I only
    II only
    I and II
    Neither I nor II
  2. Which of the following logic circuits will report true? (T stands for true, and F stands for false.)
      This problem is probably harder than something you'll see on the exam, so if you can get this one, you are doing great!
    1. logic gate diagram of (not ((T and F)) or (T and F))
    2. logic gate diagram of ((T or F) and (not (T or F)))
    I only
    II only
    I and II
    Neither I nor II

How do engineers draw logic gates?

logic gate diagram of (not and) and (or) Engineers typically draw logic gates horizontally and use special shapes that represent each gate:
AND-gate OR-gate NOT-gate
For example, engineers would draw the logic circuit shown at right like this:
Engineer's version a logic gate with (not and) and (or)
Do an image search for "logic gate diagrams" to see more examples.
There is a commented out ifTime here that would link to the adder project. I think we should add it back in as a TIF once that optional project is done. --MF, 11/30/17