Literal Projection and Circumscription.
Christoph Wernhard · 2009
Abstract. We develop a formal framework intended as a preliminary step for a single knowledge representation system that provides different representation techniques in a unified way. In particular we consider first-order logic extended by techniques for second-order quantifier elimination and non-monotonic reasoning. Background of the work is literal projection, a generalization of second-order quantification which permits, so to speak, to quantify upon an arbitrary sets of ground literals, instead of just (all ground literals with) a given predicate symbol. In this paper, an operator raise is introduced that is only slightly different from literal projection and can be used to define a generalization of circumscription in a straightforward and compact way. Some properties of this operator and of circumscription defined in terms of it, also in combination with literal projection, are then shown. A previously known characterization of consequences of circumscribed formulas in terms of literal projection is generalized from propositional to first-order logic. A characterization of answer sets according to the stable model semantics in terms of circumscription is given. This characterization does not recur onto syntactic notions like reduct and fixed-point construction. It essentially renders a recently proposed “circumscription-like ” characterization in a compact way without involvement of a specially interpreted connective. 1