Symbolic possibilistic logic: completeness and inference methods

摘要

This paper studies the extension of possibilistic logic to the case when weights attached to formulas are symbolic. These weights then stand for variables that lie in a totally ordered scale, and only partial knowledge is available on the relative strength of these weights in the form of inequality constraints. Reasoning in symbolic possibilistic logic means solving two problems. One is to compute symbolic expressions representing the weights of conclusions of a possibilistic knowledge base. The other problem is that of comparing the relative strength of derived weights, so as to find out if one formula is more certain than another one. Regarding the first problem, a proof of the soundness and the completeness of this logic according to the relative certainty semantics in the sense of necessity measures is provided. Based on this result, two syntactic inference methods are suggested. The first one shows how to use the notion of minimal inconsistent subsets and known techniques that compute them, so as to obtain the symbolic expression representing the necessity degree of a possibilistic formula. A second family of methods computes prime implicates and takes inspiration from the concept of assumption-based theory. It enables symbolic weights attached to consequences to be simplified in the course of their computation, taking inequality constraints into account. Finally, an algorithm is proposed to find if a consequence is more certain than another one. A comparison with the original version of symbolic possibilistic logic introduced by Benferhat and Prade in 2005 is provided.