Justifications for KLM-style defeasible reasoning

Imrie, Jane

Justifications for KLM-style defeasible reasoning

Thesis / Dissertation

2025

Publisher

University of Cape Town

Department

Department of Computer Science

Faculty

Faculty of Science

Abstract

The notion of using formal logic for artificial intelligence was first suggested by McCarthy in the 1950s, and this has led to extensive research into a field known as knowledge representation and reasoning, wherein research is conducted into how best to represent knowledge and reason about said knowledge in order to create more knowledge. Many systems which use formal logic were initially highly constrained as the algorithms which they employed were monotonic and consequently any inference which the system was able to compute could not be retracted, even if said information caused contradictions. This could prove detrimental, especially if the new information was more accurate vis-a-vis the domain under consideration. One of the solutions to this is non-monotonicity, and for the context of this dissertation, we will consider defeasible reasoning, which is a form of non-monotonic reasoning. There are many different types of formalisms for this type of reasoning, with the KLM (Kraus, Lehmann and Magidor) being one of the more popular. KLM has a number of desirable properties, which is why it is the formalism of choice. Regardless of the logic being used, reasoning systems also need to be able to "explain" how they were able to draw inferences. Justifications are one form of explanations, and research into them has increased throughout the years as explainable artificial intelligence researchers have highlighted their importance in creating trustworthy and reliable systems. This dissertation broadly aims to compile the research on justifications, with a focus on propositional and description logics, for both the classical and defeasible case, with a particular emphasis on the latter. We achieve this by first introducing classical propositional and description logic at a high level. We then delve into the history and current state of the literature on justifications in the classical case. We then detail how to add defeasibility into propositional logic and elaborate on different frameworks which are used to achieve this. This is then followed by work on defeasible justifications, where we highlight the algorithms used for computing them. The last chapter details gaps in the current literature for future research. By the end of this dissertation, the reader should have a keen understanding of classical and defeasible justifications, from their history and computation, to their algorithms and theoretical underpinnings.

Keywords

KLM-style

Reference:

Collections

Masters

Full item page