0:01
So, here in lecture 6.4 we're going to continue our exploration of multilevel
logic. What we know is the algebraic model
simplfies our Boolean equations and makes it possible for us to do algebraic
division by which we can divide one Boolean equation by another so we can do
some factoring. But one of the questions that we don't
have an answer for yet is where should we go look to try to find the interesting
factors of a complecated set of Boolean equations.
And it turns out that the algebraic model offers a beautiful, insightful, and simple
answer. The algebraic model actually has a deep
structure. There are some interesting foundational
parts of Boolean Equations represented in the algebraic model, and those
foundational parts are called kernels and co-kernels.
It turns out that kernels and co-kernels are where all the action is in a
multi-level Boolean logic network. So in this lecture, we're going to explore
the basic structure of and definitions of kernels and co-kernels in multi-level
logic. So, where do we look for good divisors in
a big complicated network? And surprisingly, they algebraic model has
a beautiful answer, it's one of the more reasons we, you know, we like it.
It has this surprising and elegant deep structure.
So where do you look for the divisors of a function F?
And the answer is in the kernels of F. So this is denoted K of F, this is the set
of Boolean expressions called kernels. It's pronounced like colonel in a
military, you know, like captains and generals.
It's spelled with two e's so remember that depending on your Language you may be may
be interested to try. K, e, r, n, a, l which is wrong, this is
kernel two e's. K of F, the kernels of F is another set of
2 level sum of product forms. Which are the special foundational
structure of any function f being interpreted in the algebraic model, that's
a pretty big statement. So we're going to, we're going to have to
defend that one. How do you find a kernel K, element of the
kernels of F? Well, you algebraically divide it by
something else, called a co-kernel. And I'll just say, wow, boy there's just a
lot of new math here, and a lot of new concepts.
Let's, let's go develop these ideas, because they're actually, they're actually
lovely and practical. So let's just talk about what these things
are. The kernel, or a kernel, of a Boolean
expression f is a cube-free quotient k, obtained by algebraically dividing F by a
single cube. And that single cube c has a name, it's
called the co-kernel. So, on the left-hand side of this diagram
I've just got basic algebraic division. You give me F, I divide d into it, and I
get a quotient Q. I am drawing this like long division, like
how you learn to do division when you were like, I don't know, eight years old, ten
years old. You take F, you divide it by D, you get a
quotient Q and you get a remainder R, F is D times Q plus R.
Well, what is the kernel? If you take F and you divide it by 1 cube,
write a single cube, a single product term you know, abc, or pqr, or you know, xxtz
something like that. If you divide expression F by a single
cube, when you look at the quotient if the quotient is cube free then you have found
a kernel. So we need to explain what cube free
means, because what we're saying is that F is equal to c the co-kernel, ended with k
the kernel plus R, some sort of remainder. So Cube-free is really very simple, it
means that you cannot factor a single cube, which is to say a single product
term divisor, that leaves no remainder. So technical, technically this means it
has no 1 cube product that's a factor so you just take F, you divide by the cube
and you look at result, the result if you can cross out some cube in each term than
it is not a kernel. So I've got a table here.
It's got three columns, it has expression F, F equals d and Q plus R, and the
question, cube-free? So let's just go explore this for some of
the rows of this table. Suppose I give you expression a is a
cube-free? No, of course not, a is a cube.
How can a be cube free? It can't be, and if we write F equals D
times Q plus R, you know, F is equal to a times 1 plus 0, so no, it's not cube free.
A plus b is cube free, I cannot cross out a single product term in every single
element of that Boolean expression. Conversely ab plus ac is not cube free
because I can cross out an a in both of those terms and I can pull an a out as a
factor. What about abc plus abd well no that's not
cube free either, because I could cross out an ab in each of those terms I could
pull out an ab. I get c plus d and I'd have 0 as the
remainder. What about ab plus acd plus bd?
Yes, that's actually cube for you can stare at that for a long time but your not
going to be able to pull out a single cube and simply pull it out in front and write
an equation like the top 2 like the above 2 lines.
5:41
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.