Abstract
Desirable properties of a normal form for conditional knowledge are, for instance, simplicity, minimality, uniqueness, and the respecting of adequate equivalences. In this paper, we propose the notion of antecedentwise equivalence of knowledge bases. It identifies more knowledge bases as being equivalent and allows for a simpler and more compact normal form than previous proposals. We develop a set of transformation rules mapping every knowledge base into an equivalent knowledge base that is in antecedent normal form (ANF). Furthermore, we present an algorithm for systematically generating conditional knowledge bases in ANF over a given signature. The approach is complete in the sense that, taking renamings and equivalences into account, every consistent knowledge base is generated. Moreover, it is also minimal in the sense that no two knowledge bases are generated that are antecedentwise equivalent or that are isomorphic to antecedentwise equivalent knowledge bases.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Note that it can not be more than half of these conditionals with the same antecedent because otherwise there would be a conditional together with its counter conditional, leading to inconsistency of the knowledge base.
References
Adams, E.W.: The Logic of Conditionals: An Application of Probability to Deductive Logic. Synthese Library. Springer, Dordrecht (1975). https://doi.org/10.1007/978-94-015-7622-2
Baader, F., Nipkow, T.: Term Rewriting and All That. Cambridge University Press, Cambridge (1998)
Beierle, C.: Inferential equivalence, normal forms, and isomorphisms of knowledge bases in institutions of conditional logics. In: Hung, C., Papadopoulos, G.A. (eds.) The 34th ACM/SIGAPP Symposium on Applied Computing (SAC 2019), Limassol, Cyprus, 8–12 April 2019, pp. 1131–1138. ACM, New York (2019)
Beierle, C., Eichhorn, C., Kern-Isberner, G.: A transformation system for unique minimal normal forms of conditional knowledge bases. In: Antonucci, A., Cholvy, L., Papini, O. (eds.) ECSQARU 2017. LNCS (LNAI), vol. 10369, pp. 236–245. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-61581-3_22
Beierle, C., Eichhorn, C., Kern-Isberner, G., Kutsch, S.: Skeptical, weakly skeptical, and credulous inference based on preferred ranking functions. In: Kaminka, G.A., et al. (eds.) Proceedings 22nd European Conference on Artificial Intelligence, ECAI-2016. Frontiers in Artificial Intelligence and Applications, vol. 285, pp. 1149–1157. IOS Press, Amsterdam (2016)
Beierle, C., Eichhorn, C., Kutsch, S.: A practical comparison of qualitative inferences with preferred ranking models. KI Künstliche Intelligenz 31(1), 41–52 (2017)
Beierle, C., Kern-Isberner, G.: Semantical investigations into nonmonotonic and probabilistic logics. Ann. Math. Artif. Intell. 65(2–3), 123–158 (2012)
Beierle, C., Kutsch, S.: Computation and comparison of nonmonotonic skeptical inference relations induced by sets of ranking models for the realization of intelligent agents. Appl. Intell. 49(1), 28–43 (2019)
Beierle, C., Kutsch, S.: Systematic generation of conditional knowledge bases up to renaming and equivalence. In: Calimeri, F., Leone, N., Manna, M. (eds.) JELIA 2019. LNCS (LNAI), vol. 11468, pp. 279–286. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-19570-0_18
Benferhat, S., Dubois, D., Prade, H.: Possibilistic and standard probabilistic semantics of conditional knowledge bases. J. Log. Comput. 9(6), 873–895 (1999)
Booth, R., Paris, J.B.: A note on the rational closure of knowledge bases with both positive and negative knowledge. J. Log. Lang. Comput. 7(2), 165–190 (1998)
Dubois, D., Prade, H.: Conditional objects as nonmonotonic consequence relationships. Spec. Issue Conditional Event Algebra IEEE Trans. Syst. Man Cybern. 24(12), 1724–1740 (1994)
Giordano, L., Gliozzi, V., Olivetti, N., Pozzato, G.L.: Semantic characterization of rational closure: from propositional logic to description logics. Artif. Intell. 226, 1–33 (2015)
Goldszmidt, M., Pearl, J.: Qualitative probabilities for default reasoning, belief revision, and causal modeling. Artif. Intell. 84, 57–112 (1996)
Kern-Isberner, G. (ed.): Conditionals in Nonmonotonic Reasoning and Belief Revision. LNCS (LNAI), vol. 2087. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44600-1
Knuth, D.E., Bendix, P.B.: Simple word problems in universal algebra. In: Leech, J. (ed.) Computational Problems in Abstract Algebra, pp. 263–297. Pergamon Press, Oxford (1970)
Kraus, S., Lehmann, D., Magidor, M.: Nonmonotonic reasoning, preferential models and cumulative logics. Artif. Intell. 44, 167–207 (1990)
Kutsch, S., Beierle, C.: Computation of closures of nonmonotonic inference relations induced by conditional knowledge bases. In: Kern-Isberner, G., Ognjanović, Z. (eds.) ECSQARU 2019. LNAI, vol. 11726, pp. 226–237. Springer, Cham (2019)
Lehmann, D.: Another perspective on default reasoning. Ann. Math. Artif. Intell. 15(1), 61–82 (1995)
Lehmann, D.J., Magidor, M.: What does a conditional knowledge base entail? Artif. Intell. 55(1), 1–60 (1992)
Lewis, D.: Counterfactuals. Harvard University Press, Cambridge (1973)
Paris, J.: The Uncertain Reasoner’s Companion - A Mathematical Perspective. Cambridge University Press, Cambridge (1994)
Spohn, W.: Ordinal conditional functions: a dynamic theory of epistemic states. In: Harper, W., Skyrms, B. (eds.) Causation in Decision, Belief Change, and Statistics, II, pp. 105–134. Kluwer Academic Publishers, Dordrecht (1988)
Spohn, W.: The Laws of Belief: Ranking Theory and Its Philosophical Applications. Oxford University Press, Oxford (2012)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Beierle, C., Kutsch, S. (2019). On the Antecedent Normal Form of Conditional Knowledge Bases. In: Kern-Isberner, G., Ognjanović, Z. (eds) Symbolic and Quantitative Approaches to Reasoning with Uncertainty. ECSQARU 2019. Lecture Notes in Computer Science(), vol 11726. Springer, Cham. https://doi.org/10.1007/978-3-030-29765-7_15
Download citation
DOI: https://doi.org/10.1007/978-3-030-29765-7_15
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-29764-0
Online ISBN: 978-3-030-29765-7
eBook Packages: Computer ScienceComputer Science (R0)