“Nand2Tetris Unit 1 Boolean Logic”版本间的差异

2016年2月22日 (一) 08:50的版本

Boolean Logic

So today we're starting our journey of actually building a computer. You've probably all heard that computers internally only have 0s and 1s. And the reason that they only have 0s and 1s is because that's what they can get away with. It's simplest to have only two possible values that you need to maintain. And that's going to be enough as we will see today. We're starting with actual, the completely theoretical logical kind of analysis of how to deal with 0s and 1s. And later in this later in unit three we'll actually talk about how these abstract 0 and 1 signals directly are implemented as chips inside a computer. So let's talk about the abstract 0 and 1. On and off, true or false, not, no and yes, 0 and 1. In general, we can use all these names to refer to each one of two different physical values. That are maintained somewhere in the system. We will use 0 and 1 for the rest of this the rest of this unit, but that's completely general. So what can we do with kind with, if we only have 0s and 1s? Well, we can do some kind of basic operations on them. For example, the AND operation takes two 0 1 signals, and returns 1 only if both of them were 1. So if you have 0 and 1, the result is 0, but if you have 1 and 1, the result is 1. We can actually see all of the different possibilities for combining two values of 0s and 1s into the result, which is the end of them, in a little table that is called the Truth Table. Because it actually gives all the different possibilities of the inputs, of x and of y, and for each one of these possibilities, it lists what is the output, what is x and y. So AND is a one of the possible operations. Here's another very popular one, OR. It returns 1 if any one of the two inputs is true. Is one. Or even if both of them are one. The only time to return to 0 is if both x and y are 0. And here's a third interesting operation. This one is a unary operation. It only takes a single input. Bit as input, x, and returns the opposite of it. So returns for, if the input is 0 the output is 1. If the input is 1 the output is 0. So these are possible, very simple operations and Boolean numbers. Sort of like addition and multiplication, and maybe other kind of operations, or operations on integers or on real numbers. These are operations on Boolean numbers. Once we have operations, we can start combining them, just like we combine arithmetic operations in arithmetic formulas. So for example, let us try to evaluate what would be the expression of NOT 0 OR 1 AND 1? Notice that we have parenthesis to gi, to give us the priority here. So the way we value it is very simple. We know how to evaluate 1 AND 1, which is 1. So the whole thing simplifies to NOT 0 AND 1 OR 1. We know how to evaluate 0 OR 1. That's going to be 1 because it's an OR operation so that's equal to NOT 1. And now we know how to evaluate NOT 1, that's simply 0. All very simple and we can do that. Now once we know how to evaluate a Boolean expression over values, over 0, 1 values, then we can actually get general expressions, general functions that takes indeterminates, XYZ as inputs, and for each value of XYZ, produce an output. So for example, I can define a function, a function of three inputs, XY and Z. That basically turns x AND y OR NOT x AND z and look in the parenthesis to see the priority that I was thinking about. Of course I could use, I could define any other function by any other Boolean formula and that would give me a function. If we want to know what kind of function is that, well we can actually list all the possible values of x, y and z. And for each one of them, try to write down what is the value of the function? The really nice thing about Boolean values is the fact there are only a finite number of possible inputs and we can actually list each one of them. This is completely different from functions that you've learned in third grade. Where you have function from integer through integer, then there are infinitely many integers. So you can never write down the function in a complete specification of all the possible values. But here, we can actually write down all the possible values that x, that the triplet x,y,z can have. We can have x 0, y 0 and z 0 that corresponds to the first row in the table and so on. Until the last row of the table that corresponds to all three of them being 1. Now for each one of these rows, we can just evaluate the function. What is the function f of x, y, z defined by the previous formula for these values? For example let's look at the second row. In the second row we have x equals 0, y equals 0, z equals 1 and we can just plug in the numbers 0, 0 1 into the formula. Every time we have an x we put a 0 there. Every time we have a y we put a 0 there. Every time we have a z we put a 1 there. And now we just get formula with constants in it and we can evaluate it just like we did in the previous slide. And we can figure out that is 1, that the second row should get a value of 1. We can do this similarly for each one of the possible rows and we get a, we can completely fill the table. And now notice that this table of values completely gives you the same information as the previous expression did. It completely specifies the functions, the Boolean function that we just had. The first day, the first way we described the function was as a formula. The second way we describe the function was as a Truth Table. These are two completely identical, def, def, eh, definitions. Ways to describe the same Boolean function. So now, eh, once we know we can describe Boolean functions using formulas and we are thinking we have general Boolean expressions, we can actually try to find what are a bunch of Boolean identities that always give us equality. For example, we can always see that x AND y, whatever the values of x and y is, is exactly equal to y AND x. This is called the Commutative Law. We have the same similar phenomena for x OR y equals y OR x. So these are like commutative laws that hold for this Boolean algebra, in this, in this Boolean algebra. There are a bunch of other kind of identities. For example, the use, the use, the well-known Associative Law. If you have x AND y AND z, it's the same thing if you first do x AND y, or whether you first do y AND z. Similar thing happens for all. Another well-known law, well-known law is the Distributive Law. If you have x AND y OR z, that turns out to be exactly equal, equal to x AND y, all that, OR x and z. Now as opposed to the usual arithmetic, where we only have the Distributive Law of multiplication over addition, here we have both of the Distributive Law of multi, AND over OR and the dual law of Distributive Law of OR over AND. The same trick works if you want to do x OR y AND z. That x OR y AND x OR z. [COUGH] Now there are also laws called De Morgan laws, that govern how NOTs work. How they interrelate with AND and OR. These are called loo, laws are called De Morgan laws, and they say the following into, interesting thing. If you take x AND y and do a NOT on all of that, that's equivalent to first doing NOT of x and ORing that to NOT of y. And we have the dual one that if you have NOT of x OR y, that's exactly equal to NOT of x AND NOT of y. Now all these laws can be easily proved, if you wish. Not if you wish. Really proved by simply listing all the possibilities in a Truth Table. And verifying that they get the same Truth Table for the left-hand side and the right-hand side. Now there are a bunch of other laws and we can use them to actually do manipulations and Boolean algebra. So for example, once we have a formula. For example the formula that you see here. NOT of, NOT x, AND NOT x OR y. For example, it could be any other formula. We can now start applying some of these identities to change its form to simplify it or to just bring it into a different format. So for example the first thing we can do here is look at the second part of last sub expression, the NOT x OR y. We can use De Morgan Law here and basically convert it to NOT x AND NOT y. Now if you look what we have here, we can use Associative Law. Because we have NOT x AND NOT x AND NOT y we can change the order of doing the AND. And we get another expression which is identical using the Associative Law. At this point we have something really interesting at the beginning. We have NOT x AN NOT x. That can be just simplified to NOT x. Why is that? Because we can know, we can actually see, also that's another identity that we didn't explicitly list. But it's easy to verify in the same way that, if you take any value, w. In our case, w is NOT x. And do w AND w, that's completely equivalent to w. Now this is called the Idempotence Law and we can thus simplify the previous expression by simply removing one of these w's, one of these NOT x's. Now we are ready to use De Morgan Law again, and now we got into NOT NOT x OR NOT NOT y. Now again, here's another law that we didn't list explicitly, but you obviously all know, that NOT NOT x is always equal to x. So using Double Negation Law, we can simplify that to x OR y. So that just gives you some kind of a demonstration that you can basically, just manipulate Boolean expressions, sort of like you manipulate arithmetic expressions in elementary school. There's another way to get the same conclusion, the same equivalence, without actually going through these algebraic manipulations, simply by actually looking at the Truth Table. We take the expression, we build the Truth Table for it. And we've already seen how to take an expression and find its Truth Table. And then we get the Truth Table that you see on the board. Now, once you have this Truth Table, you can say I know this Truth Table. This is exactly the Truth Table of the OR function. And then that immediately proves that the expression on the top is completely equivalent to x OR y as we've derived using an algebraic methods previously. Now of course it's not completely eh, you won't always be so lucky to do some kind of big Truth Table and recognize what it is and immediately see a better and nicer and simpler expression give, that gives you the same table. Eh, sometimes you will have to algebraic manipulations, but on the other hand it's not always true that algebraic manipulations are easy to do in the sense of finding a very simple expression. So, but in general, in principle, you can use both of these methods to actually simplify Boolean expressions or find alternative forms that give you the same Boolean expressions. So we've just finished our first unit describing how to man, how to eh, manipulate logical values. Notice that we are still keeping our abstract point of view of just logical values and not thinking about any physical realization that we will have inside our computer. In the third unit, we'll actually switch our point of view and start talking about the same kind of phenomena but from the point of view of real chips and real gates that we have inside a computer. But before we get to that, in the next unit, we'll keep maintaining [COUGH] our theoretical point of view and start talking about the following problem. How can we construct a function from basic operations? How does that, this is exactly the kind of thing we will need to do when constructing hardware. We know what it wants to do, but we'll have to actually construct it from Boolean operations. And we'll try to see how that is done, first from a theoretical point of view, in the next unit.

Boolean Functions

So, in the last unit we talked about what are Boolean functions, Boolean values, Boolean algebra, Boolean formulas. What we want to do now is actually talk about how we can construct Boolean functions from more primitive operations. So, we already saw two ways to represent the Boolean function, a Boolean expression, and a truth table. We also know how, already know how to go from the expression to the truth table. You take the expression, evaluate it for each possible, possible value of the input bits, and then you get the, and then you can fill the truth table. What we want to do now is exactly the opposite. You start with a description of a function, let's say given as a truth table, and our challenge is to come up with a formula that computes the same boolean function. Why do we need to do that? Well, that's exactly what we have to do when we come to design a computer. We know what we want to do, we know what we want a certain unit to do, but then we actually have to actually compose it from primitive gates, from primitive operations. So let's see how we can do it. So again, we continue with our abstract treatment. We're trying to see what is a basic logical way we can actually construct such a Boolean function from primitive operations. Later, once we actually talk about practically constructing them, we will be more practical oriented. We'll go step-by-step and so on. At this point, we just want to make sure, what are the principles? So let us start with a specification of a Boolean function given as a truth table. How can we construct it? Well, here's what I'm going to describe to you as a standard way of what's called constructing a disjunctive normal form formula for it, and it goes like this. We actually go row by row in the truth table. We focus only on the rows that have a value of 1. For example, the first row here has a value of 1. Now, what we can do is, we write an expression that basically gets a value of 1 only at this row. For example, so, in particular, since here in this row, the values of x, y, and z are 0, 0, and 0, if we look at the expression not x and not y and not z, that is going to be a Boolean function, the green Boolean function, that only gets a value 1 on this row. So now we have one Boolean function. We do the same thing, we construct another Boolean function, another clause for each row that has the value of 1. So for example, there's another second row with a value of 1. This time, in here, this row, y equals to 1 while x and z equal to 0. So the clause we write here is not x and y and not z. Again, this is something that completely gets a value of 1 only on this row and gets a value of 0 everywhere else. We do that for every possible row that has a value of 1, Now the purple row. Now we have a bunch of different functions that each one of them gets a value of 1 only in its row and gets a value of 0 in all other rows. But we desire a single function, a single expression, that gets exactly the value 1 exactly on all of these rows and 0 on the other rows. How do we do that? Well, that's very simple. We just or them together. And now we get a single expression, a single Boolean function that gets value 1 exactly on the rows for which we built clauses for, and gets 0 everywhere else. And now we've basically constructed our function as a Boolean expression only using ands, nots, and ors. Now, of course, once we have this expression, we can start manipulating it in varied ways. This is one way to write the function as an expression, but if you actually look at it, you can see that we can start changing, start changing its format. For example, if you look at the first two clauses, you can see that one of them is not x and not y and not z, while the other is not x and y and not z. Notice that the, what we have both possibilities for y and exactly the same fixed value for x. So instead of these two, two clauses, we can combine them into one clause which does not ask about y, and only asks about not x and not z. So we get an equivalent expression that's slightly shorter. There are more manipulations that we can do. Let's not go into them, but we can actually write the same expression in many different ways. Some of them will be shorter than others, some, some of them might be, might be more efficient in terms of when we actually go implement them in a computer. But the point is, logically, they're all completely equivalent. Now, you might wonder, how do you actually find the shortest or most efficient formula that's equivalent to the one we've just derived? Well, that's not an easy problem in general. It's not easy for humans, nor is there any algorithm that can do that efficiently. In fact, this is an NP-hard problem to actually find the shortest expression that's equivalent to a given one, or even to verify if the expression that you're given is just a constant 0 or 1. What's more interesting, what I really want to focus at this point, is that we've really prove the really remarkable mathematical theorem that any Boolean function, it doesn't really matter on how many variables and what the boolean function is, can be represented in an expression using only the operations AND, OR, and NOT. Now, to notice how remarkable that is, just think about, just think about functions on integers. Integer functions that you've learned in elementary school. Not every element, not every function and integer numbers can be represented using let's say, addition or multiplication. In fact, most functions cannot be represented just by arithmetic operations. Yet, because of the finite world that we're living in, the Boolean algebra, ever Boolean function can just be represented with ANDs, ORs, and NOTs. And that is what exactly gives us the basic power to actually construct computers only with these possible gates, only with these possible operations, AND, OR, NOT. But do we really need all of them? Well, here's a better theorem, if you wish. We don't really need OR gates. Just with ANDs and NOTs, we can construct any Boolean function. How can we prove that? Well, we already know that if we have ORs, we can do everything. We've just seen that. And now the only thing that we need to show is that we can actually compute an OR with AND and NOT gates. But we know how to do that already, we remember, we recall De Morgan formula that exactly give us a formula for OR that only uses NOT and AND gates. So now we have a really more remarkable theorem, that we only need these two basic operations to actually compute every, every Boolean function. Can we go even less? Can we give up, let's say, the AND gate? Well, that doesn't make sense, because not only it takes one value to one value, it doesn't even allow us to combine anything. Can we give up the NOT gate? Well, not really, because ANDs has this property that if you only feed it zeroes it will always have zero as output. And there are Boolean functions that when you feed 0 give you 1 as output, so AND by itself wouldn't suffice. But it turns out that there is yet another operation that by itself does suffice to actually compute everything, so let me introduce the NAND function. So the NAND function, here is a truth table. It gives 0 only if both of its inputs are 1. And every other possibility it gives 1. Logically, x NAND y is defined to be the negation of x and y. So what's so remarkable about this Boolean function? Well, the nice thing is that we can prove the following theorem, that if you only have NAND gates, you can already compute every Boolean function, you can already represent every Boolean function as an expression using just these NAND gates. How do we prove that? Well, we know that if you can do NOT and if you can do AND, you can do everything. So we just have to show how to do NOT with NAND gates and how to do AND with NAND gates. So here's how you do NOT. If you just look what happened when you feed x to both inputs of the NAND gate, you plug it into the truth table in the previous slide and you can see that NOT x is really represented by x NAND x. That's part one. The second part we need to show, how do we do AND. Well, x AND y turns out to be NOT of x NAND y. But how do we have NOT, well, we've just seen that you can do NOT with NAND itself. So now we've basically reduced the fact instead of using NOTs and ANDs, we're just using NAND gates. And we got an amazing theorem that just if you have a NAND gate, you can compute every, everything. And this is exactly what is going to be our approach when we actually go to build a computer. We will give you a basic, a primitive NAND gate operation, and you will basically build the whole computer, all the complicated logic that we'll actually ask you to build, using just from these basic NAND operations. So at this point, we've just finished our abstract point of view about Boolean logic. And now we're doing a really interesting shift of perspective from the abstract logical operations to the actual gates and, the actual gates from which we build computers. This switch really has no, there's no actual difference between the two, two different things in terms of the kind of thing that we do. But it's just in the way that we're thinking about them. Until now, we ask you to think about everything as abstract Boolean logic. From now, we're going to start asking you to think about everything as actual little pieces in a computer that compute the functionality that we want.

Logic Gates

In the previous two units in this week, we talked about Boolean functions, and most of this discussion has been theoretical. Starting with this unit we are going to talk about how we actually implement these Boolean functions using hardware. In particular, we're going to talk about a general technique called Gate Logic, which, you know, loosely speaking, it's a technique for implementing Boolean functions using logic gates. Now, what is a logic gate? Well, a logic gate is a stand alone chip or a, you know a very simple chip or an elementary chip which is designed to deliver a well-defined functionality. You know, something like NaN functionality, and functionality or, and so on. What is a composite logic gate? A composite logic gate is one which is made up from elementary logic gate and other composite logic gates. Or simply, it's, it's a more complex gate than the elementary ones. And in this course, we'll develop things like multiplexes and adders. And, obviously, most of you don't what the, what these terms mean. Don't worry about it. You will get acquainted with them and actually build them in the next few weeks of the course. All right, so let us begin with the most fundamental logic gate that we use in the course called, Nand. Here is the definition of a Nand. You know, this is actually the standard diagram that we use to describe a Nand gate. It has two inputs and a single output. Everything here is binary so a, b and out are either 0 and or 1. Here is the functional description of this of this gate. If both inputs are 1, we output 0. Under any other circumstance we output 1. And here is also a truth table description of the same functional specification. Any one of these descriptions is fine. Taken together, what we have here is an obstruction of the Nand gate. We didn't say a word about how this thing is actually working. We just describe what kind of functionality we can expect it to deliver. Okay, moving forward, here are, three classical gates that, pop up in every, digital design, project. We have an And gate which outputs 1, when both its inputs are 1 and 0 elsewhere. We, we have an Or gate which outputs 1 when either one of its inputs are 1 and 0 elsewhere. And we have a, a Not gate that operates as a converter. And we can put these gates together to create more complex functionality as we'll illustrate later on. In particular, we can use these gates to composite composite ones. So for example, here's a three-way And, which is an extension, if you will, of the of the simple two-way And. And one way to build it is to use this trick here. We can take the output of one And and feed it into one of the inputs of another And gate. And if we wire everything correctly this gate is supposed to deliver the required functionality. What we see in the dashed line rectangle around the implementation is a documentation of the interface of this chip. So the user lives outside the dashed rectangle. So, and, and so the user sees only the three inputs and the output, as you see in the left-hand side of of the gate description. If you want to go in, or to sort of open up the black box you have to see what is documented and done inside the dashed rectangle. So with that, I would like to say a few words about the notion of interface and implementation. The gate interface is the gate obstruction. You know, this is how the user thinks about what the gate is supposed to do. Interface answers the question, what. At the same time, if you want to understand how the chip is doing, what it's doing, you have to, go deeper and go int, well I'm not sure that deeper is the right word. But you have to go to another level of detail in which you actually, the black box opens up and you see how the chip is actually constructed. Or you do it yourself, you know, if, if your job is to be the person who, who is actually realizing this, obstruction. Now, the interface of the gate is unique. There's only one way to describe the gate's, functionality. Otherwise, you know, if there's more than one way, either you're not describing it well or you're confusing the user because, you know, there should be only one unique way to describe what the gate is supposed to do. At the same time, there may be several different implementations that realize the same obstruction. And some implementations may be, you know, more elegant, they may use less energy, they maybe less or more expensive, and so on. So one obstruction, many different implementations. This is very typical in in computer science, whenever you build a large system, you have this this duality. All right. Now moving along, so we talked about the gate interface and the gate implementation. Let's talk about something known as circuit implementations. If I want, I can realize these gates using hardwired circuits like, like this one. And there's a certain sort of graphical language here that describes what's going on. When we want to represent the fact that the gate outputs 1, we assume that a light bulb will be turned on. And when the gate delivers output 0, the light bulb will be off. So if we look at this implementation of an And circuit, we see that because of the architecture of this circuit the light bulb will will be on only if the two relays, both relays are latched. Under any other circumstance the light bulb will go off. And, that's, that's exactly what I want to do when I represent the And logic. What about Or logic? Well, once again, if I'm, if I have to build circuit, circuit implementation of Or, I can realize it using this particular architecture. In here it takes only one latch to close the circuit and turn on the light bulb. And once again, this is consistent with the desired obstruction of an Or circuit. Moving along, here is a circuit implement, implementation of a three-way And. And you can easily, I think, convince yourself that it will deliver the the required functionality. And yet I want to remind you that earlier in this unit we also presented this implementation of, of an And gate if you recall. So I'd like to say a few words about these two, different, approaches to, designing hardware. And, I want to start by saying that, in this particular course, we don't deal with physical implementations. And therefore, this whole discussion of circuits, transistors, relays, and so on, you know, all this stuff, and what you see in the top left corner of the screen here, this is electrical engineering. It's not computer science. And the people who build these gates using circuits and, and similar technologies, some of them are far more advanced and sophisticated. Well, these people are called electrical engineers, God bless their souls. You know, we have problems in computer science to worry about. So we are not going to worry at all about physical implementations, and all the designs that we are going to use in our course are going to be similar to what we did here at the bottom right of the screen. We are going to take existing logic gates beginning with Nand, and, and beginning with Nand only, and we're going to piece them together in some clever ways in order to generate and, and produce the required functionality. So this has been a unit in which we we gave you a first brief introduction of logic gates. And in the next unit we are going to introduce to you a language some sort of a programming language called HDL or Hardware Description Language, with which you can actually build logic gates like the ones you saw in this unit, and the far more complex logic gates and chips down the road.

Hardware Description Language

Hardware Simulation

Multi-Bit Buses

Project 1 Overview

Perspectives