Some optimization methods for non-monotonic Reasoning in System P

Abstract

System P, introduced by Kraus, Lehman and Magidor [4], represents a core of various default systems. Reasoning in System P can be modeled by a logic with approximate conditional probabilities [7]. This probabilistic logic enriches classical propositional calculus with binary probabilistic operators which are applied to propositional formulas: CP>s(α,β), CP6s(α,β) and CP≈s(α,β), with the intended meaning that the conditional probability of α given β is “at leasts”, “at mosts” and “approximatelys”, respectively. It was shown that formulas CP≈1(α,β) can be used to model defaults of the form: “ifβ, then generally α”. Satisfiability problem for a set of defaults can be converted to a satisfiability problem for a probabilistic formula in a logic mention above. That problem can be reduced to a system of linear inequalities, and as such a number of different methods can be used for its solving. The main contributions of this paper are development of methodology for using optimization methods to solve the considered problem and presentation of the obtained results.