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.txtIf 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 usebooleanvariables. 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 aboolean(true or false), and the result of g(x) is also a boolean (true or false). In fact, the result of g(x) is theoppositeof x. So if x is true, NOT x is false, andvice versa.Definition: A

boolean logical functionis 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 listsall the possible valuesof 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:

xNOT xfalse true

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

xNOT x0 1

1 0Note 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

bothof 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:

xyx AND y0 0 0

0 1 0

1 0 0

1 1 1Notice that the truth table requires

fourrows to listallthe 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

eitherx or y is true, or ifbothare true. Here is its truth table:

xyx OR y0 0 0

0 1 1

1 0 1

1 1 1Now, this was supposedly a lab on logical

circuits, not logical functions. The difference? You canbuildlogical 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

physicalmeaning 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 twoswitches. 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 alight. 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:

ABCOFF OFF OFF

OFF ON ON

ON OFF ON

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

ABC0 0 0

0 1 1

1 0 1

1 1 1If 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 gatecomputesthe 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 ofarithmetic. These seem different at first blush. Sure, we can build a circuit that computes (x AND y), but how about xplusy or xtimesy?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:

ABA + B0 0 0

0 1 1

1 0 1

1 1 2This 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:

ABA + B0 0 00

0 1 01

1 0 01

1 1 10The 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

oneoutput bit, but the answers in this table for A+B havetwobits. 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:

ABA + BCD0 0 00 0 0

0 1 01 0 1

1 0 01 0 1

1 1 10 1 0Do 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:

ABC0 0 0

0 1 0

1 0 0

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

ABD0 0 0

0 1 1

1 0 1

1 1 0This 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-orbecause itexcludesthe 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 oneFull-Adder, and then how four full-adders aredaisy chainedto form a4-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 of4-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-bitmultiplication. 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:

ABCDEFGH0 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 whenallthe 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

anylogical function:

Write the function's truth table;

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 trueon 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 expressionselectsthe one line from the truth table.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:

xyx XOR y0 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:

xyx XOR yconjunct0 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

anylogical function. This is a big deal, so we will repeat it:

We can express

any logical functionusing a DNF!There may be (and often is) a

betterway 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 usebrute forceand 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.

((NOT x) OR y)

(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:

We can build a computer using only AND, OR, and NOT gates!

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.

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

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

twokinds of gates. Can we do better? Can we build an entire computer out of justonekind 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 ifneither xnor yis true. It is the negation of the OR gate. So we have:

(x NOR y) == (NOT (x OR y))

With the following truth table:

xyx OR yx NOR y0 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:

xx OR xx NOR x0 0 1

1 1 0Be 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:

We can build a computer using only NOR gates!

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:

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

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

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

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

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

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.