A General framework for choice logics

Abstract

Eine Vielzahl an Forschungsbereichen, darunter auch die der Informatik und der künstlichen Intelligenz, beschäftigen sich mit Präferenzen. Zwei bereits bestehende formale Systeme, welche sich mit Präferenzen auseinandersetzen, sind Qualitative Choice Logic (QCL) und Conjunctive Choice Logic (CCL). In beiden Logiken schreiben Interpretationen Formeln anstatt eines Wahrheitswertes eine natürliche Zahl, auch Satisfaction Degree genannt, zu. Dabei werden jene Interpretationen bevorzugt, die in einem geringstmöglichen Satisfaction Degree resultieren. In dieser Arbeit werden QCL und CCL durch die Einführung eines formalen Frameworks für Choice Logics generalisiert. Es wird gezeigt dass sowohl QCL, als auch CCL, Teil des Frameworks sind. Neue Choice Logics, welche auf neuen, nichtklassischen Konnektiven basieren, werden eingeführt. Da das Framework nicht sehr restriktiv definiert wird, und deswegen viele verschiedene Choice Logics mit unterschiedlichen Eigenschaften spezifiziert werden können, werden mehrere Klassen von Choice Logics eingeführt und untersucht. Ein Begriff der starken Äquivalenz zwischen den Formeln einer Choice Logic wird definiert, und anderen Äquivalenzbegriffen gegenübergestellt. Dabei wird bewiesen, dass der von uns eingeführte Begriff der starken Äquivalenz bezüglich QCL und CCL ident mit einem von Brewka et al. verwendeten Äquivalenzbegriff ist. Schlußendlich wird eine Komplexitätsanalyse durchgeführt. Dadurch ergeben sich auch neue Resultate für QCL und CCL, etwa dass das Hauptproblem bezüglich bevorzugten Modellen für beide Logiken Θ2P-vollständig ist. Das selbe Problem ist für eine andere, im Zuge dieser Arbeit eingeführte, Logik ∆2P-vollständig.

The topic of preferences is of importance in many areas of research, including computer science, and, more specifically, artificial intelligence. Two formal systems in the literature that are designed for preference handling are Qualitative Choice Logic (QCL) and Conjunctive Choice Logic (CCL). Both of these logics extend classical propositional logic by a non-classical choice connective, with which preferences can be expressed. Instead of evaluating formulas to true or false, formulas in QCL and CCL are ascribed a satisfaction degree, by which interpretations are ranked. In this thesis, QCL and CCL are generalized by the formal introduction of a choice logic framework. Besides showing that QCL and CCL are captured by this framework, several new choice logics, based on new choice connectives, are introduced. Since the specified framework is not very restrictive, and therefore a multitude of different choice logics can be expressed, several classes of choice logics are defined and examined. A notion of strong equivalence between the formulas of a choice logic is introduced and related to other notions of equivalence. In the course of this analysis, it is proven that for QCL and CCL, our notion of strong equivalence is interchangeable with another notion of equivalence introduced by Brewka et al. in the original QCL paper. Lastly, the computational complexity of different reasoning tasks relevant for choice logics is examined. Although this complexity analysis is conducted in a general manner, it also yields new results regarding QCL and CCL. For example, the main decision problem regarding preferred models is Θ2P-complete in both of these logics. For the same problem, we show ∆2P-completeness for Lexicographic Choice Logic (LCL), a logic introduced in this thesis.