Measuring inconsistency with constraints for propositional knowledge bases

Measuring inconsistency has been considered as a necessary starting point to understand the nature of inconsistency in a knowledge base better. For practical applications, however, we often have to face some constraints on resolving inconsistency. In this paper, we propose a graph-based approach to measuring the inconsistency for a propositional knowledge base with one or both of two typical types of constraints on modifying formulas. Here the first type of constraint, called the hard constraint, describes a pair of sets of formulas such that all the formulas in the first set should be protected from being modified on the condition that all the formulas in the second set must be modified in order to restore the consistency of that base, while the second type, called the soft constraint, describes a set of pairs of formulas that are not allowed to be modified together. At first, we use a bipartite graph to represent the relation between formulas and minimal inconsistent subsets of a knowledge base. Then we show that such a graph-based representation allows us to characterize the inconsistency with constraints in a concise way. Based on this characterization, we thus propose measures for the degree of inconsistency and for the responsibility of each formula for the inconsistency of a knowledge base with constraints, respectively. Finally, we show that these measures can be well explained based on Halpern and Pearl's causal model and Chockler and Halpern's notion of responsibility.