Skip to main content

Open Access 03.05.2024 | Systems Description

CLKR: Conditional Logic and Knowledge Representation

verfasst von: Christoph Beierle, Jonas Haldimann, Leon Schwarzer

Erschienen in: KI - Künstliche Intelligenz

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

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.
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 AB 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}')\).
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.”
given in the .cl-format is the following:
$$\qquad\begin{aligned}{} & {} \texttt {signature}\\{} & {} \qquad \qquad \texttt {c,e,f} \\{} & {} \texttt {conditionals}\\{} & {} \texttt {car\{ } \\{} & {} \qquad \qquad \texttt {(f | c),} \\{} & {} \qquad \qquad \texttt {(!f | e),} \\{} & {} \qquad \qquad \texttt {(c | e),} \\{} & {} \qquad \qquad \texttt {(e | e,!f ),} \\{} & {} \qquad \qquad \texttt {(e,!f | e),} \\{} & {} \qquad \qquad \texttt {(!e | Top),} \\{} & {} \qquad \quad \texttt {((c,f); (!c,f) | (c,e); (c,!e))} \\{} & {} \texttt {\}} \end{aligned}$$
Conjunction is represented by “ab”, disjunction by “ab”, 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 of normal form conditionals over \(\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
Class
First conditional
Second conditional
[01]
\(r_{01}:(\{{ab}\}|\{{ab,a\overline{b}}\})\)
\(r_{02}:(\{{ab}\}|\{{ab,\overline{a}b}\})\)
[02]
\(r_{03}:(\{{a\overline{b}}\}|\{{ab,a\overline{b}}\})\)
\(r_{04}:(\{{\overline{a}b}\}|\{{ab,\overline{a}b}\})\)
[03]
\(r_{05}:(\{{ab}\}|\{{ab,\overline{a}\overline{b}}\})\)
 
[04]
\(r_{06}:(\{{\overline{a}\overline{b}}\}|\{{ab,\overline{a}\overline{b}}\})\)
 
[05]
\(r_{07}:(\{{a\overline{b}}\}|\{{a\overline{b},\overline{a}b}\})\)
\(r_{08}:(\{{\overline{a}b}\}|\{{a\overline{b},\overline{a}b}\})\)
\(\ldots\)
\(\ldots\)
\(\ldots\)
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 AB. 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:
$$\qquad\begin{aligned}{} & {} \texttt {(f | c),} \\{} & {} \texttt {(!e | Top),} \\{} & {} \texttt {(c,!f | e)} \end{aligned}$$
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.

Unsere Produktempfehlungen

KI - Künstliche Intelligenz

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.

Literatur
1.
Zurück zum Zitat Adams EW (1975) The logic of conditionals: an application of probability to deductive logic, synthese library. Springer Science+Business Media, DordrechtCrossRef Adams EW (1975) The logic of conditionals: an application of probability to deductive logic, synthese library. Springer Science+Business Media, DordrechtCrossRef
2.
Zurück zum Zitat Beierle C, Eichhorn C, Kern-Isberner G (2017) A transformation system for unique minimal normal forms of conditional knowledge bases. In A. Antonucci, L. Cholvy, and O. Papini, editors, Symbolic and Quantitative Approaches to Reasoning with Uncertainty - 14th European Conference, ECSQARU 2017, vol 10369 of LNCS, pp 236–245. Springer, Berlin Beierle C, Eichhorn C, Kern-Isberner G (2017) A transformation system for unique minimal normal forms of conditional knowledge bases. In A. Antonucci, L. Cholvy, and O. Papini, editors, Symbolic and Quantitative Approaches to Reasoning with Uncertainty - 14th European Conference, ECSQARU 2017, vol 10369 of LNCS, pp 236–245. Springer, Berlin
3.
Zurück zum Zitat Beierle C, Eichhorn C, Kern-Isberner G, Kutsch S (2021) Properties and interrelationships of skeptical, weakly skeptical, and credulous inference induced by classes of minimal models. Artif Intell 297:103489MathSciNetCrossRef Beierle C, Eichhorn C, Kern-Isberner G, Kutsch S (2021) Properties and interrelationships of skeptical, weakly skeptical, and credulous inference induced by classes of minimal models. Artif Intell 297:103489MathSciNetCrossRef
4.
Zurück zum Zitat Beierle C, Haldimann J (2020) Normal forms of conditional knowledge bases respecting system P-entailments. In A. Herzig and J. Kontinen, editors, Foundations of Information and Knowledge Systems - 11th International Symposium, FoIKS 2020, vol 12012 of LNCS, pp 22–41. Springer Beierle C, Haldimann J (2020) Normal forms of conditional knowledge bases respecting system P-entailments. In A. Herzig and J. Kontinen, editors, Foundations of Information and Knowledge Systems - 11th International Symposium, FoIKS 2020, vol 12012 of LNCS, pp 22–41. Springer
5.
Zurück zum Zitat Beierle C, Haldimann J (2022) Normal forms of conditional belief bases respecting inductive inference. In: The international FLAIRS conference proceedings, vol 35 Beierle C, Haldimann J (2022) Normal forms of conditional belief bases respecting inductive inference. In: The international FLAIRS conference proceedings, vol 35
6.
Zurück zum Zitat Beierle C, Haldimann J (2022) Normal forms of conditional knowledge bases respecting system P-entailments and signature renamings. Ann. Math. Artif. Intell. 90(2):149–179MathSciNetCrossRef Beierle C, Haldimann J (2022) Normal forms of conditional knowledge bases respecting system P-entailments and signature renamings. Ann. Math. Artif. Intell. 90(2):149–179MathSciNetCrossRef
7.
Zurück zum Zitat Beierle C, Haldimann J, Kutsch S (Apr. 2021) A complete map of conditional knowledge bases in different normal forms and their induced system P inference relations over small signatures. In: The international FLAIRS conference proceedings, vol 34 Beierle C, Haldimann J, Kutsch S (Apr. 2021) A complete map of conditional knowledge bases in different normal forms and their induced system P inference relations over small signatures. In: The international FLAIRS conference proceedings, vol 34
8.
Zurück zum Zitat Beierle C, Haldimann J, Schwarzer L (2023) Observational equivalence of conditional belief bases. In: The international FLAIRS conference proceedings, vol 36, no 1 Beierle C, Haldimann J, Schwarzer L (2023) Observational equivalence of conditional belief bases. In: The international FLAIRS conference proceedings, vol 36, no 1
9.
Zurück zum Zitat Beierle C, Kutsch S (2019) On the antecedent normal form of conditional knowledge bases. In G. Kern-Isberner and Z. Ognjanović, editors, Symbolic and Quantitative Approaches to Reasoning with Uncertainty-15th European Conference, ECSQARU 2019, vol 11762 of LNAI, pp 175–186. Springer Beierle C, Kutsch S (2019) On the antecedent normal form of conditional knowledge bases. In G. Kern-Isberner and Z. Ognjanović, editors, Symbolic and Quantitative Approaches to Reasoning with Uncertainty-15th European Conference, ECSQARU 2019, vol 11762 of LNAI, pp 175–186. Springer
10.
Zurück zum Zitat Beierle C, Kutsch S (2019) Systematic generation of conditional knowledge bases up to renaming and equivalence. In F. Calimeri, N. Leone, and M. Manna, editors, Logics in Artificial Intelligence-16th European Conference, JELIA 2019, vol 11468 of LNAI, pp 279–286. Springer Beierle C, Kutsch S (2019) Systematic generation of conditional knowledge bases up to renaming and equivalence. In F. Calimeri, N. Leone, and M. Manna, editors, Logics in Artificial Intelligence-16th European Conference, JELIA 2019, vol 11468 of LNAI, pp 279–286. Springer
11.
Zurück zum Zitat Beierle C, von Berg M, Sanin A (2022) Realization of c-inference as a SAT problem. In: The international FLAIRS conference proceedings, vol 35 Beierle C, von Berg M, Sanin A (2022) Realization of c-inference as a SAT problem. In: The international FLAIRS conference proceedings, vol 35
12.
Zurück zum Zitat Benferhat S, Dubois D, Prade H (1999) Possibilistic and standard probabilistic semantics of conditional knowledge bases. J Logic Comput 9(6):873–895MathSciNetCrossRef Benferhat S, Dubois D, Prade H (1999) Possibilistic and standard probabilistic semantics of conditional knowledge bases. J Logic Comput 9(6):873–895MathSciNetCrossRef
13.
Zurück zum Zitat Brewka G (1986) Tweety—still flying: some remarks on abnormal birds applicable rules and a default prover. In: Proceedings 5th national conference on artificial intelligence, pp 8–12. Morgan Kaufmann Brewka G (1986) Tweety—still flying: some remarks on abnormal birds applicable rules and a default prover. In: Proceedings 5th national conference on artificial intelligence, pp 8–12. Morgan Kaufmann
14.
Zurück zum Zitat Dubois D, Prade H (1994) Conditional objects as nonmonotonic consequence relationships. Special issue on conditional event algebra. IEEE Trans Syst Man Cybern 24(12):1724–1740CrossRef Dubois D, Prade H (1994) Conditional objects as nonmonotonic consequence relationships. Special issue on conditional event algebra. IEEE Trans Syst Man Cybern 24(12):1724–1740CrossRef
15.
Zurück zum Zitat Goguen J, Burstall R (1992) Institutions: abstract model theory for specification and programming. J ACM 39(1):95–146MathSciNetCrossRef Goguen J, Burstall R (1992) Institutions: abstract model theory for specification and programming. J ACM 39(1):95–146MathSciNetCrossRef
16.
Zurück zum Zitat Goldszmidt M, Pearl J (1996) Qualitative probabilities for default reasoning, belief revision, and causal modeling. Artif Intell 84:57–112MathSciNetCrossRef Goldszmidt M, Pearl J (1996) Qualitative probabilities for default reasoning, belief revision, and causal modeling. Artif Intell 84:57–112MathSciNetCrossRef
17.
Zurück zum Zitat Haldimann J, Osiak A, Beierle C (2020) Modelling and reasoning in biomedical applications with qualitative conditional logic. In U. Schmid, F. Klügl, and D. Wolter, editors, KI 2020: Advances in Artificial Intelligence-43rd German Conference on AI, vol 12325 of LNCS, pp 283–289. Springer Haldimann J, Osiak A, Beierle C (2020) Modelling and reasoning in biomedical applications with qualitative conditional logic. In U. Schmid, F. Klügl, and D. Wolter, editors, KI 2020: Advances in Artificial Intelligence-43rd German Conference on AI, vol 12325 of LNCS, pp 283–289. Springer
18.
Zurück zum Zitat Kern-Isberner G (2001) Conditionals in nonmonotonic reasoning and belief revision, LNAI, vol 2087. Springer, BerlinCrossRef Kern-Isberner G (2001) Conditionals in nonmonotonic reasoning and belief revision, LNAI, vol 2087. Springer, BerlinCrossRef
19.
Zurück zum Zitat Kern-Isberner G, Beierle C, Brewka G (2020) Syntax splitting = relevance + independence: new postulates for nonmonotonic reasoning from conditional belief bases. In D. Calvanese, E. Erdem, and M. Thielscher, editors, Principles of Knowledge Representation and Reasoning: Proceedings of the 17th International Conference, KR-2020, pp 560–571 Kern-Isberner G, Beierle C, Brewka G (2020) Syntax splitting = relevance + independence: new postulates for nonmonotonic reasoning from conditional belief bases. In D. Calvanese, E. Erdem, and M. Thielscher, editors, Principles of Knowledge Representation and Reasoning: Proceedings of the 17th International Conference, KR-2020, pp 560–571
20.
Zurück zum Zitat Komo C, Beierle C (2022) Nonmonotonic reasoning from conditional knowledge bases with system W. Ann Math Artif Intell 90(1):107–144MathSciNetCrossRef Komo C, Beierle C (2022) Nonmonotonic reasoning from conditional knowledge bases with system W. Ann Math Artif Intell 90(1):107–144MathSciNetCrossRef
21.
Zurück zum Zitat Kraus S, Lehmann D, Magidor M (1990) Nonmonotonic reasoning, preferential models and cumulative logics. Artif Intell 44:167–207MathSciNetCrossRef Kraus S, Lehmann D, Magidor M (1990) Nonmonotonic reasoning, preferential models and cumulative logics. Artif Intell 44:167–207MathSciNetCrossRef
22.
Zurück zum Zitat Kutsch S, Beierle C (2021) InfOCF-Web: an online tool for nonmonotonic reasoning with conditionals and ranking functions. In Z. Zhou, editor, Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, JCAI 2021, pp 4996–4999. ijcai.org Kutsch S, Beierle C (2021) InfOCF-Web: an online tool for nonmonotonic reasoning with conditionals and ranking functions. In Z. Zhou, editor, Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, JCAI 2021, pp 4996–4999. ijcai.org
23.
Zurück zum Zitat Kutsch S, Beierle C (2021) Semantic classification of qualitative conditionals and calculating closures of nonmonotonic inference relations. Int J Approx Reason 130:297–313MathSciNetCrossRef Kutsch S, Beierle C (2021) Semantic classification of qualitative conditionals and calculating closures of nonmonotonic inference relations. Int J Approx Reason 130:297–313MathSciNetCrossRef
24.
25.
Zurück zum Zitat Olivetti N, Pozzato GL (2014) Nescond: an implementation of nested sequent calculi for conditional logics. In: Demri S, Kapur D, Weidenbach C (eds) Autom Reason, vol 8562. Springer, Cham, pp 511–518CrossRef Olivetti N, Pozzato GL (2014) Nescond: an implementation of nested sequent calculi for conditional logics. In: Demri S, Kapur D, Weidenbach C (eds) Autom Reason, vol 8562. Springer, Cham, pp 511–518CrossRef
26.
Zurück zum Zitat Spohn W (1988) Ordinal conditional functions: a dynamic theory of epistemic states. In W. Harper and B. Skyrms, editors, Causation in decision, belief change, and statistics, II, pp 105–134. Kluwer Academic Publishers Spohn W (1988) Ordinal conditional functions: a dynamic theory of epistemic states. In W. Harper and B. Skyrms, editors, Causation in decision, belief change, and statistics, II, pp 105–134. Kluwer Academic Publishers
27.
Zurück zum Zitat Sutcliffe G (2017) The TPTP Problem Library and Associated Infrastructure. From CNF to TH0, TPTP v6.4.0. J Autom Reason 59(4):483–502MathSciNetCrossRef Sutcliffe G (2017) The TPTP Problem Library and Associated Infrastructure. From CNF to TH0, TPTP v6.4.0. J Autom Reason 59(4):483–502MathSciNetCrossRef
28.
Zurück zum Zitat von Berg M, Sanin A, Beierle C (2023) Representing nonmonotonic inference based on c-representations as an SMT problem. In Z. Bouraoui, S. Jabbour, and S. Vesic, editors, Symbolic and Quantitative Approaches to Reasoning with Uncertainty-17th European Conference, ECSQARU-2023, vol 14249 of LNCS, pp 210–223. Springer von Berg M, Sanin A, Beierle C (2023) Representing nonmonotonic inference based on c-representations as an SMT problem. In Z. Bouraoui, S. Jabbour, and S. Vesic, editors, Symbolic and Quantitative Approaches to Reasoning with Uncertainty-17th European Conference, ECSQARU-2023, vol 14249 of LNCS, pp 210–223. Springer
29.
Zurück zum Zitat von Berg M, Sanin A, Beierle C (2024) Scaling up nonmonotonic c-inference via partial MaxSAT problems. In A. Meier and M. Ortiz, editors, Foundations of Information and Knowledge Systems-13th International Symposium, FoIKS-2024, vol 14589 of LNCS, pp 182–200. Springer von Berg M, Sanin A, Beierle C (2024) Scaling up nonmonotonic c-inference via partial MaxSAT problems. In A. Meier and M. Ortiz, editors, Foundations of Information and Knowledge Systems-13th International Symposium, FoIKS-2024, vol 14589 of LNCS, pp 182–200. Springer
Metadaten
Titel
CLKR: Conditional Logic and Knowledge Representation
verfasst von
Christoph Beierle
Jonas Haldimann
Leon Schwarzer
Publikationsdatum
03.05.2024
Verlag
Springer Berlin Heidelberg
Erschienen in
KI - Künstliche Intelligenz
Print ISSN: 0933-1875
Elektronische ISSN: 1610-1987
DOI
https://doi.org/10.1007/s13218-024-00842-z

Premium Partner