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.
