Normal forms of conditional knowledge bases respecting entailments and renamings (Q2206775)

The paper introduces two new normal forms for conditional knowledge bases and studies their key properties. Conditional knowledge bases are central to nonmonotonic reasoning and typically employ rules of the form ``If \(A\) then usually \(B\)''. Normal forms are widely used in automated reasoning to improve computational efficiency. The new normal forms described in the paper allow conditional knowledge to be defined by significantly fewer conditionals. The first normal form, called the ``reduced antecedent normal form'' (RANF) is an improved version of the antecedent normal form. It builds on the previously defined system P [\textit{D. Lehmann} and \textit{M. Magidor}, Artif. Intell. 55, No. 1, 1--60 (1992; Zbl 0762.68057)]. The latter is based on six axioms which define the notion of p-entailment, where \(A\) p-entails \(B\) with respect to a knowledge base \(\mathcal R\) if and only if the conditional \((B|A)\) holds in all models of \(\mathcal R\). The semantics of conditions is defined by the ordinal conditional functions (OCF) expressing a degree of plausibility of possible worlds. According to this semantics, two knowledge bases are model equivalent (denoted mod) if they have the same set of models. Instead of using the semantic model equivalence, the authors consider syntactic notions of equivalences of knowledge bases and corresponding normal forms. They extend the set of knowledge bases by the special symbol \(\diamond\) to denote an inconsistent knowledge base. To transform a knowledge base into RANF, they propose the system \(\varTheta^{\mathrm{ra}}\) which consists of five transformation rules. It assumes a function \(v\) which maps propositional formulas into a unique normal form, and a function \(\varPi\) where \(\varPi(\mathcal R) = \diamond\) if and only if \(\mathcal R\) is inconsistent. The paper contains examples illustrating the transformation procedure and studies its properties. \(\varTheta^{\mathrm{ra}}\) is proved to terminate, as well as the resulting knowledge bases are proved to be sound and consistent if \(\varTheta^{\mathrm{ra}}(\mathcal R) \neq \{\diamond\}\). The second normal form introduced in the paper, the ``renaming normal form'' (\(\rho\)NF), is defined for knowledge bases which only contain the so-called ``normal form conditionals''. It is applied when two knowledge bases are identical, except for the names of their variables. In such cases, only one of these knowledge bases is stored. The definition of renaming suggests a function \(\rho\) such that \(X' = \rho(X)\) where \(X\) refers to formulas, worlds, conditionals, etc. The paper explores the properties of \(\rho\)NF and defines the induced ordering on formulas and conditionals. Lastly, the paper describes two algorithms for generating consistent knowledge bases in the proposed normal forms. The basic algorithm generates consistent knowledge bases in RANF which are not equivalent under renaming. The algorithm is proven to be complete, correct, and consistent, and shown not to generate equivalent knowledge bases. The second algorithm aims to improve the computational efficiency of the basic one by decreasing the search space based on refining and extending the concept of candidates and candidate elimination for knowledge base generation. This is achieved by ensuring that all generated knowledge bases are in the renaming normal form. It is shown that when taking renaming and model equivalences into account, the algorithm is complete, and every consistent knowledge base is generated. For the entire collection see [Zbl 1435.68031].