Labelled Calculi for the Logics of Rough Concepts

Abstract

We introduce sound and complete labelled sequent calculi for the basic normal non-distributive modal logic $\textbf{L}$ and some of its axiomatic extensions, where the labels are atomic formulas of the first order language of enriched formal contexts, i.e., relational structures based on formal contexts which provide complete semantics for these logics. We also extend these calculi to provide a proof system for the logic of rough formal contexts.

1 Introduction

In structural proof theory, powerful solutions to the problem of introducing analytic calculi for large classes of normal modal logics hinge on incorporating information about the relational semantics of the given logics into the calculi. This strategy is prominently used in the design of labelled calculi [8, 13, 14], a proof-theoretic format using which, analytic calculi have been introduced for the axiomatic extensions of the basic normal modal logic defined by modal axioms corresponding to geometric implications in the first order language of Kripke frames.

Labelled calculi for classical modal logics manipulate sequents $\varGamma \vdash \varDelta$ such that $\varGamma$ and $\varDelta$ are multisets of atomic formulas xRy in the first order language of Kripke frames and labelled formulas x : A interpreted on Kripke frames as $x\Vdash A$, i.e. as the condition that the modal formula A be satisfied (or forced) at the state x of a given Kripke frame. The labelled calculus $\textbf{G3K}$ for the basic normal modal logic $\textbf{K}$ is obtained by expanding the propositional fragment of the Gentzen calculus $\textbf{G3c}$ with introduction rules for the modal operators obtained by reading off the interpretation clauses of $\Box$- and $\Diamond$-formulas on Kripke frames. Labelled calculi for axiomatic extensions of $\textbf{K}$ defined by Sahlqvist axioms (including the modal logics T, K4, KB, S4, B, S5) are obtained in [13] by augmenting $\textbf{G3K}$ with the rules generated by reading off the first order conditions on Kripke frames corresponding to the given axioms.

In the present paper, we extend the design principles for the generation of labelled calculi to normal non-distributive modal logics, a class of normal LE-logics (cf. [5]) the propositional fragment of which coincides with the logic of lattices in which the distributive laws are not necessarily valid. In [3, 4], non distributive modal logics are used as the underlying environment for an epistemic logic of categories and formal concepts, and in [2] as the logical environment of a theory unifying Formal Concept Analysis [9] and Rough Set Theory [15].

Specifically, making use of the fact that the basic normal non-distributive modal logic is sound and complete w.r.t. enriched formal contexts (i.e., relational structures based on formal contexts from FCA) [3, 4], and that modal axioms of a certain syntactic shape [5] define elementary (i.e. first order definable) subclasses of enriched formal contexts, we introduce relational labelled calculi for the basic non-distributive modal logic and some of its axiomatic extensions.

Moreover, we adapt and specialize these calculi for capturing the logic of relational structures of a related type, referred to as rough formal contexts, which were introduced by Kent in [11] as a formal environment for unifying Formal Concept Analysis and Rough Set Theory. In [10], a sound and complete axiomatization for the non-distributive modal logic of rough formal contexts was introduced by circumventing a technical difficulty which in the present paper is shown to be an impossibility, since two of the three first order conditions characterizing rough formal contexts turn out to be not modally definable in the modal signature which the general theory would associate with them (cf. Lemma 4). However, in the richer language of labelled calculi, these first order conditions can still be used to define structural rules which capture the axiomatization introduced in [10] for the logic of rough formal contexts.

Structure of the Paper. Section 2 recalls preliminaries on the logic of enriched and rough formal contexts, Sect. 3 presents a labelled calculus for the logic of enriched formal contexts and its extensions. Section 4 proves soundness and completeness results for the calculus for the logic of rough formal contexts. We conclude in Sect. 5.

2 Preliminaries

In the present section, we recall the definition and relational semantics of the basic normal non-distributive modal logic in the modal signature $\{\Box , \Diamond , {\rhd }\}$ and some of its axiomatic extensions. This logic and similar others have been studied in the context of a research program aimed at introducing the logical foundations of categorization theory [2,3,4]. In this context, $\Box c$ and $\Diamond c$ and ${\rhd } c$ can be given e.g. the epistemic interpretation of the categories of the objects which are certainly, possibly, and certainly not members of category c, respectively. Motivated by these ideas, in [6], possible interpretations of (modal) non-distributive logics are systematically discussed also in their connections with their classical interpretation.

2.1 Basic Normal Non-distributive Modal Logic and Some of Its Axiomatic Extensions

Let $\textsf{Prop}$ be a (countable or finite) set of atomic propositions. The language $\mathcal {L}$ is defined as follows:

$$\begin{aligned}\begin{gathered} \varphi {:}{=}\bot \mid \top \mid p \mid \varphi \wedge \varphi \mid \varphi \vee \varphi \mid \Box \varphi \mid \Diamond \varphi \mid {\rhd } \varphi , \end{gathered}\end{aligned}$$

where $p\in \textsf{Prop}$. The basic, or minimal normal $\mathcal {L}$-logic is a set $\textbf{L}$ of sequents $\varphi \vdash \psi$, with $\varphi ,\psi \in \mathcal {L}$, containing the following axioms:

and closed under the following inference rules:

An $\mathcal {L}$-logic is any extension of $\textbf{L}$ with $\mathcal {L}$-axioms $\varphi \vdash \psi$. In what follows, for any set $\varSigma$ of $\mathcal {L}$-axioms, we let $\textbf{L}.\varSigma$ denote the axiomatic extension of $\textbf{L}$ generated by $\varSigma$. Throughout the paper, we will consider all subsets $\varSigma$ of the set of axioms listed in the table below. Some of these axioms are well known from classical modal logic, and have also cropped up in [2] in the context of the definition of relational structures simultaneously generalizing Formal Concept Analysis and Rough Set Theory. In Proposition 1, we list their first-order correspondents w.r.t. the relational semantics discussed in the next section.

2.2 Relational Semantics of $\mathcal {L}$-logics

The present subsection collects notation, notions and facts from [2, 6]. For any binary relation $T\subseteq U\times V$, and any $U'\subseteq U$ and $V'\subseteq V$, we let $T^c$ denote the set-theoretic complement of T in $U\times V$, and

$$\begin{aligned} T^{(1)}[U']:=\{v\mid \forall u(u\in U'\Rightarrow uTv)\} \quad \quad T^{(0)}[V']:=\{u\mid \forall v(v\in V'\Rightarrow uTv) \}.\end{aligned}$$

(1)

Well known properties of this construction (cf. [7, Sections 7.22–7.29]) are stated in the following lemma.

Lemma 1

For any sets U, V, $U'$ and $V'$, and for any families of sets $\mathcal {V}$ and $\mathcal {U}$,  

• 1. $X_1\subseteq X_2\subseteq U$ implies $T^{(1)}[X_2]\subseteq T^{(1)}[X_1]$, and $Y_1\subseteq Y_2\subseteq V$ implies $T^{(0)}[Y_2]\subseteq T^{(0)}[Y_1]$.

• 2. $U'\subseteq T^{(0)}[V']$ iff $V'\subseteq T^{(1)}[U']$.

• 3. $U'\subseteq T^{(0)}[T^{(1)}[U']]$ and $V'\subseteq T^{(1)}[T^{(0)}[V']]$.

• 4. $T^{(1)}[U'] = T^{(1)}[T^{(0)}[T^{(1)}[U']]]$ and $T^{(0)}[V'] = T^{(0)}[T^{(1)}[T^{(0)}[V']]]$.

• 5. $T^{(0)}[\bigcup \mathcal {V}] = \bigcap _{V'\in \mathcal {V}}T^{(0)}[V']$ and $T^{(1)}[\bigcup \mathcal {U}] = \bigcap _{U'\in \mathcal {U}}T^{(1)}[U']$.

If $R\subseteq U \times V$, and $S \subseteq V \times W$, then the composition $R;S \subseteq U \times W$ is defined as follows:

$$\begin{aligned} u (R;S) w \quad \text {iff} \quad u \in R^{(0)}[S^{(0)}[w]] \quad \text {iff} \quad \forall v(v S w \Rightarrow u R v). \end{aligned}$$

In what follows, we fix two sets A and X, and use a, b (resp. x, y) for elements of A (resp. X), and $B, C, A_j$ (resp. $Y, W, X_j$) for subsets of A (resp. of X).

A polarity or formal context (cf. [9]) is a tuple $\mathbb {P} =(A,X,I)$, where A and X are sets, and $I \subseteq A \times X$ is a binary relation. In what follows, for any such polarity, we will let $J\subseteq X\times A$ be defined by the equivalence xJa iff aIx. Intuitively, formal contexts can be understood as abstract representations of databases [9], so that A represents a collection of objects, X a collection of features, and for any object a and feature x, the tuple (a, x) belongs to I exactly when object a has feature x.

As is well known, for every formal context $\mathbb {P} = (A, X, I)$, the pair of maps

$$\begin{aligned} (\cdot )^\uparrow : \mathcal {P}(A)\rightarrow \mathcal {P}(X)\quad \text{ and } \quad (\cdot )^\downarrow : \mathcal {P}(X)\rightarrow \mathcal {P}(A), \end{aligned}$$

respectively defined by the assignments $B^\uparrow : = I^{(1)}[B]$ and $Y^\downarrow : = I^{(0)}[Y]$, form a Galois connection (cf. Lemma 1.2), and hence induce the closure operators $(\cdot )^{\uparrow \downarrow }$ and $(\cdot )^{\downarrow \uparrow }$ on $\mathcal {P}(A)$ and on $\mathcal {P}(X)$ respectively.¹ The fixed points of these closure operators are referred to as Galois-stable sets. For a formal context $\mathbb {P}=(A,I,X)$, a formal concept of $\mathbb {P}$ is a tuple $c=(B,Y)$ such that $B\subseteq A$ and $Y\subseteq X$, and $B = Y^\downarrow$ and $Y = B^\uparrow$. The subset B (resp. Y) is referred to as the extension (resp. the intension) of c and is denoted by $[\![{c}]\!]$ (resp. $(\![{c}]\!)$). By Lemma 1.3, the sets B and Y are Galois-stable. It is well known (cf. [9]) that the set of formal concepts of a formal context $\mathbb {P}$, with the order defined by

$$ c_1 \le c_2 \quad \text {iff} \quad [\![{c_1}]\!] \subseteq [\![{c_2}]\!] \quad \text {iff} \quad (\![{c_2}]\!) \subseteq (\![{c_1}]\!),$$

forms a complete lattice, namely the concept lattice of $\mathbb {P}$, which we denote by $\mathbb {P}^+$.

For the language $\mathcal {L}$ defined in the previous section, an enriched formal $\mathcal {L}$-context is a tuple $\mathbb {F} =(\mathbb {P}, R_\Box , R_\Diamond , R_{\rhd })$, where $R_\Box \subseteq A \times X$ and $R_\Diamond \subseteq X \times A$ and $R_{\rhd }\subseteq A\times A$ are I-compatible relations, that is, for all $a,b \in A$, and all $x \in X$, the sets $R_\Box ^{(0)}[x]$, $R_\Box ^{(1)}[a]$, $R_\Diamond ^{(0)}[a]$, $R_\Diamond ^{(1)}[x]$, $R_\rhd ^{(0)}[b]$, $R_\rhd ^{(1)}[a]$ are Galois-stable in $\mathbb {P}$. As usual in modal logic, these relations can be interpreted in different ways, for instance as the epistemic attributions of features to objects by agents.

A valuation on such an $\mathbb {F}$ is a map $V:\textsf{Prop}\rightarrow \mathbb {P}^+$. For every $p\in \textsf{Prop}$, we let $[\![{p}]\!]: = [\![{V(p)}]\!]$ (resp. $(\![{p}]\!): = (\![{V(p)}]\!)$) denote the extension (resp. the intension) of the interpretation of p under V. A model is a tuple $\mathbb {M} = (\mathbb {F}, V)$ where $\mathbb {F} = (\mathbb {P}, R_{\Box }, R_{\Diamond }, R_{\rhd })$ is an enriched formal context and V is a valuation on $\mathbb {F}$. For every $\varphi \in \mathcal {L}$, the following ‘forcing’ relations can be recursively defined as follows:

As to the interpretation of modal formulas:

The definition above ensures that, for any $\mathcal {L}$-formula $\varphi$,

$$ \mathbb {M}, a \Vdash \varphi \, \text {iff}\, a\in [\![{\varphi }]\!]_{\mathbb {M}}, \quad \text {and} \quad \mathbb {M},x \succ \varphi \, \text {iff}\, x\in (\![{\varphi }]\!)_{\mathbb {M}}. $$

Finally, as to the interpretation of sequents:

$$ \mathbb {M}\models \varphi \vdash \psi \quad \text {iff} \quad [\![{\varphi }]\!]_{\mathbb {M}}\subseteq [\![{\psi }]\!]_{\mathbb {M}}\quad \text {iff} \quad (\![{\psi }]\!)_{\mathbb {M}}\subseteq (\![{\varphi }]\!)_{\mathbb {M}}. $$

A sequent $\varphi \vdash \psi$ is valid on an enriched formal context $\mathbb {F}$ (in symbols: $\mathbb {F}\models \varphi \vdash \psi$) if $\mathbb {M}\models \varphi \vdash \psi$ for every model $\mathbb {M}$ based on $\mathbb {F}$. The basic non-distributive logic $\textbf{L}$ is sound and complete w.r.t. the class of enriched formal contexts (cf. [2]).

Then, via a general canonicity result (cf. [5]), the following proposition (cf. [2, Proposition 4.3]) implies that, for any subset $\varSigma$ of the set of axioms at the end of Sect. 2.1, the logic $\textbf{L}.\varSigma$ is complete w.r.t. the class of enriched formal contexts defined by those first-order sentences in the statement of the proposition below corresponding to the axioms in $\varSigma$.

These first order sentences are compactly represented as inclusions of relations defined as follows. For any enriched formal context $\mathbb {F} = (\mathbb {P}, R_{\Box }, R_{\Diamond }, R_{\rhd } )$, the relations , $R_\blacksquare \subseteq A\times X$ and $R_{\blacktriangleright }\subseteq A\times A$ are defined by iff $aR_{\Box } x$, and $a R_\blacksquare x$ iff $x R_\Diamond a$, and $a R_{\blacktriangleright }b$ iff $bR_{\rhd }a$. Moreover, for all relations $R, S\subseteq A\times X$ we let $R; S\subseteq A\times X$ be defined² by a(R; S)x iff $a\in R^{(0)}[I^{(1)}[S^{(0)}[x]]]$, and for all relations $R, S\subseteq X\times A$ we let $R; S\subseteq X\times A$ be defined by x(R; S)a iff $x\in R^{(0)}[I^{(0)}[S^{(0)}[a]]]$.

Proposition 1

For any enriched formal context $\mathbb {F} = (\mathbb {P}, R_\Box , R_\Diamond , R_{\rhd })$:

The proposition above motivated the introduction of the notion of conceptual approximation space in [2], as a subclass of the enriched formal contexts modelling the ${\rhd }$-free fragment of the language $\mathcal {L}$. A conceptual approximation space is an enriched formal context $\mathbb {F} = (\mathbb {P}, R_\Box , R_\Diamond )$ verifying the first order sentence $R_{\Box };R_{\blacksquare } \subseteq I$. Such an $\mathbb {F}$ is reflexive if $R_\Box \subseteq I$ and $R_\Diamond \subseteq J$, is symmetric if or equivalently if $R_{\blacksquare } = R_{\Box }$, and is transitive if $R_{\Box }\subseteq R_{\Box }\, ; R_{\Box }$ and $R_{\Diamond }\subseteq R_{\Diamond }\, ; R_{\Diamond }$ (cf. [1, 2] for a discussion on terminology).

2.3 The Logic of Rough Formal Contexts

Examples of conceptual approximation spaces have cropped up in the context of Kent’s proposal for a simultaneous generalization of approximation spaces from RST and formal contexts from FCA [12]. Specifically, Kent introduced rough formal contexts as tuples $\mathbb {G} = (\mathbb {P}, E)$ such that $\mathbb {P} = (A, X, I)$ is a polarity, and $E\subseteq A\times A$ is an equivalence relation. The relation E induces two relations $R_\Box , S_{{\!\Box }}\subseteq A\times X$ defined as follows: for every $a\in A$ and $x\in X$,

$$ \begin{aligned} aR_\Box x \, \text{ iff } \, \exists b(aEb \, \& \, bIx) \quad \quad \quad \quad aS_{{\!\Box }}x \, \text{ iff } \, \forall b(aEb\Rightarrow bIx) \end{aligned}$$

(2)

The reflexivity of E implies that $S_{{\!\Box }}\subseteq I\subseteq R_\Box$; hence, $R_\Box$ and $S_{{\!\Box }}$ can respectively be regarded as the lax, or upper, and as the strict, or lower, approximation of I relative to E. For any rough formal context $\mathbb {G} = (\mathbb {P}, E)$, let be defined by the equivalence iff $aS_{{\!\Box }}x$,

Lemma 2

If $\mathbb {G} = (\mathbb {P}, E)$ is a rough formal context, then .

Proof

For any $a\in A$ and $x\in X$,

In [2, Section 5] and [10, Section 3], the logic of rough formal contexts was introduced, based on the theory of enriched formal contexts as models of non-distributive modal logics, the characterization results reported on in Proposition 1, and the following:

Lemma 3

([2, Lemma 5.3]) For any polarity $\mathbb {P} = (A, X, I)$, and any I-compatible relation $E\subseteq A\times A$ such that its associated $S_{{\!\Box }}\subseteq A\times X$ (defined as in (2)) is I-compatible,³

E is reflexive    iff    $S_{{\!\Box }}\subseteq I$;          and          E is transitive    iff    $S_{{\!\Box }}\subseteq S_{{\!\Box }}; S_{{\!\Box }}$.

These results imply that the characterizing properties of rough formal contexts can be taken as completely axiomatised in the modal language $\mathcal {L}$ via the following axioms:

$$ \Box \varphi \ \,{\vdash }\ \,\varphi \quad \quad \Box \varphi \ \,{\vdash }\ \,\Box \Box \varphi \quad \quad \varphi \ \,{\vdash }\ \,{\rhd }{\rhd }\varphi . $$

Clearly, any rough formal context $\mathbb {G} = (\mathbb {P}, E)$ such that E is I-compatible is an enriched formal $\mathcal {L}_{\rhd }$-context, where $\mathcal {L}_{\rhd }$ is the $\{\Box , \Diamond \}$-free fragment of $\mathcal {L}$. However, interestingly, it is impossible to capture the reflexivity and transitivity of E by means of $\mathcal {L}_{\rhd }$-axioms, as the next lemma shows:

Lemma 4

The class of enriched formal $\mathcal {L}_{\rhd }$-contexts $\mathbb {F} = (\mathbb {P}, R_\rhd )$ such that $R_\rhd \subseteq A\times A$ is reflexive (resp. transitive) is not modally definable in its associated language $\mathcal {L}_{\rhd }$.

Proof

Assume for contradiction that $\mathcal {L}_{\rhd }$-axioms $\varphi \ \,{\vdash }\ \,\psi$ and $\chi \ \,{\vdash }\ \,\xi$ exist such that $\mathbb {F}\models \varphi \ \,{\vdash }\ \,\psi$ iff $R_\rhd$ is reflexive, and $\mathbb {F}\models \chi \ \,{\vdash }\ \,\xi$ iff $R_\rhd$ is transitive for any enriched formal $\mathcal {L}_{\rhd }$-context $\mathbb {F}= (\mathbb {P}, R_\rhd )$. Then, these equivalences would hold in particular for those special formal $\mathcal {L}_{\rhd }$-contexts $\mathbb {F} = (\mathbb {P}_W, R_\rhd )$ such that $\mathbb {P}_W = (W_A, W_X, I_{\varDelta ^c})$ such that $W_A = W_X = W$ for some set W, and $aI_{\varDelta ^c} x$ iff $a\ne x$, and $R_{\rhd }: = H_{R^c}$ is defined as $a H_{R^c}b$ iff $(a, b)\notin R$ for some binary relation $R\subseteq W\times W$. By construction, letting $\mathbb {X} = (W, R)$, the following chain of equivalences holds: $\mathbb {F}\models \varphi \ \,{\vdash }\ \,\psi$ iff $[\![{\varphi }]\!]_V\subseteq [\![{\psi }]\!]_V$ for every valuation $V: \textsf{Prop}\rightarrow \mathbb {P}^+$. However, by construction, $\mathbb {P}^+\cong \mathcal {P}(W)$ (cf. [2, Proposition 3.4]). Moreover, the definition of the forcing relation $\Vdash$ on $\mathbb {F}$ implies that

$$\begin{aligned} \begin{array}{cll} [\![{{\rhd }\varphi }]\!] = R_{\rhd }^{(0)}[[\![{\varphi }]\!]] = H_{R^c}^{(0)}[[\![{\varphi }]\!]] &{} = &{} \{b\in W_A\mid \forall a(a\Vdash \varphi \Rightarrow aR^cb)\}\\ &{} = &{} \{b\in W_A\mid \forall a(aRb \Rightarrow a \not \Vdash \varphi )\} \\ \end{array} \end{aligned}$$

That is, restricted to the class of $\mathcal {L}_{\rhd }$-contexts which arise from classical Kripke frames $\mathbb {X} = (W, R)$ in the way indicated above, the interpretation of ${\rhd }$-formulas coincides with the interpretation of $\Box \lnot$-formulas in the language of classical modal logic, which induces a translation $\tau$, from $\mathcal {L}_{\rhd }$-formulas to formulas in the language of classical modal logic, which is preserved and reflected from the special formal $\mathcal {L}_{\rhd }$-contexts $\mathbb {F}$ to the Kripke frames with which they are associated. Therefore, by construction, for any Kripke frame $\mathbb {X} = (X, R)$, R is irreflexive iff $H_{R^c}$ is reflexive iff $\mathbb {F}\models \varphi \ \,{\vdash }\ \,\psi$ iff $\mathbb {X}\models \tau (\varphi )\vdash \tau (\psi )$, contradicting the well known fact that the class of Kripke frames $\mathbb {X} = (X, R)$ such that R is irreflexive is not modally definable.

Reasoning similarly, to show the statement concerning transitivity, it is enough to see that the class of Kripke frames $\mathbb {X} = (W, R)$ s.t. $R^c$ is transitive is not modally definable. Consider the Kripke frames $\mathbb {X}_i= (W_i, R_i)$ such that $W_i= \{a_i, b_i \}$, $R_i = \{(a_i,b_i) \}$, for $1\le i\le 2$. Clearly, $R_i^c$ is transitive in $\mathcal {F}_i$, so the two frames satisfy the property. However, their disjoint union , given by $W= \{a_1,b_1,a_2,b_2\}$ and $R =\{(a_1,b_1), (a_2,b_2)\}$, does not: indeed, $(a_1, a_2), (a_2, b_1)\in R^c$ but $(a_1,b_1)\notin R^c$. Hence, the statement follows from the Goldblatt-Thomason theorem for classical modal logic.

3 Relational Labelled Calculi for $\mathcal {L}$-logics

Below, p, q denote atomic propositions; a, b, c (resp. x, y, z) are labels corresponding to objects (resp. features). Given labels a, x and a modal formula A, well-formed formulas are of the type a : A and x :  : A, while $\varphi , \psi$ are meta-variables for well-formed formulas. Well-formed terms are of any of the following shapes: aIx, $aR_\Box x$, $x R_\Diamond a$, , , and $t_1 \Rightarrow t_2$, where $t_1$ is of any of the following shapes: $a R_\Box x$, , $y R_\Diamond a$, , $a R_\rhd b$, , and $t_2$ is of the form aIy. Relational terms $t_1 \Rightarrow t_2$ are interpreted as $\forall u (t_1 \rightarrow t_2)$ where u is the variable shared by $t_1$ and $t_2$. A sequent is an expression of the form $\varGamma \ \,{\vdash }\ \,\varDelta$, where $\varGamma , \varDelta$ are meta-variables for multisets of well-formed formulas or terms. For any labels u, v and relations R, S we write u(R; S)v as a shorthand for the term $w S v \Rightarrow u R w$.

3.1 Labelled Calculus $\mathbf {R.L}$ for the Basic $\mathcal {L}$-logic

Switch rules for $R_\blacksquare$, , and $R_\blacktriangleright$ are analogous to those for $R_\Box$, $R_\Diamond$, and $R_\rhd$. These rules encode the I-compatibility conditions of $R_\blacksquare$, ,$R_\blacktriangleright$,$R_\Box$, $R_\Diamond$, and $R_\rhd$ (cf. Remark 2).

For and and for all labels u, v, w of the form a or x, we have the following switch rules:

The rules above encode the definition of I-composition of relations on formal contexts [2, Definition 3.10].

Adjunction rules encode the fact that operators $\Diamond$ and , and $\Box$, and $\rhd$ and $\blacktriangleright$ constitute pairs of adjoint operators.

Logical rules encode the definition of satisfaction and refutation for propositional and modal connectives discussed in Sect. 2.2. The proof of their soundness in Appendix A shows how this encoding works.

3.2 Relational Calculi for the Axiomatic Extensions of the Basic $\mathcal {L}$-logic

The structural rule corresponding to each axiom listed in Table 1 is generated as the read-off of the first-order condition corresponding to the given axiom as listed in Proposition 1. For any nonempty subset $\varSigma$ of modal axioms as reported in Table 1, we let $\mathbf {R.L}\varSigma$ denote the extension of $\mathbf {R.L}$ with the corresponding rules.

Table 1. Modal axioms and their corresponding rules.

3.3 The Relational Calculus $\mathbf {R.L}\rho$ for the $\mathcal {L}$-logic of Rough Formal Contexts

The calculus $\mathbf {R.L}$ introduced in Sect. 3.1 can be specialized so as to capture the semantic environment of rough formal contexts by associating the connective $\Box$ (resp. ) with relational labels in which $S_{{\!\Box }}$ (resp. ) occurs, and adding rules encoding the reflexivity and the transitivity of E, rather than the (equivalent, cf. Lemma 3) first-order conditions on $S_{{\!\Box }}$. We need the following set of switching rules encoding the relation between E and I, and the I-compatibility of E and $S_{{\!\Box }}$ (and ).

4 Properties of $\mathbf {R.L}\rho$ and $\mathbf {R.L}\varSigma$

4.1 Soundness

Any sequent $\varGamma \ \,{\vdash }\ \,\varDelta$ is to be interpreted in any enriched formal $\mathcal {L}$-context $\mathbb {F} = (\mathbb {P}, R_\Box , R_\Diamond , R_\rhd )$ based on $\mathbb {P} = (A, X, I)$ in the following way: for any assignment $V:\textsf{Prop} \rightarrow \mathbb {P}^+$ that can be uniquely extended to an assignment on $\mathcal {L}$-formulas, and for any interpretation of labels $\alpha : \{a, b, c, \ldots \} \rightarrow A$ and $\chi : \{x, y, z, \ldots \} \rightarrow X$, we let $\iota _{(V, \alpha , \chi )}$ be the interpretation of well-formed formulas and well-formed terms indicated in the following table:

a : A	$\alpha (a)\in [\![{A}]\!]_V$	x :  : A	$\chi (x) \in (\![{A}]\!)_V$
$a R_\Box x$	$\alpha (a)R_\Box \chi (x)$	$a R_\blacksquare x$	$\alpha (a)R_\blacksquare \chi (x)$
$x R_\Diamond a$	$\chi (x)R_\Diamond \alpha (a)$
$a R_\rhd b$	$\alpha (a)R_\Diamond \alpha (b)$	$a R_\blacktriangleright b$
aIx	$\alpha (a)I\chi (x)$	$t_1(u) \Rightarrow t_2(u)$	$\forall u(\iota _{(V, \alpha , \chi )}(t_1(u)) \Rightarrow \iota _{(V, \alpha , \chi )}(t_2(u)))$

Under this interpretation, sequents $\varGamma \vdash \varDelta$ are interpreted as follows⁴:

In the following, we show the soundness of the interdefinability rules in R.L$\rho$, being the proof of soundness of the (pure structure) switch rules similar. The soundness of the rules for the basic calculus R.L is proved in Appendix A.

Remark 1

Given a polarity $\mathbb {P} = (A, X, I)$, $c \in \mathbb {P}^+$, and $B\subseteq A$, the condition

$$(\forall x \in X)(c \subseteq I^{(0)}[x] \Rightarrow B \subseteq I^{(0)}[x]),$$

can be rewritten using the defining properties of $\bigcap$ as the inclusion

$$B \subseteq \bigcap \left\{ I^{(0)}[x] \mid x \in X, c \subseteq I^{(0)}[x] \right\} ,$$

which, by Lemma 2, is equivalent to $B \subseteq c$.

Lemma 5

The rules swSf, swSfi, swSdf, swSdfi, swES, swESi, curryS, uncurryS, refl, sym, and trans are sound with respect to the class of rough formal contexts.

Proof

Under the assumption that E and $S_{{\!\Box }}$ are I-compatible, all the formulae are interpreted as concepts. In what follows, we will refer to the objects (resp. features) occurring in $\varGamma$ and $\varDelta$ in the various rules with $\overline{d}$ (resp. $\overline{w}$). For the sake of readability, in what follows we omit an explicit reference to the interpretation maps $\alpha$ and $\chi$.

(swSf and swSfi)

(swSdf and swSdfi)

(curryS and uncurryS)

(swES and swESi) The proof is similar to the previous ones. The soundness of rules refl, sym, and trans follows from the fact that relation E is equivalence relation in a rough formal context.

Remark 2

The soundness of the switch rules is proved exactly as the soundness of the interdefinability rules in Lemma 5 by the I-compatibility of the relations in enriched formal contexts. More in general, these rules encode exactly the I-compatibility of such relations. Let us show this for $R_\Box$, as the others are proved similarly. One of the two I-compatibility conditions can be rewritten as

In what follows we are not assuming that $R_\Box$ is I-compatible; hence the valuation of an arbitrary formula does not need to be closed, but rather just a pair containing an arbitrary set of objects and its intension, or a an arbitrary set of features and its extension. Ignoring the contexts for readability, the rule $S_{x\Box a}$ is interpreted as

⁵The second I-compatibility condition for $R_\Box$ is proved similarly using $S_{a\Box x}$.

4.2 Syntactic Completeness of the Basic Calculus and Its Axiomatic Extensions

In the present section, we show that the axioms and rules of $\mathbf {R.L}\varSigma$, where $\varSigma$ is a subset of the set of axioms in Table 1, are derivable in $\mathbf {R.L}$ extended with the corresponding rules. The axioms and rules of the basic logic $\textbf{L}$ and some of its axiomatic extensions are discussed in Appendix B. Below, we show how the axioms $\Box p \ \,{\vdash }\ \,p$, $\Box p \ \,{\vdash }\ \,\Box \Box p$, and $p \ \,{\vdash }\ \,{\rhd }{\rhd } p$ can be derived using rules refl, sym, and trans respectively.

5 Conclusions

In the present paper, we have introduced labelled calculi for a finite set of non-distributive modal logics in a modular way, and we have shown that the calculus associated with each such logic is sound w.r.t. the relational semantics of that logic given by elementary classes of enriched formal contexts, and syntactically complete w.r.t. the given logic. These results showcase that the methodology introduced in [13] for introducing labelled calculi by suitably integrating semantic information in the design of the rules can be extended from classical modal logics to the wider class of non-distributive logics. This methodology has proved successful for designing calculi for classical modal logics enjoying excellent computational properties, such as cut elimination, subformula property, being contraction-free, and being suitable for proof-search. Future developments of this work include the proofs of these results for the calculi introduced in the present paper.

Appendices

A Soundness of the Basic Calculus

Lemma 6

The basic calculus $\mathbf {R.L}$ is sound for the logic of enriched formal contexts.

Proof

The soundness of the axioms, cut rules and propositional rules is trivial from the definitions of satisfaction and refutation relation for enriched formal contexts. We now discuss the soundness for the other rules.

Adjunction rules. The soundness of the adjunction rules follows from the fact that $R_\blacksquare = R_\Diamond ^{-1}$, and .

Approximation rules. We only give proof for $approx_a$. The proof for $approx_x$ is similar. In what follows, we will refer to the objects (resp. features) occurring in $\varGamma$ and $\varDelta$ in the various rules with $\overline{d}$ (resp. $\overline{w}$).

Invertible rules for modal connectives. We only give proofs for $\Box _L$ and $\Box _R$. The proofs for $\Diamond _R$, $\Diamond _L$, $\rhd _R$, and $\rhd _L$ can be given in a similar manner.

The invertibility of the rule $\Box _L$ is obvious from the fact that the premise can be obtained from the conclusion by weakening.

Switch rules. Soundness of the rules Sxa and Sax follows from the fact that for any concepts $c_1$ and $c_2$ we have

$$\begin{aligned}{}[\![{c_1}]\!] \subseteq [\![{c_2}]\!] \quad \iff \quad (\![{c_2}]\!) \subseteq (\![{c_1}]\!). \end{aligned}$$

The soundness of all other switch rules follows from the definition of modal connectives and I-compatibility. As all the proofs are similar we only prove the soundness of S$a \Diamond x$ as a representative case. Soundness of other rules can be proved in an analogous manner.

Soundness of the axiomatic extensions considered in Sect. 3.2 is immediate from the Proposition 1.

B Syntactic completeness

As to the axioms and rules of the basic logic $\textbf{L}$, below, we only derive in $\mathbf {R.L}$ the axioms and rules encoding the fact that $\Diamond$ is a normal modal operator plus the axiom $p \ \,{\vdash }\ \,p \vee q$.

The syntactic completeness for the other axioms and rules of $\textbf{L}$ can be shown in a similar way. In particular, the admissibility of the substitution rule can be proved by induction in a standard manner.

We now consider the reflexivity axiom $p \ \,{\vdash }\ \,\Diamond p$ and the transitivity axiom $\Box p \ \,{\vdash }\ \,\Box \Box p$. The derivation for dual axioms $\Box p \ \,{\vdash }\ \,p$ and $\Diamond \Diamond p \ \,{\vdash }\ \,\Diamond p$ can be provided analogously.

Completeness for the other axiomatic extensions can be shown in a similar way.