[SOUND] So here we are in lecture 2.2, Computational Boolean Algebra. What we did in the last lecture was we introduced the Shannon cofactors and the Shannon expansion theorem. We showed how you can take a complicated Boolean object apart into smaller simpler pieces and manipulate it. What we want to start talking about now is the fact that the co-factors are incredibly useful objects and even when we're not rebuilding the original Boolean equations, they take on an interesting life of their own. And in fact, important combinations of these co-factors have famous names and famous uses in the chip design business. And so we're going to start talking about the first one of these which is called the Boolean difference. >> So, here's our first question. What else can you do with cofactors? So for example, from a hardware sort of view, suppose I got two functions F and G, different functions of say variables x1 to xn. And I make a new function. For example, I invert function F and I call that H or I end the functions together or or them or something. And it's worth just reminding ourselves that this is kind of a hardware thing, right? So here's function F, and here's all the Xs going in. And here's function G, and it's the same set of Xs going in to those things. And here's F of X coming out, and here's G of X coming out. And what I really really said here is, I've got to put then into an AND gate. I'm going to make a new function H. Here's the new question I'd like to start talking about. Can I tell anything about H's cofactors if I know something about the cofactors of F and G? So, good question on the bottom is what is the positive x cofactor of h which is the positive cofactor of this new function F and G? What can we say about that? And the wonderful news is that pretty much the cofactors tell you everything you need to know and they also give you some wonderful practical tricks for calculating stuff. So for example suppose I take F and I compliment it and then I would like to do the positive co factor operation, what is that? And it turns out that the other thing I could do is could take X and I could cofactor it first and then I could invert it. Or depending on how you like to write this, I take F and I cofactor it first, and then I complement the whole thing, and in English, I'm writing it underneath. The cofactor of the complement is the complement of the cofactor right. So, it doesn't matter what order I do it in. I get to do it in whichever order makes the calculation easier. And, similarly, for basically all binary boolean operators, it works like that. The cofactor of the AND is the AND of the cofactors. The cofactor of the OR is the OR of the cofactors. The cofactor of the exclusive or, EXOR, right that's this gate remember, is the EXOR of the cofactors. This is really very useful because this can often help in getting cofactors of complex formulas. And in fact we're going to see that just later in this particular slide deck. So now let's consider some operations on the cofactors themselves. Suppose I have f of x and I told you about the Shannon cofactor which is one way of utilizing them. What if I just take the positive and negative cofactors and I just start putting them together in different ways. What happens if I exclusive or them? What happens if I and them? What happens if I or them? It turns out that all of those things are useful. In fact they're so useful they all actually have names. Each of the three things above has a famous name and it's a famous thing. So let's go look at them. And the first one is, we're going to go look at this one, we're going to go look at the exclusive or. And surprisingly enough, I'm going to take you back to calculus and derivatives. All right so, remember way back when, whenever you learned introductory calculus and basic derivatives, and we said, okay you have a function y is f(x) and we define the derivative as the slope of the curve. Right, it was this thing right here and the way we defined that was we said all right look we're going to take x and then we're going to change x just a little bit by Delta. And then we're going to look and see how much the value of the function changes between f of x and f of x plus delta. And then we're going to take the ratio of those two things and we're going to let Delta go to 0 and when we're done we're going to get this really interesting mathematical object called the derivative. So here's a maybe an unusual question for you. Do Boolean functions have derivatives? And amazingly enough, yes, and they're useful and they have a name. The trick is how do you define them? So the basic idea for real valued functions was that df/dx the derivative tells you how f changes when x changes and that's the thing to hang on to conceptually. How does the output change when the input changes? For a 0, 1 value Boolean function, we cannot change X by some small delta. The only thing you can do is you can change it by 0 to 1 or 1 to 0 but you can still ask how X changes. And it turns out there's actually a very nice definition for something like a Boolean derivative and it looks like this. We take the positive cofactor and we exclusive or it with the negative cofactor. And that's the definition of this interesting kind of a derivative. The way you can think about that is that it compares the value of f when x is zero against the value of x when it's 1. And this mathematical object is a 1 just if these two things are different. And the one thing that I'll remind you of again right, is that the exclusive or operation the thing we are drawing like that. If we say, a exclusive or b, right that is equal to a b bar plus a bar b and this thing is equal to 1 if and only if a is not equal to b. So this object down here is a 1 just if these two things are different. Now, we've seen those pieces before. The derivative is just the exclusive or of the Shannon cofactors, the positive and the negative cofactors, but I will note that it's not written df, dx. It's written del f, del x. That's just a historical thing. And it's got a slightly different name. Since it's not a derivative in the continuous valued sense, it's called the Boolean Difference. Just to be sort of clear about that.and the thing that's interesting is that it kind of behaves like calculus. So for example, You can do derivatives, differences with respect to more than one variable. You can do del f, del x, and then del y, and it doesn't matter if you do x first or y first. The order doesn't matter. That's just like calculus. And the derivative of the exor is the exor of the derivatives. That's interesting, that is kind of like addition right? In regular calculus so that's interesting and if the function f is actually a constant which means it's always one or always zero then its Boolean difference is zero all the time. And that's also like calculus which is kind of interesting and one of the reasons why people find this stuff interesting and why we use this notation. Now it'd be great if this stuff actually behaved like calculus but it doesn't. And so here's some scary stuff. If you take the derivatives of the and Of f and g or the OR of f and g, it doesn't work the same. You get these really very complicated, complicated, complicated boolean expressions. And the reason is that AND and OR despite the fact that we'd like to kind of write them like multiplication and write them like addition, they do not always behave like real numbers. And so ultimately it comes back and something different happens. Here's a little interesting example that I'm going to walk you through to try to give you some sense of what the boolean difference actually does. So let's just calculate the boolean difference delta f delta x for all four of these very trivial gates. And we're going to see an interesting pattern right? So here is a function which is just f is x bar and so remember that the Boolean difference here is f x exclusive odd fx bar all right? So what's f x here? Well, we take x and we make it a one and so we're going to get a zero and if we take f x bar right? We take a 1. We're going to get a 1, right? And so the derivative with respect to x is going to be 0 exclusive or 1, which is just 1. And it's not at all clear there's a pattern yet, but there is. We have to do a little more work. So here is f is xy. This is a simple and gate. All right f of x the positive cofactor is one and y so that's just y and f of x bar the negative cofactor we take x and we make it a zero and you just get a zero. All right so the derivative of the difference del f del x is y exclusive or zero and that's just y. And so let me ask you, a kind of a question there. Suppose that I do whatever it takes to make this Boolean derivative, this Boolean difference equal to a 1, right? So then what that would mean is that, I'd have to put a 1 on that input. Here's something interesting that happens. If you make this input a 1, any time you make a change on x, I guarantee you, it will make a change on the output. This is actually the pattern we're going to discover. If you make the Boolean difference a one, it guarantees for those values of the other inputs that if you wiggle x, x will change. So let's try that again and with an or gate, kind of convince ourselves that that's the pattern x + y. X plus y, f of x is going to be 1 plus y, which is going to be 1. F of x bar is zero plus y and so it's going to be y. And so the difference delta f, delta x is going to be 1 exclusive or y and if you do the boolean algebra on that one, you discover that that's just y bar. And I sort of said the same thing, what does it take to make this thing a one? What it takes to make this thing a one is that you make y a zero. All right, that's what it takes to make the Boolean derivative a one. So if you make this thing a zero, look, if you put a zero on the other or gate anytime you change x, I guarantee you, you will change f. That's cool. So evaluate the boolean difference, figure out how to make it a 1. If you put that pattern of inputs on the gate when you change x, f will change. Right, what about an exclusive or? So this is x exclusive or y del f del, I'm sorry. F of x is equal to 1 exclusive of y so that's y bar, f of x bar is equal to 0 exclusive of y so that's y del f, del x is equal to y exclusive or y bar. Do the boolean algebra and you'll discover that it's a 1. That makes sense. What does it take to make that boolean derivative a 1? And the answer is everything makes it a 1. You can't not make it a 1, and so that means it does not matter what value you put on Y. If you put a wiggle on X, if you change X the output will always always always change. And now if we go back to the inverter we can see the pattern. X will always change the output no matter what you do. X will always change the output. That's why the boolean difference evaluates to a 1. And for all of these others, the meaning is that when del f del x is 1 then F changes if X changes. And that's a wonderful thing because with just some math, we were able to do some sensitivity studies on an interesting piece of logic. So we can sort of expand that to a much bigger thing. Here's a big blob of logic, all right. And I'm trying to ask the question when does an input change on X turn into an input, turn into an output change? And the answer is that what I should go do is I should go evaluate del F, del X and I should figure out what values of these variables here make it a one. And if I can put those values of the variables on all of those other inputs, if I can make del F/del X, which recall, is a function of everything up at the top but not X. If I can make this function a 1, okay, then I guarantee that if I put that pattern on the input, right, the output will change. That's a very useful thing. Here's just another little kind of an example. So here's a 1-bit adder, a very simple little object. It's got a sum and it's got a carry. Basically right now, we're going to look at just the carry out. So the carry out is A B the two bits being added plus A plus B C in, so a simple equation. What's the boolean difference of the carry out with respect to the carry in? Or kind of in English, when does a change in the carry in make a change in the carry out? Okay, well, we can go do the math. The notation's a little weird. Carry out sub, carry in is what you get when you take the carry in and make it a one. So if you look at the equation, I get ab+(a+b). Okay and that's just a+b. And then I do carry out, sub carry in bar. And that's what happens when I make the carry in a zero. And obviously I'm just going to get ab, because the second term is just going to drop out. Okay, and if I want to do the carry out with respect to the carry in. They'll carry in. I'm going to get a plus b exclusive or ab. So that's a plus b bar, ab plus a plus b ab bar the Boolean algebra is a little tedious, I'll just kind of like to do it. Turn out you get a exclusive or b, which makes total sense, right? What does it takes to make the Boolean difference of the carry out with respect to carry on 1? A has to be different than B right? If A is not equal to B right then if you change the carry in you will change the carry out. That makes sense because you know if A is equal to B and they're both 0, I don't care what you do with the carry in. You are not going to make a carry out. You just can't do it. And you know if a and b are both one, they make a carry out all by itself and again I don't care what you do with the carry in doesn't matter. But if a and b are not the same, then I guarantee you a change in the carry in will change the carry out. So arithmetically this all makes sense but the thing that's really nice and very elegant about this is that I can do all of this entirely in the Boolean domain. So a couple quick things to remember about the Boolean difference. It's not like the physical interpretation of calculus derivative. There is no slope in the current stuff but it explains how an input change can cause an output change for Boolean function. The Boolean difference del f del x is a Boolean function but it does not depend on x. That's a big one and if I don't tell you that five more times you'll forget it. because you know in calculus land when you differentiate between something with respect to x, the x did not always go away. But in boolean land, it does. Look, it can't have an x in it, it's made out of cofactors and cofactors don't have x's in them. They got replaced by constants. And this is really surprisingly useful. We're going to see this in a bunch of later places. [NOISE]
