System LS: A Three-Tiered Nonmonotonic Reasoning System

In this paper, a formal system of nonmonotonic reasoning is developed, which takes as its inspiration the manner in which some people make logically justifiable conclusions about nonmonotonic reasoning problems. The people, when asked about individuals, compare the logical strength of the arguments relating any sets to which the individual belongs, to other sets. A three-tiered system of rules including rules of System P as well as Transitivity and Monotonicity is developed. The system, known as System LS for logical strength, deals with three levels of non-strict relationships:

• α ₁β  α are normally β ( more than half of the α are β ) ;

       
  
  

A Classification and Survey of Preference Handling Approaches in Nonmonotonic Reasoning

In recent years, there has been a large amount of disparate work concerning the representation and reasoning with qualitative preferential information by means of approaches to nonmonotonic reasoning. Given the variety of underlying systems, assumptions, motivations, and intuitions, it is difficult to compare or relate one approach with another. Here, we present an overview and classification for approaches to dealing with preference. A set of criteria for classifying approaches is given, followed by a set of desiderata that an approach might be expected to satisfy. A comprehensive set of approaches is subsequently given and classified with respect to these sets of underlying principles.     

'Classical' Negation in Nonmonotonic Reasoning and Logic Programming

Gelfond and Lifschitz were the first to point out the need for a symmetric negation in logic programming and they also proposed a specific semantics for such negation for logic programs with the stable semantics, which they called 'classical'. Subsequently, several researchers proposed different, often incompatible, forms of symmetric negation for various semantics of logic programs and deductive databases. To the best of our knowledge, however, no systematic study of symmetric negation in non-monotonic reasoning was ever attempted in the past. In this paper we conduct such a systematic study of symmetric negation. We introduce and discuss two natural, yet different, definitions of symmetric negation: one is called strong negation and the other is called explicit negation. For logic programs with the stable semantics, both symmetric negations coincide with Gelfond–Lifschitz' 'classical negation'. We study properties of strong and explicit negation and their mutual relationship as well as their relationship to default negation 'not', and classical negation '¬'. We show how one can use symmetric negation to provide natural solutions to various knowledge representation problems, such as theory and interpretation update, and belief revision. Rather than to limit our discussion to some narrow class of nonmonotonic theories, such as the class of logic programs with some specific semantics, we conduct our study so that it is applicable to a broad class of non-monotonic formalisms. In order to achieve the desired level of generality, we define the notion of symmetric negation in the knowledge representation framework of AutoEpistemic logic of Beliefs, introduced by Przymusinski.     

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.     

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.     

Process and Policy: Resource-Bounded NonDemonstrative Reasoning

This paper investigates the appropriateness of formal dialectics as a basis for nonmonotonic reasoning and defeasible reasoning that takes computational limits seriously. Rules that can come into conflict should be regarded as policies, which are inputs to deliberative processes. Dialectical protocols are appropriate for such deliberations when resources are bounded and search is serial.
AI, it is claimed here, is now perfectly positioned to correct many misconceptions about reasoning that have resulted from mathematical logic's enormous success in this century: among them, (1) that all reasons are demonstrative, (2) that rational belief is constrained, not constructed, and (3) that process and disputation are not essential to reasoning. AI mainly provides new impetus to formalize the alternative (but older) conception of reasoning, and AI provides mechanisms with which to create compelling formalism that describes the control of processes.
The technical contributions here are: the partial justification of dialectic based on controlling search; the observation that nonmonotonic reasoning can be subsumed under certain kinds of dialectics; the portrayal of inference in knowledge bases as policy reasoning; the review of logics of dialogue and proposed extensions; and the preformal and initial formal discussion of aspects and variations of dialectical systems with nondemonstrative reasons.     

Operational Concepts of Nonmonotonic Logics Part 2: Autoepistemic Logic

The subject of nonmonotonic reasoning is reasoning with incompleteinformation. One of the main approaches is autoepistemic logic inwhich reasoning is based on introspection. This paper aims at providing a smooth introduction to this logic,stressing its motivation and basic concepts. The meaning (semantics)of autoepistemic logic is given in terms of so-called expansionswhich are usually defined as solutions of a fixed-point equation. Thepresent paper shows a more understandable, operational method fordetermining expansions. By improving applicability of the basicconcepts to concrete examples, we hope to make a contribution to awider usage of autoepistemic logic in practical applications.     

The Possibilistic Handling of Irrelevance in Exception-Tolerant Reasoning

In nonmonotonic reasoning, the preferential system P is known to provide reasonable but very cautious conclusions, and in particular, preferential inference is blocked by the presence of irrelevant properties. When using Lehmann's rational closure, the inference machinery, which is then more productive, may still remain too cautious. These two types of inference can be represented using a possibility theory-based semantics. To overcome the cautiousness of system P, we first progressively augment preferential inference with two extensions which are in between system P and rational closure. Then, in order to overcome some remaining limitations of rational closure the second half of this paper focuses more particularly on the use of (contextual) independence assumptions of the form: the fact that is true (or is false) does not affect the validity of the rule normally if then . The modelling of such independence assumptions is discussed in the possibilistic framework. Algorithms are provided to jointly handle default rules and independence relations, and to check their multual consistency.     

Action-Based Causal Reasoning

In this paper we present a causal theory based on aninterventionist conception of causality, i.e., a preference toselect causes among a set of actions which an agent has the abilityto perform or not to perform (free will). The most interestingproposals encountered in the literature, in nonmonotonic reasoning,all revolve around the ordered notion of similarity, abnormality,preference etc... but do not provide a full-fledgedsolution to the problem of the concrete definition of this order. Inour approach we relate the notion of action to norms (what isnormally the case when an action is undertaken, what is normally theoutcome of that action) and considering reasonable assumptions, weshow the existence and uniqueness of the set of voluntary causes foran observed effect (explanation problem). Moreover, the approach advocated in this paper handles ramifications correctly.     

An Empirical Test of Patterns for Nonmonotonic Inference

Human inference can be used to test the inference patterns a reliable nonmonotonic consequence should satisfy, because it appears to be nonmonotonic, it is adaptive and it generally achieves efficiency. In this study, an experiment is conducted to investigate whether human inference tends to be consistent with rationality postulates (System P plus Rational Monotony), especially when it no longer satisfies the Monotony property. The experimental protocol uses a possibilistic semantics for plausible rules. Our results appear to be consistent with all the studied properties. Exceptions are the Cut property (with one kind of content out of two) and Left Logical Equivalence which could not be tested. Moreover, when Monotony was not satisfied by participants' inferences, Cut, Cautious Monotony and And properties were corroborated (Rational Monotony was only plausibly supported and the other properties were not tested). Our results emphasize the psychological plausibility of rationality postulates and support the working hypothesis in Artificial Intelligence that System P plus Rational Monotony offer a plausible basic set of properties for nonmonotonic logics.     

行动推理中循环因果关系的研究

近年来行动推理的研究成为人工智能领域的热门问题,而结果问题是目前行动推理研究的核心问题之一．该文针对许多行动推理系统不能处理循环因果关系的问题,提出了解决方法．基于适当修改后的McCain和Turner的因果理论,该文提出了一种能处理循环依赖的理论转化方法．转化后的因果理论消除了循环依赖,而且可以采用单调推理方法．基于因果闭包语义,证明了转化前后的因果理论具有相同的模型．当因果关系不存在循环依赖时,该文方法得到与McCain,Turner方法(1997)相同的结果．     

What Should Default Reasoning be,by Default?

This is a position paper concerning the role of empirical studies of human default reasoning in the formalization of AI theories of default reasoning. We note that AI motivates its theoretical enterprise by reference to human skill at default reasoning, but that the actual research does not make any use of this sort of information and instead relies on intuitions of individual investigators. We discuss two reasons theorists might not consider human performance relevant to formalizing default reasoning: (a) that intuitions are sufficient to describe a model, and (b) that human performance in this arena is irrelevant to a competence model of the phenomenon. We provide arguments against both these reasons. We then bring forward three further considerations against the use of intuitions in this arena: (a) it leads to an unawareness of predicate ambiguity, (b) it presumes an understanding of ordinary language statements of typicality, and (c) it is similar to discredited views in other fields. We advocate empirical investigation of the range of human phenomena that intuitively embody default reasoning. Gathering such information would provide data with which to generate formal default theories and against which to test the claims of proposed theories. Our position is that such data are the very phenomena that default theories are supposed to explain.     

Nonmonotonic theories and their axiomatic varieties

The properties of monotonic inference systems and the properties of their theories are strongly linked. These links, however, are much weaker in nonmonotonic inference systems. In this paper we introduce the notion of anaxiomatic variety for a theory and show how this notion, instead of the notion of a theory, can be used for the syntactic and semantic analysis of nonmonotonic inferences.     

Probabilistic Reasoning Under Coherence in System P

In this paper we apply a probabilistic reasoning under coherence to System P. We consider a notion of strict probabilistic consistency, we show its equivalence to Adams' probabilistic consistency, and we give a necessary and sufficient condition for probabilistic entailment. We consider the inference rules of System P in the framework of coherent imprecise probabilistic assessments. Exploiting our coherence-based approach, we propagate the lower and upper probability bounds associated with the conditional assertions of a given knowledge base, obtaining the precise probability bounds for the derived conclusions of the inference rules. This allows a more flexible and realistic use of System P in default reasoning and provides an exact illustration of the degradation of the inference rules when interpreted in probabilistic terms. We also examine the disjunctive Weak Rational Monotony rule of System P⁺ proposed by Adams in his extended probabilistic logic. Finally, we examine the propagation of lower bounds with real -values and, to illustrate our probabilistic reasoning, we consider an example.