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]

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]

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.