Nonmonotonic reasoning from conditional knowledge bases with system W

Abstract

Abstract For nonmonotonic reasoning in the context of a knowledge base $\mathcal {R}$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>R</mml:mi></mml:math> containing conditionals of the form If A then usually B , system P provides generally accepted axioms. Inference solely based on system P, however, is inherently skeptical because it coincides with reasoning that takes all ranking models of $\mathcal {R}$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>R</mml:mi></mml:math> into account. System Z uses only the unique minimal ranking model of $\mathcal {R}$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>R</mml:mi></mml:math> , and c-inference, realized via a complex constraint satisfaction problem, takes all c-representations of $\mathcal {R}$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>R</mml:mi></mml:math> into account. C-representations constitute the subset of all ranking models of $\mathcal {R}$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>R</mml:mi></mml:math> that are obtained by assigning non-negative integer impacts to each conditional in $\mathcal {R}$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>R</mml:mi></mml:math> and summing up, for every world, the impacts of all conditionals falsified by that world. While system Z and c-inference license in general different sets of desirable entailments, the first major objective of this article is to present system W . System W fully captures and strictly extends both system Z and c-inference. Moreover, system W can be represented by a single strict partial order on the worlds over the signature of $\mathcal {R}$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>R</mml:mi></mml:math> . We show that system W exhibits further inference properties worthwhile for nonmonotonic reasoning, like satisfying the axioms of system P, respecting conditional indifference, and avoiding the drowning problem. The other main goal of this article is to provide results on our investigations, underlying the development of system W, of upper and lower bounds that can be used to restrict the set of c-representations that have to be taken into account for realizing c-inference. We show that the upper bound of n − 1 is sufficient for capturing c-inference with respect to $\mathcal {R}$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>R</mml:mi></mml:math> having n conditionals if there is at least one world verifying all conditionals in $\mathcal {R}$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>R</mml:mi></mml:math> . In contrast to the previous conjecture that the number of conditionals in $\mathcal {R}$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>R</mml:mi></mml:math> is always sufficient, we prove that there are knowledge bases requiring an upper bound of 2 n − 1 , implying that there is no polynomial upper bound of the impacts assigned to the conditionals in $\mathcal {R}$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>R</mml:mi></mml:math> for fully capturing c-inference.

Topics & Concepts