Implication (information science)

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.