General Concept Lattice

The GCL claims to take into account the extended formal context for preservation of information content. Consider describing a three-ball system (3BS) with three distinct colours, e.g., $a:=$red, $b:=$green and $c:=$blue. {{Anchor|a4}}According to Table 1, one may refer to different attribute sets, say, $M=\backslash \{a,b,c\; \backslash \}$, $M\_1=\backslash \{a\backslash \; \{\backslash bf\; or\}\backslash \; b,\; b\backslash \; \{\backslash bf\; or\}\backslash \; c,c\; \backslash \; \{\backslash bf\; or\}\backslash \; a\; \backslash \}$ or $M\_2=\backslash \{a\backslash \; \{\backslash bf\; or\}\backslash \; b,\; b\backslash \; \{\backslash bf\; or\}\backslash \; c,c\; \backslash \}$ to reach different formal contexts. The concept hierarchy for the 3BS is supposed to be unique regardless of how the 3BS being described. {{Anchor|fig1}}However, the FCA exhibits different formal concept lattices subject to the chosen formal contexts for the 3BS , see Fig. 1. In contrast, the GCL is an invariant lattice structure with respect to these formal contexts since they can infer each other and ultimately entail the same information content.

In information science, the Formal Concept Analysis (FCA) promises practical applications in various fields based on the following fundamental characteristics.

• It orders the formal concepts in a hierarchy i.e. the formal concept lattice (FCL) which can be visualized as a line diagram that may be helpful for understanding the data.

• {{Anchor|cnb}}It enables the attribute exploration,{{Cite book |last1=Ganter |first1=Bernhard |title=Conceptual exploration |last2=Obiedkov |first2=Sergei |date=2016 |publisher=Springer-Verlag |isbn=978-3-662-49290-1 |location=Berlin}} a knowledge acquisition technique based on implications. It is possible to acquire the canonical (Guigues-Duquenne{{Cite journal |last1=Guigues |first1=J. L. |last2=Duquenne |first2=V. |date=1986 |title=Familles minimales d'implications informatives résultant d'un tableau de données binaires |url=https://eudml.org/doc/94331 |journal=Mathématiques et Sciences Humaines |volume=95 |pages=5–18 |issn=0987-6936 |access-date=2023-07-19 |archive-date=2022-04-19 |archive-url=https://web.archive.org/web/20220419154311/https://eudml.org/doc/94331 |url-status=live }}) basis, the non-redundant collection of informative implications based on which valid implications available from the formal context can be derived by the Armstrong rules.

{{Anchor|fclrsl}}The FCL does not appear to be the only lattice applicable to the interpretation of data table. Alternative concept lattices subject to different derivation operators based on the notions relevant to the Rough Set Analysis have also been proposed.{{Cite book |last1=Duntsch |first1=N. |last2=Gediga |first2=G. |chapter=Modal-style operators in qualitative data analysis |date=2002 |title=2002 IEEE International Conference on Data Mining, 2002. Proceedings. |chapter-url=https://ieeexplore.ieee.org/document/1183898 |publisher=IEEE Comput. Soc |pages=155–162 |doi=10.1109/ICDM.2002.1183898 |isbn=978-0-7695-1754-4 |s2cid=13170017 |access-date=2024-01-07 |archive-date=2023-12-06 |archive-url=https://web.archive.org/web/20231206170723/http://ieeexplore.ieee.org/document/1183898/ |url-status=live }}{{Citation |last1=Düntsch |first1=Ivo |title=Approximation Operators in Qualitative Data Analysis |date=2003 |url=http://dx.doi.org/10.1007/978-3-540-24615-2_10 |work=Lecture Notes in Computer Science |pages=214–230 |access-date=2023-07-19 |place=Berlin, Heidelberg |publisher=Springer Berlin Heidelberg |isbn=978-3-540-20780-1 |last2=Gediga |first2=Günther |doi=10.1007/978-3-540-24615-2_10 |archive-date=2024-02-25 |archive-url=https://web.archive.org/web/20240225153444/https://link.springer.com/chapter/10.1007/978-3-540-24615-2_10 |url-status=live |url-access=subscription }}{{Cite book |last=Yao |first=Y.Y. |chapter=Concept lattices in rough set theory |date=2004 |title=IEEE Annual Meeting of the Fuzzy Information, 2004. Processing NAFIPS '04 |chapter-url=http://dx.doi.org/10.1109/nafips.2004.1337404 |pages=796-801 Vol.2 |publisher=IEEE |doi=10.1109/nafips.2004.1337404 |isbn=0-7803-8376-1 |s2cid=6716057 |access-date=2023-07-19 |archive-date=2024-02-25 |archive-url=https://web.archive.org/web/20240225153447/https://ieeexplore.ieee.org/document/1337404/ |url-status=live }} Specifically, the object-oriented concept lattice, which is  referred to as the rough set lattice{{Cite journal |last1=Liaw |first1=Tsong-Ming |last2=Lin |first2=Simon C. |date=2020-10-12 |title=A general theory of concept lattice with tractable implication exploration |url=https://www.sciencedirect.com/science/article/pii/S0304397520302826 |journal=Theoretical Computer Science |language=en |volume=837 |pages=84–114 |doi=10.1016/j.tcs.2020.05.014 |s2cid=219514253 |issn=0304-3975 |access-date=2023-07-19 |archive-date=2020-05-28 |archive-url=https://web.archive.org/web/20200528022615/https://www.sciencedirect.com/science/article/pii/S0304397520302826 |url-status=live }} (RSL) afterwards, is found to be particularly instructive to supplement the standard FCA in further understandings of the formal context.

• The FCL exhibits the categorisation for object class according to their common properties while the RSL is according to those properties which other classes do not possess.

• The RSL provides an alternative scheme for implications available from the formal context which are beyond the scope of FCL, as will be clarified later. 

Consequently, there are two crucial points to be contemplated.{{Anchor|fig2}}

• The FCL and RSL reflect different concept hierarchies interpreting the same formal context in a complementary way. However, similar to the case of FCL, RSL also suffers from different lattice structures varying with respect to the chosen formal contexts, see Fig. 2.

• The implication relations extracted via the RSL from the formal context signify a different part of logic content from the ones extractable via the FCL. The treatment via the RSL would require further efforts of construction, the Guigues-Duquenne basis for the RSL. Moreover, it is unwarranted that the implications of these two together suffices the full logic content.File:VaryRsl.pdf.|300x300px]]

The GCL accomplishes a sound theoretical foundation for the concept hierarchies acquired from formal context. Maintaining the generality that preserves the information, the GCL underlies both the FCL and RSL, which correspond to substructures at particular restrictions. Technically, the GCL would be reduced to the FCL and RSL when restricted to conjunctions and disjunctions of elements in the referred attribute set ($M$), respectively. In addition, the GCL unveils extra information complementary to the results via the FCL and RSL. Surprisingly, the implementation of formal context via GCL is much more manageable than those via FCL and RSL.

The derivation operators constitute the building blocks of concept lattices and thus deserve distinctive notations. Subject to a formal context concerning the object set $G$ and attribute set $M$,

$I\backslash \; :\backslash$

\begin{array}{l}

X\subseteq G \mapsto\ X^I=\lbrace m\in M \mid gRm,\ \forall g \in X \rbrace\subseteq M\\

Y\subseteq M \mapsto\ Y^I=\lbrace g\in G \mid gRm,\ \forall m \in Y \rbrace\subseteq G

\end{array},

$\backslash Box\backslash \; :\backslash$

\begin{array}{l}

X\subseteq G \mapsto\ X^{\Box}=\lbrace m\in M \mid \forall g \in G, gRm \implies g\in X \rbrace\subseteq M\\

Y\subseteq M \mapsto\ Y^{\Box}=\lbrace g\in G \mid \forall m \in M, gRm \implies m\in Y \rbrace\subseteq G

\end{array},

$\backslash Diamond\backslash \; :\backslash$

\begin{array}{c}

X\subseteq G \mapsto\ X^{\Diamond}= \lbrace m \in M \mid \exists g\in G, (gRm,\ g\in X) \rbrace\subseteq M\\

Y\subseteq M \mapsto\ Y^{\Diamond}= \lbrace g \in G \mid \exists m\in M, (gRm,\ m\in Y) \rbrace\subseteq G

\end{array}

are considered as different modal operators (Sufficiency, Necessity and Possibility, respectively) that generalise the FCA. For notations, $I$, the operator adopted in the standard FCA, follows {{ill|Bernhard Ganter|de}}{{Cite journal |last=Ganter |first=Bernhard |date=1999-04-06 |title=Attribute exploration with background knowledge |journal=Theoretical Computer Science |series=ORDAL'96 |volume=217 |issue=2 |pages=215–233 |doi=10.1016/S0304-3975(98)00271-0 |issn=0304-3975 |doi-access=free }} and R. Wille; $\backslash Box\backslash mbox\{\; and\; \}\backslash Diamond$ as well as $R$ follows Y. Y. Yao. By $gRm$, i.e., $(g,m)\backslash in\; R$ the object $g$ carries the attribute $m$ as its property, which is also referred to as $g\backslash in\; m^R$ where $m^R$ is the set of all objects carrying the attribute $m$.

{{Anchor|a3}} With $X,X\_1,X\_2\; \backslash subseteq\; G\; \backslash mbox\{\; and\; \}\; X^c:=G\backslash backslash\; X$ it is straightforward to check that

$X^\{III\}=X^I,\backslash quad$

\begin{array}{c}

X^{\Box\Diamond\Box}=X^{\Box}\\

X^{\Diamond\Box\Diamond}=X^{\Diamond}

\end{array},\quad

\begin{array}{c}

X^{c\Box c}=X^{\Diamond}\\

X^{c\Diamond c}=X^{\Box}

\end{array}, $X\_1\backslash subseteq\; X\_2\backslash iff\; (X\_2)^I\backslash subseteq\; (X\_1)^I,\backslash quad$

\begin{array}{c}

X_1\subseteq X_2 \iff (X_1)^{\Box}\subseteq (X_2)^{\Box}\\

X_1\subseteq X_2

\iff (X_1)^{\Diamond}\subseteq (X_2)^{\Diamond}

\end{array},

where the same relations hold if given in terms of $Y,Y\_1,Y\_2\; \backslash subseteq\; M\; \backslash mbox\{\; and\; \}\; Y^c:=M\backslash backslash\; Y$.

{{Anchor|2gc}}From the above algebras, there exist different types of Galois connections, e.g.,

(1) $X\backslash subseteq\; Y^I$ $\backslash iff\; Y\backslash subseteq\; X^I$, (2) $Y^\{\backslash Diamond\}\backslash subseteq\; X$ $\backslash iff\; Y\backslash subseteq\; X^\{\backslash Box\}$

and (3) $X\backslash subseteq\; Y^\{\backslash Box\}$ $\backslash iff\; X^\{\backslash Diamond\}\backslash subseteq\; Y$ that corresponds to (2) when one replaces $X\; \backslash mbox\{\; for\; \}\; X^c$and $Y\; \backslash mbox\{\; for\; \}\; Y^c$. Note that (1) and (2) enable different object-oriented constructions for the concept hierarchies FCL and RSL, respectively. Note that (3) corresponds to the attribute-oriented construction where the roles of object and attribute in the RSL are exchanged. The FCL and RSL apply to different 2-tuple $(X,Y)$ concept collections that manifest different well-defined partial orderings.

Given as a concept, the 2-tuple $(X,Y)$ is in general constituted by an extent $X\backslash subseteq\; G$ and an intent $Y\backslash subseteq\; M$, which should be distinguished when applied to FCL and RSL. The concept $(X,Y)\_\{fcl\}$ is furnished by $X^I=Y\backslash mbox\{\; and\; \}Y^I=X$ based on (1) while $(X,Y)\_\{rsl\}$ is furnished by $X^\{\backslash Box\}=Y\backslash mbox\{\; and\; \}Y^\{\backslash Diamond\}=X$ based on (2). In essence, {{Anchor|a5}}there are two Galois lattices based on different orderings of the two collections of concepts as follows.

$(X\_1,\; Y\_1)\_\{fcl\}\backslash leq\; (X\_2,\; Y\_2)\_\{fcl\}$ entails $X\_1\backslash subseteq\; X\_2$ and $Y\_2\; \backslash subseteq\; Y\_1$

since $X\_1\backslash subseteq\; X\_2$ iff $Y\_2=X\_2^I\backslash subseteq\; X\_1^I=Y\_1$, and $Y\_2\backslash subseteq\; Y\_1$ iff $X\_1=Y\_1^I\backslash subseteq\; Y\_2^I=X\_2$.

$(X\_1,\; Y\_1)\_\{rsl\}\backslash leq\; (X\_2,\; Y\_2)\_\{rsl\}$ entails $X\_1\backslash subseteq\; X\_2$ and $Y\_1\; \backslash subseteq\; Y\_2$

since $X\_1\backslash subseteq\; X\_2$ iff $Y\_1=X\_1^\backslash Box\backslash subseteq\; X\_2^\backslash Box=Y\_2$, and $Y\_1\; \backslash subseteq\; Y\_2$ iff $X\_1=Y\_1^\backslash Diamond\backslash subseteq\; Y\_2^\backslash Diamond=X\_2$.

Every attribute listed in the formal context provides an extent for FCL and RSL simultaneously via the object set carrying the attribute. Though the extents for FCL and for RSL do not coincide totally, every $m^R$ for $m\backslash in\; M$ is known to be a common extent of FCL and RSL. This turns up from the main results in FCL ({{ill|Formale Begriffsanalyse#Hauptsatz der Formalen Begriffsanalyse|de}}) and RSL: every $Y^I$ ($Y\backslash subseteq\; M$) is an extent for FCL and $Y^\backslash Diamond$is an extent for RSL. Note that choosing $Y=\backslash \{m\backslash \}$ gives rise to $Y^I=Y^\backslash Diamond=m^R$.

The consideration of the attribute set-to-set implication $A\backslash stackrel\{\backslash scriptscriptstyle\; fcl\}\{\backslash rightarrow\}\; B$ ($A,\; B\backslash subseteq\; M$) via FCL has an intuitive interpretation: every object possessing all the attributes in $A$ possesses all the attributes in $B$, in other words $A^I\backslash subseteq\; B^I$. Alternatively, one may consider $A\backslash stackrel\{\backslash scriptscriptstyle\; rsl\}\{\backslash rightarrow\}\; B$ based on the RSL in a similar manner: the set of all objects carrying any of the attributes in $A$ is contained in the set of all objects carrying any of the attributes in $B$, in other words $A^\backslash Diamond\backslash subseteq\; B^\backslash Diamond$. It is apparent that $A\backslash stackrel\{\backslash scriptscriptstyle\; fcl\}\{\backslash rightarrow\}\; B$ and $A\backslash stackrel\{\backslash scriptscriptstyle\; rsl\}\{\backslash rightarrow\}\; B$ relate different pairs of attribute sets and are incapable of expressing each other.

For every formal context one may acquire its extended version deduced in the sense of completing a truth-value table. It is instructive to explicitly label the object/attribute dependence for the formal context, say, $F(G,M):=(G,\; M,\; I)$ rather than $\backslash mathbb\{K\}:=\; (G,\; M,\; I)$ since one may have to investigate more than one formal contexts. As is illustrated in Table 1, $F\_\{\backslash scriptscriptstyle\; 3BS\}\; (G,M)$ can be employed to deduce the extended version $F\_\{\backslash scriptscriptstyle\; 3BS\}^\backslash ast\; (G,M^\backslash ast)$, where $M^\backslash ast$ is the set of all attributes constructed out of elements in $M$ by means of Boolean operations. Note that $F\_\{\backslash scriptscriptstyle\; 3BS\}\; (G,M)$ includes three columns reflecting the use of $M=\backslash \{a,b,c\; \backslash \}$ and $F\_1(G,M\_1)$ the attribute set $M\_1=\backslash \{a\backslash \; \{\backslash bf\; or\}\backslash \; b,\; b\backslash \; \{\backslash bf\; or\}\backslash \; c,c\; \backslash \; \{\backslash bf\; or\}\backslash \; a\; \backslash \}$.

The FCL and RSL will not be altered if their intents are interpreted as single attributes.

$(X,Y)\_\{fcl\}$ can be understood as $(X,\backslash mu)\_\{fcl\}$ with $\backslash mu=\backslash prod\; Y$ (the conjunction of all elements in $Y$),$\backslash \; \backslash begin\{smallmatrix\}\; \backslash prod\; X^I=\backslash mu\backslash \backslash$

\mu^R=X\end{smallmatrix}

plays the role of $$

\begin{smallmatrix} X^I=Y\\

Y^I=X\end{smallmatrix} since $Y^I=(\backslash prod\; Y)^R=\backslash mu^R\backslash subseteq\; G$.

$(X,Y)\_\{rsl\}$ can be understood as $(X,\backslash mu)\_\{rsl\}$ with $\backslash mu=\backslash sum\; Y$ (the disjunction of all elements in $Y$),$\backslash \; \backslash begin\{smallmatrix\}\; \backslash sum\; X^\backslash Box=\backslash mu\backslash \backslash$

\mu^R=X\end{smallmatrix}

plays the role of $$

\begin{smallmatrix} X^{\Box}=Y\\

Y^{\Diamond}=X\end{smallmatrix} since $Y^\backslash Diamond=(\backslash sum\; Y)^R=\backslash mu^R\backslash subseteq\; G$.

Here, the dot product $\backslash cdot\backslash \; (\backslash prod)$ stands for the conjunction (the dots is often omitted for compactness) and the summation $+\backslash \; (\backslash sum)$ the disjunction, which are notations in the Curry-Howard style. Note that the orderings become

$(X\_1,\backslash mu\_1)\_\{fcl\}\backslash leq\; (X\_2,\backslash mu\_2)\_\{fcl\}$ and $(X\_1,\backslash mu\_1)\_\{rsl\}\backslash leq\; (X\_2,\backslash mu\_2)\_\{rsl\}$, both are implemented by $$

X_1\subseteq X_2$$

\iff$$

\mu_1\leq \mu_2

.

Concerning the implications extracted from formal context,

$\backslash mu\_1\backslash rightarrow\; \backslash mu\_2$ serves as the general form of implication relations available from the formal context, which holds for any pair of $\backslash mu\_1,\backslash mu\_2\backslash in\; M^\backslash ast$ fulfilling $\backslash mu\_1^R\backslash subseteq\; \backslash mu\_2^R$.

Note that $\backslash mu\_1^R\backslash subseteq\; \backslash mu\_2^R$ turns out to be trivial if $\backslash mu\_1\backslash leq\; \backslash mu\_2$, which entails $\backslash mu\_1=\backslash mu\_1\backslash cdot\; \backslash mu\_2$. Intuitively, every object carrying $\backslash mu\_1$ is an object carrying $\backslash mu\_2$, which means the implication any object having the property $\backslash mu\_1$ must also have the property $\backslash mu\_2$. In particular,

$A\backslash stackrel\{\backslash scriptscriptstyle\; fcl\}\{\backslash rightarrow\}\; B$ can be interpreted as $\backslash mu\_1\backslash rightarrow\; \backslash mu\_2$ with $\backslash mu\_1=\backslash prod\; A$ and $\backslash mu\_2=\backslash prod\; B$,

$A\backslash stackrel\{\backslash scriptscriptstyle\; rsl\}\{\backslash rightarrow\}\; B$ can be interpreted as $\backslash mu\_1\backslash rightarrow\; \backslash mu\_2$ with $\backslash mu\_1=\backslash sum\; A$ and $\backslash mu\_2=\backslash sum\; B$,

where $A^I\backslash subseteq\; B^I$ and $A^\backslash Diamond\backslash subseteq\; B^\backslash Diamond$ collapse into $\backslash mu\_1^R\backslash subseteq\; \backslash mu\_2^R$.

When extended to $F^\backslash ast(G,M^\backslash ast)$, the algebras of derivation operators remain formally unchanged, apart from the generalisation from $m\backslash in\; M$ to $\backslash mu\; \backslash in\; M^\backslash ast$ which is signified in terms of the replacements $I\backslash mbox\{\; by\; \}I^\backslash ast$, $\backslash Box\backslash mbox\{\; by\; \}\backslash Box^\backslash ast$ and $\backslash Diamond\backslash mbox\{\; by\; \}\backslash Diamond^\backslash ast$. The concepts under consideration become then $(X,\; Y)^\backslash ast\_\{fcl\}$ and $(X,\; Y)^\backslash ast\_\{rsl\}$, where $X\backslash subseteq\; G$ and $Y\backslash subseteq\; M^\backslash ast$, which are constructions allowable by the two Galois connections i.e. $X\backslash subseteq\; Y^\{I^\backslash ast\}\backslash iff\; Y\; \backslash subseteq\; X^\{I^\backslash ast\}$ and $Y^\{\backslash Diamond^\backslash ast\}\backslash subseteq\; X\; \backslash iff\; Y\backslash subseteq\; X^\{\backslash Box^\backslash ast\}$, respectively. Henceforth,

X^{I^\ast}=Y and $Y^\{I^\backslash ast\}=X$

for $(X,\; Y)^\backslash ast\_\{fcl\}$, $$

X^{\Box^\ast}=Y and $$

Y^{\Diamond^\ast}=X for $(X,\; Y)^\backslash ast\_\{rsl\}$.

The extents for the two concepts now coincide exactly. All the attributes in $M^\backslash ast$ are listed in the formal context $F^\backslash ast(G,M^\backslash ast)$, each contributes a common extent for FCL and RSL. {{Anchor|Dk}}Furthermore, the collection of these common extents $E\_F:=\backslash \{\backslash mu^R\backslash mid\backslash mu\backslash in\; M^\backslash ast\backslash \}$ amounts to $\backslash \{\backslash bigcup\_\{k\backslash in\; J\}\; D\_k\backslash mid\; J\backslash subseteq\; \backslash \{1\backslash ldots\; n\_F\backslash \}\backslash \}$ which exhausts all the possible unions of the minimal object sets discernible by the formal context. Note that each $D\_k$ collects objects of the same property, see Table 2. One may then join $(X,\; Y)^\backslash ast\_\{fcl\}$ and $(X,\; Y)^\backslash ast\_\{rsl\}$ into a 3-tuple with common extent:

$(X,Y^\{fcl\backslash ast\},Y^\{rsl\backslash ast\})$ where $X^\{I^\backslash ast\}=Y^\{fcl\backslash ast\}$, $X^\{\backslash Box^\backslash ast\}=\{Y^\{rsl\backslash ast\}\}$ and $\{Y^\{fcl\backslash ast\}\}^\{I^\backslash ast\}=\{Y^\{rsl\backslash ast\}\}^\{\backslash Diamond^\backslash ast\}=X$.

Note that $Y^\{fcl\backslash ast\}\backslash mbox\{\; and\; \}Y^\{rsl\backslash ast\}$are introduced in order to differentiate the two intents. Clearly, the number of these 3-tuples equals the cardinality of set of common extent which counts $|E\_F|=2^\{n\_F\}$. Moreover, $(X,Y^\{fcl\backslash ast\},Y^\{rsl\backslash ast\})$ manifests well-defined ordering. For $X\_1,\; X\_2\backslash in\; E\_F\backslash subseteq\; G\backslash$

, where $\{Y\_1^\{fcl\backslash ast\}\},\{Y\_2^\{fcl\backslash ast\}\}\backslash subset\; M^\backslash ast$

and $$

{Y_1^{rsl\ast}},{Y_2^{rsl\ast}}\subset M^\ast,

$(X\_1,\{Y\_1^\{fcl\backslash ast\}\},\{Y\_1^\{rsl\backslash ast\}\})\backslash leq\; (X\_2,\{Y\_2^\{fcl\backslash ast\}\},\{Y\_2^\{rsl\backslash ast\}\})$ iff $$

X_1 \subseteq X_2 and $\{Y\_2^\{fcl\backslash ast\}\}\backslash subseteq\; \{Y\_1^\{fcl\backslash ast\}\}$ and $\{Y\_1^\{rsl\backslash ast\}\}\backslash subseteq\; \{Y\_2^\{rsl\backslash ast\}\}$.

{{Anchor|eta_rho}}While it is generically impossible to determine $Y^\{fcl\backslash ast\}\backslash mbox\{\; and\; \}Y^\{rsl\backslash ast\}$ subject to $X\backslash in\; E\_F\backslash subseteq\; G$

, the structure of concept hierarchy need not rely on these intents directly. An efficient way to implement the concept hierarchy for $(X,Y^\{fcl\backslash ast\},Y^\{rsl\backslash ast\})$ is to consider intents in terms of single attributes.

Let henceforth $$

\eta(X):=\prod Y^{fcl\ast}

and $$

\rho(X):=\sum Y^{rsl\ast}

. Upon introducing $[X]\_F:=\backslash \{\backslash mu\backslash in\; M^\backslash ast\backslash mid\; \backslash mu^R=X\backslash \}$, one may check that $\backslash prod\; [X]\_F=\backslash prod\; Y^\{fcl\backslash ast\}$ and $\backslash sum\; [X]\_F=\backslash sum\; Y^\{rsl\backslash ast\}$, $\backslash forall\; X\backslash in\; E\_F$. Therefore,

$[X]\_F\backslash equiv\; [\backslash eta(X),\; \backslash rho(X)]=\backslash \{\backslash mu\backslash in\; M^\backslash ast\backslash mid\; \backslash eta(X)\backslash leq\backslash mu\backslash leq\; \backslash rho(X)\backslash \}$,

which is a closed interval bounded from below by $\backslash eta(X)$ and from above by $\backslash rho(X)$ since $\backslash forall\backslash mu\backslash \; \backslash mu^R=X\backslash implies\; \backslash eta(X)\backslash leq\backslash mu\backslash leq\; \backslash rho(X)$. Moreover,

$\backslash forall\; X\_1\backslash forall\; X\_2\backslash in\; E\_F\backslash \; X\_1\backslash neq\; X\_2$ iff $[X\_1]\_F\backslash cap\; [X\_2]\_F=\backslash emptyset$, $X\_1\; \backslash subset\; X\_2$ iff iff .

In addition, $\backslash bigcup\_\{X\backslash in\; E\_F\}[X]\_F=M^\backslash ast$, namely, the collection of intents $[X]\_F$ exhausts all the generalised attributes $M^\backslash ast$, in comparison to $\backslash bigcup\_\{X\backslash in\; E\_F\}\; X=G$. Then, the GCL enters as the lattice structure $\backslash Gamma\_F:=(L\_F,\backslash wedge,\backslash vee)$ based on the formal context via $F^\backslash ast(G,M^\backslash ast)$:

• The collection of all the general concepts $L\_F=\backslash \{(X,[X]\_F)\backslash mid\backslash \; X\backslash in\; E\_F\backslash \}$ constitutes the poset $(L\_F,\backslash leq)$ ordered as{{Anchor|setorder}}

$l\_1:=(X\_1,[X\_1]\_F)\backslash leq\; l\_2:=(X\_2,[X\_2]\_F)$

iff $$

X_1 \subseteq X_2 and $$

\eta(X_1)\leq\eta(X_2)

and $$

\rho(X_2)\leq\rho(X_2)

.

• Both $\backslash wedge$ (meet) and $\backslash vee$ (join) operations are applicable for finding further lattice points:

$l\_1\backslash wedge\; l\_2\; =\; \backslash left(X\_1\backslash cap\; X\_2,\; [X\_1\backslash cap\; X\_2]\_F\backslash right)$

\in L_F, where $[X\_1\backslash cap\; X\_2]\_F=[\backslash eta(X\_1\backslash cap\; X\_2),\; \backslash rho(X\_1\backslash cap\; X\_2)]$

=[\eta(X_1)\cdot \eta(X_2), \rho(X_1)\cdot \rho(X_2)],

$l\_1\backslash vee\; l\_2\; =\; \backslash left(X\_1\backslash cup\; X\_2,[X\_1\backslash cup\; X\_2]\_F\backslash right)$

\in L_F, where$[X\_1\backslash cup\; X\_2]\_F=[\backslash eta(X\_1\backslash cup\; X\_2),\; \backslash rho(X\_1\backslash cup\; X\_2)]$

=[\eta(X_1)+\eta(X_2), \rho(X_1)+\rho(X_2)].

• The GCL appears to be a complete lattice since both $l\_\{sup\}$ and $l\_\{inf\}$ can be found in $L\_F$:

$l\_\{sup\}=\backslash bigvee\_\{l\backslash in\; L\_F\}\; l=(G,\; [G]\_F)=(G,[\backslash eta(G),\{\backslash bf\; 1\}])$, $l\_\{inf\}=\backslash bigwedge\_\{l\backslash in\; L\_F\}\; l=(\backslash emptyset,\; [\backslash emptyset]\_F)=(\backslash emptyset,[\{\backslash bf\; 0\},\backslash rho(\backslash emptyset)])$.

The construction for FCL was known to count on efficient algorithms,{{Cite journal |last=Kuznetsov |first=Sergei O. |date=2001-12-01 |title=On Computing the Size of a Lattice and Related Decision Problems |url=https://doi.org/10.1023/A:1013970520933 |journal=Order |language=en |volume=18 |issue=4 |pages=313–321 |doi=10.1023/A:1013970520933 |s2cid=11571279 |issn=1572-9273 |access-date=2023-08-12 |archive-date=2024-02-25 |archive-url=https://web.archive.org/web/20240225153445/https://link.springer.com/article/10.1023/A:1013970520933 |url-status=live |url-access=subscription }}{{Cite journal |last1=Kuznetsov |first1=Sergei O. |last2=Obiedkov |first2=Sergei A. |date=April 2002 |title=Comparing performance of algorithms for generating concept lattices |url=http://www.tandfonline.com/doi/abs/10.1080/09528130210164170 |journal=Journal of Experimental & Theoretical Artificial Intelligence |language=en |volume=14 |issue=2–3 |pages=189–216 |doi=10.1080/09528130210164170 |s2cid=10784843 |issn=0952-813X |access-date=2023-08-12 |archive-date=2023-10-17 |archive-url=https://web.archive.org/web/20231017163804/http://www.tandfonline.com/doi/abs/10.1080/09528130210164170 |url-status=live |url-access=subscription }} not to mention the construction for RSL which did not receive much attention yet. Intriguingly, though the GCL furnishes the general structure on which both the FCL and RSL can be rediscovered, the GCL can be acquired via simple readout.

The completion of GCL is equivalent to the completion of the intents of GCL in terms of the lower and bounds.

• The lower bounds $(\backslash eta(X)\backslash mbox\{\; for\; \}\; X\backslash in\; E\_F)$ can be employed to determine the upper bounds $(\backslash rho(X)\backslash mbox\{\; for\; \}\; X\backslash in\; E\_F)$, and vice versa. For concreteness, both $X$ and $X^c$ are extents of the GCL, $(X,[X]\_F)=(X,[\backslash eta(X),\backslash rho(X)])$ coexists with $(X^c,[X^c]\_F)$$=(X^c,[\backslash eta(X^c),\backslash rho(X^c)])$. Subsequently, $\backslash eta(X^c)=\backslash neg\; \backslash rho(X)$ and $\backslash neg\; \backslash eta(X)=\; \backslash rho(X^c)$, where $\backslash eta(X^c)=\backslash neg\; \backslash rho(X)\backslash iff\backslash neg\; \backslash eta(X)=\; \backslash rho(X^c)$.

• The lower bounds of intents corresponding to minimal discernible object sets ($D\_k$s for $1\backslash leq\; k\backslash leq\; n\_F$

) can be employed to determine all the intents. Note that $D\_k\backslash in\; E\_F$ and $\backslash eta(D\_k)=\backslash prod\; \backslash Psi^k$ appears to be a direct readout by means of $\backslash Psi^k=\backslash lbrace\; m\backslash in\; M\; \backslash mid\; m\backslash in\; D\_k^I\backslash rbrace\backslash cup\backslash lbrace\; \backslash neg\; m\; \backslash mid\; m\backslash not\backslash in\; D\_k^I,\; m\backslash in\; M\backslash rbrace$.

File:RslFclGcl0.pdf according to the formal context $F(G,M)$ in Table 1. Every general intent $[X]\_F$ comprises all the attributes uniquely possessed by the object set $X$ in common. Elements on $[X]\_F$ can be ordered as a Hasse diagram identifiable with the closed interval $[\backslash eta(X),\backslash rho(X)]$ where $\backslash rho(X)=\backslash eta(X)+0\_\backslash rho$.]]

{{Anchor|fig3}}The above enables the determinations of the intents depicted as in Fig. 3 for the 3BS given by Table 1, where one can read out that $\backslash eta(\backslash \{1\backslash \})=a\backslash neg\; b\backslash neg\; c$, $\backslash eta(\backslash \{2\backslash \})=\backslash neg\; a\; b\backslash neg\; c$ and $\backslash eta(\backslash \{3\backslash \})=\backslash neg\; a\; b\backslash neg\; c$. Hence, e.g., $\backslash rho(\backslash \{1,2\backslash \})=\backslash neg\; \backslash eta(\backslash \{\; 3\; \backslash \})=\; a+\; b+\backslash neg\; c$, $\backslash eta(\backslash \{1,2\backslash \})=a\backslash neg\; b\backslash neg\; c+\; \backslash neg\; a\; b\backslash neg\; c=\backslash neg\; \backslash rho(\backslash \{\; 3\; \backslash \})$

. Note that the GCL also appears to be a Hasse diagram due to the resemblance of its extents to a power set. Moreover, each intent $[X]\_F=[\backslash eta(X),\; \backslash rho(X)]$ at $X$ also exhibits another Hasse diagram isomorphic to the ordering of attributes in the closed interval $[\{\backslash bf\; 0\},\; 0\_\backslash rho]$. It can be shown that $\backslash forall\; X\backslash in\; E\_F\backslash \; \backslash rho(X)=\backslash eta(X)+0\_\backslash rho$ where $0\_\backslash rho:=\backslash neg\; 1\_\backslash eta\backslash equiv\; \backslash rho(\backslash emptyset)$ with $1\_\backslash eta:=\backslash sum\_\{k=1\}^\{n\_F\}\; \backslash eta(D\_k)\backslash equiv\; \backslash eta(G)$. Hence, $[X]\_F=\backslash \{\; \backslash eta(X)+\backslash tau\backslash mid\; \{\backslash bf\; 0\}\backslash leq\backslash tau\backslash leq\; 0\_\backslash rho\backslash \}$

making the cardinality $|[X]\_F|$ a constant given as $2^\{2^$

The GCL underlies the original FCL and RSL subject to $F(G,M)$, as one can tell from $$

\eta(X)=\prod Y^{fcl\ast}

and $$

\rho(X)=\sum Y^{rsl\ast}

. To rediscover a node for FCL, one looks for a conjunction of attributes in $M$ contained in $[X]\_F$, which can be identified within the conjunctive normal form of $\backslash eta(X)$ if exists. Likewise, for the RSL one looks for a disjunction of attributes in $M$ contained in $[X]\_F$, which can be found within the disjunctive normal form of $\backslash rho(X)$, see Fig 3.

For instance, from the node $(\backslash \{3\backslash \},[\backslash \{3\; \backslash \}]\_F)$ on the GCL, one finds that $\backslash eta(\backslash \{3\backslash \})=\backslash neg\; a\backslash neg\; bc\backslash leq\; c$ $\backslash leq\; (a+\backslash neg\; b+c)(\backslash neg\; a+\; b+c)$$=\; \backslash rho(\backslash \{\; 3\backslash \})$. Note that $c$ appears to be the only attribute belonging to $[\backslash \{3\backslash \}]\_F$, which is simultaneously a conjunction and a disjunction. Therefore, both the FCL and RSL have the concept $(\backslash \{3\backslash \},\backslash \{c\backslash \})$ in common. To illustrate a different situation, $\backslash rho(\backslash \{1,3\backslash \})=(a+\backslash neg\; b+c)\backslash geq\; a+c$$\backslash geq\; a\backslash neg\; b\backslash neg\; c+\backslash neg\; a\backslash neg\; bc$$=\; \backslash eta(\backslash \{\; 1,3\; \backslash \})$. Apparently, $a+c$ is the attribute emerging as disjunction of elements in $M$ which belongs to $[\backslash \{1,3\backslash \}]\_F$, in which no attribute composed by conjunction of elements in $M$ is found. Hence, $\backslash \{1,3\backslash \}$ could not be an extent of FCL, it only constitutes the concept $(\backslash \{1,\; 3\backslash \},\backslash \{a,c\backslash \})$ for the RSL.

Non-tautological implication relations signify the information contained in the formal context and are referred to as informative implications. In general, $\backslash mu\_1^R\backslash subseteq\; \backslash mu\_2^R$ entails the implication $\backslash mu\_1\backslash rightarrow\; \backslash mu\_2$. The implication is informative if it is $not\backslash \; \backslash mu\_1\; \backslash leq\; \backslash mu\_2$ (i.e. $\backslash mu\_1\backslash neq\; \backslash mu\_1\backslash cdot\backslash mu\_2$).

In case it is strictly $\backslash mu\_1^R\backslash subset\; \backslash mu\_2^R$, one has $\backslash mu\_1^R=\backslash mu\_1^R\backslash cap\backslash mu\_2^R=(\backslash mu\_1\backslash cdot\; \backslash mu\_2)^R$ where $\backslash mu\_1^R\backslash cap\backslash mu\_2^R\backslash subset\; \backslash mu\_2^R$. Then, $\backslash mu\_1\backslash rightarrow\; \backslash mu\_2$ can be replaced by means of $\backslash mu\_1\backslash leftrightarrow\; \backslash mu\_1\backslash cdot\backslash mu\_2$ together with the tautology $\backslash mu\_1\backslash cdot\; \backslash mu\_2\backslash implies\; \backslash mu\_2$. Therefore, what remains to be taken into account is the equivalence $\backslash mu^R=\; \backslash nu^R=X$ for some $X\backslash in\; E\_F$. Logically, both attributes are properties carried by the same object class, $\backslash mu\backslash leftrightarrow\; \backslash nu$ reflects that equivalence relation.

All attributes in $[X]\_F$ must be mutually implied, which can be implemented, e.g., by $\backslash forall\; \backslash mu\backslash in\; [X]\_F\backslash \; \backslash mu\backslash rightarrow\; \backslash eta(X)$ (in fact, $\backslash mu\backslash leftrightarrow\; \backslash eta(X)$ where $\backslash eta(X)\backslash rightarrow$

\mu is a tautology), i.e., all attributes are equivalent to the lower bound of intent.

Extraction of the implications of type $A\backslash stackrel\{\backslash scriptscriptstyle\; fcl\}\{\backslash rightarrow\}\; B$ from the formal context was known to be complicated,{{Cite journal |last1=Kuznetsov |first1=Sergei O. |last2=Obiedkov |first2=Sergei |date=2008-06-06 |title=Some decision and counting problems of the Duquenne–Guigues basis of implications |journal=Discrete Applied Mathematics |series=In Memory of Leonid Khachiyan (1952–2005 ) |volume=156 |issue=11 |pages=1994–2003 |doi=10.1016/j.dam.2007.04.014 |issn=0166-218X |doi-access=free }}{{Cite book |last=Sertkaya |first=Barış |date=2009 |editor-last=Rudolph |editor-first=Sebastian |editor2-last=Dau |editor2-first=Frithjof |editor3-last=Kuznetsov |editor3-first=Sergei O. |chapter=Towards the Complexity of Recognizing Pseudo-intents |chapter-url=https://link.springer.com/chapter/10.1007/978-3-642-03079-6_22 |journal=Conceptual Structures: Leveraging Semantic Technologies |series=Lecture Notes in Computer Science |volume=5662 |language=en |location=Berlin, Heidelberg |publisher=Springer |pages=284–292 |doi=10.1007/978-3-642-03079-6_22 |isbn=978-3-642-03079-6 |title=Archived copy |access-date=2023-09-04 |archive-date=2023-09-04 |archive-url=https://web.archive.org/web/20230904125549/https://link.springer.com/chapter/10.1007/978-3-642-03079-6_22 |url-status=live }}{{Cite book |last=Distel |first=Felix |date=2010 |editor-last=Kwuida |editor-first=Léonard |editor2-last=Sertkaya |editor2-first=Barış |chapter=Hardness of Enumerating Pseudo-intents in the Lectic Order |chapter-url=https://link.springer.com/chapter/10.1007/978-3-642-11928-6_9 |journal=Formal Concept Analysis |series=Lecture Notes in Computer Science |volume=5986 |language=en |location=Berlin, Heidelberg |publisher=Springer |pages=124–137 |doi=10.1007/978-3-642-11928-6_9 |isbn=978-3-642-11928-6 |title=Archived copy |access-date=2023-09-04 |archive-date=2023-09-04 |archive-url=https://web.archive.org/web/20230904125546/https://link.springer.com/chapter/10.1007/978-3-642-11928-6_9 |url-status=live }}{{Cite journal |last1=Distel |first1=Felix |last2=Sertkaya |first2=Barış |date=2011-03-28 |title=On the complexity of enumerating pseudo-intents |url=https://www.sciencedirect.com/science/article/pii/S0166218X10004105 |journal=Discrete Applied Mathematics |volume=159 |issue=6 |pages=450–466 |doi=10.1016/j.dam.2010.12.004 |s2cid=17769297 |issn=0166-218X |access-date=2023-09-04 |archive-date=2023-09-04 |archive-url=https://web.archive.org/web/20230904125545/https://www.sciencedirect.com/science/article/pii/S0166218X10004105 |url-status=live }}{{Cite journal |last1=Babin |first1=Mikhail A. |last2=Kuznetsov |first2=Sergei O. |date=2013-04-01 |title=Computing premises of a minimal cover of functional dependencies is intractable |journal=Discrete Applied Mathematics |volume=161 |issue=6 |pages=742–749 |doi=10.1016/j.dam.2012.10.026 |issn=0166-218X |doi-access=free }} it necessitates efforts for constructing a canonical basis, which does not apply to the implications of type $A\backslash stackrel\{\backslash scriptscriptstyle\; rsl\}\{\backslash rightarrow\}\; B$. By contrast, the above equivalence only proposes

• the {{Anchor|uf}}single formula generating all the informative implications:

$\backslash forall\; \backslash mu\; \backslash in\; M^\backslash ast\backslash \; \backslash mu\backslash rightarrow\; \backslash mu\backslash cdot\; 1\_\backslash eta$, which can be restated as $\backslash forall\; \backslash mu\; \backslash in\; M^\backslash ast\backslash \; \backslash mu+0\_\backslash rho\backslash rightarrow\; \backslash mu$,

• {{Anchor|auxf}}as an auxiliary formula,

$\backslash mu\_1\backslash rightarrow\; \backslash mu\_2$ is allowed by the formal context iff $\backslash mu\_1\backslash cdot\; 1\_\backslash eta\; \backslash leq\; \backslash mu\_2\backslash cdot\; 1\_\backslash eta$ (or $\backslash mu\_1+\; 0\_\backslash rho\; \backslash leq\; \backslash mu\_2+\; 0\_\backslash rho$).

Hence, purely algebraic formulae can be employed to determine the implication relations, one need not consult the object-attribute dependence in the formal context, which is the typical effort in finding the canonical basis. {{Anchor|cntxtul}}

Remarkably, $1\_\backslash eta$ and $0\_\backslash rho$ are referred to as the contextual truth and falsity, respectively. $\backslash forall\; X\; \backslash in\; E\_F$

$0\_\backslash rho+\backslash rho(X)=\backslash rho(X)$

and $0\_\backslash rho\backslash cdot\backslash rho(X)=0\_\backslash rho$

as well as $1\_\backslash eta\backslash cdot\; \backslash eta(X)=\backslash eta(X)$

and $1\_\backslash eta+\; \backslash eta(X)=1\_\backslash eta$

similar to the conventional truth 1 and falsity 0 that can be identified with $\backslash rho(G)$ and $\backslash eta(\backslash emptyset)$, respectively.

$A\backslash stackrel\{\backslash scriptscriptstyle\; fcl\}\{\backslash rightarrow\}\; B$ and $A\backslash stackrel\{\backslash scriptscriptstyle\; rsl\}\{\backslash rightarrow\}\; B$ are found to be particular forms of $\backslash mu\_1\backslash rightarrow\; \backslash mu\_2$. Assume $A=\backslash \{a\_1,a\_2,\backslash ldots\backslash \}\backslash subseteq\; M$ and $B=\backslash \{b\_1,b\_2,\backslash ldots\backslash \}\backslash subseteq\; M$ for both cases. By $A\backslash stackrel\{\backslash scriptscriptstyle\; fcl\}\{\backslash rightarrow\}\; B$, an object set carrying all the attributes in $A$ implies carrying all the attributes in $B$ simultaneously, i.e. $\backslash prod\_i\; a\_i\backslash rightarrow\; \backslash prod\_i\; b\_i$. By $A\backslash stackrel\{\backslash scriptscriptstyle\; rsl\}\{\backslash rightarrow\}\; B$, an object set carrying any of the attributes in $A$ implies carrying some of the attributes in $B$, therefore $\backslash sum\_i\; a\_i\backslash rightarrow\; \backslash sum\_i\; b\_i$. Notably, the point of view conjunction-to-conjunction has also been emphasised by Ganter while dealing with the attribute exploration.

One could overlook significant parts of the logic content in formal context were it not for the consideration based on the GCL. Here, the formal context describing 3BS given in Table 1 suggests an extreme case where no implication of the type $A\backslash stackrel\{\backslash scriptscriptstyle\; rsl\}\{\backslash rightarrow\}\; B$ could be found. Nevertheless, one ends up, e.g., $\backslash \{a,b\backslash \}\backslash stackrel\{\backslash scriptscriptstyle\; fcl\}\{\backslash rightarrow\}\; \backslash \{a,b,c\; \backslash \}$ (or $\backslash \{a,b\backslash \}\backslash stackrel\{\backslash scriptscriptstyle\; fcl\}\{\backslash rightarrow\}\; \backslash \{c\; \backslash \}$), whose meaning appears to be ambiguous. Though it is true that $ab\; \backslash rightarrow\; abc$, one also notices that $(ab)^R=\backslash \{a,b\backslash \}^I=\backslash emptyset$ as well as $(abc)^R=\backslash \{a,b,c\backslash \}^I$ $=\; \backslash emptyset$. Indeed, by using the above formula with the $1\_\backslash eta$

provided in Fig. 2 it can be seen that $ab\backslash cdot\; 1\_\backslash eta\backslash equiv\; \{\backslash bf\; 0\}$ $\backslash equiv\; abc\backslash cdot\; 1\_\backslash eta$, hence it is $ab\; \backslash leftrightarrow\; \{\backslash bf\; 0\}$ and $abc\; \backslash leftrightarrow\; \{\backslash bf\; 0\}$ that underlies $ab\; \backslash rightarrow\; abc$.

Remarkably, the same formula will lead to (1) $a\backslash rightarrow\; a\backslash neg\; b\backslash neg\; c$ (or $a\; \backslash rightarrow\; \backslash neg\; b\backslash neg\; c$) and (2) $\backslash neg\; b\backslash neg\; c\backslash rightarrow\; \backslash neg\; b\backslash neg\; ca$ (or $\backslash neg\; b\backslash neg\; c\backslash rightarrow\; a$), where $a$, $b$ and $c$ can be interchanged. Hence, what one has captured from the 3BS are that (1) no two colours could coexist and that (2) there is no colour other than $a$, $b$ and $c$. The two issues are certainly less trivial in the scopes of $A\backslash stackrel\{\backslash scriptscriptstyle\; fcl\}\{\backslash rightarrow\}\; B$ and $A\backslash stackrel\{\backslash scriptscriptstyle\; rsl\}\{\backslash rightarrow\}\; B$.

The rules to assemble or transform implications of type $\backslash mu\backslash rightarrow\; \backslash nu$ are of direct consequences of object set inclusion relations. Notably, some of these rules can be reduced to the Armstrong axioms, which pertain to the main considerations of Guigues and Duquenne based on the non-redundant collection of informative implications acquired via FCL. In particular,

(1) $\backslash mu\_1\backslash rightarrow\; \backslash mu\_2$ and $\backslash nu\_1\backslash rightarrow\; \backslash nu\_2$ $\backslash implies$ $\backslash mu\_1\backslash cdot\backslash nu\_1\backslash rightarrow\; \backslash mu\_2\backslash cdot\backslash nu\_2$

since $\backslash mu\_1^R\backslash subseteq\; \backslash mu\_2^R$ and $\backslash nu\_1^R\backslash subseteq\; \backslash nu\_2^R$ leads to $\backslash mu\_1^R\backslash cap\backslash nu\_1^R\backslash subseteq\; \backslash mu\_2^R\backslash cap\backslash nu\_2^R$, i.e., $(\backslash mu\_1\backslash cdot\; \backslash nu\_1)^R\backslash subseteq\; (\backslash mu\_2\backslash cdot\backslash nu\_2)^R$.

In the case of $\backslash mu\_1=\backslash prod\; A\_1$, $\backslash nu\_1=\backslash prod\; B\_1$, $\backslash mu\_2=\backslash prod\; A\_2$ and $\backslash nu\_2=\backslash prod\; B\_2$, where $A\_1,A\_2,B\_1,B\_2$ are sets of attributes, the rule (1) can be re-expressed as Armstrong's composition:

(1') $A\_1\backslash stackrel\{\backslash scriptscriptstyle\; fcl\}\{\backslash rightarrow\}\; A\_2$ and $B\_1\backslash stackrel\{\backslash scriptscriptstyle\; fcl\}\{\backslash rightarrow\}\; B\_2$$\backslash implies$ $A\_1\backslash cup\; B\_1\backslash stackrel\{\backslash scriptscriptstyle\; fcl\}\{\backslash rightarrow\}\; A\_2\backslash cup\; B\_2$

$\backslash because\; (\backslash prod\; A\_1)\backslash cdot\; (\; \backslash prod\; B\_1)\backslash equiv\; \backslash prod\; (A\_1\backslash cup\; B\_1)$ and $(\backslash prod\; A\_2)\backslash cdot\; (\; \backslash prod\; B\_2)\backslash equiv\; \backslash prod\; (A\_2\backslash cup\; B\_2)$.

The Armstrong axioms are not suited for $A\backslash stackrel\{\backslash scriptscriptstyle\; rsl\}\{\backslash rightarrow\}\; B$ which requires $A\backslash subseteq\; B$. This is in contrast to $A\backslash stackrel\{\backslash scriptscriptstyle\; fcl\}\{\backslash rightarrow\}\; B$ for which Armstrong's reflexivity is implemented by $A\backslash supseteq\; B$. Nevertheless, a similar composition may occur but signify a different rule from (1). Note that one also arrives at

(2) $(\backslash mu\_1\backslash rightarrow\; \backslash mu\_2)$ and $(\backslash nu\_1\backslash rightarrow\; \backslash nu\_2)$ $\backslash implies$ $(\backslash mu\_1+\backslash nu\_1\backslash rightarrow\; \backslash mu\_2+\backslash nu\_2)$

since $\backslash mu\_1^R\backslash subseteq\; \backslash mu\_2^R$ and $\backslash nu\_1^R\backslash subseteq\; \backslash nu\_2^R$ $\backslash implies$ $(\backslash mu\_1+\backslash nu\_1)^R\backslash subseteq\; (\backslash mu\_2+\backslash nu\_2)^R$, which gives rise to

(2') $A\_1\; \backslash stackrel\{\backslash scriptscriptstyle\; rsl\}\{\backslash rightarrow\}\; A\_2$ and $B\_1\backslash stackrel\{\backslash scriptscriptstyle\; rsl\}\{\backslash rightarrow\}\; B\_2$ $\backslash implies$$A\_1\backslash cup\; A\_2\backslash stackrel\{\backslash scriptscriptstyle\; rsl\}\{\backslash rightarrow\}\; B\_1\backslash cup\; B\_2$ whenever $\backslash mu\_1=\backslash sum\; A\_1$, $\backslash nu\_1=\backslash sum\; B\_1$, $\backslash mu\_2=\backslash sum\; A\_2$ and $\backslash nu\_2=\backslash sum\; B\_2$.

For concreteness, consider the example depicted by Table 2, which has been originally adopted for clarification of the RSL but worked out for the GCL.

|

! colspan="5" |$F(G,M)$

! colspan="6" |$2^\{2^5\}-5\; \backslash mbox\{\; more\; columns\}$

|-

!{{diagonal split header|$G$|$M^\backslash ast$}}

!$a$

!$b$

!$c$

!$d$

!$e$

!$\backslash neg\; a+b$

!$\backslash neg\; b$

!$a+\backslash neg\; c+d\backslash neg\; e$

!$\backslash ldots$

!$\{\backslash quad\; \}$

!$\backslash ldots$

|-

!1

!$\backslash times$

!

!$\backslash times$

!$\backslash times$

!$\backslash times$

!

!$\backslash times$

!$\backslash times$

!

!

!

|-

!2

!$\backslash times$

!

!$\backslash times$

!

!

!

!$\backslash times$

!$\backslash times$

!

!

!

|-

!3

!

!$\backslash times$

!

!

!$\backslash times$

!$\backslash times$

!

!$\backslash times$

!

!

!

|-

!4

!

!$\backslash times$

!

!

!$\backslash times$

!$\backslash times$

!

!$\backslash times$

!

!

!

|-

!5

!$\backslash times$

!

!

!

!

!

!$\backslash times$

!$\backslash times$

!

!

!

|-

!6

!$\backslash times$

!$\backslash times$

!

!

!$\backslash times$

!$\backslash times$

!

!$\backslash times$

!

!

!

|}

• The determinations of the nodes of GCL for Table 2 are straightforward, as is depicted in Fig.4. For example, one may read out {{Anchor|fig4}}File:ReadoutGCL.pdf

$\backslash eta(\backslash \{2,5\backslash \})$ $=\backslash eta(D\_2\backslash cup\; D\_4)$$=\backslash eta(D\_2)+\backslash eta(D\_4)$$=\backslash eta(\backslash \{2\backslash \})+\backslash eta(\backslash \{5\backslash \})$$=a\backslash neg\; bc\backslash neg\; d\backslash neg\; e+a\backslash neg\; b\backslash neg\; c\backslash neg\; d\backslash neg\; e$$=a\backslash neg\; b\backslash neg\; d\backslash neg\; e$,

$\backslash rho(\backslash \{2,5\backslash \})=\backslash neg\; \backslash eta(\backslash \{1,3,4,6\backslash \})$

$=(\backslash neg\; a+b+\backslash neg\; c+\backslash neg\; d+\backslash neg\; e)$$(\backslash neg\; b+c+d+\backslash neg\; e)$,

$\backslash eta(\backslash \{3,4\backslash \})$

$=\backslash eta(D\_3)$

$=\backslash neg\; ab\backslash neg\; c\backslash neg\; de$

, and so forth.

Clearly, one may also check that $\backslash rho(\backslash \{2,5\backslash \})=\backslash neg\; \backslash eta(\backslash \{1,3,4,6\backslash \})=\backslash eta(\backslash \{2,5\backslash \})+0\_\backslash rho$

.

• To rediscover the original FCL and RSL see Fig. 5. Observe, e.g.,

$\backslash eta(\backslash \{1,2,5,6\backslash \})=a\backslash neg\; bcde$$+a\backslash neg\; bc\backslash neg\; d\backslash neg\; e$$+a\backslash neg\; b\backslash neg\; c\backslash neg\; d\backslash neg\; e$$+ab\backslash neg\; c\backslash neg\; de$ $=\; a(\backslash neg\; b+e)$$(\backslash neg\; d+e)$

$(\backslash neg\; b+\backslash neg\; c)$$(\backslash neg\; b+\backslash neg\; d)$$(b+c+\backslash neg\; e)$$(c+\backslash neg\; d)$$(b+d+\backslash neg\; e)$$(\backslash neg\; c+d+\backslash neg\; e)$,

$\backslash rho(\backslash \{1,2,5,6\backslash \})$$=a$$+\backslash neg\; b$$+c$$+d$$+\backslash neg\; e$

$=\backslash neg\backslash eta(\backslash \{3,4\backslash \})$

.

Within the expression of $\backslash eta(\backslash \{1,2,5,6\backslash \})$ it can be seen that $\{a\}^R=\backslash lbrace\; a\; \backslash rbrace^I$$=\backslash lbrace\; 1,2,5,6\; \backslash rbrace$, while within $\backslash rho(\backslash \{1,2,5,6\backslash \})$ it can be seen $(\; a+\; c+d\; )^R$$=\backslash lbrace\; \{a,c,d\}\; \backslash rbrace^\backslash Diamond$$=\backslash lbrace\; 1,2,5,6\; \backslash rbrace$. Therefore, one finds out the concepts $(\backslash lbrace\; 1,2,5,6\; \backslash rbrace,\backslash lbrace\; a\backslash rbrace)$ for FCL and $(\backslash lbrace\; 1,2,5,6\; \backslash rbrace,\backslash lbrace\; a,c,d\backslash rbrace)$ for RSL. By contrast,

$\backslash eta(\backslash \{1,6\; \backslash \})$ $=ae(\backslash neg\; bcd+b\backslash neg\; c\backslash neg\; d)$, $\backslash rho(\backslash lbrace\; 1,6\; \backslash rbrace)=$

{d}+ab+ce$+\backslash neg\; be$$+\backslash neg\; a\backslash neg\; e$

with $(ae)^R=\backslash \{a,e\backslash \}^I$ $=\backslash \{\; 1,6\backslash \}$ gives rise to the concept $(\backslash lbrace\; 1,6\; \backslash rbrace,\backslash lbrace\; a,e\backslash rbrace)$ for FCL however fails to provide an extent for RSL because $d^R\backslash equiv\; \backslash lbrace\; d\backslash rbrace^\backslash Diamond=$

\lbrace 1\rbrace\neq \lbrace 1,6\rbrace.{{Anchor|fig5}}

• The meanings of $A\backslash stackrel\{\backslash scriptscriptstyle\; fcl\}\{\backslash rightarrow\}\; B$ and $A\backslash stackrel\{\backslash scriptscriptstyle\; rsl\}\{\backslash rightarrow\}\; B$ are essentially different.

$\backslash \{c,\; d\backslash \}\backslash stackrel\{\backslash scriptscriptstyle\; fcl\}\{\backslash rightarrow\}\; \backslash \{a\backslash \}$ and $\backslash \{c,d\; \backslash \}\backslash stackrel\{\backslash scriptscriptstyle\; rsl\}\{\backslash rightarrow\}\; \backslash \{a\backslash \}$ denote $c\backslash cdot\; d\backslash rightarrow\; a$ and $c+d\backslash rightarrow\; a$, respectively.

For the present case, the above relations can be examined via the auxiliary formula:

$c\backslash cdot\; d\backslash cdot\; 1\_\backslash eta\; \backslash leq\; a\backslash cdot\; 1\_\backslash eta$ (or $c\backslash cdot\; d+\; 0\_\backslash rho\; \backslash leq\; a+\; 0\_\backslash rho$), $(c+d)\backslash cdot\; 1\_\backslash eta\; \backslash leq\; a\backslash cdot\; 1\_\backslash eta$ (or $c+\; d+0\_\backslash rho\; \backslash leq\; a+\; 0\_\backslash rho$).

• $A\backslash stackrel\{\backslash scriptscriptstyle\; fcl\}\{\backslash rightarrow\}\; B$ and $A\backslash stackrel\{\backslash scriptscriptstyle\; rsl\}\{\backslash rightarrow\}\; B$ are equivalent when both $A\backslash mbox\{\; and\; \}B$ are reduced to sets of single element.

Both $\backslash \{c\; \backslash \}\backslash stackrel\{\backslash scriptscriptstyle\; fcl\}\{\backslash rightarrow\}\; \backslash \{a\backslash \}$ and $\backslash \{c\; \backslash \}\backslash stackrel\{\backslash scriptscriptstyle\; rsl\}\{\backslash rightarrow\}\; \backslash \{a\backslash \}$, according to the formal context of Table 2, are interpreted as $c\backslash rightarrow\; a$, which means $\backslash \{c\; \backslash \}\backslash stackrel\{\backslash scriptscriptstyle\; fcl\}\{\backslash rightarrow\}\; \backslash \{a\backslash \}$ based on $\backslash \{c\backslash \}^I\backslash subset\; \backslash \{a\backslash \}^I$and $\backslash \{c\; \backslash \}\backslash stackrel\{\backslash scriptscriptstyle\; rsl\}\{\backslash rightarrow\}\; \backslash \{a\backslash \}$ based on $\backslash \{c\backslash \}^\backslash Diamond\backslash subset\; \backslash \{a\backslash \}^\backslash Diamond$.

Note that $c^R=\backslash \{c\backslash \}^I=\backslash \{c\backslash \}^\backslash Diamond$$=\backslash \{1,2\backslash \}$ $\backslash subset\; \backslash \{1,2,5,6\backslash \}$$=a^R$$=\backslash \{a\backslash \}^I$$=\backslash \{a\backslash \}^\backslash Diamond$. Moreover, $c\backslash rightarrow\; a$ entails both $c\backslash rightarrow\; c\backslash cdot\; a$ and $c+a\backslash rightarrow\; a$, which correspond to $\backslash \{c\backslash \}\backslash stackrel\{\backslash scriptscriptstyle\; fcl\}\{\backslash rightarrow\}\; \backslash \{a,c\backslash \}$ and $\backslash \{c,a\backslash \}\backslash stackrel\{\backslash scriptscriptstyle\; rsl\}\{\backslash rightarrow\}\; \backslash \{a\backslash \}$, respectively.

• The single formula suffices to generate all the informative implications, where one may choose any attribute in $M^\backslash ast$ as the antecedent or consequent.

(1) With $\backslash mu\backslash rightarrow\; \backslash mu\backslash cdot\; 1\_\backslash eta$ one may infer the properties of objects of interest from the condition $1\_\backslash eta$ by specifying $\backslash mu$, thereby incorporating abundant informative implications as equivalent relations between any pair of attributes within the interval $[\backslash mu\; \backslash cdot\; 1\_\backslash eta,\backslash mu]$, i.e., $\backslash forall\; \backslash mu\_1\backslash forall\backslash mu\_2$ $\backslash mu\_1\backslash leftrightarrow\; \backslash mu\_2$ if $\backslash mu\; \backslash cdot\; 1\_\backslash eta\backslash leq\; \backslash mu\_1\; \backslash leq\; \backslash mu$ and $\backslash mu\; \backslash cdot\; 1\_\backslash eta\backslash leq\; \backslash mu\_2\backslash leq\; \backslash mu$. Note that $\backslash mu\backslash rightarrow\; \backslash mu\backslash cdot\; 1\_\backslash eta$ entails $\backslash mu\; \backslash leftrightarrow\; \backslash mu\backslash cdot\; 1\_\backslash eta$ since $\backslash mu\backslash cdot\; 1\_\backslash eta\; \backslash leq\; \backslash mu$.

For instance, by $(c+d)\backslash cdot\; 1\_\backslash eta$ $=c\backslash cdot\; 1\_\backslash eta$ $=a\backslash neg\; bc(de+\backslash neg\; d\backslash neg\; e)$ the relation $c+d$ $\backslash rightarrow\; a\backslash neg\; bc(de+\backslash neg\; d\backslash neg\; e)$ is neither of the type $A\backslash stackrel\{\backslash scriptscriptstyle\; fcl\}\{\backslash rightarrow\}\; B$ nor of the type $A\backslash stackrel\{\backslash scriptscriptstyle\; rsl\}\{\backslash rightarrow\}\; B$. Nevertheless, one may also derive, e.g., $c+d\backslash rightarrow\; c$, $c+d\backslash rightarrow\; a$ and $cd\backslash rightarrow\; a$, which are $\backslash \{\; c,\; d\; \backslash \}\backslash stackrel\{\backslash scriptscriptstyle\; rsl\}\{\backslash rightarrow\}\; \backslash \{\; c\; \backslash \}$, $\backslash \{c,\; d\backslash \}\backslash stackrel\{\backslash scriptscriptstyle\; rsl\}\{\backslash rightarrow\}\; \backslash \{a\backslash \}$ and $\backslash \{c,\; d\backslash \}\backslash stackrel\{\backslash scriptscriptstyle\; fcl\}\{\backslash rightarrow\}\; \backslash \{a\backslash \}$, respectively. As a further interesting implication $c+d\; \backslash rightarrow\; \backslash neg\; b(de+\; \backslash neg\; d\backslash neg\; e)$ entails $c+d\; \backslash rightarrow\; \backslash neg\; b\; \backslash cdot\; (\; e\; \backslash leftrightarrow\; d\; )$ by means of material implication. Namely, for the objects carrying the property $c$ or $d$, $\backslash neg\; b$ must hold and, in addition, objects carrying the property $e$ must also carry the property $d$ and vice versa.

(1') Alternatively, the equivalent formula $\backslash mu+0\_\backslash rho\backslash rightarrow\; \backslash mu$ can be employed to specify the objects of particular interest. In effect, $\backslash forall\; \backslash mu\_1\backslash forall\backslash mu\_2$ $\backslash mu\_1\backslash leftrightarrow\; \backslash mu\_2$ if $\backslash mu\; \backslash leq\; \backslash mu\_1\; \backslash leq\; \backslash mu+0\_\backslash rho$ and $\backslash mu\; \backslash leq\; \backslash mu\_2\; \backslash leq\; \backslash mu+0\_\backslash rho$.

One may be interested in the properties inferring a particular consequent, say, $e\backslash rightarrow\; a$. Consider $\backslash mu:=\backslash neg\; e+a$ $\backslash iff\; e\backslash rightarrow\; a$ giving rise to $\backslash mu+\; 0\_\backslash rho$ $=a+\backslash neg\; b+c+d+\backslash neg\; e$ according to Table 2. Clearly, with $\backslash neg\; e+a$ $\backslash leq\; \backslash mu\_1$$\backslash leq\; a+\backslash neg\; b+c+d+\backslash neg\; e$ one has $\backslash mu\_1\; \backslash leftrightarrow\; (\; e\; \backslash rightarrow\; a\; )$. This gives rise to many possible antecedents such as $(e\backslash rightarrow\; a+c+d)\; \backslash rightarrow\; (e\backslash rightarrow\; a)$, $(b\backslash rightarrow\; (e\backslash rightarrow\; a+c\; ))\; \backslash rightarrow\; (e\backslash rightarrow\; a)$, $(e\backslash rightarrow\; (b\; \backslash rightarrow\; a+c\; ))\; \backslash rightarrow\; (e\backslash rightarrow\; a)$, $(b\backslash rightarrow\; (e\backslash rightarrow\; a+c+d))\; \backslash rightarrow\; (e\backslash rightarrow\; a)$ and so forth.

(2) $1\_\backslash eta$ governs all the implications extractable from the formal context by means of (1) and (1'). Indeed, it plays the role of canonical basis with one single implication relation.

$1\_\backslash eta$ can be understood as $\{\backslash bf\; 1\}\backslash rightarrow\; 1\_\backslash eta$ or equivalently $0\_\backslash rho\backslash rightarrow\; \{\backslash bf\; 0\}$, which turns out be the only non-redundant implication one needs to deduce all the informative implications from any formal context. The basis $\{\backslash bf\; 1\}\backslash rightarrow\; 1\_\backslash eta$ or $0\_\backslash rho\backslash rightarrow\; \{\backslash bf\; 0\}$ suffices the deduction of all implications as follows. While $\backslash forall\; \backslash mu$ $\{\backslash bf\; 1\}\backslash rightarrow\; 1\_\backslash eta$$\backslash implies\; \backslash mu\; \backslash rightarrow\; \backslash mu\; 1\_\backslash eta$ and $\backslash forall\; \backslash nu$ $0\_\backslash rho\backslash rightarrow\; \{\backslash bf\; 0\}$$\backslash implies\; \backslash nu+0\_\backslash rho\; \backslash rightarrow\; \backslash nu$, choosing either $\backslash mu=\backslash rho(X)$ or $\backslash nu=\backslash eta(X)$ gives rise to $\backslash rho(X)\backslash rightarrow\; \backslash eta(X)$. Notably, this encompasses (1) and (1') by means of $$

\mu\cdot 1_\eta\equiv

\eta(\mu^R) $$

\leq \mu $$

\leq \rho(\mu^R)\equiv \mu+0_\rho for any $\backslash mu$, where $\backslash mu^R$ can be identified with some $X$ corresponding to one of the 32 nodes on the GCL in Fig. 4.

$\backslash rho(X)\backslash rightarrow\; \backslash eta(X)$ develops equivalence, at each single node, for all attributes contained within the interval $[\; \backslash eta\; (X),\; \backslash rho(X)\; ]$. Moreover, informative implications could also relate different nodes via Hypothetical syllogism by invoking tautology. Typically, $\backslash forall\; \backslash mu\_1\backslash in\; [X\_1]\_F\backslash forall\backslash mu\_2\backslash in\; [X\_2]\_F$ $\backslash mu\_1\backslash rightarrow\backslash mu\_2$ whenever $(\; X\_1,[X\_1]\_F)$ $\backslash leq\; (\; X\_2,[X\_2]\_F)$. This corresponds to the cases considered in (1'): $(b\backslash rightarrow\; c)\; \backslash rightarrow\; (e\backslash rightarrow\; a)$, $c\; \backslash rightarrow\; (e\backslash rightarrow\; a)$, $\backslash neg\; b\; \backslash rightarrow\; (e\backslash rightarrow\; a)$ etc. Explicitly, $(\; b\backslash rightarrow\; c\; )\backslash rightarrow\; (e\backslash rightarrow\; a)$ is based upon $\backslash neg\; b+c\backslash in\; [\backslash \{1,2,5\backslash \}]\_F$ and $\backslash neg\; e+a\backslash in\; [\backslash \{1,2,5,6\backslash \}]\_F$ where $\backslash \{1,2,5\backslash \}\backslash subseteq\backslash \{1,2,5,6\backslash \}$. Note that $\backslash neg\; b\; +c\backslash leftrightarrow\; \backslash rho(\backslash \{1,2,5\backslash \})$$\backslash leftrightarrow\; \backslash eta\; (\backslash \{1,2,5\backslash \})$ and $\backslash neg\; e+a\backslash leftrightarrow\; \backslash rho(\backslash \{1,2,5,6\backslash \})$$$

\leftrightarrow \eta (\{ 1,2,5,6 \}) while $\backslash rho(\backslash \{1,2,5\backslash \})$$\backslash leq\; \backslash rho\; (\backslash \{1,2,5,6\backslash \})$ (also $\backslash eta(\backslash \{\; 1,2,5\; \backslash \})\; \backslash leq\; \backslash eta(\backslash \{\; 1,2,5,6\; \backslash \})$). Therefore, $(\; b\backslash rightarrow\; c\; )\backslash rightarrow\; (e\backslash rightarrow\; a)$. Similarly, $c\backslash in\; [\backslash \{1,2\backslash \}]\_F$ with $\backslash \{1,2\backslash \}\; \backslash subseteq\backslash \{1,2,5,6\backslash \}$ gives $c\; \backslash rightarrow\; (e\backslash rightarrow\; a)$.

Indeed, $\{\backslash bf\; 1\}\backslash rightarrow\; 1\_\backslash eta$ or equivalently $0\_\backslash rho\backslash rightarrow\; \{\backslash bf\; 0\}$ plays the role of canonical basis with one single implication relation.

{{reflist}}

Category:Information science