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. 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. That is an amazing result, because in a real Boolean logic network, you could have thousands of Boolean network nodes. Okay and if you're trying to think to yourself, wow, where do I go look for divisors that can actually have some impact on the number of literals is this network. It seems a big complicated problem and the answer is no, I know exactly where to go look. Get the kernels of one of the nodes, get the kernels of the other node. Look for, to see if the kernels overlap, if they intersect, if they have, if they do, wow, you have found yourself good divisors. So we now know why they're important. You know, the next question is, how do you find the kernels? Well, there's an algorithm. Let's go look at that next.