[music] So here, in Lecture 2.4, we're going to continue working on Computational Boolean Algebra. And now that we've done some interesting things with cofactors, and we've put them together in some interesting ways, let's, let's do an interesting application. Let's actually do a realistic application. This is a network repair application. So, suppose I, I, I gave you a specification for a Boolean function, let's say something complicated with a lot of logic gates in it and suppose you got, you got that wrong and, and suppose you're pretty sure that one of those gates in your thousand or 5,000 or 10,000 gates is incorrect and you'd like to figure out how to change it that seems to be an incredibly complicated kind of a problem. It turns out that by using some clever cofactor-based computational techniques, we can pose the problem, we can write an equation like Physics, that expresses the problem when we can solve the equation like Physics. And the solution of the problem will not only tell us that the gate is wrong, the solution to the problem will actually tell us what gate we should use to repair it. That's a pretty amazing amount of stuff that you can do just by manipulating Boolean Algebra with a computational kind of a mindset. So, let's go see how that works. This is Lecture 2.4, . We're continuing our development of Computational Boolean Algebra. We've just done a lot of interesting things with cofactors. Let's actually do a, a realistic sort of application, something called logic network repair. So, suppose that I gave you a logic block to implement, and let's say, I specified it as Boolean Algebra and this is how I specified it. Now, I will admit right away that this is very silly because if you just do a little Boolean Algebra on this what you will discover is that this is a plus B bar. So, I'm just going to say, please ignore this. I need this to be simple so that the example works out in a nice way. So, I give you the specification, right, and then I ask you to implement it. And you know, maybe you're having a bad day and it's, you know, just kind of not working. And, you know, some of this stuff you got right so there's an inversion, right, you got the inverter right and that's an and gate and you got the and gate right and that is an or gate and, oh, gosh, I have no idea what you did, you don't know what you did but you didn't do the right thing and this function g, wow, it's just not doing the right thing. It's, it's not implementing f. Here's what I'd like to ask as an Engineering problem. Can I deduce precisely how to change this gate to restore the correct function? And the answer is yes. And what's amazing is that I'm going treat this like a Physics problem. And in a Physics problem, you know, you get some physics. You have a cannon, you know, you shoot a cannonball up in the air, you ask how high it goes, and at what time it gets there and you write an equation and you solve it. But, in order to do this network repair, I'm going to do exactly the same thing. I'm going to write an equation in the Boolean domain, I'm going to solve it, and the solution is going to tell me if this gate can be repaired and if so, what gate to replace it with to repair it, which is pretty amazing. So, we are going to use this trivial test case so that you can see how the mechanics all work, right? So, the first thing is that there is a trick and the trick is that we're going to replace our suspect gate with a 4 to 1 multiplexer. And remember that a 4 to 1 multiplexer has two select lines and it selects from one of four values, in this case, d0 through d3 shown down here. And by putting some constant values on the d's, we can pretend to be, or fake any gate, right? So those two inputs right to the gates, are now the select lines. By putting constant values on the d's, we can make the gate anything we want. So, the big question we are trying to figure out is what are the right values of the d so g is repaired, so that g is actually the same thing? Now, it's just a, a little reminder, you can do any function of two variables with one four input multiplexer, right? So, in this particular example, I have zeros in all, on all of the inputs, except when both s1 and s0 are one. And so this thing is actually pretending to be an and gate. And similarly, over here the only times I have ones are when the s1 and s0 are different. And so, this guy here is pretending to be an exclusive or gate, that's great. What we know is that, if I can solve for the constants that go into the multiplexers and make that, the logic networks correct, right, if I can make the network with the multiplexer do the same thing as the specification network, then I can repair things. So, here's the next interesting trick. I'm going to make this new function Z, and Z is a function of the original variables, alright, so there's the original variables. Z has got them, but the Z is also a function of all of these multiplexeor inputs. And note what I'm doing here, this is required, this is a known good version of the logic, or at least just some Boolean equation that does the right thing, even if I don't have it implemented in engineering practical gates. I just gotta have it written down somewhere. And I'm comparing the, the function up here, okay, the G function with the funny multiplexer with the known good version, and I'm doing over here an exclusive nor gate. And just a little, a little reminder, okay, alright? An exclusive nor gate looks, looks like, looks like that. People I like to write this as an exclusive or sign with a bar over it, x exclusive nor y. And this is xy plus x bar y bar, and this thing is equal to 1 if and only if x is the same thing as y, alright? This is an equality gate. So, we're going to take this equality gate, and we're going to compare G and we're going to compare f, right? And we're going to call this whole thing Z, and Z is the thing that we're going to try to figure out. So, what do I want? You just think real hard about, about what I want. This is what I want from an engineering point of view. I want the values of these constants, d0, d1, d2, d3, that make this interesting new function, that make this thing Z exactly equal to 1. And look what I'm writing. I'm being very careful. For all possible values of the original inputs a and b I know how to do that. If you give me the Z function, what I will do is I will universally quantify away a and b out of the Z function, that's a new function. And that functions depends only on d0, d1, d2 and d3, it doesn't have any a's and b's in it. And then I will ask the question, can I make this thing a 1, can I find some values of the d's that make it a 1? And so, just like the bullet says, hey, this is something I know how to do. Universal quantification of Z with respect to the variables a and b will do the trick. Any pattern of the d's that makes this new universally quantified function of one solves my problem. That's petty amazing. And aside, you know where the a and b went? They went away because they got consumed in the co-factors when we set a and b to all four possible values of the a and b, 00 01 10 11. Let's go do it, okay? Let's convince ourselves we can do it. So, the first thing I'm doing on the top is I'm just writing the equation for the multiplexer, alright? So, for example, you know, when s1 is a 0 and s0 is a 0, d0 is the value you, you send on out, right? So, that's just the mux. Alright. So, what's the, what's the G function, right? The G function is if we just take the, the function shown on the top and replace it with basically this logic, alright, what I get is I get d0 ab bar, b bar, bar, two bars, plus d1 ab bar, b with a bar, plus d2 ab, b with two bars, plus d3 ab b bar. Well, okay, that one just goes right away. And then if I simplify this a little bit I will get d0 a bar b plus d1 b bar plus d2 ab. So, that's the G function. That's the thing with the multiplexer pretending to be a gate, whose function is determined by the d's. I'm going to put that into an exclusive nor inequality gate, okay? I'm also going to put that in, that's the, that's the f function, and the result of that is going to be my Z. So, Z is G exclusive nor f which is Gf plus G bar f bar and what I want is to go calculate this thing with the star, for all abZ, right, which is going to be the ab cofactor ended with the a bar b cofactor ended with the a, b bar cofactor ended with the a bar b bar cofactor. Now one could take a frontal assault on this and just go pound out all of these all of these exclusive nors and one would be badly advised if one did that. That would, golly that would hurt. I really don't advise you to do that. I advise you to be smart and use some of the tricks that we just showed you a couple of lectures ago, alright? So, here it is again, all written out nice. Z is equal to the G exclusive nored with the f. And I've just got a little reminder over here, if you don't play with exclusive nors too often. If you exclusive nor something with a zero, you complement it. And if you exclusive nor something with a 1, you return it unchanged. Let's use the nice property that we showed a couple of lectures ago. The cofactor of an exnor is the exnor of the cofactors. So, in other words, I don't have to do this terrible exnor and make this, this terrible big expression and then go cofactor it. I can go cofactor it first. If I cofactor it first, life is ever so much easier. Then, all I have to do is in the, the G function, and in the f function, I have to set the a's and the b's to all four possible constant values. So, if I set the a to 0, and the b to 0, right okay it turns out that what I will get is just d1, right? The first term goes away because b is a 0 and the third term goes away because b is a 0, right, but the second term stays because b is a 0, alright? And then that's going to be exclusive nored with a 1, and that's going to give me d1, right? And if I take a as a 0 and b as a 1, it turns out I get a d0, and it turns out I am exclusive noring it with a 0, so that turns out to be d0 bar. If I take a as a 1, and b as a 0, it turns out I get d1 exclusive nored with a 1. I get d1 back again and in this last one, I get d2 exclusive nored with a 1, a 1, I get d2. And the thing to remember is that the thing I'm trying to calculate, the universal quantification of Z, right, which is a function of d0, d1, d2, d3, right? It's just the end of all of these cofactors and so that's just d0 bar, d1, d2. And that's not so horrible, alright? Trust me. If you had exclusive nored those things out and made this really horrible big Boolean expression, and then cofactored it, and then tried to and them all together, it would be very painful. This is a much smarter way of doing it. Sorry, draw it in the right place there. So what did we get? What we got was that the, the quantification that got rid of the a's and the b's in the matter that we needed is just d0 bar, d1, d2. And we know that our goal is to solve this, aright and make it a 1. So you know, what do you have to do to make this thing a 1? And the answer is you have to make d0 a 0, you have to make d1 a 1, you have to make d2 a 1 and d3 is I don't really care, don't care. Anything you want, it doesn't matter, which is interesting. And it's going to be surprising, it's going to be actually of relevance. Those values will repair this network, alright? So remember what I said. If you take d0 is a 0, d1 is a 1, d2 is a 1, and d3 is a don't care, it repairs this network, alright? Well, look, one of these values makes eminently good sense, right? If you do this as 0110, that's an or gate, right? That makes a 1, I'm sorry 0111, okay? That is an or gate, right? And look, that's what we expected, alright? We expected that if this Boolean thing worked, it would produce an or gate, because we knew that produced the right answer. But what's interesting is that if you take the other value, 0110, it specifies an exclusive or gate, and that will also repair it. That's very cool, alright? Because in the real world, you don't have a tiny example like this one is, you have a big network. It has a hundred inputs, it has 50,000 gates. It's big and complicated, and you can localize the problem to some blob of gates, right? And you can point at the gate and say, gosh, I wonder what that gate is supposed to be? And perhaps you have a specification that you can actually work with for what is, what the golden correct version of the logic is. But it alone is quite complicated. The fact that you can do this as a Boolean equation, that you can do this like physics, you can write an equation and solve the equation. And if you solve the equation, the Boolean expression equals 1, it repairs the network. That's a completely amazing kind of a result. That's why we're focusing on this Computational Boolean Algebra business. You've never really done Boolean Algebra like Physics, where you write equations and expect solutions. So, what have I just done? I've given you a mechanical procedure to answer, can I change one gate and repair it? Now, what you really haven't seen yet are a lot of computational strategies. In this particular case, what I needed was to find inputs, okay, that make this particular value of this function a one. That is the most famous computational problem in all of Boolean Algebra. That's called Boolean satisfiability. Give me a Boolean expression, tell me if there is a way to make it a 1, or tell me that there is no possible way to make it a 1. That's called the SAT problem. And the ability to do Boolean SAT efficiently is a big goal for this. We're going to, we're going to see how to do this in some, in some later lectures, but for now, what we're going to do next, is give you some more computational infrastructure for Boolean Algebra. [music]
