Nonmonotonic Logic

gramming environment, BABY-SIT, which is based on situation theory. We then demonstrate how problems requir-.

Agents which perform inferences on the basis of unreliable information need an ability to revise their beliefs if they discover an inconsistency. Such a belief revision algorithm ideally should be rational, should respect any preference ordering over the agent’s beliefs (removing less preferred beliefs where possible) and should be fast. However, while standard approaches to rational belief revision for classical reasoners allow preferences to be taken into account, they typically have quite high complexity. In this paper, we consider belief revision (...) for agents which reason in a simpler logic than full first-order logic, namely rule-based reasoners. We show that it is possible to define a contraction operation for rule-based reasoners, which we call McAllester contraction, which satisfies all the basic Alchourrón, Gärdenfors and Makinson (AGM) postulates for contraction (apart from the recovery postulate) and at the same time can be computed in polynomial time. We prove a representation theorem for McAllester contraction with respect to the basic AGM postulates (minus recovery), and two additional postulates. We then show that our contraction operation removes a set of beliefs which is least preferred, with respect to a natural interpretation of preference. Finally, we show how McAllester contraction can be used to define a revision operation which is also polynomial time, and prove a representation theorem for the revision operation. (shrink)

The traditional connection between logic and reasoning has been under pressure ever since Gilbert Harman attacked the received view that logic yields norms for what we should believe. In this article I first place Harman's challenge in the broader context of the dialectic between logical revisionists like Bob Meyer and sceptics about the role of logic in reasoning like Harman. I then develop a formal model based on contemporary epistemic and doxastic logic in which the relation between logic and norms (...) for belief can be captured. (shrink)

Modal logics have in the past been used as a unifying framework for the minimality semantics used in defeasible inference, conditional logic, and belief revision. The main aim of the present paper is to add adaptive logics, a general framework for a wide range of defeasible reasoning forms developed by Diderik Batens and his co-workers, to the growing list of formalisms that can be studied with the tools and methods of contemporary modal logic. By characterising the class of abnormality models, (...) this aim is achieved at the level of the model-theory. By proposing formulae that express the consequence relation of adaptive logic in the object-language, the same aim is also partially achieved at the syntactical level. (shrink)

In this paper we provide a formal description of what it means to be in a local or partial information-state. Starting from the notion of locality in a relational structure, we define so-called adaptive gen- erated submodels. The latter are then shown to yield an adaptive logic wherein the derivability of Pφ is naturally interpreted as a core property of being in a state in which one holds the information that φ.

The term "non-monotonic logic" covers a family of formal frameworks devised to capture and represent defeasible inference , i.e., that kind of inference of everyday life in which reasoners draw conclusions tentatively, reserving the right to retract them in the light of further information. Such inferences are called "non-monotonic" because the set of conclusions warranted on the basis of a given knowledge base does not increase (in fact, it can shrink) with the size of the knowledge base itself. This is (...) in contrast to classical (first-order) logic, whose inferences, being deductively valid, can never be "undone" by new information. (shrink)

I present a possible worlds semantics for a hyperintensional belief revision operator, which reduces the logical idealization of cognitive agents affecting similar operators in doxastic and epistemic logics, as well as in standard AGM belief revision theory. belief states are not closed under classical logical consequence; revising by inconsistent information does not perforce lead to trivialization; and revision can be subject to ‘framing effects’: logically or necessarily equivalent contents can lead to different revisions. Such results are obtained without resorting to (...) non-classical logics, or to non-normal or impossible worlds semantics. The framework combines, instead, a standard semantics for propositional S5 with a simple mereology of contents. (shrink)

I want to model a finite, fallible cognitive agent who imagines that p in the sense of mentally representing a scenario—a configuration of objects and properties—correctly described by p. I propose to capture imagination, so understood, via variably strict world quantifiers, in a modal framework including both possible and so-called impossible worlds. The latter secure lack of classical logical closure for the relevant mental states, while the variability of strictness captures how the agent imports information from actuality in the imagined (...) non-actual scenarios. Imagination turns out to be highly hyperintensional, but not logically anarchic. Section 1 sets the stage and impossible worlds are quickly introduced in Sect. 2. Section 3 proposes to model imagination via variably strict world quantifiers. Section 4 introduces the formal semantics. Section 5 argues that imagination has a minimal mereological structure validating some logical inferences. Section 6 deals with how imagination under-determines the represented contents. Section 7 proposes additional constraints on the semantics, validating further inferences. Section 8 describes some welcome invalidities. Section 9 examines the effects of importing false beliefs into the imagined scenarios. Finally, Sect. 10 hints at possible developments of the theory in the direction of two-dimensional semantics. (shrink)

We study probabilistic logic under the viewpoint of the coherence principle of de Finetti. In detail, we explore how probabilistic reasoning under coherence is related to model- theoretic probabilistic reasoning and to default reasoning in System . In particular, we show that the notions of g-coherence and of g-coherent entailment can be expressed by combining notions in model-theoretic probabilistic logic with concepts from default reasoning. Moreover, we show that probabilistic reasoning under coherence is a generalization of default reasoning in System (...) . That is, we provide a new probabilistic semantics for System , which neither uses infinitesimal probabilities nor atomic bound (or big-stepped) probabilities. These results also provide new algorithms for probabilistic reasoning under coherence and for default reasoning in System , and they give new insight into default reasoning with conditional objects. (shrink)

Plausible Logic allows defeasible deduction with arbitrary propositions, and yet when sufficiently simplified it is very similar to the Defeasible Logics of Billington and Nute. This paper presents Plausible Logic, explains some of the ideas behind the definitions, applies Plausible Logic to an example, and proves a coherence result which indicates that Plausible Logic is well behaved. We also report the first complete implementation of propositional Plausible Logic. The implementation has a web interface which makes it available to researchers and (...) students everywhere. The implementation is evaluated experimentally, and is shown to be capable of handling tens of thousands of rules and sufficiently many disjunctions for realistic problems. (shrink)

This is the first book that integrates nonmonotonic reasoning and belief change into a single framework from an artificial intelligence logic point-of-view.

A notion of an epistemic state is introduced as a generalization of common representations suggested for belief change. Based on it, a new kind of nonmonotonic inference relation corresponding to belief contractions is defined. A number of representation results is established that cover both traditional AGM contractions and contractions that do not satisfy recovery.

The belief base approach to belief representation and belief dynamics is developed as an alternative to the belief set approaches, which are pioneered by the AGM model. The belief base approach models collections of information and expectations of an agent as possibly incomplete and possibly inconsistent foundations for her beliefs. Nevertheless, the beliefs of an agent are always consistent; this is ensured by a sophisticated inference relation. Belief changes take place on the information base instead of on the belief set, (...) providing a reasonable account of belief change, for the content of the information base is much smaller than a closed belief set, and directly accessible by the agent for its elements are characterized as explicit and non- inferential information the agent acquires, while the closed belief set represents what the agent is committed to believe. In chapter 2, I present an investigation of the belief base approach, both its statics (formation of beliefs from an information base) and its dynamics, while presenting the consequences of the approach; as well as a brief investigation of the AGM model as the representative of the belief set approaches, to make comparisons between the two approaches. In chapter 3, I offer a modal model of the statics of the belief base approach using situation semantics. The choice of semantics is primarily due to that situation semantics can model incomplete and inconsistent collections of sentences. The belief modality offered in this model is intended to capture the inference process in the belief base approach as much as possible. (shrink)

Machine learning and nonmonotonic reasoning are closely related, both concerned with making plausible as well as certain inferences based on available data. In this document a brief overview of different approaches to nonmonotonic reasoning is presented, and it is shown how the concept of argumentation systems arises. The relationship with machine learning work is also discussed. The document aims to highlight the links between nonmonotonic reasoning, argumentation and machine learning and as a result propose some potentially useful directions for new (...) research. (shrink)

This note corrects an error in the statement and proof of Propositions 9 and 10 of [C. Cross, Nonmonotonic inconsistency, Artificial Intelligence 149 (2) (2003) 161–178]. Both results turn out to depend on the postulate of Consistency Preservation.

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. (shrink)

Peter Gärdenfors has proved (Philosophical Review, 1986) that the Ramsey rule and the methodologically conservative Preservation principle are incompatible given innocuous-looking background assumptions about belief revision. Gärdenfors gives up the Ramsey rule; I argue for preserving the Ramsey rule and interpret Gärdenfors's theorem as showing that no rational belief-reviser can avoid reasoning nonmonotonically. I argue against the Preservation principle and show that counterexamples to it always involve nonmonotonic reasoning. I then construct a new formal model of belief revision that does (...) accommodate nonmonotonic reasoning. (shrink)

We describe and try to motivate our project to build systems using both a knowledge based and a neural network approach. These two approaches are used at different stages in the solution of a problem, instead of using knowledge bases exclusively on some problems, and neural nets exclusively on others. The knowledge base (KB) is defined first in a declarative, symbolic language that is easy to use. It is then compiled into an efficient neural network (NN) representation, run, and the (...) results from run time and (eventually) from learning are decompiled to a symbolic description of the knowledge contained in the network. After inspecting this recovered knowledge, a designer would be able to modify the KB and go through the whole cycle of compiling, running, and decompiling again. The central question with which this project is concerned is, therefore, How do we go from a KB to an NN, and back again? We are investigating this question by building tools consisting of a repertoire of language/translation/network types, and trying them on problems in a variety of domains. (shrink)

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. (shrink)

Both the traditional Aristotelian and modern symbolic approaches to logic have seen logic in terms of discrete symbol processing. Yet there are several kinds of argument whose validity depends on some topological notion of continuous variation, which is not well captured by discrete symbols. Examples include extrapolation and slippery slope arguments, sorites, fuzzy logic, and those involving closeness of possible worlds. It is argued that the natural first attempts to analyze these notions and explain their relation to reasoning fail, so (...) that ignorance of their nature is profound. (shrink)

A. Tarski [22] proposed the study of infinitary consequence operations as the central topic of mathematical logic. He considered monotonicity to be a property of all such operations. In this paper, we weaken the monotonicity requirement and consider more general operations, inference operations. These operations describe the nonmonotonic logics both humans and machines seem to be using when infering defeasible information from incomplete knowledge. We single out a number of interesting families of inference operations. This study of infinitary inference operations (...) is inspired by the results of [12] on nonmonotonic inference relations, and relies on some of the definitions found there. (shrink)

We introduce a simple generalization of Gardenfors and Makinson’s epistemic entrenchment called partial entrenchment. We show that preferential inference can be generated as the sceptical counterpart of an inference mechanism defined directly on partial entrenchment.

We show that Gabbay’s nonmonotonic consequence relations c an be reduced to a new family of relations, called entrenchment relations. Entrenchment relations provide a direct generalization of epistemic entrenchment and expectation ordering introduced by G ̈ardenfors and Makinson for the study of belief revision and expectation inference, respectively.

Rational inference relations were introduced by Lehmann and Magidor as the ideal systems for drawing conclusions from a conditional base. However, there has been no simple characterization of these relations, other than its original representation by preferential models. In this paper, we shall characterize them with a class of total preorders of formulas by improving and extending G ̈ardenfors and Makinson’s results f or expectation inference relations. A second representation is application-oriented and is obtained by considering a class of consequence (...) operators that grade sets of defaults according to our reliance on them. The finitary fragment of this class of consequence operators has been employed by recent default logic formalisms based on maxiconsistency. (shrink)

The paper considers contemporary models of presumption in terms of their ability to contribute to a working theory of presumption for argumentation. Beginning with the Whatelian model, we consider its contemporary developments and alternatives, as proposed by Sidgwick, Kauffeld, Cronkhite, Rescher, Walton, Freeman, Ullmann-Margalit, and Hansen. Based on these accounts, we present a picture of presumptions characterized by their nature, function, foundation and force. On our account, presumption is a modal status that is attached to a claim and has the (...) effect of shifting, in a dialogue, a burden of proof set at a local level. Presumptions can be analysed and evaluated inferentially as components of rule-based structures. Presumptions are defeasible, and the force of a presumption is a function of its normative foundation. This picture seeks to provide a framework to guide the development of specific theories of presumption. (shrink)

The Pleadings Game is a major contribution to artificial intelligence and legal theory. The book draws on jurisprudence and moral philosophy to develop a formal model of argumentation called the pleadings game. From a technical perspective, the work can be viewed as an extension of recent argumentation-based approaches to non-monotonic logic: (1) the game is dialogical rather than mono-logical; (2) the validity and priority of defeasible rules is subject to debate; and (3) resource limitations are acknowledged by rules for fairly (...) dividing the burdens of representation and proof among the players. Gordon's work evaluates important jurisprudential theories of argumentation and reasoning in the context of the U.S. commercial law on secured transactions. Audience: It is not necessary to have a formal background in law to appreciate The Pleadings Game. It will be of equal interest to both the artificial intelligence community and legal theorists. (shrink)

The paper consists of three parts. In the first part five kinds of defeasibility are distinguished that is ontological, conceptual, epistemic, justification and logical defeasibility. In the second part it is argued that from these, justification defeat is the phenomenon that plays a role in legal reasoning. In the third part, the view is defended that non-monotonic logics are not necessary to model justification defeat, but that they are so to speak the natural way to model this phenomenon.

We present a formal semantics for epistemic logic, capturing the notion of knowability relative to information (KRI). Like Dretske, we move from the platitude that what an agent can know depends on her (empirical) information. We treat operators of the form K_AB (‘B is knowable on the basis of information A’) as variably strict quantifiers over worlds with a topic- or aboutness- preservation constraint. Variable strictness models the non-monotonicity of knowledge acquisition while allowing knowledge to be intrinsically stable. Aboutness-preservation models (...) the topic-sensitivity of information, allowing us to invalidate controversial forms of epistemic closure while validating less controversial ones. Thus, unlike the standard modal framework for epistemic logic, KRI accommodates plausible approaches to the Kripke-Harman dogmatism paradox, which bear on non-monotonicity, or on topic-sensitivity. KRI also strikes a better balance between agent idealization and a non-trivial logic of knowledge ascriptions. (shrink)

Rational consequence relations and Popper functions provide logics for reasoning under uncertainty, the former purely qualitative, the latter probabilistic. But few researchers seem to be aware of the close connection between these two logics. I’ll show that Popper functions are probabilistic versions of rational consequence relations. I’ll not assume that the reader is familiar with either logic. I present them, and explicate the relationship between them, from the ground up. I’ll also present alternative axiomatizations for each logic, showing them to (...) depend on weaker axioms than usually recognized. (shrink)

In a previous paper I described a range of nonmonotonic conditionals that behave like conditional probability functions at various levels of probabilistic support. These conditionals were defined as semantic relations on an object language for sentential logic. In this paper I extend the most prominent family of these conditionals to a language for predicate logic. My approach to quantifiers is closely related to Hartry Field's probabilistic semantics. Along the way I will show how Field's semantics differs from a substitutional interpretation (...) of quantifiers in crucial ways, and show that Field's approach is closely related to the usual objectual semantics. One of Field's quantifier rules, however, must be significantly modified to be adapted to nonmonotonic conditional semantics. And this modification suggests, in turn, an alternative quantifier rule for probabilistic semantics. (shrink)

I will describe the logics of a range of conditionals that behave like conditional probabilities at various levels of probabilistic support. Families of these conditionals will be characterized in terms of the rules that their members obey. I will show that for each conditional, →, in a given family, there is a probabilistic support level r and a conditional probability function P such that, for all sentences C and B, 'C → B' holds just in case P[B | C] ≥ (...) r. Thus, each conditional in a given family behaves like conditional probability above some specific support level. (shrink)

Any inferential system in which the addition of new premises can lead to the retraction of previous conclusions is a non-monotonic logic. Classical conditional probability provides the oldest and most widely respected example of non-monotonic inference. This paper presents a semantic theory for a unified approach to qualitative and quantitative non-monotonic logic. The qualitative logic is unlike most other non- monotonic logics developed for AI systems. It is closely related to classical (i.e., Bayesian) probability theory. The semantic theory for qualitative (...) non-monotonic entailments extends in a straightforward way to a semantic theory for quantitative partial entailment relations, and these relations turn out to be the classical probability functions. (shrink)

We chart the ways in which closure properties of consequence relations for uncertain inference take on different forms according to whether the relations are generated in a quantitative or a qualitative manner. Among the main themes are: the identification of watershed conditions between probabilistically and qualitatively sound rules; failsafe and classicality transforms of qualitatively sound rules; non-Horn conditions satisfied by probabilistic consequence; representation and completeness problems; and threshold-sensitive conditions such as `preface' and `lottery' rules.

In substructural logics, structural principles may hold in some fragments of a consequence relation without holding globally. I look at this phenomenon in my preferred substructural logic, in which Weakening and Cut fail but which is supra-intuitionistic. I introduce object language operators that keep track of the admissibility of Weakening and of intuitionistic implications. I end with some ideas about local transitivity.

I am presenting a sequent calculus that extends a nonmonotonic consequence relation over an atomic language to a logically complex language. The system is in line with two guiding philosophical ideas: (i) logical inferentialism and (ii) logical expressivism. The extension defined by the sequent rules is conservative. The conditional tracks the consequence relation and negation tracks incoherence. Besides the ordinary propositional connectives, the sequent calculus introduces a new kind of modal operator that marks implications that hold monotonically. Transitivity fails, but (...) for good reasons. Intuitionism and classical logic can easily be recovered from the system. (shrink)

This paper points out some problems with two recent logical systems – one due to Prakken and Sartor, the other due to Kowalski and Toni – designedfor the representation of defeasible arguments in general, but with a specialemphasis on legal reasoning.

From a philosophical standpoint, the work presented here is based on van Fraassen [26]. The bulk of that paper is organized around a series of arguments against the assumption, built into standard deontic logic, that moral dilemmas are impossible; and van Fraassen only briefly sketches his alternative approach. His paper ends with the conclusion that “the problem of possibly irresolvable moral conflict reveals serious flaws in the philosophical and semantic foundations of ‘orthodox’ deontic logic, but also suggests a rich set (...) of new problems and methods for such logic.” My goal has been to suggest that some of these methods might be found in current research on nonmonotonic reasoning, and that some of the problems may have been confronted there as well.I have shown that nonmonotonic logics provide a natural framework for reasoning about moral dilemmas, perhaps even more useful than the ordinary modal framework, and that the issues surrounding the treatment of exceptional information within these logics run parallel to some of the problems posed by conditional oughts. However, there is also another way in which deontic logic might benefit from a connection to nonmonotonic reasoning. A familiar criticism among ethicists of work in deontic logic is that it is too abstract, and too far removed from the kind of problems confronted by real agents in moral deliberation. It must be said that similar criticisms of abstraction and irrelevance are often lodged against work in nonmonotonic reasoning by more practically minded researchers in artificial intelligence; but here, at least, the criticisms are taken seriously. Nonmonotonic logic aims at a qualitative account of commonsense reasoning, which can be used to relate planning and action to defeasible goals and beliefs; and at least some of the theories developed in this area have been tested in realistic situations. By linking the subject of deontic logic to this research, it may be possible also to relate the idealized study of moral reasoning typical of the field to a more robust treatment of practical deliberation. (shrink)