Proof Methods for Conditional and Preferential Logics

By Gian Luca Pozzato,
Università degli Studi di Torino
February 2007


This work is focused on proof methods and theorem proving for Conditional and Preferential logics. Conditional logics are extensions of classical logic by means of a conditional operator, usually denoted as =>. Conditional logics have a long history and recently they have found application in several areas of AI, including belief revision and update, the representation of causal inferences in action planning and the formalization of hypothetical queries in deductive databases.

Conditional logics have also been applied in order to formalize nonmonotonic reasoning. The study of the relations between conditional logics and nonmonotonic reasoning has led to the seminal work by Kraus, Lehmann and Magidor, who have introduced the so-called KLM framework. According to this framework, a defeasible knowledge base is represented by a finite set of conditional assertions of the form A |~ B, whose intuitive reading is “typically (normally), the A’s are B’s”. The operator |~ is nonmonotonic in the sense that A |~ B does not imply A and C |~ B.

The logics of the KLM framework, also known as preferential logics, allow to infer new conditional assertion from a given knowledge base. In spite of their significance, very few deductive mechanisms have been developed for conditional and preferential logics.

In this work, the author tries to (partially) fill the existing gap by introducing proof methods (sequent and tableau calculi) for conditional and preferential logics, as well as theorem provers obtained by implementing the proposed calculi.