Fundamenta Informaticae

Current research in the area of nonmonotonic reasoning suggests that autoepistemic logic provides a general framework for formalizing commonsense reasoning in various domains of discourse. The goal of this paper is to investigate the suitability of autoepistemic logic for formalization of some forms of inheritance reasoning. To this end we propose a new semantics for inheritance networks with exceptions based on autoepistemic logic.

We introduce 3-valued stable models which are a natural generalization of standard (2-valued) stable models. We show that every logic program P has at least one 3-valued stable model and that the well-founded model of any program P [Van Gelder et al., 1990] coincides with the smallest 3-valued stable model of P. We conclude that the well-founded semantics of an arbitrary logic program coincides with the 3-valued stable model semantics.

The 3-valued stable semantics is closely related to non-monotonic formalisms in AI. Namely, every program P can be translated into a suitable autoepistemic (resp. default) theory P ˆ so that the 3-valued stable semantics of P coincides with the (3-valued) autoepistemic (resp. default) semantics of P ˆ . Similar results hold for circumscription and CWA. Moreover, it can be shown that the 3-valued stable semantics has a natural extension to the class of all disjunctive logic programs and deductive databases.

Finally, following upon the recent approach developed by Gelfond and Lifschitz, we extend all of our results to more general logic programs which, in addition to the use of negation as failure, permit the use of classical negation.

Large logic programs are normally designed by teams of individuals, each of whom designs a subprogram. While each of these subprograms may have consistent completions, the logic program obtained by taking the union of these subprograms may not. However, the resulting program still serves a useful purpose, for a (possibly) very large subset of it still has a consistent completion. We argue that “small” inconsistencies may cause a logic program to have no models (in the traditional sense), even though it still serves some useful purpose. A semantics is developed in this paper for general logic programs which ascribes a very reasonable meaning to general logic programs irrespective of whether they have consistent (in the classical logic sense) completions.

We investigate possible belief sets of an agent reasoning with default rules. Besides of Reiter’s extensions which are based on a proof-theoretic paradigm (similar to Logic Programming), other structures for default theories, based on weaker or different methods of constructing belief sets are considered, in particular, weak extensions and minimal sets. The first of these concepts is known to be closely connected to autoepistemic expansions of Moore, the other to minimal stable autoepistemic theories containing the initial assumptions. We introduce the concept of stratifed collection of default rules and investigate the properties of the largest stratified subset of the family D, determined by W. We find a necessary and sufficient condition for a weak extension to be an extension in terms of stratification. We prove that for theories (D, W) without extension, the least fixed point of the associated operator (with weak extension or minimal set as a context) is an extension of suitably chosen (D’, W) with D’ ⊆ D. We investigate conditions for existence of extensions and introduce the notion of perfectly-stratified set of default rules and its variant of maximally perfectly-stratified set. Existence of such set of default rules turns out to be equivalent to the existence of extension. Finally, we investigate convergence of algorithm for computing extensions.