The Nature of Nonmonotonic Reasoning

Conclusions reached using common sense reasoning from a set of premises are often subsequently revised when additional premises are added. Because we do not always accept previous conclusions in light of subsequent information, common sense reasoning is said to be nonmonotonic. But in the standard formal systems usually studied by logicians, if a conclusion follows from a set of premises, that same conclusion still follows no matter how the premise set is augmented; that is, the consequence relations of standard logics are monotonic. Much recent research in AI has been devoted to the attempt to develop nonmonotonic logics. After some motivational material, we give four formal proofs that there can be no nonmonotonic consequence relation that is characterized by universal constraints on rational belief structures. In other words, a nonmonotonic consequence relation that corresponds to universal principles of rational belief is impossible. We show that the nonmonotonicity of common sense reasoning is a function of the way we use logic, not a function of the logic we use. We give several examples of how nonmonotonic reasoning systems may be based on monotonic logics.     

Semantic forgetting in answer set programming

The notion of forgetting, also known as variable elimination, has been investigated extensively in the context of classical logic, but less so in (nonmonotonic) logic programming and nonmonotonic reasoning. The few approaches that exist are based on syntactic modifications of a program at hand. In this paper, we establish a declarative theory of forgetting for disjunctive logic programs under answer set semantics that is fully based on semantic grounds. The suitability of this theory is justified by a number of desirable properties. In particular, one of our results shows that our notion of forgetting can be entirely captured by classical forgetting. We present several algorithms for computing a representation of the result of forgetting, and provide a characterization of the computational complexity of reasoning from a logic program under forgetting. As applications of our approach, we present a fairly general framework for resolving conflicts in inconsistent knowledge bases that are represented by disjunctive logic programs, and we show how the semantics of inheritance logic programs and update logic programs from the literature can be characterized through forgetting. The basic idea of the conflict resolution framework is to weaken the preferences of each agent by forgetting certain knowledge that causes inconsistency. In particular, we show how to use the notion of forgetting to provide an elegant solution for preference elicitation in disjunctive logic programming.     

Deontic logic as founded on nonmonotonic logic

Ever since its inception in the work of von Wright, deontic logic has been developed primarily as a species of modal logic. I argue in this paper, however, that the techniques of nonmonotonic logic may provide a better theoretical framework — at least for the formalization of commensense normative reasoning — than the usual modal treatment. After reviewing some standard approaches to deontic logic, I focus on two areas in which nonmonotonic techniques promise improved understanding: reasoning in the presence of conflicting obligations, and reasoning with conditional obligations.     

Uniform semantic treatment of default and autoepistemic logics

We revisit the issue of epistemological and semantic foundations for autoepistemic and default logics, two leading formalisms in nonmonotonic reasoning. We develop a general semantic approach to autoepistemic and default logics that is based on the notion of a belief pair and that exploits the lattice structure of the collection of all belief pairs. For each logic, we introduce a monotone operator on the lattice of belief pairs. We then show that a whole family of semantics can be defined in a systematic and principled way in terms of fixpoints of this operator (or as fixpoints of certain closely related operators). Our approach elucidates fundamental constructive principles in which agents form their belief sets, and leads to approximation semantics for autoepistemic and default logics. It also allows us to establish a precise one-to-one correspondence between the family of semantics for default logic and the family of semantics for autoepistemic logic. The correspondence exploits the modal interpretation of a default proposed by Konolige. Our results establish conclusively that default logic can be viewed as a fragment of autoepistemic logic, a result that has been long anticipated. At the same time, they explain the source of the difficulty to formally relate the semantics of default extensions by Reiter and autoepistemic expansions by Moore. These two semantics occupy different locations in the corresponding families of semantics for default and autoepistemic logics.     

Reasoning about Minimal Knowledge in Nonmonotonic Modal Logics

We study the problem of embedding Halpern and Moses's modal logic of minimal knowledge states into two families of modal formalism for nonmonotonic reasoning, McDermott and Doyle's nonmonotonic modal logics and ground nonmonotonic modal logics. First, we prove that Halpern and Moses's logic can be embedded into all ground logics; moreover, the translation employed allows for establishing a lower bound (3p) for the problem of skeptical reasoning in all ground logics. Then, we show a translation of Halpern and Moses's logic into a significant subset of McDermott and Doyle's formalisms. Such a translation both indicates the ability of Halpern and Moses's logic of expressing minimal knowledge states in a more compact way than McDermott and Doyle's logics, and allows for a comparison of the epistemological properties of such nonmonotonic modal formalisms.     

Preferential Accessibility and Preferred Worlds

Modal accounts of normality in non-monotonic reasoning traditionally have an underlying semantics based on a notion of preference amongst worlds. In this paper, we motivate and investigate an alternative semantics, based on ordered accessibility relations in Kripke frames. The underlying intuition is that some world tuples may be seen as more normal, while others may be seen as more exceptional. We show that this delivers an elegant and intuitive semantic construction, which gives a new perspective on defeasible necessity. Technically, the revisited logic does not change the expressive power of our previously defined preferential modalities. This conclusion follows from an analysis of both semantic constructions via a generalisation of bisimulations to the preferential case. Reasoners based on the previous semantics therefore also suffice for reasoning over the new semantics. We complete the picture by investigating different notions of defeasible conditionals in modal logic that can also be captured within our framework.     

A computationally tractable nonmonotonic logic

Nonmonotonic logic is intended to apply specifically to situations where the initial information is incomplete. Using nonmonotonic reasoning procedures we shall be able to jump to conclusions, but withdraw them later when we gain additional information. A number of nonmonotonic logics have been introduced and widely discussed. Nonmonotonic logics tend to be introduced proof theoretically, and little attention is paid to their semantic characteristics or their computational tractability. We address both of these issues by presenting a nonmonotonic logic for the Herbrand subset of first-order predicate logic. This nonmonotonic logic is shown to be both sound and complete. Theories formulated in this logic can be executed in logic programming fashion     

Modal nonmonotonic logics demodalized

The study of the relation between default logic and modal nonmonotonic logics has been mostly concerned with the task of translating default logic to autoepistemic or some other modal nonmonotonic logic. Here, we discuss the reverse problem, that is, the possibility of translating modal nonmonotonic logics into default-type systems formulated in the language without modal operators. To this end, we first consider a reformulation of both formalisms in terms of what we call default consequence relations. These consequence relations turn out to be especially suitable for studying default and modal nonmonotonic reasoning. We show, in particular, that different kinds of such reasoning naturally correspond to different structural rules imposed on default consequence relations. Our main results also demonstrate that all modal nonmonotonic objects considered have exact nonmodal counterparts. As an immediate consequence of these results, we obtain a method of reducing common types of modal nonmonotonic reasoning to nonmodal default reasoning.     

Nonmonotonic logic and temporal projection

Nonmonotonic formal systems have been proposed as an extension to classical first-order logic that will capture the process of human “default reasoning” or “plausible inference” through their inference mechanisms, just as modus ponens provides a model for deductive reasoning. But although the technical properties of these logics have been studied in detail and many examples of human default reasoning have been identified, for the most part these logics have not actually been applied to practical problems to see whether they produce the expected results.We provide axioms for a simple problem in temporal reasoning which has long been identified as a case of default reasoning, thus presumably amenable to representation in nonmonotonic logic. Upon examining the resulting nonmonotonic theories, however, we find that the inferences permitted by the logics are not those we had intended when we wrote the axioms, and in fact are much weaker. This problem is shown to be independent of the logic used; nor does it depend on any particular temporal representation. Upon analyzing the failure we find that the nonmonotonic logics we considered are inherently incapable of representing this kind of default reasoning.The first part of the paper is an expanded version of one that appeared in the 1986 AAAI proceedings. The second part reports on several responses to our result that have appeared since the original paper was published.     

From systems to logic in the early development of nonmonotonic reasoning

This note describes how the notion of nonmonotonic reasoning emerged in Artificial Intelligence from the mid-1960's to 1980. It gives particular attention to the interplay between three kinds of activities: design of high-level programming systems for AI, design of truth-maintenance systems, and the development of nonmonotonic logics. This was not merely a development from logic to implementation; in several cases there was a development from a system design to a corresponding logic. The article concludes with some reflections on the roles and relationships between logicist theory and system design in AI, and in particular in Knowledge Representation.     

A study of aboutness in information retrieval

This paper addresses the notion of aboutness in information retrieval. First, an exposition is given on how aboutness relates to relevance—a fundamental notion in information retrieval. A short summary is given on how aboutness is defined in more prominent information retrieval models. A model-theoretic definition of aboutness is then analyzed in an abstract setting using so called information fields. These allows properties of aboutness to be expressed independent of any given information retrieval model. As a consequence, information retrieval models can be theoretically compared according to what aboutness postulates they support. The Boolean and Coordinate retrieval models are compared in this fashion. In addition to model-theoretic aboutness, preferential entailment and conditional probabilities are employed to define aboutness between primitive information carriers. The preferential entailment approach is based on a preference semantics derived from nonmonotonic logics. The nonmonotonic behaviour of aboutness under information composition is highlighted. Rules describing how aboutness may be preserved under composition are proposed. Finally, a term aboutness definition drawn from a network-based probabilistic framework is analyzed. Conclusions regarding the implied retrieval effectiveness are drawn.     

经验逻辑：一种非单调逻辑的统一形式

人的常识推理是一种充满经验性知识的累积过程,而经验推理具有非单调性。本文提出一种关于典型与例外的经验逻辑,特别研究它的非单调性,它提供了一个现存的主要非单调逻辑的统一基础,这是通过一种类似的规则把它们翻译成经验逻辑获得的。因此,经验逻辑给出了一类更一般而且直观的非单调推理形式。     

Presenting functors on many-sorted varieties and applications

This paper studies several applications of the notion of a presentation of a functor by operations and equations. We show that the technically straightforward generalisation of this notion from the one-sorted to the many-sorted case has several interesting consequences. First, it can be applied to give equational logic for the binding algebras modelling abstract syntax. Second, it provides a categorical approach to algebraic semantics of first-order logic. Third, this notion links the uniform treatment of logics for coalgebras of an arbitrary type T with concrete syntax and proof systems. Analysing the many-sorted case is essential for modular completeness proofs of coalgebraic logics.     

Disjunctive Stable Models: Unfounded Sets, Fixpoint Semantics, and Computation

Disjunctive logic programs have become a powerful tool in knowledge representation and commonsense reasoning. This paper focuses on stable model semantics, currently the most widely acknowledged semantics for disjunctive logic programs. After presenting a new notion of unfounded sets for disjunctive logic programs, we provide two declarative characterizations of stable models in terms of unfounded sets. One shows that the set of stable models coincides with the family of unfounded-free models (i.e., a model is stable iff it contains no unfounded atoms). The other proves that stable models can be defined equivalently by a property of their false literals, as a model is stable iff the set of its false literals coincides with its greatest unfounded set. We then generalize the well-founded operator to disjunctive logic programs, give a fixpoint semantics for disjunctive stable models and present an algorithm for computing the stable models of function-free programs. The algorithm's soundness and completeness are proved and some complexity issues are discussed.     

Multi-modal nonmonotonic logics of minimal knowledge

In this paper we introduce multi-modal logics of minimal knowledge. Such a family of logics constitutes the first proposal in the field of epistemic nonmonotonic logic in which the three following aspects are simultaneously addressed: (1) the possibility of formalizing multiple agents through multiple modal operators; (2) the possibility of using first-order quantification in the modal language; (3) the possibility of formalizing nonmonotonic reasoning abilities for the agents modeled, based on the principle of minimal knowledge. We illustrate the expressive capabilities of multi-modal logics of minimal knowledge to provide a formal semantics to peer-to-peer data integration systems, which constitute one of the most recent and complex architectures for distributed information systems.      

Contrary‐to‐duty reasoning with preference‐based dyadic obligations

In this paper we introduce Prohairetic Deontic Logic (PDL), a preference‐based dyadic deontic logic. In our preference‐based interpretation of obligations “α should be (done) if β is (done)” is true if (1) no ¬α ∧ β state is as preferable as an α ∧ β state and (2) the preferred β states are α states. We show that this representation solves different problems of deontic logic. The first part of the definition is used to formalize contrary‐to‐duty reasoning, which, for example, occurs in Chisholm’s and Forrester’s notorious deontic paradoxes. The second part is used to make deontic dilemmas inconsistent.     

The relationship between KLM and MAK models for nonmonotonic inference operations

The purpose of this note is to make quite clear the relationship between two variants of the general notion of a preferential model for nonmonotonic inference: the models of Kraus, Lehmann and Magidor (KLM models) and those of Makinson (MAK models). On the one hand, we introduce the notion of the core of a KLM model, which suffices to fully determine the associated nonmonotonic inference relation. On the other hand, we slightly amplify MAK models with a monotonic consequence operation as additional ingredient. We give two equivalent characterizations of the cores of KLM models: they are precisely the amplified MAK models whose satisfaction relation:

may be expressed as the intersection of some non-empty family of satisfaction relations each of which is classically well-behaved; or

satisfies certain syntactic conditions.

This gives corollary characterizations of certain particular classes of KLM models, notably those that are (in their terminology) cumulative and more specifically those they call preferential.