[music] So here, in Lecture 2.6, we're going to finish our discussion of

Computational Boolean Algebra by completing our discussion of recursive

tautology. So, at the end of the last lecture, what

we showed was a, a computational vision of how this would work.

A recursion, where, if we cannot answer the question as to whether the function is

a tautology, we can pick a variable, use Shannon cofactoring, split things, turn

them into simpler pieces and build the outlines of a recursive implementation.

However, there's a whole bunch of more interesting properties of Boolean Algebra

and Boolean equation that we can use to make this efficient from an Engineering

point of view. So, in this lecture, we're going to show

what those interesting tricks are. And we're going to put it all together in

something called URP, the Unate Recursive Paradigm, which is an incredible, famous,

powerful set of methods for doing Iinteresting things on complicated Boolean

objects. So, we think we have a recursive strategy

that will do it. And if we can't calculate whether a

function is a tautology just by looking at its positional cube notation list, we

shall select a variable, split it into positive and negative cofactors.

These are simpler objects. They have smaller data structures, we

hope, and we should answer the question recursively only if they are both one

tautology, can their original function be one.

And so, this brings up a bunch of mechanical algorithm questions like what

are the selection rules, like how should I pick the x, what are the termination

rules, how do I know when I can actually stop and not recurse and just, you know,

mechanically, how do I do all this stuff. Let's start with the mechanics because

they're actually pretty easy. Now, I'll admit that this is a bit of a

complex looking slide but what I will just say is that this is just a recipe, this is

just all the mechanics written down on one slide.

How do you do the cofactors? How do you actually take the positional

cube notation list and take a variable and either cofactor it by setting the variable

equal to 1 or setting the variable equal to 0?

This is what you do, all you do is you look at every cube in the list, if you're

attempting to set the x to be a 1 to compute the positive cofactor.

You look, if the slot for x has a 1 0, well that's an x bar, you make the cube go

away, you remove it. If the slot has a 0 1, well, that's

actually got an x. When you set x to 1, you set it to a don't

care, because that, that variable also went away.

And if the cubed didn't have an x in it in the first place, well, you just leave it

alone. You don't do anything to it.

And the rules sort of flip if you're attempting to compute the x equals 0

cofactor. If there's a 0 1 in that slot, well, you

should just remove the cube, because there's an x there.

If there's a 1 0 there, well, you should just put a don't care there.

And if there's a 1, 1 there, well there's no x there in the first place, you don't

have to do anything. It makes a lot more sense to just go look

at an example. So here's a cube abd and here's a cube bc

bar. What if you want to do f of a?

And so, we're going to, we're going to set, set the value of a to be a 1, well,

in the, in this particular case, if you set the value of a, right, to be a 1,

well, in this cube, that becomes a don't care because the, the a goes away, and

everything else in the cube stays the same, right?

So, this is just a bd cube now. And similarly, if you said a to 1 in this

cube, well, nothing happens. And the reason that nothing happens, is

that there wasn't an a here in the first place, and so there wasn't any work to do.

Well, what if you take c and set it to be a value equal to 1, right?

Well, in the abd cube, nothing happens because there's no c's.

So, 01 11, 11 , sorry, 01, 01 11 01, alright, nothing happens it's still the

same. On the other hand, in the bc cube,

alright, because there is a, a c-bar in the slot, this cube just goes away,

alright? And that's one of the ways how when you

set the value of a variable to a constant to make a Shannon cofactor, the data

structure representation of the cube list gets smaller.

Some of the cubes vanish, right? They just go away, you don't have to worry

about them anymore. So, that's a good thing.

What about the selection and termination rules?

You know, how do you know which variable to pick?

And how do you know when you can just look at the list of bcn cubes and calculate

whether it's a 1 or not? Well, there's another really cool trick.

There's a class of Boolean functions you've probably not been, been exposed to.

They're called unate. And a function is unate if in a sum of

products representations, it has each literal, so that's just the appearance of

a variable in exactly one polarity, either they're all true or all complemented.

So, this particular function ab plus ac bar d plus c bar de bar is unate.

And the reason it's unate is that you only see each variable in true form.

So, you see a's but you don't see any a bars.

And you see b's, but you don't see any b bars.

And you see c, bars but you don't see any c's.

And you see d's, but no d bars and you see e bars, but no e's.

It doesn't matter what polarity. They don't all have to be positive.

They don't all have to be negative. They just have to be 1 polarity, right?

So, this other function here that I'm showing here is not unate.

And it's not unate because, among other things I see x's, and I also, I'm sorry,

and I also see x bars. However, it's possible for it to say that,

that it is unate in a specific variable. So, it's actually unate in variable y, and

the reason for that is you only see y's but no y bars.

And the terminology is that we way that the function is positive unate in a

variable, right, if changing the value of the variable from 0 to 1 keeps the

function constant or makes it increase, go up, 0 to 1.

And it's negative unate if changing that value of x from 0 to 1 keeps the function

constant or it makes the value of the function go down, from 1 to 0, and a

function that's not unate is called binate.

And if, that's sort of an analogy that I think is helpful here.

This particular function y equals f of x is monotone non-decreasing.

So, if I take a value of x1 here and I increase it, right, to a value of x2 here

what we can see in the function is that either it's flat or it goes up.

That's what monotone non-decreasing means. It means it doesn't get smaller.

Unate does exactly the same kind of a concept but for a Boolean expression, for

a Boolean function expressed in a sum of products form, right?

So, suppose that we have a positive unate variable x, then if this variable gets

bigger goes from 0 to 1, just like the graph above then, what happens on the

output is that either f goes from being a 0 to a 0 or it goes from being sorry a 1

to a 1, which is to say its day is flat, right, or it goes from a 0 to a 1, which

is to say, it increases, alright? So, this is kind of like flat or up, in

the monotone non-decreasing function, but in the Boolean universe.

Now, why we care about this is really sort of surprising.

First, let's just convince ourselves that it's not hard to check, alright?

So, suppose you have a cube-list for f, a cube-list is a unate if each variable in

each cube only appears in 1 polarity, not both.

We don't care what polarity, just 1 polarity.

So, this function that I'm showing on the top is unate, and the function that I'm

showing on the bottom is not, and it's much easier to sort of do visually if you

if you put them vertically and just ignore the don't care.

So, I'm just literally, I'm just going to cross out all the don't cares here.

Okay, and then what you can see is oh, look, a appears in 1 polarity, it just

appears in the 0 1 polarity. B appears in 1 polarity, it appears in the

1 0 polarity. C appears in 1 polarity, it appears in the

0 1 polarity. You can see that it's very easy to check

this mechanically, you just walk down all the cubes and for each cube you look in

the slot and you say is this the same as all the other cubes or not?

Yes or no. And in this one you can see, alright, if I

cross out the don't cares, you can see that this one is immediately, the problem

b appears in both b and b bar. So, it's not unate in this variable, not

unate. Now, why do we care about this?

Because it's a beautiful result. It's easy to check a unate cube-list for

tautology. A unate cube-list is a tautology if and

only if it contains the all don't care cube.

And that's literally a cube where every single slot is a 1, 1.

Now, let's just think for a minute. Again, what is that as a product term?

Because, so here is clearly a positional cube notation cube for the product abc.

And if I take the, the c variable, and I make it a don't care, this is clearly the

positional cube notation for ab. And then, if I take another one and I make

it a don't care, this is clearly the positional cubed notation for a.

But if I do it again, what do I get and the answer is that's how you represent a 1

in this business, you just put the all don't care, just like circling the whole

kernel map, alright? And this result actually make sense.

The only way you can make a 1 with product terms where all the literals are in

exactly one polarity, is if everyone in the kernel map is on.

There's no other way, because if you actually try to circle terms in the kernel

map and have every single product term appear with its literals in exactly 1

polarity, there will always be one square in the kernel map that you can't find.

Try it, it's, it's a good little exercise. Try it.

Convince yourself. So, we can look for tautology directly if

we have a unate cube-list. That's a wonderful thing.

So, I get two quick rules here. The first rule says the unate, the, I'm

sorry, the cube list is a 1. It's a tautology if it has the all don't

care cubes at this leaf, right? So, that's kind of simple, right?

If it's got all ones in it, it doesn't matter what's going on.

It's like saying, oh, look, this is stuff plus 1 plus stuff.

Alright, so, this easy and, in fact, I'd even say this is trivial, alright, this is

not rocket science here. You know 1 plus a bunch of stuff is 1.

Rule 2 is the interesting one, rule 2 is the, the flip of that, it's not 1 if the

cube list is unate and the all don't care cube is missing, right?

So, you go check and you see if the, if the cube it list is unate, and then, you

know that if the all don't cares cube is not there, it cannot be unate, I'm sorry,

it cannot be tautology and you can quit right out, you don't have to recurse, you

can just stop. So again, you know, I'm crossing out

everything. Oh, look, all of the a's are in 1

polarity. All of the b's are in 1 polarity.

All of the c's are in 1 polarity but there's no all don't care cubes here.

So it's unate, but the all don't cares cube is here.

It's not a tautology, it cannot be a tautology.

You can return a zero, alright? So, this one returns yes for a tautology

and this one returns no. So, these rules are important because it

means that you don't always have to go down to one cube at the bottom before you

can calculate stuff. You can calculate that you can stop and

return an answer with big and very complicated lists of cubes.

And you know you can have more rules if you like, this is a, a more mechanical

kind of a rule. What if you have a single cube that

appears in both polarities that just has one variable in it, right?

So, in this case we have one cube over here which is just let's say, x and we

have another cube over here which is just say x bar.

Oh, look, that's x plus x bar that's a 1. Yes, you can return a 1.

You get the idea, you can have a lot more rules if you like but you know, it's

generally the case that you don't want too many rules because there's a computational

cost in checking them. So, there's some balance between the

complexity of the rules for your termination conditions and just sort of

recursing a little bit further. Now I got one more mechanical step that we

need to figure out, and it's that, you know, I can't use the nicer termination

rules unless I have a unate cube-list. So, when I pick variables to split on,

maybe I should try to pick the splitting variables to force the cofactors to be

unate. So, the big idea is to pick the most

not-unate variable as the variable to split on the variable to cofactor on.

So, you try to pick the most binate variable.

And this is a heuristic, right, no guarantees.

Heuristic, exclamation point, exclamation point.

You know, this, this works pretty good but you know, I can't, I can't guarantee it.

So, what you do, just as I said before, you know, go in and you know, figure out

for every single variable, you know, which ones are unate and which ones are not,

okay? So x is binate and w is binate, right,

they are not unate, so those are the variables we should, we should focus on, x

and w. But they are both present in 4 cubes.

So, your first heuristic, sort of your first rule is pick the binate variable

that appears in the most product terms. And the reason you basically want to do

that, is that you'll simplify more cubes. There's the possibility that more cubes

will vanish, right? So, you want to pick the most binate

variable that appears in the most cubes. But what if there's a tie?

And that's true here, both x and w are binate and they both appear in 4 cubes,

now what do you do? Well, you calculate how many cubes they

appear in with true form and how many cubes they appear in with complement form.

So, that's how many places do you see x bars versus how many places do you see

x's. And you, you just calculate the absolute

value of the difference, and you pick the smallest value.

And the reason you do that is that probably you're going to balance the

complexity of the positive cofactor tree and the, and the negative cofactor tree.

They're both going to be, have basically the same amount of work.

And a balance is usually good in this. And again, no guarantees, it's just

another heuristic. So in this case, you would pick x because

it appears in four cubes, but it's the difference between it's true and

complement count as 0. It appears in two true cubes and two

complement cubes, that's a zero, that's the smallest number and that's the one you

pick. And so, this is the algorithm.

It's not all that much to it, it has a bunch of rules for, you know, for

termination, right? So, the first thing you do in any

recursive algorithm is,say, hey, can I compute the answer and stop, or do I

actually have to do some work? And if the answer is that you can not

compute the answer and stop, right then you have the selection problem where you

figure out the most not unate variable. And then, you have the recursion where you

call tautology on positive the cofactor and the negative cofactor and the really

cool thing about this is that's just code, right?

You know, each of these things returns a Boolean 1 bit value.

True, false, you just and them together in standard code fashion and that's what you

return. It's a beautiful little algorithm.

Here's just a little example, you know, showing what happens.

So suppose I just got this, this positional cube notation list at a node of

the tree, and I'm trying to figure out what to do, and so, the first thing I do

is I look at it and I say, wow, that's too complicated, I can't compute the right

answer. And it turns out that all of the variables

are binate, and a affects the most implicants.

It's in the most product terms, so we'll split on a, right?

So, when we go down this side of the recursion, we're setting a equals 1, and

we go down this side of the recursion, we're setting a equals 0.

And so, when we set a equal to 1 what happens, well we're going to pass in a

cube that looks like 11 01 11 and so that's just the b cube, right, because the

ab, the a goes away. And then, we're going to pass down a cube

that looks like 11, 11 01, that's a c cube because the a went away in the second

cube. And then, we're also going to pass down a

cube that looks like 11 10, 10 that's a, a b bar c cube because the a went away.

But when we go down the, this side, the a bar cube, alright, this cube, right, that

one just, that one just went away because when, when, when you have a cube that just

has an a bar in it and you set a to 1 that cube goes away, that cube vanishes, right?

That's a zero. So, only three cubes go down there and

then it turns out that you're going to have to recursive some more because you

can't actually tell anything about the value from this.

There are no rules to apply. Whereas, on the other side if you set a to

the 0, the first cube goes away and you don't pass it, it's a 0.

The second cube goes away and you don't pass it, the third cube goes away and you

don't pass it and again I am empathizing the whole reason for a sort of careful

selection of the splitting variables is to try to kill as more, many cubes as you

can. And then the third the fourth cube a bar

when you said a to 0, hey, there's the all don't cares cube so this thing has a 1 in

it and so it's a tautology. So, this one can just immediately send

back a yes. And I'm just finishing it out here so you

can see what happens. On the left-hand side when you go down and

recurse and set b equals 1, right, on the left-hand side, you get an all don't care

cubes so that's the, that's the one. And on this one, you get the, you know,

the c plus c bar rule 3 that we gave and that one is a yes.

And so this function is actually yes. This is a tautology.

Every single one of these things computes a yes and this is the computation tree

that is traced out. It has tautologies at all the leaves and

so, this is, in fact, a tautology and we're done.

This computational philosophy, if you will is very famous and very general and it has

a name. And so, this is called the Unate Recursive

Paradigm. It's a paradigm because it's actually a

big and impressive sort of, sort of a family of algorithms.

It's recursive because we use the Shannon cofactor as the, the critical step to take

a complicated problem and make it simpler, solvable.

That's our divide and conquer. And we use unate because it's just this

really clever trick that makes it possible to calculate complicated things tautology

on complicated representations without a lot of work.

And so, it's usually called URP. Please don't call it URP.

Nobody calls it URP, URP, Unate Recursive Paradigm.

So, here we are at the end of our, our introductory lecture set on Computational

Boolean Algebra. What if, what if I told you cofactors,

Shannon cofactors are really important and functions of cofactors are really

important. The Boolean difference, universal and

existential quantification, you know, network repair, there's some amazing

things you can do once you understand cofactors.

And representations, data structures for Boolean fit functions those are really

critical. In order for you to actually compute

stuff, you got to have a data representation and we showed you a very

simple one, cube-list, positional cube notation and with the cofactor ideas, we

were able to compute something really hard tautology using the Unate Recursive

Paradigm. So look, truth tables, kernel maps,

equations it's just not easy to manipulate those things with software.

The positional cube notation, notation that's one good way of doing it but it's

not honestly the way most people do it. The next week's lectures have lots of

stuff about how people actually do the representational problems for

Computational Boolean Algebra.