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.     

'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.     

A Critical Reexamination of Default Logic, Autoepistemic Logic, and Only Knowing

Fifteen years of work on nonmonotonic logic has certainly increased our understanding of the area. However, given a problem in which nonmonotonic reasoning is called for, it is far from clear how one should go about modeling the problem using the various approaches. We explore this issue in the context on two of the best–known approaches, Reiter's default logic and Moore's autoepistemic logic, as well as two related notions of "only knowing," due to Halpern and Moses and to Levesque. In particular, we return to the original technical definitions given in these papers and examine the extent to which they capture the intuitions they were designed to capture.     

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.     

Reasoning with Sets of Defaults in Default Logic

We present a general approach for representing and reasoning with sets of defaults in default logic, focusing on reasoning about preferences among sets of defaults. First, we consider how to control the application of a set of defaults so that either all apply (if possible) or none do (if not). From this, an approach to dealing with preferences among sets of default rules is developed. We begin with an ordered default theory , consisting of a standard default theory, but with possible preferences on sets of rules. This theory is transformed into a second, standard default theory wherein the preferences are respected. The approach differs from other work, in that we obtain standard default theories and do not rely on prioritized versions of default logic. In practical terms this means we can immediately use existing default logic theorem provers for an implementation. Also, we directly generate just those extensions containing the most preferred applied rules; in contrast, most previous approaches generate all extensions, then select the most preferred. In a major application of the approach, we show how semimonotonic default theories can be encoded so that reasoning can be carried out at the object level. With this, we can reason about default extensions from within the framework of a standard default logic. Hence one can encode notions such as skeptical and credulous conclusions, and can reason about such conclusions within a single extension.     

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.     

N-SHOQ(D): 描述逻辑SHOQ(D)的一个非单调扩展

描述逻辑SHOQ(D)给出了Web本体语言DAML+OIL的语义,但SHOQ(D)只能处理严格成立的完备 知识,不能处理在实际情况中经常出现的不完备知识.对描述逻辑SHOQ(D)进行扩展,提出了 能够处理不完备知识的非单调描述逻辑N-SHOQ(D).给出了N-SHOQ(D)的语法和语义,定义了N -SHOQ(D)中的蕴涵推理关系,研究了N-SHOQ(D)所具有的性质. N-SHOQ(D)为扩展DAML+OIL语 言到能够处理不完备知识的情形提供了语义支持.     

Embedding defaults into terminological knowledge representation formalisms

We consider the problem of integrating Reiter's default logic into terminological representation systems. It turns out that such an integration is less straightforward than we expected, considering the fact that the terminological language is a decidable sublanguage of first-order logic. Semantically, one has the unpleasant effect that the consequences of a terminological default theory may be rather unintuitive, and may even vary with the syntactic structure of equivalent concept expressions. This is due to the unsatisfactory treatment of open defaults via Skolemization in Reiter's semantics. On the algorithmic side, we show that this treatment may lead to an undecidable default consequence relation, even though our base language is decidable, and we have only finitely many (open) defaults. Because of these problems, we then consider a restricted semantics for open defaults in our terminological default theories: default rules are applied only to individuals that are explicitly present in the knowledge base. In this semantics it is possible to compute all extensions of a finite terminological default theory, which means that this type of default reasoning is decidable. We describe an algorithm for computing extensions and show how the inference procedures of terminological systems can be modified to give optimal support to this algorithm.This is a revised and extended version of a paper presented at the3rd International Conference on Principles of Knowledge Representation and Reasoning, October 1992, Cambridge, MA.     

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.     

Bilattices and Reasoning in Artificial Intelligence: Concepts and Foundations

The past few decades have seen a resurgence ofreasoning techniques in artificial intelligenceinvolving both classical and non-classical logics. Inhis paper, ``Multi-valued Logics: A Uniform Approach toReasoning in Artificial Intelligence', Ginsberg hasshown that through the use of bilattices,several reasoning techniques can be unified under asingle framework. A bilattice is a structure that canbe viewed as a class of truth values that canaccommodate incomplete and inconsistent informationand in certain cases default information. Inbilattice theory, knowledge is ordered along twodimensions: truth/falsity and certainty/uncertainty. By defining the corresponding bilattices as truthspaces, Ginsberg has shown that the same theoremprover can be used to simulate reasoning in firstorder logic, default logic, prioritized default logicand assumption truth maintenance system. Although thisis a significant contribution, Ginsberg's paper waslengthy and involved. This paper summarizes some ofthe essential concepts and foundations of bilatticetheory. Furthermore, it discusses the connections ofbilattice theory and several other existingmulti-valued logics such as the various three-valuedlogics and Belnap's four-valued logic. It is notedthat the set of four truth values in Belnap's logicform a lattice structure that is isomorphic to thesimplest bilattice. Subsequently, Fitting proposed aconflation operation that can be used to selectsub-sets of truth values from this and otherbilattices. This method of selecting sub-sets oftruth values provides a means for identifyingsub-logic in a bilattice.     

Informational Logic as a Tool for Automated Reasoning

A logical entropy-based Informational Logic is presented which provides new tools for probabilistic automated reasoning and knowledge representation. Applications in automated theorem proving are examined, and a decision theory for probabilistic theorems is proposed.     

Combinations of Modal Logics

There is increasing use of combinations of modal logics in bothfoundational and applied research areas. This article provides anintroduction to both the principles of such combinations and to thevariety of techniques that have been developed for them. In addition,the article outlines many key research problems yet to be tackledwithin this callenging area of work.     

DEFAULT LOGICS: A UNIFIED VIEW

Default logic has been introduced for handling reasoning with incomplete knowledge. It has been widely studied, and various definitions have been proposed for it. Most of the variants have been defined by means of fixed points of some operator. We propose here another approach, which is based on a study of the way in which general rules with exceptions, used in a default reasoning process, can contradict one another. We then isolate sets of noncontradicting rules, as large as possible in order to exploit as much information as possible, and construct, for each of these sets of rules, the set of conclusions that can be deduced from it. We show that our framework encompasses most of the existing variants of default logic, allowing those variants to be compared from a knowledge representation point of view. Our approach also enables us to provide an operational definition of extensions in some interesting cases. Proof-theoretical and semantical aspects are investigated.