And by that I mean they're low pointers which point to their zero children, both

go to a y node and their high pointers. Which go, when the value is set to a 1,

both go to the z node. And they don't go to any old y, random y

node or z node, they both go to the same. X y node and this same z node.

The exact same nodes. And so what happens up here is that I

don't need both of them. I can get rid of one of them.

And so I can simply replace it with one, any one, It doesn't matter.

And I can keep the children. Right?

As I'm just drawing here, right. So there's an x node.

Its low child goes to y, and its high child goes to z, and then y and z are

unaffected, but there are two pointers that go into, in this case, go into the x

nodes. One of them goes into the left x node, and

one of them goes into the right x node. And what now happen is that you simply

redirect them both. To go into the x node.

So whatever was happening above the x node in this BDD, right?

And that traversed some edge with a variable decision to get to x.

Those pointers, they just point to the single copy of x.

And there's a little gray box over at the side here.

That just, just gives the recipe. You remove the redundant node, which in

this case is the extra x node. You redirect all the edges that went into

the redundant node into the one copy that you kept.

So in this case the edges into the right x node are not going into the left x node as

well. That is an example of merging isomorphic

nodes to reduce the complexity of the BDD. So let us apply Rule 2 to our example.

And if we stare at it for a little while, the big thing that we have to look for is,

what are some nodes that have the same variable label.

And identical children. So, you know, there's just no other node

then x1, so it can't be x1. And if we look at the x2's, they don't

have identical children. But if we stare at the x3's for a little

while. What we will discover is that those folks,

the right most x3's, those are all isomorphic.

They all have 0 as the low child, and 1 as the high child.

And so I only need one of them. I don't need all of them.

So I can redraw this BDD. It's got an x1.

Okay, at the top. And then it's got at the next rank, it's

got two x2 nodes, right? And the low child goes to the left x2

node. And the high child goes to the right x2

node. And then on the right side, there is a

single x3 child, right? And there is the high child of x2 and the

low child of x2 both go to that single x3 node.

I'm going to put little stars by them because those are new edges.

On the left hand side, the x2 node also goes, its low child goes to the x3 node.

And down at the bottom, I have a single 0 constant and a single 1 constant.

The x3 child on the left, both of its children low and high, go to the 0 node.

The x3 node on the right, the low child goes to the 0 node, but the high child

goes to the 1 node. And the x2 node on the left, write that,

high child goes to x3. I'm going to put a little star by that,

all right? So, those are all of the things that I

redid, right? As a consequence of killing two of the

three x3 nodes. And replacing them with a single x3 node.

And one of the things you can immediately see is there's less to this graph.

There's just less of it, it's a lot less complicated, that's a good thing.

You know simpler's gotta be better. But wait, there's more, there's another

rule that we can use to eliminate redundant, nodes.

And this is the rule called, eliminate redundant test, and this is another one of

the ones that feels kind of simple, when you look at it.

A test in this case means a variable node, right?

So this is If x equals 1 what do I do? If x equals 0 what do I do?

Redundant tests are the circumstance where a variable has both of its children going

to the same node. And that's just dumb, right?

I don't need, in the diagram above, I don't need to know what x is.

If x is 0, I go ask the y node what to do. If x is 1, I go ask the y node what to do.

That's not necessary. Right?

And so I can kill the x node. I can keep the y node.

Right? And again when I look at the, the in this

case, the edges that were going into the x node, however, many them there are.

I simply redirect them to go into the y node.

Instead, I bypass the x node. The x node goes away.

I do not care what value it takes. It does not affect the output of my

function and so I get rid of it. And so, again, there is a little gray box

at the upper right that gives you a little formula, says, remove the redundant node,

redirect all the edges into the redundant node which was x in this case, into the

child, y in this case, of the removed node.

So that's the, that's the recipe but it, it simplifies things.

So, if we go back to our evolving BDD and we apply rule three, what I have drawn on

the left was the same example. That I did by hand a couple of slides ago.

X1 is the top rank node it has low children and high child x2 respectively.

Right? The next rank are two x3's, right?

The x2 on the left has a low child that goes to x3.

The high child is the right x3. The x2 on the right, both of the children,

go to the right x3. The x3 on the left, both of them, go to 0.

And the x3 on the right, low goes to 0, high goes to 1.

We can immediately look at this and we can see that the x3 on the left is redundant

because both of its children go to the 0 node.

And the x2 on the right is redundant because both if its children go to the x3

node. And so, I can kill both of them.

I can just kill them both and I can redirect the edges.

I'm going to put little stars by them. I can redirect the edges that go into

those nodes that I kill. I can simply send them to their children.

Right? And so in the right-hand diagram, I'm

going to put a little star by each of these edges that were redirected.

And we have a vastly simpler BDD. There's a x1 node at the top, and there's

a single x2 node at the second rank. X1's low child is this x2 node.

There's a single x3 node at the third rank.

X1's high child is that x3 node. X2's child is that x3 node.

And then there are constants at the bottom.

X2's low child is the 0. X3's low child is the 0.

X3's high child is the 1. Wow, this is way less BDD than I started

with. This is way less graph than I started

this. This is way fewer nodes and way fewer

edges. Now, if you might ask.

How does one apply these rules? And for now I'm just going to say

iteratively. When you can't find another graph match,

the graph is reduced. Is, is this how programs really do it?

No. Absolutely not.

Not only no, no with two exclamation points.

Look, if I give you a function with a hundred variables, the way I just showed

you, you have to build the decision diagram with 2 to the 100 you know, nodes

at the bottom. And then you have to apply this reduction

stuff, that's crazy. There's no way you could do that.

There's actually a much smarter set of ways, and we'll do a very high level

overview of what those ways are. But for now, and for some homework

problems and sort of getting kind of intellectually on top of this stuff.

If I give you a function with three or four variables and I ask you to do the BDD

its perfectly okay for you to do this by hand.

You'll get the right answer and you'll get some insight in to how this stuff works.

Now, the big thing going on here is that we started with a decision diagram and it

was really big. And we ordered the variables and we said,

let's see if that makes the graph that we get canonical.

If we always get the same graph, and the answer was no because there could be

redundancies. Even if you always visit all the variables

in the same order from the root to the leaf, as you do decisions, you can still

get a different graph. So then we reduce the diagram by all of

these merging operations. And we got a new thing.

We got a thing called a Reduced Ordered BDD.

And the result of that is a really, really cool result.

And the really cool result is that a Reduced Ordered BDD is a canonical form.

Right? So I'm just going to say data structure.

For any Boolean function. I'm even going to stop it with an

exclamation point. Our reduced order BDD is a canonical form.

The same function always generates exactly the same graph, exactly the same nodes,

with exactly the same edges, with exactly the same children.

If you give me the same variable ordering. Two Boolean functions are identical if and

only if their Reduced Ordered BDD graphs are isomorphic which is a fancy way of

saying they are the same. Now, you might think, wow, how hard is

that to check? And the answer is going to be, amazingly

trivial. It's a wonderful result.

And this is a really beautiful property to have.