0:00

[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].