Abstract
Conditionals are defeasible rules of the form If A then usually B, and they play a central role in many approaches to nonmonotonic reasoning. Normal forms of conditional knowledge bases consisting of a set of such conditionals are useful to create, process, and compare the knowledge represented by them. In this article, we propose several new normal forms for conditional knowledge bases. Compared to the previously introduced antecedent normal form, the reduced antecedent normal form (RANF) represents conditional knowledge with significantly fewer conditionals by taking nonmonotonic entailments licenced by system P into account. The renaming normal form (ρNF) addresses equivalences among conditional knowledge bases induced by renamings of the underlying signature. Combining the concept of renaming normal form with other normal forms yields the renaming antecedent normal form (ρ ANF) and the renaming reduced antecedent normal form (ρ RANF). For all newly introduced normal forms, we show their key properties regarding, existence, uniqueness, model equivalence, and inferential equivalence, and we develop algorithms transforming every conditional knowledge base into an equivalent knowledge base being in the respective normal form. For the most succinct normal form, the ρ RANF, we present an algorithm KBρra systematically generating knowledge bases over a given signature in ρ RANF. We show that the generated knowledge bases are consistent, pairwise not antecedentwise equivalent, and pairwise not equivalent under signature renaming. Furthermore, the algorithm is complete in the sense that, when taking signature renamings and model equivalence into account, every consistent knowledge base is generated. Observing that normalizing the set of all knowledge bases over a signature Σ to ρ RANF yields exactly the same result as KBρra (Σ), highlights the interrelationship between normal form transformations on the one hand and systematically generating knowledge bases in normal form on the other hand.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Robinson, J.A.: A machine oriented logic based on the resolution principle. J. ACM 12(1), 23–41 (1965)
Robinson, J A, Voronkov, A (eds.): Handbook of automated reasoning (in 2 volumes). Elsevier and MIT Press (2001)
Adams, E.W.: The Logic of Conditionals: An Application of Probability to Deductive Logic. Synthese Library. Springer Science+Business Media, Dordrecht (1975)
Lewis, D.: Counterfactuals. Harvard University Press, Cambridge (1973)
Kraus, S., Lehmann, D., Magidor, M.: Nonmonotonic reasoning, preferential models and cumulative logics. Artif. Intell. 44, 167–207 (1990)
Pearl, J.: System Z: A natural ordering of defaults with tractable applications to nonmonotonic reasoning. In: Parikh, R. (ed.) Proceedings of the 3rd conference on Theoretical aspects of reasoning about knowledge (TARK1990), pp 121–135. Morgan Kaufmann Publishers Inc., San Francisco (1990)
Lehmann, D., Magidor, M.: What does a conditional knowledge base entail?. Artif. Intell. 55, 1–60 (1992)
Dubois, D., Prade, H.: Conditional objects as nonmonotonic consequence relationships. IEEE Trans. Syst. Man Cybern. Spec. Issue Cond. Event Algebra 24(12), 1724–1740 (1994)
Goldszmidt, M., Pearl, J.: Qualitative probabilities for default reasoning, belief revision, and causal modeling. Artif. Intell. 84, 57–112 (1996)
Benferhat, S., Dubois, D., Prade, H.: Possibilistic and standard probabilistic semantics of conditional knowledge bases. J. Log. Comput. 9(6), 873–895 (1999)
Kern-Isberner, G.: Conditionals in nonmonotonic reasoning and belief revision. LNAI, vol. 2087. Springer, Berlin (2001)
Kern-Isberner, G.: A thorough axiomatization of a principle of conditional preservation in belief revision. Ann. Math. Artif. Intell. 40(1-2), 127–164 (2004)
Beierle, C., Eichhorn, C., Kern-Isberner, G., Kutsch, S.: Properties and interrelationships of skeptical, weakly skeptical, and credulous inference induced by classes of minimal models. Artif. Intell. 297. https://doi.org/10.1016/j.artint.2021.103489. (in press, online 2 Mar 2021) (2021)
Beierle, C., Eichhorn, C., Kern-Isberner, G.: A transformation system for unique minimal normal forms of conditional knowledge bases. In: ECSQARU 2017, LNCS 10369, pp. 236–245. Springer, Berlin (2017)
Beierle, C., Eichhorn, C., Kern-Isberner, G.: On transformations and normal forms of conditional knowledge bases. In: Benferhat, S., Tabia, K., Ali, M. (eds.) Advances in Artificial Intelligence: From Theory to Practice, LNCS, vol. 10350, pp 488–494. Springer (2017)
Beierle, C.: Inferential equivalence, normal forms, and isomorphisms of knowledge bases in institutions of conditional logics. In: Hung, C.-C., Papadopoulos, G.A. (eds.) The 34th ACM/SIGAPP Symposium on Applied Computing (SAC ’19), April 8–12, 2019, Limassol, Cyprus, pp 1131–1138. ACM, New York (2019)
Beierle, C., Kutsch, S.: On the antecedent normal form of conditional knowledge bases. In: Kern-Isberner, G., Ognjanović, Z. (eds.) Symbolic and Quantitative Approaches to Reasoning with Uncertainty - 15th European Conference, ECSQARU 2019, Lecture Notes in Computer Science, vol. 11762, pp 175–186. Springer (2019)
Goguen, J., Burstall, R.: Institutions: Abstract model theory for specification and programming. J. ACM 39(1), 95–146 (1992)
Beierle, C., Haldimann, J.: Normal forms of conditional knowledge bases respecting system P-entailments. In: Herzig, A, Kontinen, J (eds.) FoIKS 2020, LNCS, vol. 12012, pp 22–41. Springer (2020)
Beierle, C., Haldimann, J.: Transforming conditional knowledge bases into renaming normal form. In: Barták, R., Bell, E. (eds.) Proceedings of the 33rd International Florida Artificial Intelligence Research Society Conference, FLAIRS 2020, pp 563–568. AAAI Press (2020)
Spohn, W.: The Laws of Belief: Ranking Theory and Its Philosophical Applications. Oxford U. Press, Oxford (2012)
Pearl, J.: Probabilistic reasoning in intelligent systems. Morgan Kaufmann, San Mateo (1988)
Beierle, C., Kutsch, S.: Systematic generation of conditional knowledge bases up to renaming and equivalence. In: Calimeri, F., Leone, N., Manna, M. (eds.) Logics in Artificial Intelligence - 16th European Conference, JELIA 2019, Rende, Proceedings, LNAI, vol. 11468, pp 279–286. Springer (2019)
Agrawal, R., Mannila, H., Srikant, R., Toivonen, H., Verkamo, A.I.: Fast discovery of association rules. In: Fayyad, U.M., Piatetsky-Shapiro, G., Smyth, P., Uthurusamy, R. (eds.) Advances in knowledge discovery and data mining, pp 307–328. MIT Press, Cambridge (1996)
Beierle, C., Eichhorn, C., Kutsch, S.: A practical comparison of qualitative inferences with preferred ranking models. KI – Künstliche Intell. 31(1), 41–52 (2017)
Kutsch, S.: InfOCF-Lib: A Java library for OCF-based conditional inference. In: Beierle, C., Ragni, M., Stolzenburg, F., Thimm, M. (eds.) Proceedings of the 8th Workshop on Dynamics of Knowledge and Belief (DKB-2019) and the 7th Workshop KI & Kognition (KIK-2019) co-located with 44nd German Conference on Artificial Intelligence (KI 2019), CEUR Workshop Proceedings, vol. 2445, pp 47–58. CEUR-WS.org, Kassel (2019)
Beierle, C., Haldimann, J., Kutsch, S.: A complete map of conditional knowledge bases in different normal forms and their induced system P inference relations over small signatures. In: Proceedings of the 34th International Florida Artificial Intelligence Research Society Conference, FLAIRS 2021 (2021)
Britz, K., Casini, G., Meyer, T., Varzinczak, I.: A KLM perspective on defeasible reasoning for description logics. In: Lutz, C., Sattler, U., Tinelli, C., Turhan, A.-Y., Wolter, F. (eds.) Description Logic, Theory Combination, and All That - Essays Dedicated to Franz Baader on the Occasion of His 60th Birthday, LNCS, vol. 11560, pp 147–173. Springer (2019)
Funding
Open Access funding enabled and organized by Projekt DEAL.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher’s note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
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/.
About this article
Cite this article
Beierle, C., Haldimann, J. Normal forms of conditional knowledge bases respecting system P-entailments and signature renamings. Ann Math Artif Intell 90, 149–179 (2022). https://doi.org/10.1007/s10472-021-09745-3
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10472-021-09745-3
Keywords
- Conditional knowledge base
- Signature renaming
- Inferential equivalence
- Renaming normal form ρ NF
- Antecedent normal form ANF
- Reduced antecedent normal form RANF
- ρ ANF
- ρ RANF
- Knowledge base generation