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.
[Ganter, Bernhard and Obiedkov, Sergei (2016) ''Conceptual Exploration''. Springer, ]
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''".
[Ganter, Bernhard and Wille, Rudolf (1999) ''Formal Concept Analysis -- Mathematical Foundations''. Springer, ]
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 In mathematics, a closure operator on a set ''S'' is a function \operatorname: \mathcal(S)\rightarrow \mathcal(S) from the power set of ''S'' to itself that satisfies the following conditions for all sets X,Y\subseteq S
:
Closure operators are de ...
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
Inferences are steps in reasoning, moving from premises to logical consequences; etymologically, the word '' infer'' means to "carry forward". Inference is theoretically traditionally divided into deduction and induction, a distinction that in ...
. Formal contexts with finitely many attributes possess a ''canonical basis'' of valid implications,
[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.] 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''", where ''P'' is a ''pseudo-intent'', i.e., a
pseudo-closed set in the closure system of intents. See
for algorithms.
References
{{reflist
Information science