[SOUND] [MUSIC] So far, we've been talking mainly about concepts and lattices. Another important tool of formal concept analysis is implications. Implications are simple conditions of the form if, then. If a triangle is equilateral then it is isosceles. If a number if divisible by 20 then it is divisible by 10. If a person likes cats then she likes dogs. Implications may or may not be true with the respect to the data. And finding implications that hold in data is important task in data analysis. So let me give you formal definition. An implication, Over subset M, Is an expression of the form A arrow B. And we say that A implies B. And here, A and B are subsets of M. We say that A is the premise. And B, Is the conclusion of this implication. A subset of M satisfies this implication if whenever it has A it also has B. More formally, we'll say that T which is a subset of M is a model, Of implication A implies B. I said T has two chances to be a model of an implication. If A, the premise of the implication, is not a subset of T, then T is a model. And if B is a subset of T then T is also a model. So either T doesn't contain A or it contains B. Well, why so? Suppose early in the morning you go to work and you tell your wife or your mother if I'm late I will call you. And then you don't call but you are also not late, then you haven't violated your promise. So this is this case, you are not late. You said, if I'm late I'll call you and you're not late, so it's okay. Or maybe, you're late so you satisfy the promise or the implication. And then you make a phone call, so you satisfy the conclusion. This is the second case, so B is a subset of T. Again, you kept your promise. The only chance for you not to keep your promise, to violate your promise is to be late and not to call. Okay, so, we say that T is a model of A implies B if A is not a subset of T or B is a subset of T. Instead of saying that T is a model we sometimes say that T respects the implication, implies B or that T satisfies this implication. And if we have a whole set of implications, then we say that T is a model, Of the set, If it's a model of every implication from this set. And let me use some notation here. So we're saying that T is a model of A implies B, we'll write as follows. T, this sign, A implies B. And so, T is a model of a set L of implications, if T is a model of every implication from L. So, for all implications A, B from L, we have that T is a model of A implies B. And we denote this by T satisfies T as a model of L. So we've defined implications for an auditory set M. Well, how is it related to follow context? Let's now assume that M is the attribute set of a formal context. And so let A, B be subsets of M. And then we say that the implication A implies B, holds or is valid in context, G, M, I, If for all objects G we have the g prime as a model of A implies B. So, an implication holds in a context, if every object intent is a model of this implication. This is for attribute implications. We can, similarly, define object implications, all we need is to replace M with G here, and G with M here. The rest is the same, and object implications are somehow less useful, but we'll need them later as well. But now let's continue working with attribute implications. On the other hand from the formal point of view object implications and attribute implications are very similar in the sense that whatever we can proof about attribute implications, we can transfer this, the same results almost immediately to object implications. So, let's prove something about implications. Suppose that an implication A implies B, isn't it valid, In our formal context K. What does it mean? Well, according to this definition it means that all object intents satisfy this implication. All object intents are models of these implications. And for an object intent to a model of this implication it's efficient to not contain A or to contain B. So now let's look at only objects that contain A. So, we'll look at all g from A prime. Objects that are not in A prime, their object intents are models of the implication A implies B for this reason. So we only need to check that objects from A prime are models. And for them to be models of the implication A implies B, we need them to contain B. So, B must be a subset of g prime. But, this is the same as saying that B is a subset of A double prime. What's A double prime? It is the set of all attributes shared by all objects from A prime. But all objects from A prime have attributes B. So this set of attributes B must be among those shared by all objects from A prime. So B is a subset of A double prime. And this is the same as saying that A prime, Is a subset of B prime. Well, because B prime is the set of all objects that have all attributes from B. And we know that all objects from A prime have all attributes from B, so objects from A prime are among those from B prime. And so we have three conditions for implications to hold. If we want to check that an implication holds, then we can either go through all object intents and check that they're all models of this implication. Or we can simply compute A double prime and check that B is a subset of A double prime. Or we can check that A prime is a subset of B prime. These three conditions are equivalent. In the next video let's see how we can use them if an implications holds in a formal context. [SOUND]