An overview of KLM-style defeasible entailment

Kaliski, Adam

An overview of KLM-style defeasible entailment

Master Thesis

2020

Abstract

The usage of formal logic to solve problems in artificial intelligence has a long history in the field. Information is represented in a formal language, which facilitates algorithmic reasoning about some domain knowledge. Traditionally, the algorithms used for the reasoning services are monotonic, which states that adding knowledge never causes the retraction of an inference. A result of this is that if the knowledge in question contains examples that are exceptions to stated rules, then the entire knowledge base may become unsatisfiable. If the knowledge accurately represents the domain, then such a result is undesirable. One solution is nonmonotonic reasoning, which encompasses patterns of defeasible or “common sense” reasoning that may retract conclusions upon the addition of new information to a knowledge base. One of the most prominent frameworks for nonmonotonic reasoning is the one defined by Kraus, Lehmann, and Magidor (KLM). The KLM framework has very desirable features both for theoretical study of nonmonotonic reasoning, as well as for implementation in AI applications. However, the current state of the KLM framework spans numerous papers over two decades of research. This provides a challenge for new researchers to understand the current problems being studied, as well as to understand the framework well enough to either extend it or apply it. This dissertation aims to compile the theoretical work done in this framework to provide a single point of reference for anyone wishing to understand the KLM framework, as well as to know how to define a defeasible entailment relation, using homogenised terminology and notation that is now typical of the field. Firstly, the propositional logic used as the base language will be defined. Then, paralleling the way the framework was historically built up, a preferential semantics over that language will be described, before modifying the language itself with a defeasible connective, and introducing a nonmonotonic entailment relation over such a language. Then, recent extensions to this framework defining various classes of defeasible entailment are described. By the end of this dissertation, the reader should have a well rounded understanding of the KLM framework, from classical logic to defeasible logic.

Keywords

Computer Science

Reference:

Collections

Masters

Full item page