Nonmonotonic reasoning with multiple belief sets

In complex reasoning tasks it is often the case that there is no single, correct set of conclusions given some initial information. Instead, there may be several such conclusion sets, which we will call belief sets. In the present paper we introduce nonmonotonic belief set operators and selection operators to formalize and to analyze structural aspects of reasoning with multiple belief sets. We define and investigate formal properties of belief set operators as absorption, congruence, supradeductivity and weak belief monotony. Furthermore, it is shown that for each belief set operator satisfying strong belief cumulativity there exists a largest monotonic logic underlying it, thus generalizing a result for nonmonotonic inference operations. Finally, we study abstract properties of selection operators connected to belief set operators, which are used to choose some of the possible belief sets. This revised version was published online in June 2006 with corrections to the Cover Date.     

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.     

认识逻辑(1):关于知识和信念的逻辑框架

知识和信念是人工智能领域研究中经常涉及到的两个重要概念。本文讨论了知识和信念的涵义与关系，定义了认识逻辑系统ＥＩ，讨论了它的语法和语义，证明了认识逻辑ＥＬ不但是可靠的而且是完备的，认为逻辑ＥＬ不但可以用来描述人类的认识过程，还可以用于对常识推理以及分布式系统的形式化描述。     

Programming in temporal-nonmonotonic reasoning

Nonmonotonic reasoning has been proposed as an extension to classical first-order logic. Now people are interested in temporal reasoning with nonmonotonic logic [6]. We combine the monotonic logic [7] with a temporal logic to get a more general reasoning language. We discuss a monotonic logic TML which has predicate formulas, temporal formulas and a special modal formula, and give a completeness theorem of it. We use TH() to designate the set of theorems of a temporal-nonmonotonic theory which has the same language with TML. The completeness theorem of the temporal-nonmonotonic logic naturally arises. Like the relationship between predicate logic with a practical logic programming language PROLOG, we propose a useful temporal-nonmonotonic reasoning language TN for the temporal-nonmonotonic logic. As an appendix we supply an algorithm for the programming language TN.     

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

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

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.     

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.     

Minimal Belief and Negation as Failure in Multi-Agent Systems

We propose an epistemic, nonmonotonic approach to the formalization of knowledge in a multi-agent setting. From the technical viewpoint, a family of nonmonotonic logics, based on Lifschitz's modal logic of minimal belief and negation as failure, is proposed, which allows for formalizing an agent which is able to reason about both its own knowledge and other agents' knowledge and ignorance. We define a reasoning method for such a logic and characterize the computational complexity of the major reasoning tasks in this formalism. From the practical perspective, we argue that our logical framework is well-suited for representing situations in which an agent cooperates in a team, and each agent is able to communicate his knowledge to other agents in the team. In such a case, in many situations the agent needs nonmonotonic abilities, in order to reason about such a situation based on his own knowledge and the other agents' knowledge and ignorance. Finally, we show the effectiveness of our framework in the robotic soccer application domain.     

On a rule-based interpretation of default conditionals

In nonmonotonic reasoning, a default conditional α→β has most often been informally interpreted as a defeasible version of a classical conditional, usually the material conditional. There is however an alternative interpretation, in which a default is regarded essentially as a rule, leading from premises to conclusion. In this paper, we present a family of logics, based on this alternative interpretation. A general semantic framework under this rule-based interpretation is developed, and associated proof theories for a family of weak conditional logics is specified. Nonmonotonic inference is easily defined in these logics. Interestingly, the logics presented here are weaker than the commonly-accepted base conditional approach for defeasible reasoning. However, this approach resolves problems that have been associated with previous approaches.      

Epistemic Logic for Rule-Based Agents

The logical omniscience problem, whereby standard models of epistemic logic treat an agent as believing all consequences of its beliefs and knowing whatever follows from what else it knows, has received plenty of attention in the literature. But many attempted solutions focus on a fairly narrow specification of the problem: avoiding the closure of belief or knowledge, rather than showing how the proposed logic is of philosophical interest or of use in computer science or artificial intelligence. Sentential epistemic logics, as opposed to traditional possible worlds approaches, do not suffer from the problems of logical omniscience but are often thought to lack interesting epistemic properties. In this paper, I focus on the case of rule-based agents, which play a key role in contemporary AI research but have been neglected in the logical literature. I develop a framework for modelling monotonic, nonmonotonic and introspective rule-based reasoners which have limited cognitive resources and prove that the resulting models have a number of interesting properties. An axiomatization of the resulting logic is given, together with completeness, decidability and complexity results.     

Representing model theory in a type-theoretical logical framework

In a broad sense, logic is the field of formal languages for knowledge and truth that have a formal semantics. It tends to be difficult to give a narrower definition because very different kinds of logics exist. One of the most fundamental contrasts is between the different methods of assigning semantics. Here two classes can be distinguished: model theoretical semantics based on a foundation of mathematics such as set theory, and proof theoretical semantics based on an inference system possibly formulated within a type theory.Logical frameworks have been developed to cope with the variety of available logics unifying the underlying ontological notions and providing a meta-theory to reason abstractly about logics. While these have been very successful, they have so far focused on either model or proof theoretical semantics. We contribute to a unified framework by showing how the type/proof theoretical Edinburgh Logical Framework (LF) can be applied to the representation of model theoretical logics.We give a comprehensive formal representation of first-order logic, covering both its proof and its model theoretical semantics as well as its soundness in LF. For the model theory, we have to represent the mathematical foundation itself in LF, and we provide two solutions for that. Firstly, we give a meta-language that is strong enough to represent the model theory while being simple enough to be treated as a fragment of untyped set theory. Secondly, we represent Zermelo-Fraenkel set theory and show how it subsumes our meta-language. Specific models are represented as LF morphisms.All representations are given in and mechanically verified by the Twelf implementation of LF. Moreover, we use the Twelf module system to treat all connectives and quantifiers independently. Thus, individual connectives are available for reuse when representing other logics, and we obtain the first version of a feature library from which logics can be pieced together.Our results and methods are not restricted to first-order logic and scale to a wide variety of logical systems, thus demonstrating the feasibility of comprehensively formalizing large scale representation theorems in a logical framework.     

计算机科学中的一些逻辑理论的推理性质研究

由于一阶 词逻辑的基本特征是具有可靠性,完全性,在推广一阶谓词逻辑表达能力及扩充其推理能力时,可以定义了了一些具有可靠性,完全性的逻辑,对此,在分析逻辑理论特征的基础上,给出了一些逻辑的推理系统之间相似性的实质,证明这些逻辑在实质上并不能扩充一阶谓词逻辑的推理能力,并指出非常单调推理中的缺省推理及限定推理所采用的技术是扩充时必需的。     

An inquiry into computer understanding

This essay addresses a number of issues centered around the question of what is the best method for representing and reasoning about common sense (sometimes called plausible inference). Drew McDermott has shown that a direct translation of commonsense reasoning into logical form leads to insurmountable difficulties, from which McDermott concluded that we must resort to procedural ad hocery. This paper shows that the difficulties McDermott described are a result of insisting on using logic as the language of commonsense reasoning. If, instead, (Bayesian) probability is used, none of the technical difficulties found in using logic arise. For example, in probability, the problem of referential opacity cannot occur and nonmonotonic logics (which McDermott showed don't work anyway) are not necessary. The difficulties in applying logic to the real world are shown to arise from the limitations of truth semantics built into logic–probability substitutes the more reasonable notion of belief. In Bayesian inference, many pieces of evidence are combined to get an overall measure of belief in a proposition. This is much closer to commonsense patterns of thought than long chains of logical inference to the true conclusions. Also it is shown that English expressions of the “IF A THEN B” form are best interpreted as conditional probabilities rather than universally quantified expressions. Bayesian inference is applied to a simple example of linguistic information to illustrate the potential of this type of inference for AI. This example also shows how to deal with vague information, which has so far been the province of fuzzy logic. It is further shown that Bayesian inference gives a theoretical basis for inductive inference that is borne out in practice. Instead of insisting that probability is the best language for commonsense reasoning, a major point of this essay is to show that real inference is a complex interaction between probability, logic, and other formal representation and reasoning systems.     

Autoepistemic logic of first order and its expressive power

We study the expressive power of first-order autoepistemic logic. We argue that full introspection of rational agents should be carried out by minimizing positive introspection and maximizing negative introspection. Based on full introspection, we propose the maximal well-founded semantics that characterizes autoepistemic reasoning processes of rational agents, and show that breadth of the semantics covers all theories in autoepistemic logic of first order, Moore's AE logic, and Reiter's default logic. Our study demonstrates that the autoepistemic logic of first order is a very powerful framework for nonmonotonic reasoning, logic programming, deductive databases, and knowledge representation.This research is partially supported by NSERC grant OGP42193.     

人工智能科学中的概率逻辑

人工智能科学,从其诞生之日起便与逻辑学密不可分。本文首先对逻辑学的分类、相互关系以及泛逻辑的概念等进行了讨论,并对人工智能中逻辑学的应用及发展进行了必要的分析。然后讲述了逻辑学与概率论两大理论基础之上的不确定性推理方法——概率逻辑,重点研究了二值概率逻辑与三值概率逻辑。最后阐述了概率逻辑在人工智能科学中的应用以及对它的思考。     

Coalgebraic semantics of modal logics: An overview

Coalgebras can be seen as a natural abstraction of Kripke frames. In the same sense, coalgebraic logics are generalised modal logics. In this paper, we give an overview of the basic tools, techniques and results that connect coalgebras and modal logic. We argue that coalgebras unify the semantics of a large range of different modal logics (such as probabilistic, graded, relational, conditional) and discuss unifying approaches to reasoning at this level of generality. We review languages defined in terms of the so-called cover modality, languages induced by predicate liftings as well as their common categorical abstraction, and present (abstract) results on completeness, expressiveness and complexity in these settings, both for basic languages as well as a number of extensions, such as hybrid languages and fixpoints.     

Nonmonotonic inconsistency

Nonmonotonic consequence is the subject of a vast literature, but the idea of a nonmonotonic counterpart of logical inconsistency—the idea of a defeasible property representing internal conflict of an inductive or evidential nature—has been entirely neglected. After considering and dismissing two possible analyses relating nonmonotonic consequence and a nonmonotonic counterpart of logical inconsistency, this paper offers a set of postulates for nonmonotonic inconsistency, an analysis of nonmonotonic inconsistency in terms of nonmonotonic consequence, and a series of results showing that nonmonotonic inconsistency conforms to these postulates given the analysis of nonmonotonic inconsistency presented here and certain postulates for nonmonotonic consequence.The results presented here establish the interest of certain previously undiscussed postulates of nonmonotonic consequence. These results also show that nonmonotonicity, which has never seemed useful in the formulation of general principles governing nonmonotonic reasoning, is relevant to the positive characterization of nonmonotonic inference after all.