CLKR (Conditional Logic and Knowledge Representation) is an online repository of conditional logic resources for knowledge representation and reasoning. The question which entailments should follow from a conditional knowledge base consisting of a set of conditionals “If A then usually B“ is central in logic-based AI. In order to support the practical side of this question, CLKR provides various collections of conditional knowledge bases and related resources. All knowledge bases available in CLKR can be processed directly with a corresponding reasoning system like InfOCF-Web. The sets of knowledge bases include examples as they are used in the literature for illustration, application knowledge bases from different domains, and systematically generated knowledge bases for evaluating implementations of nonmonotonic reasoning. A main emphasis of the current version of CLKR is on providing collections of knowledge bases in various normal forms that have been proposed for conditional knowledge bases, e.g., conditional normal form, antecedent normal form, and renaming normal form.

Hinweise

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

1 Introduction

Conditionals of the form “If A then usually B” establish a plausible, yet defeasible connection between the antecedent A and the consequent B. There is a rich body of theoretical investigations and approaches addressing the question which entailments should follow from a conditional knowledge base consisting of a set of such conditionals, (e.g., [1, 12, 14, 16, 18, 21, 24]); this question plays a major role in logic-based AI. Less attention has been paid to the practical side of this question, for instance regarding implementations, empirical evaluations, or real-world applications. While for deduction in classical logics one can observe a strong emphasis on automated theorem proving, applications, and implemented systems (e.g., [27]), the situation with respect to such practical aspects is quite different for nonmonotonic reasoning from conditionals (e.g., [25]).

This paper gives a short description of CLKR (Conditional Logic and Knowledge Representation), an online repository of conditional logic resources for knowledge representation and reasoning. CLKR provides various collections of conditional knowledge bases and related resources. All available knowledge bases can be parsed directly with the online reasoning platform InfOCF-Web and the library InfOCF-Lib [22]. They include examples as used in the literature for illustrating nonmonotonic reasoning and its specific aspects and properties, application knowledge bases modelling scenarios and problems from various domains, and systematically generated knowledge bases for testing and empirically evaluating implementations. Because for comparing the semantics of syntactic descriptions or for automatically processing them, normal forms may provide considerable advantages, a main emphasis of the current version of CLKR is on providing knowledge bases in various normal forms. There are complete collections of knowledge bases over a signature in normal forms that take equivalences induced by, e.g., p-entailments [16] or signature renamings [6], into account.

Anzeige

After briefly recalling the required background in Sect. 2, we give an overview of CLKR in Sect. 3 and present normal forms for conditionals and knowledge bases in Sects. 4 and 5. In Sect. 6, we give examples of how the current CLKR resources have already been used successfully to address scientific questions, conclude, and point out further work.

2 Background: Conditional Logic

Let \(\mathcal {L}(\Sigma )\) be the propositional language over a finite signature \(\Sigma\). We call a signature \(\Sigma\) with a linear ordering \(\lessdot\) an ordered signature and denote it by \((\Sigma , \lessdot )\). The language may be denoted by \(\mathcal {L}\) if the signature is clear from context. The formulas of \(\mathcal {L}\) will be denoted by letters \(A,B,C, \ldots\). We write AB for \(A \wedge B\) and \(\overline{A}\) for \(\lnot A\). We identify the set of all complete conjunctions over \(\Sigma\) with the set \(\Omega\) of possible worlds over \(\mathcal {L}\). For \(\omega \in \Omega\) and \(A \in \mathcal {L}\), \(\omega \models A\) means that A holds in \(\omega\). The set of worlds satisfying A is \(\Omega _A = \{\omega \mid \omega \models A\}\). Two formulas A, B are equivalent, denoted as \(A \equiv B\), if \(\Omega _A = \Omega _B\).

In analogy to the usual notation \(P({y}|{x})\) for the conditional probability of y if x is given, a qualitative conditional “Given A, than usually B holds” will be represented by \(({B}|{A})\). Thus, by introducing a new binary operator |, we obtain the set \(({\mathcal {L}} \mid {\mathcal {L}})_\Sigma = \{ (B|A) \mid A,B \in \mathcal {L}(\Sigma )\}\) of conditionals over \(\mathcal {L}(\Sigma )\). Again, \(\Sigma\) may be omitted. A conditional \(({B}|{A})\) is trivial if it is self-fulfilling (\(A \models B\)) or contradictory (\(A \models \overline{B}\)). A finite set \(\mathcal {R}\) of conditionals is called a knowledge base, also called a belief base.

As an illustrative semantics for conditionals, we use ordinal conditional functions (OCF), also called ranking functions, first introduced (in a more general form) in [26]. An OCF is a function \(\kappa :\, {\Omega } \rightarrow {{\mathbb {N}}}\) with \(\kappa ^1(0) \not = \emptyset\), expressing degrees of implausibility of possible worlds where a lower degree denotes “less surprising”. Each \(\kappa\) uniquely extends to a function mapping formulas to \({\mathbb {N}}\cup \{\infty \}\) given by \(\kappa (A) = \min \{\kappa (\omega ) \mid \omega \models A\}\) where \(\min \emptyset = \infty\). An OCF \(\kappa\)accepts a conditional \(({B}|{A})\), written \(\kappa \models ({B}|{A})\), if the verification of the conditional is less surprising than its falsification, i.e., if \(\kappa (AB) < \kappa (A\overline{B})\); equivalently, \(\kappa \models ({B}|{A})\) iff for every \(\omega ' \in \Omega _{A\overline{B}}\) there is \(\omega \in \Omega _{AB}\) with \(\kappa (\omega ) < \kappa (\omega ')\). An OCF \(\kappa\) accepts a knowledge base \(\mathcal {R}\) if \(\kappa\) accepts all conditionals in \(\mathcal {R}\), and \(\mathcal {R}\) is consistent if an OCF accepting \(\mathcal {R}\) exists. \({ Mod}(\mathcal {R})\) denotes the set of all OCFs \(\kappa\) accepting \(\mathcal {R}\). Two knowledge bases \(\mathcal {R}, \mathcal {R}'\) are model equivalent, denoted by \(\mathcal {R}\equiv _{{ mod}}\mathcal {R}'\), if \({ Mod}(\mathcal {R}) = { Mod}(\mathcal {R}')\).

Anzeige

An inference relation\(|\!\!\!\sim \subseteq \mathcal {L}\times \mathcal {L}\) is a binary relation on formulas capturing (nonmonotonic) inferences: \(A |\!\!\!\sim B\) iff B can be inferred from A. An inductive inference operator [19] is a mapping \(C\!\!:{\mathcal {R}} \mapsto |\!\!\!\sim _{\!\!{{\mathcal {R}}}}\) that maps a knowledge base \({\mathcal {R}}\) to an inference relation such that direct inference and trivial vacuity are fulfilled:

(DI)

if \(({B}|{A}) \in {\mathcal {R}}\) then \(A |\!\!\!\sim _{\!\!{{\mathcal {R}}}} B\)

(TV)

if \({\mathcal {R}} = \emptyset\) and \(A |\!\!\!\sim _{\!\!{{\mathcal {R}}}} B\) then \(A \models B\)

Thus, the concept of inductive inference operator formalizes how an inference relation \(\mathord {|\!\!\!\sim } \subseteq \mathcal {L}\times \mathcal {L}\) is obtained by inductive completion of a given knowledge base. If no confusion arises, we may simply use \(|\!\!\!\sim\) to denote the inductive inference operator mapping \({\mathcal {R}}\) to \(|\!\!\!\sim _{\!\!{{\mathcal {R}}}}\).

System P [24] provides widely accepted postulates for nonmonotonic inference relations. If B can be derived from A using the knowledge base \(\mathcal {R}\) by applying the rules in system P, we denote this by \(A |\!\!\!\sim ^{\!p}_{\!\!{\mathcal {R}}} B\). Thus, system P inference is an example of an inductive inference operator, and it has been shown (see [1, 14, 24]) that it coincides with p-entailment which requires that all models of \(\mathcal {R}\) accept \(({B}|{A})\) [16].

3 Overview of CLKR

All knowledge bases CLKR are in the .cl-format, which can be parsed by the online reasoning tool InfOCF-Web and the library InfOCF-Lib [22]. For an illustration, we use a knowledge base about cars [2] which can be found in CLKR (Fig. 1) under Knowledge Bases\(\vartriangleright\)Examples.

Example 1

[\({\mathcal {R}_{{ car}}}\)] Let \({\Sigma _{{ car}}}=\{c,e,f\}\) where c stands car, e for e-car, and f for fossil fuel. The knowledge base \({\mathcal {R}_{{ car}}}\) containing the seven conditionals

\(q_1\):

\(({f}|{c})\) “Cars usually need fossil fuel.”

\(q_2\):

\(({\overline{f}}|{e})\) “Usually e-cars do not need fossil fuel.”

\(q_3\):

\(({c}|{e})\) “E-cars usually are cars.”

\(q_4\):

\(({e}|{e\overline{f}})\) “E-cars that do not need fossil fuel usually are e-cars.”

\(q_5\):

\(({e\overline{f}}|{e})\) “E-cars usually are e-cars that do not need fossil fuel.”

\(q_6\):

\(({\overline{e}}|{\top })\) “Usually things are no e-cars.”

\(q_7\):

\(({cf\vee \overline{c}f}|{ce\vee c\overline{e}})\) “Things that are cars and e-cars or cars but not e-cars are cars that need fossil fuel or are no cars but need fossil fuel.”

Conjunction is represented by “a, b”, disjunction by “a; b”, negation by “!a”, a tautology by “Top”, and a contradiction by “Bottom”. The name of the knowledge base, here “car”, preceeds the conditionals, and for the given signature, a .cl-file may contain more than one knowledge base. The buttons CLKR Files and Syntax on the CLKR homepage (see Fig. 1) provide information about the format and the syntax of the files in CLKR. Under Conditionals, collections of conditionals in two different normal forms (see Sect. 4) are available.

Under Knowledge Bases, four categories of knowledge bases are provided. Via the link Examples, one can find collections of knowledge bases used as examples in the literature. For instance, there are several variations of \({\mathcal {R}_{{ car}}}\) (Example 1), and multiple different instances of the birds-and-penguins scenario popular for illustrating nonmonotonic reasoning (e.g., [13, 16, 24]). Under Medical Domain, there are knowledge bases modelling diagnostic situations regarding anemia, chest pain, malaria infections, and chronic myeloid leukaemia [17]. Under Randomly Generated, there are knowledge bases with up to 80 signature elements, thus involving \(2^{80}\) possible worlds, and up to 100 conditionals that were generated for evaluating SMT-based implementations of c-inference [28]. A main emphasis of the current version of CLKR is on providing complete collections of knowledge bases in various normal forms that have been proposed in the literature; these are available via Normal Form KBs and will be discussed in detail in Sect. 5.

4 Conditionals in Normal Form

While the set of syntactically different conditionals and thus also the set of different knowledge bases over \(\Sigma\) is infinite because \(\mathcal {L}= \mathcal {L}(\Sigma )\) is infinite, we can abstract from the syntactic variants of the underlying propositional language \(\mathcal {L}\) and represent each formula \(A \in \mathcal {L}\) uniquely by its set \(\Omega _A\) of satisfying worlds, thus closely reflecting the canonical disjunctive normal form (CDNF) of A. We also exploit that the satisfaction relation between models and conditionals in the different semantics mentioned above does not depend on the syntactic form of \(({B}|{A})\), but on its verifying and falsifying worlds. Therefore, we say that \(({B}|{A})\) and \(({B'}|{A'})\) are conditionally equivalent, denoted by \(({B}|{A}) \equiv _{{ ce}}({B'}|{A'})\), if \(A \equiv A'\) and \(AB \equiv A'B'\). This allows us to simplify the representation of conditionals by using only normal form conditionals. In the following proposition, the two conditions \(B \subsetneqq A\) and \(B \not = \emptyset\) ensure both the falsifiability and the verifiability of a conditional \(({B}|{A})\), thereby excluding any trivial conditional.

Proposition 1

(\({ NFC}(\Sigma )\) [10]) For\({ NFC}(\Sigma ) = \{({B}|{A}) \mid A \subseteq \Omega _{\Sigma }, \, B \subsetneqq A, \, B \not = \emptyset \},\)the set ofnormal form conditionalsover\(\Sigma\), the following holds: (i) \({ NFC}(\Sigma )\)does not contain any trivial conditional. (ii) For every nontrivial conditional over\(\Sigma\)there is a conditionally equivalent conditional in\({ NFC}(\Sigma )\). (iii) All conditionals in\({ NFC}(\Sigma )\)are pairwise not conditionally equivalent.

For instance, \(({\{ab\}}|{\{ab, a\overline{b}\}})\) and \(({\{a\overline{b}\}}|{\{ab, a\overline{b}\}})\) are conditionals in \({ NFC}(\Sigma _{ab})\) where \(\Sigma _{ab}= \{a,b\}\). Given a signature \(\Sigma\) with a linear ordering \(\lessdot\), in [4] an induced linear ordering \(\prec \!\!\!\cdot\) on \({ NFC}(\Sigma )\) is defined by extending \(\lessdot\) to worlds and conditionals. The idea is to consider atoms to be smaller than their negation, to consider sets with fewer elements to be smaller than sets with more elements, to order conditionals first by considering their antecedents and then their consequents, and furthermore, to take equivalence classes induced by renamings on \(\Sigma\) into account. A renaming for \(\Sigma\) is a bijection \(\rho :\, {\Sigma } \rightarrow {\Sigma }\); it is extended canonically to worlds, formulas, conditionals, knowledge bases, and to sets thereof. Then X and \(X'\) are isomorphic with respect to signature renamings, denoted by \(X \simeq X'\), if there exists a renaming \(\rho\) such that \(\rho (X) = X'\). Furthermore, for a set M, \(m \in M\), and an equivalence relation \(\equiv\) on M, the set of equivalence classes induced by \(\equiv\) is denoted by \([{M}]_{/{\equiv }}\), and the unique equivalence class containing m is denoted by \([{m}]_{{\equiv }}\). E.g., \(\rho _{ab}\) with \(\rho _{ab}(a)=b\) and \(\rho _{ab}(b)=a\) is a renaming for \(\Sigma _{ab}\), \([{\Omega _{\Sigma _{ab}}}]_{/{\simeq }} = \{[ab], [a\overline{b}, \overline{a}b], [\overline{a}\overline{b}]\}\) are the three equivalence classes of worlds over \(\Sigma _{ab}\), and we have \([{({ab}|{ab \vee a\overline{b}})}]_{{\simeq }} = [{({ab}|{ab \vee \overline{a}b})}]_{{\simeq }}\). For an illustration, Table 1 shows some of the conditionals in \({ NFC}(\Sigma _{ab})\) and their ordering \(\prec \!\!\!\cdot\) induced by \(a \lessdot b\). \({ NFC}(\Sigma _{ab})\) contains 50 conditionals, and \([{{ NFC}(\Sigma _{ab})}]_{/{\simeq }}\) has 31 equivalence classes; 19 of these classes contain two conditionals, while the other 12 classes are singletons. The \(\prec \!\!\!\cdot\)-minimal conditional in each equivalence class is a canonical normal form conditional (CNFC).

Table 1

The first eight of the conditionals \(r_{01} \prec \!\!\!\cdot \ldots \prec \!\!\!\cdot r_{50}\) in \({ NFC}(\Sigma _{ab})\) given in CDNF for \(\Sigma _{ab}= \{a, b\}\) with \(a \lessdot b\), and their equivalence classes \([{01}],\ldots ,[{31}]\) induced by renamings

For \(\left| {\Sigma }\right| = 3\), there are 6050 normal form conditionals and 1326 canonical normal form conditionals. For \(\left| {\Sigma }\right| = 4\), there are more than 42 million normal form conditionals. Via Conditionals in CLKR, the complete sets \({ NFC}(\Sigma )\) and \({ CNFC}(\Sigma )\) for \(\Sigma = \Sigma _{ab}= \{a,b\}\) and for \(\Sigma = \Sigma _{abc}=\{a,b,c\}\) are available.

5 Knowledge Bases in Normal Form

We present a series of successively refined normal forms. Starting with a set of NFC conditionals as introduced above and taking increasingly more powerful equivalences into account, this leads to more succinct and fewer knowledge bases in the resulting normal form, see Knowledge Bases\(\vartriangleright\)Normal Form KBs in CLKR.

Conditional Normal Form (CndNF) Using only \({ NFC}(\Sigma )\)-conditionals yields the CndNF normal form, which is uniquely determined for each \(\mathcal {R}\).

Definition 1

(CndNF, \({CndNF}(\mathcal {R})\) [5]) A knowledge base \(\mathcal {R}\) over \(\Sigma\) is in conditional normal form (CndNF) if \(\mathcal {R}\subseteq { NFC}(\Sigma )\). For each consistent knowledge base \(\mathcal {R}\) over \(\Sigma\), its CndNF representation is \(\textrm{CndNF}(\mathcal {R}) = \{({\Omega _{AB}}|{\Omega _A}) \mid ({B}|{A}) \in \mathcal {R}\} \cap { NFC}(\Sigma )\).

Two knowledge bases \(\mathcal {R}, \mathcal {R}'\) are inferentially equivalent (with respect to system P), denoted by \(\mathcal {R}{\mathop {\sim }\limits ^{p}}\mathcal {R}'\), if \(A |\!\!\!\sim ^{\!p}_{\!\!{\mathcal {R}}} B\) holds if and only if \(A |\!\!\!\sim ^{\!p}_{\!\!{\mathcal {R}'}} B\) for all formulas A, B. This leads to the well-known result that model equivalence and inferential equivalence w.r.t. system P coincide, i.e., \(\mathcal {R}\equiv _{{ mod}}\mathcal {R}'\) if and only if \(\mathcal {R}{\mathop {\sim }\limits ^{p}}\mathcal {R}'\) [16]. Since \(({B}|{A})\) and \(({AB}|{A})\) are model equivalent, by replacing any conditional \(({B}|{A})\) in a knowledge base \(\mathcal {R}\) by \(({AB}|{A})\) we obtain a model equivalent knowledge base, and using only \({ NFC}(\Sigma )\)-conditionals yields \(\textrm{CndNF}(\mathcal {R})\) with \(\mathcal {R}\equiv _{{ mod}}\textrm{CndNF}(\mathcal {R})\).

Example 2

Using the CDNF for \(\mathcal {R}_{935}= \{({\overline{a}}|{b}), ({b}|{a \vee b}), ({\overline{a} \vee b}|{a \vee \overline{b}})\}\) and replacing conditionals by their equivalent normal forms yields \({\mathcal {R}_{935}' =} \{({\{\overline{a}b\}}|{\{ab, \overline{a}b\}}), ({\{ab, \overline{a}b\}}|{\{ab, a\overline{b}, \overline{a}b\}}), ({\{ab, \overline{a}\overline{b}\}}|{\{ab, a\overline{b}, \overline{a}\overline{b}\}})\}\).

Due to the combinatorial explosion on the three levels of building possible worlds, conditionals, and knowledge bases, there are well over 500 million consistent knowledge bases in CndNF already over the two element signature \(\Sigma _{ab}\). The maximal number of conditionals in any of these \(\Sigma _{ab}\)-knowledge bases is 25 because adding any further \(\Sigma _{ab}\)-conditional would yield an inconsistent knowledge base because of two contradictory conditionals of the form \(({B}|{A})\) and \(({\overline{B}}|{A})\). In CLKR, a partial collection of \(\Sigma _{ab}\)-knowledge bases in CndNF is available.

Antecedent Normal Form (ANF) The basic idea of antecedentwise equivalence of two knowledge bases \(\mathcal {R},\mathcal {R}'\) is to require that the sets of conditionals having equivalent antecedents correspond to each other in \(\mathcal {R}\) and \(\mathcal {R}'\) [9]. This leads to the notion of antecedent normal form where all conditionals in a knowledge base have pairwise non-equivalent antecedents.

Definition 2

(RANF [9]) Let \(\mathcal {R}\) be a consistent knowledge base. \({ Ant}(\mathcal {R}) = \{A \mid ({B}|{A}) \in \mathcal {R}\}\) are the antecedents of\(\mathcal {R}\). For \(A \in { Ant}(\mathcal {R})\), \({\mathcal {R}}_{|{A}} = \{({B'}|{A'}) \mid ({B'}|{A'}) \in \mathcal {R}\text { and } A \equiv A'\}\) are the A-conditionals in\(\mathcal {R}\). \(\mathcal {R}\) is in antecedent normal form (ANF) if it is in CndNF and \(\left| {{\mathcal {R}}_{|{A}}}\right| = 1\) for all \(A \in { Ant}(\mathcal {R})\).

Each knowledge base has a uniquely determined ANF.

Proposition 2

(ANF\((\mathcal {R})\) [9]) For each consistent\(\mathcal {R}\), \(\textrm{ANF}(\mathcal {R}) = \{({\Omega _{A B_1 \ldots B_n}}|{\Omega _A}) \mid A \in { Ant}(\mathcal {R}), {\mathcal {R}}_{|{A}} = \{({B_1}|{A_1}), \ldots , ({B_n}|{A_n})\}, A \not \models B_1 \ldots B_n \}\)is in ANF and antecedentwise equivalent to\(\mathcal {R}\).

Example 3

The two knowledge bases \(\{({a}|{a \vee b}), ({b}|{a \vee b})\}\) and \(\{({ab}|{a \vee b})\}\) are antecedentwise equivalent. \(\mathcal {R}_{935}'\) from Example 2 is in ANF.

Example 4

(\({\mathcal {R}_{{ car}}}\), cont.) The ANF of \({\mathcal {R}_{{ car}}}\) contains three conditionals, written in the .cl-format as:

Antecedentwise equivalence ensures inferential equivalence w.r.t. system P. Thus, for all \(\mathcal {R}\), we have \(\mathcal {R}{\mathop {\sim }\limits ^{p}}\textrm{ANF}(\mathcal {R})\). If an inductive inference operator \(|\!\!\!\sim\) satisfies certain criteria, then this inferential equivalence property for ANF also holds w.r.t. \(|\!\!\!\sim\) [5, Prop. 12]. A set of transformation rules can map every knowledge base into its uniquely determined ANF [9].

Compared to CndNF, there is a huge reduction in the number of knowledge bases in ANF. Instead of over 500 million knowledge bases in CndNF over \(\Sigma _{ab}\), there are only 1 353 105 consistent knowledge bases in ANF, and instead of 25 conditionals, the maximal number of conditionals in a consistent \(\Sigma _{ab}\)-knowledge base in ANF is 11. CLKR provides the complete collection of all 1 353 105 knowledge bases in ANF over \(\Sigma _{ab}\).

Reduced Antecedent Normal Form (RANF) If \(\mathcal {R}\) is in ANF, it may still contain redundancies in form of conditionals that can be inferred form the other conditionals in \(\mathcal {R}\). For instance, in \(\mathcal {R}= \{({ab}|{a}), ({ab}|{b}), ({ab}|{a \vee b})\}\), the third conditional can be derived from the first two conditionals with system P’s axiom (OR) [24]; omitting it does not change the induced inference relation of \(\mathcal {R}\) with respect to system P inference.

Definition 3

(Reduced form, RANF [4]) A knowledge base \(\mathcal {R}\) is in reduced form (with respect to system P) if there is no conditional \(({B}|{A}) \in \mathcal {R}\) such that \(A \, |\!\!\!\sim ^{\!p}_{\!\!{\mathcal {R}{\setminus }{({B}|{A})}}} \, B\). \(\mathcal {R}\) is in reduced antecedent normal form (RANF) if \(\mathcal {R}\) is in ANF and in reduced form.

In [4], a transformation system \(\Theta ^{{ ra}}\) is provided such that every \(\mathcal {R}' \in \Theta ^{{ ra}}(\mathcal {R})\) is in RANF and model equivalent to \(\mathcal {R}\). While for \(\mathcal {R}\), its model equivalent CndNF and ANF is uniquely determined, this is not the case for RANF. Furthermore, the concept of reduced form w.r.t. system P can be generalized by taking any other inductive inference operator \(|\!\!\!\sim\) into account [5].

Instead of 1 353 105 \(\Sigma _{ab}\)-knowledge bases in ANF, there are just 4168 consistent \(\Sigma _{ab}\)-knowledge bases in RANF, each containing at most 4 conditionals [7]; CLKR provides the complete collection.

Sytem P Normal Form (SPNF) There are still different knowledge bases in RANF that are inferentially equivalent with respect to system P. In order to take this equivalence \({\mathop {\sim }\limits ^{p}}\) into account, we extend the linear ordering \(\prec \!\!\!\cdot\) on \({ NFC}(\Sigma )\) induced by \(\lessdot\) on \(\Sigma\) (Sect. 4) to knowledge bases. The lexicographic extension of \(\preccurlyeq \!\!\cdot\) to strings over \({ NFC}(\Sigma )\) is denoted by \({\preccurlyeq \!\!\cdot }_{{ lex}}\). For knowledge bases \(\mathcal {R}= \{r_1, \ldots , r_n\}\) and \(\mathcal {R}' = \{r'_1, \ldots , r'_{n'}\}\) over \({ NFC}(\Sigma )\) with \(r_i \prec \!\!\!\cdot r_{i+1}\) and \(r'_j \prec \!\!\!\cdot r'_{j+1}\) the ordering \({\preccurlyeq \!\!\cdot }_{{ set}}\) is given by: \(\mathcal {R}{\preccurlyeq \!\!\cdot }_{{ set}} \mathcal {R}' \text { iff } n < n' \text {, or } n = n' \text { and } r_1 \ldots r_n {\preccurlyeq \!\!\cdot }_{{ lex}} r'_1 \ldots r'_{n'}\) The ordering \({\preccurlyeq \!\!\cdot }_{{ set}}\) is a linear ordering on the set of knowledge bases over \({ NFC}(\Sigma )\), and in the following, we will abbreviate \(\mathcal {R}{\prec \!\!\cdot }_{{ set}} \mathcal {R}'\) simply by \(\mathcal {R}\prec \!\!\cdot \mathcal {R}'\), and analogously for the non-strict version \({\preccurlyeq \!\!\cdot }_{{ set}}\).

Definition 4

(SPNF [7]) A knowledge base \(\mathcal {R}\) is in system P normal form (SPNF) if \(\mathcal {R}\) is in RANF and for every knowledge base \(\mathcal {R}' \subseteq { NFC}(\Sigma )\) in RANF with \(\mathcal {R}{\mathop {\sim }\limits ^{p}}\mathcal {R}'\) it holds that \(\mathcal {R}\preccurlyeq \!\!\cdot \mathcal {R}'\).

For every consistent \(\mathcal {R}\subseteq { NFC}(\Sigma )\) there is a uniquely determined \(\mathcal {R}'\) in SPNF with \(\mathcal {R}{\mathop {\sim }\limits ^{p}}\mathcal {R}'\). CLKR provides the complete collection of all 484 \(\Sigma _{ab}\)-knowledge bases that are in SPNF.

Renaming Normal Form A fundamental concept in logic can be summed up in the slogan “Truth is invariant under change of notation” [15]. Using the equivalence \(\simeq\) on knowledge bases induced by signature renamings (Sect. 4), this leads to the normal form \(\rho\)NF.

Definition 5

(\(\rho\)NF [6]) A knowledge base \(\mathcal {R}\) in CndNF is in renaming normal form (\(\rho\)NF) if for every \(\mathcal {R}'\) with \(\mathcal {R}\simeq \mathcal {R}'\) it holds that \(\mathcal {R}\preccurlyeq \!\!\cdot \mathcal {R}'\).

The \(\rho\)NF can be combined with other normal forms given above. A knowledge base is in renaming antecedent normal form (\(\rho\)ANF) if it is in \(\rho\)NFand in ANF, it is renaming reduced antecedent normal form (\(\rho\)RANF) if it is in RANF and in \(\rho\)NF, and it is in renaming sytem P normal form (\(\rho\)SPNF) it is is in SPNF and in \(\rho\)NF. These normal forms exibit desirable properties; for instance, for every system P inference relation \(|\!\!\!\sim\) there is a conditional knowledge base \(\mathcal {R}\) in \(\rho\)SPNF and a renaming \(\rho\) such that \(|\!\!\!\sim = \rho (|\!\!\!\sim ^{\!p}_{\!\!{\mathcal {R}}})\) [7]. For \(\Sigma _{ab}\), CLKR provides the full collections of the 676 951 knowledge bases in \(\rho\)ANF, the 2143 knowledge bases in \(\rho\)RANF, and the 262 knowledge bases in \(\rho\)SPNF. An overview of the knowledge bases available in CLKR is given in Tables 2 and 3.

Table 2

Knowledge bases in normal forms in CLKR. For ANF, RANF, SPNF and their combinations with \(\rho\)NF, CLKR provides the complete sets of all \(\Sigma _{ab}\)-knowledge bases

\(\Sigma\)

Normal form

Number of KBs

Normal form

Number of KBs

Max. \(|\mathcal {R}|\)

\(\Sigma _{ab}\)

CndNF

1,144,860

25

\(\Sigma _{ab}\)

ANF

1,353,105

\(\rho\)ANF

676,951

11

\(\Sigma _{ab}\)

RANF

4168

\(\rho\)RANF

2143

4

\(\Sigma _{ab}\)

SPNF

484

\(\rho\)SPNF

262

4

\(\Sigma _{abc}\)

\(\rho\)RANF

2,869,302

2

Table 3

Range of signature size, knowledge base size, and number of knowledge bases in the current version of CLKR

Range of \(|\Sigma |\)

Range of \(|\mathcal {R}|\)

Number of KBs

Example

3–6

3–7

24

Medical Domain

4–61

3–33

21

Randomly Generated

4–80

4–100

1319

Normal From KBs

2–3

1–25

6,051,281

CLKR

2–80

1–100

6,052,645

6 Applications, Conclusions, and Further Work

Examples of successful uses of the current CLKR resources include solving the previously open question [3] whether weakly skeptical c-inference satisfies the postulate (Weak Or) or automatically detecting counter examples for other nonmonotonic postulates and inference operators [23], the qualitative comparison of inference methods in certain domains [17], the evaluation of SAT and SMT based implementations of c-inference [11, 28, 29], and the generation and comparison of all inference relations that can be obtained from different inference operators (system P [24], system Z [16], c-inference [3], system W [20]) by inductively completing a consistent knowledge base over a 2-element signature [8]. Our future work includes adding knowledge bases from other domains and also from probablistic conditional logic, and including further benchmark problems consisting of knowledge bases and sets of corresponding queries. Contributions from the scientific community are welcome and will also be integrated into CLKR.

Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

The Scientific journal "KI – Künstliche Intelligenz" is the official journal of the division for artificial intelligence within the "Gesellschaft für Informatik e.V." (GI) – the German Informatics Society - with constributions from troughout the field of artificial intelligence.