A Monotonicity Theorem for Extended Logic Programs

Because general and extended logic programs behave nonmonotonically, it is in general difficult to predict how even minor changes to such programs will affect their meanings. This paper shows that for a restricted class of extended logic programs --- those with signings --- it is possible to state a fairly general theorem comparing the entailments of programs. To this end, we generalize (to the class of extended logic programs) the definition of a signing, first formulated by Kunen for general programs, and establish a theorem characterizing a restricted monotonicity property for signed extended programs. The theorem is formulated in terms of simple syntactic criteria on pairs of programs. To demonstrate the usefulness of this result, we use it to compare the strengths of two families of extended logic programs for commonsense reasoning about action. 1 Introduction We would like to be able to characterize the relative strengths of logic programs in terms of simple syntactic features..