[SOUND] [MUSIC] Let's see how this algorithm works on this simple example. This is a formal context for attributes a, b, c, d, and has four options, let's compute its canonical basis, L. So initially L is going to be empty, and our algorithm starts with an empty set A. And then it enumerates all other pre-closed set, well A itself is pre-closed, why? The empty set is always pre-closed, it's either closed or pseudo-closed. If a set is not closed, then what can go wrong for it not to be pseudo closed? It must contain a pseudo closed proper subset but empty set has no proper subsets. So empty set is always pseudo-closed even if it's not closed and in any case, it is always pre-closed. So we start with an empty set and we compute its closure, A''. In this case, it's empty set again so next closure returns of the next pre-closed set. The next pre-closed set in this case is {d}, now what's the closure of {d}? Let's look at the objects that have d, it's this one and this one, and they have nothing more in common. So the closure of {d} is {d} again, okay, the next pre-closed set is {c}, and it's also closed. Then we have {c,d} Okay, and now there's only one object that has both c and d, it's the first object and it also has a, so the closure of {c,d} is {a,c,d}. And so we add the first implication to our basis, cd implies a. Or I could write cd implies acd, but it's the same. So cd implies a. That's our first implication. Let's continue. The logical next set after cd is b. But it is closed, so nothing interesting here. The next set is {b,d} and it's closed again. {b,c} is also closed. And then we would normally consider bcd or I mean bcd is dialectical next set after bc. But this set is no longer pre-closed because it's not closed under our current set of implications L. The pre-closure of bcd is its closure under L, and this includes a. So it's a, b, c, d. So the cd is pre-closed, and the next closure would not return it as the next pre-closed set, it would ignore it. So we're not going to see it in our algorithm computing the canonical basis. And thus the next set is going to be a. Now the closure of a in this context is ac. We have two objects that have a and they both have c. And this gives us the second implication, a implies c. Let's continue, then we have ad but ad is not pre-closed. The pre-closure of ad is acd, so when I'm going to see ad, what else then ac. And ac is closed. Then acd. And it is closed again. Then we will have ab, but next closure will compute the pre-closure of ab. So the closure under L, the closure of ab under L is abc, because of this implication. A implies b. So the next set is the next pre-closed set, pre-closed set, is abc. What's the closure of abc? Well, there is no option that has all attributes from this set. All the three attributes, a, b, and c. And therefore the closure of a, b, c is the set of all attributes, a, b, c, and d. And this gives us the third implication, a, b, c implies d. Okay and then next set is a, b, c, d which is equal to M so the algorithm stops. And this is the basis, the canonical implication basis of this formal context. If you want to, you can manual check that all these three sets are indeed pseudo closed. [MUSIC]