CoSTARS Sidebar #1:
Logical Circuits


1.  Background

In this sidebar, we learn about Logical Circuits, which are the building blocks of digital computers.  We will use the xLogicCircuits lab, a fantastic learning tool developed by David Eck at Hobart and William Smith Colleges in beautiful Geneva, NY.

Note that Dr. Eck provides an excellent and detailed introduction in his lab, and we will provide just a few extra comments here.  So the first step of this sidebar is to use the xLogicCircuits lab.

2.  The xLogicCircuits Lab

Read about the xLogicCircuits lab from here:
   http://math.hws.edu/TMCM/java/labs/xLogicCircuitsLab1.html
Note that you should not run the lab as an applet (do not use the "Launch xLogicCircuits" button), as you will not be able to save your work.  Instead, use the application version, as described in the next step.

Run the xLogicCircuits Lab application (not applet) from here:
   http://math.hws.edu/TMCM/java/classes/xLogicCircuits.jar
Note that you may have to first save this to your desktop and then run it from there.

To include the examples from the lab, save this file onto your desktop and then run the lab software and load this file:
   FirstExamples.txt

If you are interested in material beyond these notes, you might read the second circuits lab from the TMCM web site, which discusses memory circuits.  In that case, you would also want the examples from that lab, which are in this file:
   MemoryCircuits.txt

Problems #1-10:  Do Exercises 1-10 from the xLogicCircuitsLab.

3.  Logical Functions, Truth Tables, and Logical Circuits

You are already familiar with functions from your math courses.  So this is a function:
   f(x) = x + 5
And this function f(x) clearly takes a number and adds 5 to it.  Just as functions can use numeric variables, they can also use boolean variables.  You should recall that boolean variables can have only one of two values -- true or false, which we also sometimes write as 1 or 0, respectively.  So we can have this function:
   g(x) = NOT x
This is a function, just like f(x), but here the variable x must be a boolean (true or false), and the result of g(x) is also a boolean (true or false).  In fact, the result of g(x) is the opposite of x.  So if x is true, NOT x is false, and vice versa.

Definition:  A boolean logical function is a function over boolean variables that computes a boolean result.

We can specify a boolean function using a Truth Table.  This is a table that lists all the possible values of the input variables to the function, and for each combination of values it also lists the function's output.  In this way, the behavior of the function is fully described.

Here is the truth table for the function g(x) = NOT x:

  x     NOT x
false   true
true    false

Recall that we often write true as 1 and false as 0, so here is the more succinct form of this table:

x  NOT x
0    1
1    0

Note that most boolean logical functions take more than one input variable.  For example, the AND function takes two variables, and it is true only if both of its input variables are true, and false otherwise.  So (x AND y) is true if both x and y are true (see why it is called AND?).  Here is its truth table:

x  y  x AND y
0  0    0
0  1    0
1  0    0
1  1    1

Notice that the truth table requires four rows to list all the possible legal values for x and y.  Also, while we can list the rows of this table in any order, it is customary to list them in this way:  if the two input variables were viewed as a single 2-digit binary number, the rows are listed in increasing order (00, 01, 10, 11).  See?

Another important logical function is OR, where (x OR y) is true if either x or y is true, or if both are true.  Here is its truth table:

x  y  x OR y
0  0    0
0  1    1
1  0    1
1  1    1

Now, this was supposedly a lab on logical circuits, not logical functions.  The difference?  You can build logical circuits as real physical devices that you can hold, touch, and in some cases, even plug in and use to write Java programs (as, after all, computers are built out of logical circuits).

We can build a logical circuit that is equivalent to the OR function.  To do this, we must give physical meaning to the 1's and 0's in the truth table.  So we say that a 1 means that there is voltage or electricity present, and a 0 means that there is not.  Then, we build a device with two wires leading in and one leading out, as such:

Now, on the left side of the picture we have two switches.  These are just like switches on the wall, and can turn wires A and B on (1) or off (0).  Also, on the right side of the picture we have a light.  This will shine if wire C is on (1) and will not shine if it is off (0).

The magic is this: electrical engineers have figured out how to build a device, called an OR gate, that has the behavior exactly described by the OR boolean logical function.  That is, if either A or B is switched ON, then C will be ON, and the light will shine.  If both A and B are OFF, then C will be OFF and the line will not shine.  If you were to build a table describing this behavior, it would like this:

A    B   C
OFF OFF OFF
OFF ON  ON
ON  OFF ON
ON  ON  ON

Rewriting ON as 1 and OFF as 0, we have:

A  B  C
0  0  0
0  1  1
1  0  1
1  1  1

If you compare this with the table for the boolean logical function (x OR y), you will see that the tables are the same.  So, in a deep sense, the physical OR gate computes the logical OR circuit.  It is a simple computer.  A very simple one.  But it is a computer nonetheless!

Similarly, electrical engineers can build a NOT gate that computes the NOT function and an AND gate that computes the AND function.

Now, so long as we can reduce a logical function to AND, OR, and NOT, then we can build a physical circuit (that is, a collection of physical gates) that computes that function.

4.  Logical Functions as Binary Arithmetic Functions

When we think of computers, we not only think of logic, but also of arithmetic.  These seem different at first blush.  Sure, we can build a circuit that computes (x AND y), but how about x plus y or x times y?

Part of the genius of the early pioneers in computers is that they tied these two ideas together.  They figured out how to perform arithmetic using logical functions.  Genius!  The trick is to represent numbers in binary, or base 2.  You already know how to do this.  So, for example, you know that 0101 in binary equals 4+1 or 5 in decimal.  But how does this help?

To see this, let's solve the simplest arithmetic problem:  add two single bits.  We will label the input bits A and B, and we have this table:

A B A + B
0 0   0
0 1   1
1 0   1
1 1   2

This table has a problem.  The last number is a 2 (since 1+1=2), and we have to represent the entire table in binary.  So we have to convert that number to 10 (2 in binary), giving us:

A B A + B
0 0  00
0 1  01
1 0  01
1 1  10

The next part of the genius was in teasing apart a binary number into individual binary bits.  See, the logical functions like AND, OR, and NOT only have one output bit, but the answers in this table for A+B have two bits.  The solution is to split these bits into their own columns, which we will label C and D, where we think of the number CD as the number being computed:

A B A + B C D
0 0  00   0 0
0 1  01   0 1
1 0  01   0 1
1 1  10   1 0

Do you see how CD is equivalent to (A+B)?  But now we can look at C and D individually, and each is its own logical function!  Consider C:

A B C
0 0 0
0 1 0
1 0 0
1 1 1

We've seen this function before.  This is just the AND function!  So C = (A AND B).  Now onto D:

A B D
0 0 0
0 1 1
1 0 1
1 1 0

This is trickier.  D is a new logical function for us.  It is XOR, where (A XOR B) is the same as (A OR B), except that exactly one and not both must be true.  We say XOR is exclusive-or because it excludes the case where both A and B are true.  Now, if we had an XOR gate, we would be done.  If we did not have an XOR gate, however, we could use a combination of AND, OR, and NOT gates to get the job done, because (A XOR B) is equivalent to (((NOT A) AND B) OR ((NOT B) AND B))).  How did we know this?  We'll explain soon.  But for now, we can see that if we connect A and B to C with an AND gate, and we connect A and B to D with an XOR gate (or its equivalent), then we will have built a simple device that computes 1-bit addition.

So we did it!  We converted an arithmetic problem (addition) to a logical problem (by splitting the answer into individual bits, and thinking of each bit as a logical function over the input).  Then we converted these logical functions into actual physical circuits, and in this way we built an arithmetic computer!!!

Of course, a 1-bit adder is not much of a computer, but if we can do it for 1 bit, we can surely do it for 2, or 32 for that matter.  And if we can add, we can surely subtract, multiply, and divide.  You bet!  And so we see how can extend these ideas to construct all the arithmetic circuits inside a modern computer!

Now, the 1-bit adder we just wrote is called a Half-Adder.  Study the xCircuitsLab notes to understand how two half-adders are combined to form one Full-Adder, and then how four full-adders are daisy chained to form a 4-Bit-Adder.  It is important for you to understand how the daisy-chained full-adders really do correspond to how you would add two numbers yourself.  Once you understand a 4-bit-adder, then use your knowledge of representing negative numbers in two's complement to understand the operation of 4-Bit-Minus.

Problem 11:  Using just AND, OR, and NOT gates, create your own Half-Adder.  It should take two bits A and B as input, and it should have two bits C and D of output, where A+B=CD.  Arrange your output bits so the high-order bit (the 2's bit) is on the left.  Save your Half-Adder as a circuit named MyHalfAdder.

Problem 12: Using your MyHalfAdder circuit, construct a Full-Adder, called MyFullAdder.

Problem 13:  Using your MyFullAdder circuit, construct a 2-Bit-Adder, called MyTwoBitAdder.  This takes two 2-bit numbers (for 4 bits of input) and produces their 3-bit sum as output.

5.  DeMorgan's Laws

In class, we discussed DeMorgan's Laws:
     (x AND y) ==  (NOT  ((NOT x) OR (NOT y)))
and:
     (x OR y) ==  (NOT  ((NOT x) AND (NOT y)))

Problem 14:  Confirm each of these laws is true using truth tables.  To do this, construct a truth table for (x AND y), and then another for (NOT ((NOT x) OR (NOT y))).  Show that their last columns are the same, and so the two expressions are equivalent.  Do the same for the other law (x OR y).

Problem 15:  Confirm each of these laws again using circuits.  To do this, construct a circuit that has two inputs, x and y, and two outputs.  The first output is (x AND y).  The second output is (NOT ((NOT x) OR (NOT y))).  Test your circuit over all four possible combinations of values for x and y, and verify that the two outputs are the same for every input.  Do the same for the other law (x OR y).

Problem 16:  We can restate DeMorgan's Laws as such:
      (NOT (x AND y)) == ((NOT x) OR (NOT y))
and
     (NOT (x OR y)) == ((NOT x) AND (NOT y))
Explain why this works.

Problem 17:  We have seen that (x XOR y) == ((NOT x) AND y) OR ((x AND (NOT y)).  Use repeated applications of DeMorgan's Law (along with the fact that NOT NOT x is equivalent to x) to show that:
   (x XOR y) ==NOT ((x OR (NOT y)) AND ((NOT x) OR y)))
Show your work!  Also, create a truth table that verifies this result.
Hint:  Start with ((NOT x) AND y) OR ((x AND (NOT y)).  See how this has the form (A OR B), where A is the expression ((NOT x) AND y) and B is the expression (x AND (NOT y))?   Now, DeMorgan's Law states that (A OR B) can be rewritten as (NOT ((NOT A) AND (NOT B)), so do this, but replace A and B with the expressions they stand for.  Then you will have to do this two more times, and finally eliminate any double-negatives (NOT-NOTs).

Problem 18:  For this problem, we will take the first steps toward making a circuit that computes 2-bit multiplication.  This circuit should have 4 inputs, A, B, C, and D, representing the two two-bit binary numbers AB and CD, and three bits of output, E, F, and G, representing the 4-bit number EFGH (where E is the 8's digit) resulting from multiplying AB by CD.  Note that the largest 2-bit number is 11, which is 3 in decimal, so the largest product is 3x3, or 9, which requires 4 bits to represent.  This is why we have 4 bits of output.  So, for example, if our input was 1011, then A=1, B=0, C=1, D=1, so AB = 10 (in binary, which is 2 in decimal) and CD=11 (in binary, which is 3 in decimal).  Now, 2 times 3 equals 6, so 4-bit output should equal 6, which in binary is 0110.  So our output would be 0110.

Here is the start of the truth table you should use for this circuit:

A B  C D  E F G H
0 0  0 0  0 0 0 0  (0 x 0 = 0)
0 0  0 1  0 0 0 0  (0 x 1 = 0)
0 0  1 0  0 0 0 0  (0 x 2 = 0)
0 0  1 1  0 0 0 0  (0 x 3 = 0)
0 1  0 0  0 0 0 0  (1 x 0 = 0)
0 1  0 1  0 0 0 1  (1 x 1 = 1)
0 1  1 0  0 0 1 0  (1 x 2 = 2)
0 1  1 1  0 0 1 1  (1 x 3 = 3)
1 0  0 0  0 0 0 0  (2 x 0 = 0)
1 0  0 1  0 0 1 0  (2 x 1 = 1)
1 0  1 0  0 1 0 0  (2 x 2 = 4)
1 0  1 1  0 1 1 0  (2 x 3 = 6)
...

Be sure you understand this table!  For this problem, you just need to provide the final 4 lines of the table.
 

Problem 19 (BONUS):  Finish problem #18 by creating the circuit defined by the truth table you finished.  This circuit has 4 inputs, A, B, C, and D, and 4 outputs, E, F, G, and H.  Each of the output lines can be thought of as its own function over the input lines.  Think about that!  As one example, line E (which is the 8's bit) is only true when you multiply 3x3 to get 9, so it is only true when all the inputs are true.  That is:
   E = (((A AND B) AND C) AND D)
Great -- that's one down (E) and three to go (F, G, and H).  Do these in the same way, then construct your circuit in xCircuitsLab.  Finally, check that your circuit works by testing it with various sample inputs (for example, as with the previous problem, when you enter 1011, this represents the problem 2x3, and the answer is 6, or 0110, so your circuit should output 0110.  You will want to check other inputs and outputs as well.

6.  Disjunctive Normal Form

In class, we also discussed Disjunctive Normal Form, or DNF.  There is a simple technique for generating the DNF for any logical function:

  1. Write the function's truth table;

  2. For each row that is a 1 (true), write a conjunct (AND's) selecting that row's input variables;
    So if we have two input variables, x and y, and if x is 0 and y is 1, the conjunct would be ((NOT x) AND y).  Notice that this expression is only true on that one line.  On any other line, either (NOT x) is false or y is false, and so ((NOT x) AND y) is false.  So that expression selects the one line from the truth table.

  3. Connect these line-selecting conjuncts with disjuncts (OR's), since the expression is true for any of these lines.

Let's go over that again with an example.  Let's work with XOR.  So first we construct the truth table:

x  y  x XOR y
0  0    0
0  1    1
1  0    1
1  1    0


Now, we add  conjuncts that select the rows that have 1's in them, as such:

x  y  x XOR y  conjunct
0  0    0         -
0  1    1      (NOT x) AND y
1  0    1      x AND (NOT y)
1  1    0         -

Finally,  we take the disjunct of those conjuncts -- that is, we OR them together, to get:

     x XOR y == ((NOT x) AND y)  OR  (x AND (NOT y))

The expression on the right is the Disjunctive Normal Form of (x XOR y).

Note that we can apply this same technique to any logical function.  This is a big deal, so we will repeat it:

There may be (and often is) a better way to express the function, perhaps using fewer gates, but you can always construct the DNF.  What's more, it's a mechanical process, as described above.  So if you do not see a clever little circuit for some function, you can always use brute force and construct the DNF for it.

Problem 20:  Construct the DNF for each of the following functions.  Then construct the circuit in xLogicCircuits and verify that the circuit works the same as the original expression.

  1. ((NOT x) OR y)

  2. (NOT (x OR (NOT y)))

7.  Logical Bases ({And, Or, Not},  {And, Not},  {Or, Not}, {Nand}, {Nor}, others?)

So far, we have seen that we can reduce arithmetic functions like adding and multiplying to boolean logical functions.  Then we saw that we could reduce any boolean logical function to Disjunctive Normal Form.  Finally, because DNF only uses AND, OR, and NOT gates, we conclude that we can build a computer using only AND, OR, and NOT gates.  That is worth repeating:

Wow!  That's amazing!  We will call a set of different gates that together are enough to build any logical function (and so, any computer) a logical basis.  So we just determined the amazing fact that the set {AND, OR, NOT} forms a logical basis.  Can we do better?  Can we use find a smaller logical basis?

Yes, we can.  To begin with, consider applying DeMorgan's Law:
     (x AND y) ==  (NOT  ((NOT x) OR (NOT y)))
and:
     (x OR y) ==  (NOT  ((NOT x) AND (NOT y)))

Once we reduce an expression to its DNF, we can use the first form of DeMorgan's Law to replace every (x AND y) with  (NOT  ((NOT x) OR (NOT y))).  But this eliminates all the AND's, leaving only OR and NOT.  So { OR, NOT } is a logical basis.  Similarly, we could have used the second form of DeMorgan's Law to replace the OR's with AND's and NOT's.  So { AND, NOT } is also a logical basis!  Wow.

Problem 21:  Use DeMorgan's Laws to rewrite the DNF's from Problem 20 as follows.

  1. Rewrite the DNF for ((NOT x) OR y) so that it only uses NOT and OR (no AND's).

  2. Rewrite the DNF for (NOT (x OR (NOT y))) so that it only uses NOT and AND (no OR's).

Now we're down to two kinds of gates.  Can we do better?  Can we build an entire computer out of just one kind of gate?  Let's see.  Consider the NOR gate.  This gate, which can be constructed in the real world out of physical transistors, takes two inputs x and y and outputs true only if neither x nor y is true.  It is the negation of the OR gate.  So we have:
      (x NOR y)  == (NOT (x OR y))
With the following truth table:
x  y  x OR y  x NOR y
0  0    0        1
0  1    1        0
1  0    1        0
1  1    1        0


Now, we know that {OR, NOT} is a logical basis, so we try to construct each of these two gates using only NOR gates.  First, for NOT, we see the following:

x  x OR x  x NOR x
0    0       1
1    1       0

Be sure you understand this table.  It shows that (x NOR x) is equivalent to (NOT x).  So we can rewrite each NOT gate with a NOR gate.  What about OR gates?  Well, since NOR is the negation of OR, NOT-NOR is the double-negation, which is equivalent to OR.  That is:
     (NOT (x NOR y)) == (x OR y)
But we know that (NOT z) == (z NOR z), so we put these together to see that:
     ((x NOR y) NOR (x NOR y)) == (x OR y)

Now we've done it!  We have shown that { NOR } is a logical basis.  Or, reworded, we have proven this amazing fact:

Wow!  This is incredible.  With enough NOR gates, and enough patience, you can wire together a modern digital computer.  In fact, you would use exactly these steps:

  1. For each arithmetic function to compute, reduce the function to a boolean logical function.

  2. For each of these boolean logical functions, express the function in Disjunctive Normal Form.  Now we have circuits with AND, OR, and NOT.

  3. Use DeMorgan's Law to replace each AND with OR and NOT, because (x AND y) ==  (NOT  ((NOT x) OR (NOT y))).

  4. Next, replace each OR with NOR with this rule:  (x OR y) == ((x NOR y) NOR (x NOR y))

  5. Finally, replace each NOT with NOR with this rule:  (NOT x) == (x NOR x)

  6. That's it.   The only gates remaining are NOR gates!

Problem 22:  Using this technique, rewrite the expression in part (a) of Problem 21 using only NOR gates.  This is tedious!  Now, for bonus, create this circuit in xLogicCircuits.  Note that you can construct a NOR gate by clearing the screen, constructing a simple circuit that connects the output of an OR gate to a NOT gate and then to the output, and then naming this "NOR" and clicking on the "iconify" button.  Now you have a NOR gate to construct your XOR circuit!

Problem 23:  Just as NOR is (NOT (x OR y)), NAND is (NOT (x AND y)).  Also, just as NOR is a logical basis, so is NAND.  Prove this fact by showing how to convert circuits that only have AND and NOT gates into equivalent circuits that only have NAND gates.  The argument follows the analogous argument for NOR gates as just described.

8.  Bonus:  Circuits That Remember

This is just the tip of the iceberg for digital circuits, and a lot more cleverness is required to build an actual modern computer.  For example, how can you use circuits to build computer memory?  We need circuits that remember their input, and then can change their input on demand!  This is no small feat!  If this interests you, and/or if you are interested in obtaining more bonus points, then you should continue on with Part 2 of the xLogicCircuits Lab.  Submit your answers to the 9 Exercises in that lab for your extra bonus points.  Carpe diem.