[MUSIC] Last time we talked about implications of a formal context. There may be a lot of implications valid in a formal context. As an extreme case, consider a context which has no objects at all. So in this context, A double prime equals M for all Subsets of M. Well, in this case, because this context has no objects, it has no counter example to any implication you may think of. And therefore, all implication are valid in this context. So if we have that a'' = m, then A implies B for all a and b. And if M contains N attributes, then there are two to the N possible subsets of M. And so we have two to the n possible As, two the N possible Bs. And this gives us two to the 2n possible implications. A huge number if n is big. But what's interesting is that they all follow from a single implication, empty set implies m. So when we have a formal context and we want to compute it's implicational theory, we generally don't want to have to see all the implications. We want to see a small sub-set. From which a small subset of valid implications from which all of other valid implication follow. Such a fad is called an implication basis. Let's give a formal definition. So a set L of implications A is called an implication basis. If it satisfied three properties. Well, first it must be sound. It must include only valid implications. if A implies B isn't L then or formal context, G,M,I and I should say although this is an implication basis over formal context, G,M,I. So if A implies B is an L, then this implication must be valid in G,M,I. The second property is completeness. Well, we need to ask for some kind of reverse property. But we don't want to ask the reverse property exactly, because we don't want L to contain all valid implications. We want this set to be small, so we'll ask for something weaker. If A-B is a valid implication We don't need it to be contained in L but it must follow from L. Okay, but now that the set of all valid implications satisfies these two properties, and it may be huge, as in this case, we want something small, like this. So to call L a basis, we'll need a third property. And this is non-redundancy. So that is a crucial perpeture for L to be basis. A set is non redundant an implication set l is non redundant if you can't remove an implication from it without losing the second property completeness. So if we have an implication A implies B in L. This implication doesn't follow from a smaller set of implications. So if you remove it from l you can't get it back. It doesn't follow from what remains. So in a way it's necessary. You can't remove any implication without losing completeness. So that's the meaning on nonredundancy. Okay, and so this is the definition of an implication basis. Another, if we were working with the formal context, it's quite easy to check this property. So it implies is volatile in G,M,I. If a null if. B is a subset of A double prime. And so we can replace this condition in the first two properties by this one. b is a subset of a double prime and we'll still get the definition of an implication basis of a formal context. [SOUND] [MUSIC]