So cube-free just means you can't cross out the same product term in every single

element of the sum of products form, it's as simple as that.

So let's look at some kernel examples. Kernels of function F are K of F suppose F

is abc plus abd plus bcd. I've got another table here.

I've got a divisor cube d. I'm going to divide d into F, right?

So F is d times Q plus R. So we're just going to write it in that

form. And then I'm going to ask is the quotient

a kernel? Okay, is Q a kernel of F?

So, what if I took F and divided it by D? Well then, I'm just going to, you know

divide it by D equals 1. Well, this is not very exciting, I'm going

to get F back again. And it turns out, in this case, F actually

is not cube-free. It's got a, an ab in every single term.

Sorry, it's gotta b in every single term. It's gotta b, gotta b, gotta b, right?

So this has cube b as a factor, so this is just not going to work.

What if we took divisor cube a and divided that into F, what would happen?

Well, it turns out that we get a for the divisor cube d and Q would be bc plus bd,

and it again has a common cube b in every term and so it's not cube-free.

So, now look. What happens if I divide F by b?

Oh, well, then it turns out I get a c plus ad plus cd.

Yes, that's a kernel, ac plus ad plus cd is a kernel, why?

Because I divided f by one cube, co-kernel b and I got something that was cube-free,

simple as that. What about if I divided by ab?

Yes, again if I divided by ab, ab is a cube, so the co-kernel is ab and the thing

I get, c plus d is cube free, I can't cross out a product term in every single

element. And you could just keep doing this as long

as you, you know, as long as you want but, but that's the basic idea.

So one of the things to take away from this immediately is that any Boolean

function F can have many different kernels.

But why are they important? And secondly, how do I compute them if it

is actually true that they are important? Well, let's start from the first reason,

you know. Why are they important?

They're important because of this very famous theorem, the Brayton and McMullen

theorem. From a paper by Bob Brayton and Curtis

McMullen way back when, expressions F and G have a common multiple cube divisor d if

and only if and this is important, there are kernels k1 which is a kernel of F and

k2 which is a kernel of G, such that when you intersect those two kernels, and

that's just a sum of products formed with common cubes in it, the resulting d is an

expression with at least two cubes in it. So that sounds very technical, it makes a

lot more sense if I draw a picture. Alright, so here's a nice little picture.

Why do I care about the Braiton-McMullen theorem?

Because it says in words that the only place to look for multiple cube divisors

is in the intersection of kernels. But that is a very powerful statement,

because it says, there is one and only one place to go look for divisors of a bunch

of complicated Boolean functions expressed in the algebraic model, and that's in the

intersections of their kernels. It's if and only if, there is no place

else. So suppose F was some Boolean function in

algebraic form and G was some Boolean function in algebraic form.

I could go extract their kernels, and so I would get a bunch of kernels in this nice

little cloud picture of F, k1, k2, k3 and then I could extract some kernels from G,

k4, k5, k6, k7 And I can say hey, do those any of those kernels intercept and what

that means is do they have some common cubes, are they're at least two cubes in

some of those intersections. So for example, you know, do we get

something that looks like this, ab plus c, that's at least 2 cubes.

If there's more, then there's more cubes. If the answer is yes, then I have

identified a multi-cube divisor. I can extract that, pull that out and

simplify both F and G. So, we had something that sounded like a

very complicated problem, you have a Boolean nation network with like thousands

of nodes, thousands of F's thousands of G's.

Your looking to extract good common divisors, and the answer is Kernel things.

Kernel F, Kernel G, ask if when you intersect them you can see something there

that has at least two cubes in it. If so, hey, you found a divisor and the

only way to find a divisor is this way. There are no other divisors.

It's a beautiful, powerful and as it turns out practical result.

So this is a little concrete example that sort of shows informally why this thing

works. Suppose F is a Boolean function and it's

got kernel1. Alright and so what we know is that

there's a cube which is a co kernel ended with kernel1 plus some remainder that,

that makes F and similarly G has a kernel called kernel2.

So, there's some cube called cube2 you end it with kernel2 and you order the

remainder and that makes G. Well, I could rewrite those things.

So let's just take you know, kernel1 and kernel2 and say alright look, kernel1 is X

plus Y plus stuff1. And X and Y I'm just arbitrarily making

this stuff up, those are some common product terms.

And G similarly cubed two times, X plus Y some, plus some different stuff, stuff2

plus a remainder. And again, x and y are just some product

terms. I could do a little Boolean algebra.

I could pull out the X plus Y, and say, oh, F is cube 1 times x plus y plus.

And then I'm just doing the Boolean algebra cube1 times stuff1 plus

remainder1. So this is just, you know, a little simple

algebra. And similarly G is cube2 times X plus Y

plus some other complicated stuff. And what I have discovered here is, oh

look, I took kernel1 from F, and kernel2 from F, and I intersected them.

And what did I find? I found two common cubes, X and Y.

And so kernal1 intersect kernal2 is X plus Y, and now I can extract d as X plus Y.

And F is now cube1 times d, F, G is cube2 times d plus some other stuff.

It got simpler, right? There's less stuff inside the F and the G

nodes because I've pulled d out. And what Brayton-McMullen says is this is

the only way this happens. The only place to look for these multiple

cube divisors is in the intersections of their kernels.

And this is just a, a more concrete example, so suppose F is ae plus be plus

cde plus ab it's got a kernel K of F of a plus b plus cd with co-kernel e.

Its got ab plus e kernel, co-kernel a. Its got an a plus e co-kernel, a plus e

kernel co-kernel b. And its got the original function with a

co-kernel of 1. And similarly on the right hand side g is

ad plus ae plus bd plus be plus bc. It's got kernels a plus b which turns out

to be something you can get with either d or e.

It's got a kernel d plus e which turns out to be something you can get either a or b

as the co-kernel. It's got a kernel d plus e plus c with

co-kernel b and again it's got its own self, which happens to be a kernel with

co-kernel 1. If you intersect the ab plus cd kernel of

F, with the a plus b kernel of G, you get a plus b, that's an intersection of

kernels. That is a workable multi-cube divisor.

We can consider using that for both of those functions.