Implication (information science)

In formal concept analysis (FCA) implications relate sets of properties (or, synonymously, of attributes). An implication A→B holds in a given domain when every object having all attributes in A also has all attributes in B. Such implications characterize the concept hierarchy in an intuitive manner. Moreover, they are "well-behaved" with respect to algorithms. The knowledge acquisition method called attribute exploration uses implications.^[1]

Definitions

An implication A→B is simply a pair of sets A⊆M, B⊆M, where M is the set of attributes under consideration. A is the premise and B is the conclusion of the implication A→B . A set C respects the implication A→B when ¬(C⊆A) or C⊆B.

A formal context is a triple (G,M,I), where G and M are sets (of objects and attributes, respectively), and where I⊆G×M is a relation expressing which objects have which attributes. An implication that holds in such a formal context is called a valid implication for short. That an implication is valid can be expressed by the derivation operators: A→B holds in (G,M,I) iff A′ ⊆ B′ or, equivalently, iff B⊆A".^[2]

Implications and formal concepts

A set C of attributes is a concept intent if and only if C respects all valid implications. The system of all valid implications therefore suffices for constructing the closure system of all concept intents and thereby the concept hierarchy.

The system of all valid implications of a formal context is closed under the natural inference. Formal contexts with finitely many attributes possess a canonical basis of valid implications,^[3] i.e., an irredundant family of valid implications from with all valid implications can be inferred. This basis consists of all implications of the form P→P"\P, where P is a pseudo-intent, i.e., a pseudo-closed set in the closure system of intents. See^[1] for algorithms.

References

^ ^a ^b Ganter, Bernhard and Obiedkov, Sergei (2016) Conceptual Exploration. Springer, ISBN 978-3-662-49290-1
^ Ganter, Bernhard and Wille, Rudolf (1999) Formal Concept Analysis -- Mathematical Foundations. Springer, ISBN 978-3-540-62771-5
^ Guigues, J.L. and Duquenne, V. Familles minimales d'implications informatives résultant d'un tableau de données binaires. Mathématiques et Sciences Humaines 95 (1986): 5-18.

[GanterObiedkov-1] Ganter, Bernhard and Obiedkov, Sergei (2016) Conceptual Exploration. Springer, ISBN 978-3-662-49290-1

[GanterWille-2] Ganter, Bernhard and Wille, Rudolf (1999) Formal Concept Analysis -- Mathematical Foundations. Springer, ISBN 978-3-540-62771-5

[3] Guigues, J.L. and Duquenne, V. Familles minimales d'implications informatives résultant d'un tableau de données binaires. Mathématiques et Sciences Humaines 95 (1986): 5-18.

[1]

[2]

[3]