Inferential equivalence, normal forms, and isomorphisms of knowledge bases in institutions of conditional logics
Christoph Beierle · 2019
Conditionals of the form "If A, then usually B" play an important role in formal approaches to knowledge representation and reasoning. Sets of such conditionals, called a knowledge base, may represent the explicitly given knowledge of an intelligent agent. For many operations involving kowledge bases, it is advantageous to have a compact and standardized form for them. In this paper, we show how to obtain a unique minimal normal form for every conditional knowledge base. The normal form is independent of a specific notion of semantic models and their particular notion of satisfaction between models and conditionals. This abstraction is achieved by employing Goguen and Burstall's framework of institutions and introducing the general notion of an institution of conditional logic. It covers previously proposed formalizations of conditional logics as institutions with specific semantics, like total preorders on worlds, possibility distributions, ranking functions, or big-stepped probabilities. The concepts of model equivalence and elementwise equivalence of knowledge bases are generalized first to arbitrary institutions of conditional logic and then further by taking also isomorphisms into account. We introduce the notion of inferential equivalence of knowledge bases for two different nonmonotonic inference relations induced by a knowledge base. For inferential equivalences with respect to these nonmonotonic inference relations, we prove how they are preserved under normalization and isomorphisms.