Lexicographic Logic: a Many-valued Logic for Preference Representation
This work provides a new logical formalism for representing and reasoning about user preferences, particularly for ranking query results.
This paper introduces lexicographic logic, an extension of classical propositional logic designed to express various preferences, especially lexicographic ones. It defines a new connective using finite lists of truth values and demonstrates its natural definition over a subset of rational numbers, enabling the simple definition of well-known preferential operators.
Logical formalisms provide a natural and concise means for specifying and reasoning about preferences. In this paper, we propose lexicographic logic, an extension of classical propositional logic that can express a variety of preferences, most notably lexicographic ones. The proposed logic supports a simple new connective whose semantics can be defined in terms of finite lists of truth values. We demonstrate that, despite the well-known theoretical limitations that pose barriers to the quantitative representation of lexicographic preferences, there exists a subset of the rational numbers over which the proposed new connective can be naturally defined. Lexicographic logic can be used to define in a simple way some well-known preferential operators, like "$A$ and if possible $B$", and "$A$ or failing that $B$". Moreover, many other hierarchical preferential operators can be defined using a systematic approach. We argue that the new logic is an effective formalism for ranking query results according to the satisfaction level of user preferences.