[music] So, in lecture 2.3, we're going to continue our exploration of computational Boolean algebra and continue our study of the cofactors of, as, as important objects for manipulating interesting Boolean objects. In the last lecture we talked about the boolean difference, now we're going to put the cofactors together in another couple of interesting ways and build two new extraordinarily important operations, which are called quantification. They have interesting unusual names, existential quantification and universal quantification. So it sounds like philosophy but it's actually an interesting engineering it's an incredibly powerful and important way of taking complicated Boolean questions, removing the variables that I don't really care about, creating a smaller Boolean object, which we can then interrogate and ask the engineering question that we seek an answer to. So, let's start talking about the quantification operators. This is lecture 2.3. We are continuing our study of computation Boolean Algebra. Now we're going to combine the Shannon co-factors in yet more interesting ways to yield some things called quantification operators. So, you know that the Shannon expansion lets you take Boolean functions apart and put them together in interesting ways, using the Shannon cofactors. Combinations of cofactors do interesting things. We just introduced one. Right the Boolean difference which was based on the exclusive war of cofactors. Now we're going to look at other combinations of cofactors, we're going to look at the big ones are these things called the quantification operators. And once I've gotten the quantification operators to find for you, we're going to, we're going to apply them. We're going to actually be able to do something really impressive, that's the next lecture. So, what happens if I just take the 2 Shannon co-factors, the positive co-factor with respect to variable xi, the negative co-factor with respect to variable XI and I just add them together, and this little diagram over here shows exactly what we're doing. We're just, you know, the hardware sort of a diagram. We've got, we've got 0 going in over there. Right. So that's the negative co-factor. We've got one going in the bottom. That's the positive co-factor. All of the other inputs are, are shared and connected. We've got an AND gate. What do you get? You get something with a very strange name. Alright, so we get something called the universal quantification of F with respect to variable xi, and this thing over here, I'm going to write it over here, that's the name of this function. So, the upside down A, with an X, in this case, and F, and then we're going to put parentheses around it. And it's read, and it reads for all X F, for all X, F. So for all XF is a new function. And yeah, that for all sign is actual from logic, predicate calculus, if you've ever done that. And just like everything with co-factors, it doesn't have an XI in it. It's a very interesting new function. Sort of the same thing happens. What if I have function F and I or the co-factors together? Right, so positive co-factor and negative co-factor, right, I OR them together; I get a, a, an interesting new function with another strange name: Backwards E, there exists, x f. That is the name of this function. The backwards E is read, there exists x, f, right, so, the x existential quantification is what you get when you or these things together, and the backward e sign that there exist sign is also from logic. And like everything involving cofactors, both of these functions do not depend on the variables that we just got rid of. In this case the variable we quantify away. So for all x f and for there exist x f both omit that variable. So, these things look really strange, I've got to admit. Alright, so, let's go back to the hardware diagram, because I find that the hardware diagram almost always helps. So, let's look at the universal quantification. Alright, so that's this guy right here, okay I and together the negative and the positive cofactors and let's ask the question, what makes that thing a 1, because this thing is a function. It's a function of all the original variables except x, right? What has to be true if this thing is a 1? Alright, well, what has to be true, okay, is that these other inputs, make the original value of the function f equal one, for all values of x. That's why it's called for all x, F. If for all xF is a one, for those other variables in the function, then it must have been the case that when you put that pattern of inputs on the original function, the original function made a one for all values of x, in this case, for both values of x, right? Well, what about this one? Right, there, and you know, that there exists x F. What makes that guy a one? Well, it's, you know, sort of the same thing, right? It must be the case that there exists a value of x that makes the original function equal to one for this input pattern of the other variables. Right. So if you look at the, the, the and, you know, I mean obviously both of those things got to have a 1 going into them in order to make the and a 1. So it must be the case that, that F was 1 for all values of X. But for the or gate, you know, you only, you only need one of them to be a 1. Right? I mean if, if both of them are a 1 that's great, but, sorry, you only, you only need one of them to be a 1, so it must be the case that there exists a value of x that makes at least one of these blocks 1. Might make both of them 1, but it can't be, can't be the case that it makes neither of them a 1. That's why it's called there exists. And just like the other cofactor kinds of things you can do it with respect with more than one variable. So, if you quantify away two variables either universally or existentially right what that really means is that, you know, in this case let's say you quantify away the y and then you quantify away the x, all that happens is you AND together all the co-factors, and for the existential version, all that happens is you bore together all the co-factors. So, just like when we took the Shannon co-factor expansion and decomposed the function into pieces to build the function and we had four co-factors. Right again, we've got the four co-factors[UNKNOWN]. Add them altogether or you bore them altogether. And again, remember, can't keep emphasizing this enough, these are all functuions. They're not numbers, right? They're all functions but they don't have Xs in them, which is very strange. Because they've got X's written all over them, but there's no X's inside the function. The X's are removed because of the co-factor operation. We got rid of the X and we made three new functions. You can do interesting things with these things and I'm just going to show you one little example here and then a much longer example in the next lecture. Consider this circuit. So this is just a little adder circuit. It adds a number a0, a1, oh sorry, a1, a0 to a number b1 b0. And in this case it really adds a 1 bit number, okay? A 1 bit number x equals 0 or x equals 1 because we got the, the, high input for the b bit just pinned to a 0. So this takes a 2 bit number a1, a0 and it add a 1 bit number x. And there's also over here a carry-in, and a carry-out. Right. So the carry-in is called D; the carry-out is called C. This thing adds a 1-bit number x with possibly a carry-in. And so we ask a question, what if we quantify away the A operand? What if we universally quantify a way the a operands? Well then the a's are going to go away, and this is going to be a function that's only depending on the x number and the d carry in. What is this? It's a function of x and d. It makes a one for values of x and d that make the carry. C equals one for all values of the operand a one and a zero. Right? So, this universally quantified function makes a one, just if you can tell me when there's a carry by only telling me X and D. I don't need to know about A1 and A0. Right, if you tell me these particular values of X and D, I guarantee I'll make it carry out, independent, okay, right? The other way to write this is independent. My very bad handwriting. Independent of A1 and A0. What about the uni, sorry, the existential quantification? Well, same kind of idea. This is also a function of just x and d. It makes a 1 for values of x and d that make a carry out for some value of A1 and A0. And so what just this says is there exists a value of a one and a zero that will make the carry out one if you tell me this X and A, D. I don't know what it is and that's a little strange. Right, what this function says is if this existentially quantified function makes a one, alright? If this, this guy makes a one for this value in X and D, then it is true that you can find a value of A, A1 and A0, that will make it work, it will make, but I don't know what it is. And what's interesting is that we can just go do the math, and we can convince ourselves that this all works. So, here is the function for the carry out, all right, that's, that's this guy over here. All right? It just goes, I'm going to write it over there. There it is. Write A 1 A 0 plus A 1 and A 0 plus X and D. And remember that C with those subscripts just means I'm going to set, A one and a zero to one, one. Zero one, one zero, and zero, zero respectively. So if I set A1 and A0 to one, and then evaluate the Shannon co-factor, right? Well, I'm going to get an x, right? Because the A0 and the A1 go away, and then I'm going to get a d. Right, so, they want an A0 or one and I evaluate C that's what I get. For this one, and for this one, okay, what you can see is that if you make A1, a 0, the whole function just goes away. You can't do anything. And if you make A1 a 1 and A0 a 0 it turns out that again the first term goes away and the second term is reduced to x and d. And the thing to remember is that when you universally quantify it basically what you do is you AND everything together. So if you AND all of these things together well, hey, there's some zeros in there. You're going to get a zero, and that makes sense, right? So the universal quantification says, can you tell me when the carry is a one just by telling me X and D? Independent of telling me the values of the A operand and the answer is no, you can't tell me that, there is no way you can tell met that. I have to know the A values to tell me the carry. There is no way you can tell me the lower order bit X and the carry and tell me the high order carry up. It's impossible, or arithmetically it's impossible. Hey, the Boolean algebra tells me that. What about the existential quantification? Well, for that when you or them altogether and for those the 0's they don't really hurt, you're going to get X plus D plus 0 plus XD plus 0 and if you just do the Boolean Algebra on that you're going to get X plus D. Oh, that makes sense. Can you tell me that there is a way to make the carry-out a one if I tell you X and D? It doesn't need to be true for all values of the A operand, can you just tell me that there is a value of the A operand that will make this work? Yes, I can. What has to be true? Oh, at least one of the low order bid and the carry-in have gotta be a 1. If at least the low order bet and/or the carry-in is a one, then yeah, there's a way of making the A operand propagate that carry-out. Oh, look the arithmetic works, but I did it all entirely in the Boolean domain. That's what's very cool here [music].
