The First International Workshop brings together researchers from the theoretical ends of the logic programming and artificial intelligence communities to discuss their mutual interests. Logic programming deals with the use of models of mathematical logic as a way of programming computers, where theoretical AI deals with abstract issues in modeling and representing human knowledge and beliefs. One common ground is nonmonotonic reasoning, a family of logics that includes room for the kinds of variations that can be (...) found in human reasoning. Topics covered: Stable Semantics. Default Logic. AutoEpistemic Logic. Truth Maintenance Systems. Implementation Issues. Diagnosis. Applications. Inheritance Reasoning. Logics of Belief. Inconsistency and Non-Monotonicity. (shrink)

The Joint International Conference on Logic Programming, sponsored by the Association for Logic Programming, is a major forum for presentations of research, applications, and implementations in this important area of computer science. Logic programming is one of the most promising steps toward declarative programming and forms the theoretical basis of the programming language Prolog and its various extensions. Logic programming is also fundamental to work in artificial intelligence, where it has been used for nonmonotonic and (...) commonsense reasoning, expert systems implementation, deductive databases, and applications such as computer-aided manufacturing. Krzysztof R. Apt is project leader at the Centre for Mathematics and Computer Science in Amsterdam and part-time Professor in Computer Science at the University of Amsterdam. Topics covered: Theory Foundations. Programming Languages. Implementation. Programming Methodologies and Tools. Applications. Deductive Databases. Artificial Intelligence. Parallelism. (shrink)

Nonmonotonic logics were created as an abstraction of some types of common sense reasoning, analogous to the way classical logic serves to formalize ideal reasoning about mathematical objects. These logics are nonmonotonic in the sense that enlarging the set of axioms does not necessarily imply an enlargement of the set of formulas deducible from these axioms. Such situations arise naturally, for example, in the use of information of different degrees of reliability. This book emphasizes basic concepts by (...) outlining connections between different formalisms of nonmonotonic logic, and gives a coherent presentation of recent research results and reasoning techniques. It provides a self-contained state-of-the-art survey of the area addressing researchers in AI lo. (shrink)

A textbook for graduate students of philosophy, computer science, and mathematics, on various approaches to nonmonotonic logic, with emphasis on they way in which they fall into an overall pattern.

An graduate level introduction to nonmonotonic reasoning, emphasizing structures and spirit common to different formulations, with exercises.

Logics are like shadows on a wall; to understand why they dance as they do, and how they can be made to move differently, one needs to look at the mathematical structures from which they can be projected. That is a methodology that has long proven its value for classical and other forms of deductive inference; this book manifests its pertinence to logics of uncertain qualitative reasoning. It draws together and refines work from the literature on preferential and other quite (...) different semantics for such reasoning and then, in its central chapter, integrates the leading ideas from them into a single multi-dimensional semantics. It enters new territory with investigations of interpolation and qualitative independence in non-monotonic contexts as well as connections between non-monotonic logic and neuroscience, specifically with Edelman's theory of organization of the brain. Finally, it proposes novel applications such as equational modellings for contrary-to-duty normative reasoning and mathematical analyses of some kinds of casuistic reasoning in the Talmudic tradition. Profusely signposted at every turn, the volume is accessible to readers equipped with a modicum of set theory and abstract algebra. Visitors to the area can come in by the front gate and work their way, in various orders, through as much of the garden as strikes their fancy; specialists will enter at Chap. 11 or at whatever special topic interests them, well assured that they can easily backtrack to whatever bits and pieces are needed from what they skipped. A volume with a clear vision, a book to return to many times." (David Makinson). (shrink)

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)

The paper presents an exhaustive menu of nonmonotonic logics. The options are individuated in terms of the principles they reject. I locate, e.g., cumulative logics and relevance logics on this menu. I highlight some frequently neglected options, and I argue that these neglected options are particularly attractive for inferentialists.

The goal of a logic is to define a consequence relation between a set of formulas Γ and, in most cases, an individual formula A. This definition generally takes one of two forms. From a proof theoretic standpoint, A is said to be a consequence of Γ whenever there is a deduction of A from the set Γ, viewed as a set of premises; from a model theoretic standpoint, A is said to be a consequence of Γ whenever A (...) holds in every model that satisfies each formula in Γ. (shrink)

The purpose of this paper is to take some of the mystery out of what is known as nonmonotonic logic, by showing that it is not as unfamiliar as may at first sight appear. In fact, it is easily accessible to anybody with a background in classical propositional logic, provided that certain misunderstandings are avoided and a tenacious habit is put aside. In effect, there are logics that act as natural bridges between classical consequence and the principal (...) kinds of nonmonotonic logic to be found in the literature. Like classical logic, they are perfectly monotonic, but they already display some of the distinctive features of the nonmonotonic systems. As well as providing easy conceptual passage to the nonmonotonic case these logics, which we call paraclassical, have an interest of their own. (shrink)

Judgment aggregation studies how to aggregate individual judgments on logically correlated propositions into collective judgments. Different logics can be used in judgment aggregation, for which Dietrich and Mongin have proposed a generalized model based on general logics. Despite its generality, however, all nonmonotonic logics are excluded from this model. This paper argues for using nonmonotonic logic in judgment aggregation. Then it generalizes Dietrich and Mongin’s model to incorporate a large class of nonmonotonic logics. This generalization broadens (...) the theoretical boundaries of judgment aggregation by proving that, even if these nonmonotonic logics are employed, certain typical impossibility results still hold. (shrink)

In this essay I enter into a recently published debate between Stephen Schiffer and Jerry Fodor concerning whether adequate sense can be made of the ceteris paribus conditions in special science laws, much of their focus being on the case of putative psychological laws. Schiffer argues that adequate sense cannot be made of ceteris paribus clauses, while Fodor attempts to overcome Schiffer's arguments, in defense of special science laws. More recently, Peter Mott has attempted to show that Fodor's response to (...) Schiffer fails, and furthermore that further study shows that the logical framework in which Schiffer and Fodor address their issue is susceptible to inconsistency.In this essay I argue that adequate sense can be made of ceteris paribus conditions. Against Mott, I argue that recent work in the model theory of non-monotonic logic indicates how his problem involving logical inconsistencies can be overcome. Against Schiffer, I argue that the claims that he makes against ceteris paribus clauses would lead to a fatal skepticism concerning indefinitely many of the claims we make about the world (and indeed that his claims would be destructive of the view of the special sciences that Schiffer himself presents in his paper), and that the semantical considerations from non-monotonic logic that I present provide a suitable framework for dealing with his complaints. Thus I come out on the whole on Fodor's side of this debate, although for my own reasons, as I argue against much of Fodor's own argumentation. (shrink)

We present a straightforward embedding of modal nonmonotonic logics into default logic.

Interpretation is the process whereby a hearer reasons to an interpretation of a speaker's discourse. The hearer normally adopts a credulous attitude to the discourse, at least for the purposes of interpreting it. That is to say the hearer tries to accommodate the truth of all the speaker's utterances in deriving an intended model. We present a nonmonotonic logical model of this process which defines unique minimal preferred models and efficiently simulates a kind of closed-world reasoning of particular interest (...) for human cognition. Byrne's “suppression” data (Byrne, 1989) are used to illustrate how variants on this logic can capture and motivate subtly different interpretative stances which different subjects adopt, thus indicating where more fine-grained empirical data are required to understand what subjects are doing in this task. We then show that this logical competence model can be implemented in spreading activation network models. A one pass process interprets the textual input by constructing a network which then computes minimal preferred models for (3-valued) valuations of the set of propositions of the text. The neural implementation distinguishes easy forward reasoning from more complex backward reasoning in a way that may be useful in explaining directionality in human reasoning. (shrink)

Interpretation is the process whereby a hearer reasons to an interpretation of a speaker's discourse. The hearer normally adopts a credulous attitude to the discourse, at least for the purposes of interpreting it. That is to say the hearer tries to accommodate the truth of all the speaker's utterances in deriving an intended model. We present a nonmonotonic logical model of this process which defines unique minimal preferred models and efficiently simulates a kind of closed-world reasoning of particular interest (...) for human cognition. Byrne's “suppression” data (Byrne, 1989) are used to illustrate how variants on this logic can capture and motivate subtly different interpretative stances which different subjects adopt, thus indicating where more fine-grained empirical data are required to understand what subjects are doing in this task. We then show that this logical competence model can be implemented in spreading activation network models. A one pass process interprets the textual input by constructing a network which then computes minimal preferred models for (3-valued) valuations of the set of propositions of the text. The neural implementation distinguishes easy forward reasoning from more complex backward reasoning in a way that may be useful in explaining directionality in human reasoning. (shrink)

Examines the link between nonmonotonic inference relations and theory revision operations, focusing on the correspondence between abstract properties which each may satisfy.

David Makinson, "Bridges from Classical to Nonmonotonic Logic", King’s College Publications, London, 2005, pp. 216, ISBN 1-904987-00-1.

This paper is an effort to realize and explore the connections that exist between nonmonotonic logic and confirmation theory. We pick up one of the most wide-spread nonmonotonic formalisms – default logic – and analyze to what extent and under what adjustments it could work as a logic of induction in the philosophical sense. By making use of this analysis, we extend default logic so as to make it able to minimally perform the task (...) of a logic of induction, having as a result a system which we believe has interesting properties from the standpoint of theory of confirmation. It is for instance able to represent chains of inductive rules as well as to reason paraconsistently on the conclusions obtained from them. We then use this logic to represent some traditional ideas concerning confirmation theory, in particular the ones proposed by Carl Hempel in his classical paper "Studies in the Logic of Confirmation" of 1945 and the ones incorporated in the so-called abductive and hy-pothetico-deductive models. (shrink)

This dissertation develops, justifies, and examines the jurisprudential implications of a non-monotonic theory of common law legal reasoning. Legal rules seem to have exceptions but identifying all of them is difficult. This hinders attempts to formalize legal rules using classical logics. Non-monotonic logics allow defeasible inference, permitting rules that hold generally but can be defeated in the presence of exceptions. This ameliorates the problem of characterizing all exceptions to a rule, because exceptions can be added piecemeal while the rule remains. (...) The first portion of the dissertation rebuts a prominent criticism leveled at a large class of theories of legal reasoning that includes my theory. The charge is that no coherent theory can recognize both the difference between distinguishing and overruling, and the constraint of precedent. The critics argue that is more important than and that can only be explained by monotonic legal rules. Drawing on cognitive psychology as well as legal theory, I show that coherent theories, such as my own, can accommodate both and. The second chapter provides motivation for understanding precedential constraint in terms of non-monotonic default rules and introduces my positive theory, which elaborates on John Horty's work in treating legal rules as prioritized defaults involving reasons. I motivate and implement a relaxation of Horty's restrictions on the form of rules to allow a more fine-grained characterization of precedent. Finally, I explore the relationship between these relaxations and the concept of precedent. The final section explains how my theory fits into the traditional jurisprudential ecosystem. I demonstrate that, contrary to assertions in the legal theory literature, this non-monotonic approach is entirely compatible with positivism's commitment to extracting rules from authoritative legal sources, namely court opinions. I also suggest how it might be attractive to law and economics theorists, pragmatists, and followers of Dworkin. (shrink)

We defend a set of acceptance rules that avoids the lottery paradox, that is closed under classical entailment, and that accepts uncertain propositions without ad hoc restrictions. We show that the rules we recommend provide a semantics that validates exactly Adams’ conditional logic and are exactly the rules that preserve a natural, logical structure over probabilistic credal states that we call probalogic. To motivate probalogic, we first expand classical logic to geologic, which fills the entire unit cube, and (...) then we project the upper surfaces of the geological cube onto the plane of probabilistic credal states by means of standard, linear perspective, which may be interpreted as an extension of the classical condition of indifference. Finally, we apply the geometrical/logical methods developed in the paper to prove a series of trivialization theorems against question-invariance as a constraint on acceptance rules and against rational monotonicity as an axiom of conditional logic in situations of uncertainty. (shrink)

In this book the author gives a broad overview of different areas of research in nonmonotonic reasoning, and presents some new results and ideas based on his research. The guiding principles are: clarification of the different research activities in the area, which have sometimes been undertaken independently of each other; and appreciation of the fact that these research activities often represent different means to the same ends, namely sound theoretical foundations and efficient computation. The book begins with a discussion (...) of the various types of nonmonotonic reasoning, their applications and their logics. Theorem proving techniques for these logics are also described. The following chapters deal with formulations of nonmonotonic inheritance, and nonmonotonic reasoning based on nonmonotonic rules. The final chapter discusses the achievements in the field in the light of the Yale shooting example. The book will be welcomed by researchers in theoretical computer science and artificial intelligence. (shrink)

Using Gärdenfors's notion of epistemic entrenchment, we develop the semantics of a logic which accounts for the following points. It explains why we may generally infer `If ~A then B´ if all we know is AvB while must not generally infer `If ~A then B´ if all we know is {AvB, A}. More generally, it explains the nonmonotonic nature of the consequence relation governing languages which contain conditionals, and it explains how we can deduce conditionals from premise sets (...) without conditionals. Depending on the language at hand, our logic provides different ways of keeping the Ramsey test and getting round the Gärdenfors triviality theorem. I argue that consistent additions of new items of belief are not to be performed by transitions to logical expansions. (shrink)

Reasoning with conditionals is often thought to be non-monotonic, but there is no incompatibility with classical logic, and no need to formalise inference itself as probabilistic. When the addition of a new premise leads to abandonment of a previously compelling conclusion reached by modus ponens, for example, this is generally because it is hard to think of a model in which the conditional and the new premise are true.

Graham Priest defends the use of a nonmonotonic logic, LPm, in his analysis of reasoning in the face of true contradictions, such as those arising from the paradoxes of self-reference. In the course of defending this choice of logic in the face of the criticism that this logic is not truth preserving, Priest argued that requirement is too much to ask: since LPm is a nonmonotonic logic, it necessarily fails to preserve truth. In this (...) article, I show that this assumption is incorrect, and I explain why nonmonotonic logics can nonetheless be truth preserving. Finally, I diagnose Priest's error, to explain when nonmonotonic logics do indeed fail to preserve truth. (shrink)

Charles Morgan has argued that nonmonotonic logic is ``impossible''. We show here that those arguments are mistaken, and that Morgan's preferred alternative, the representation of nonmonotonic reasoning by ``presuppositions'' fails to provide a framework in which nonmonotonic reasoning can be constructively criticised. We argue that an inductive logic, based on probabilistic acceptance, offers more than Morgan's approach through presuppositions.

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

Three studies of human nonmonotonic reasoning are described. The results show that people find such reasoning quite difficult, although being given problems with known subclass-superclass relationships is helpful. The results also show that recognizing differences in the logical strengths of arguments is important for the nonmonotonic problems studied. For some of these problems, specificity – which is traditionally considered paramount in drawing appropriate conclusions – was irrelevant and so should have lead to a “can’t tell” response; however, people (...) could give rational conclusions based on differences in the logical consequences of arguments. The same strategy also works for problems where specificity is relevant, suggesting that in fact specificity is not paramount. Finally, results showed that subjects’ success at responding appropriately to nonmonotonic problems involving conflict relies heavily on the ability to appreciate differences in the logical strength of simple, non-conflicting, statements. (shrink)

ABSTRACT What characterizes human reasoning is the ability of dealing with incomplete information. Incomplete logic is developed for modeling incomplete knowledge. The most distinctive feature of incomplete logic is its semantics. This is an alternative presentation of partial semantics. In this paper, we will introduce the general notion of incomplete logic (ICL), compare it with partial logic, and give the resolution method for it. We will also show how ICL can be applied to nonmonotonic reasoning. (...) We define nonmonotonic derivation as monotonic derivation in ICL from the database and some consistent assumptions. The mechanism of ICL makes it easy to assert the consistency of an assumption without asserting the assumption itself. (shrink)

Parametric logic is a framework that generalises classical first-order logic. A generalised notion of logical consequence—a form of preferential entailment based on a closed world assumption—is defined as a function of some parameters. A concept of possible knowledge base—the counterpart to the consistent theories of first-order logic—is introduced. The notion of compactness is weakened. The degree of weakening is quantified by a nonnull ordinal—the larger the ordinal, the more significant the weakening. For every possible knowledge base T, (...) a hierarchy of sentences that are generalised logical consequences of T is built. The first layer of the hierarchies corresponds to sentences that can be obtained by a deductive inference, characterised by the compactness property. The second layer of the hierarchies corresponds to sentences that can be obtained by an inductive inference, characterised by the property of weak compactness quantified by 1. Weaker forms of compactness—quantified by nonnull ordinals—determine higher layers in the hierarchies, corresponding to more complex inferences. The naturalness of the hierarchies built over the possible knowledge bases is attested by fundamental connections with notions from Learning theory and from topology. The naturalness of the hierarchies built over the possible knowledge bases is attested by fundamental connections with notions from Learning theory—classification in the limit, with or without a bounded number of mind changes—and from topology—in reference to the Borel and the difference hierarchies. In this paper, we introduce the key model-theoretic aspects of Parametric logic, justify the concept of the knowledge base, define the hierarchies of generalised logical consequences and illustrate their relevance to Nonmonotonic reasoning. More specifically, we show that the degree of nonmonotonicity that is required to infer a sentence can be characterised by the least nonnull ordinal that quantifies the weakening of compactness used to locate the inferred sentence in the hierarchies. (shrink)

The problems we deal with concern reasoning about incomplete knowledge. Knowledge is understood as ability of an ideal rational agent to make decisions about pieces of information. The formalisms we are particularly interested in are Moore's autoepistemic logic (AEL) and its variant, the logic of acceptance and rejection (AEL2). It is well-known that AEL may be seen as the nonmonotonic KD45 modal logic. The aim is to give an appropriate modal formalization for AEL2.

A few years ago, believing that human thinking is nonmonotonic, I tried to reconstruct a nonmonotonic reasoning by application of two monotonic procedures. I called them “step forward” and “step backward” . The first procedure is just a consequence operation responsible for an extension of the set of beliefs. The second one, defined on the base of the logic of falsehood reconstructed for the given logic of truthfulness, is responsible for a reduction of the set of (...) beliefs. Both procedures taken together were successfully verified by using so-called AGM , postulates for expansion, contraction and revision formulated by Alchourrón, Gärdenfors and Makinson . Reasoning composed of the mutual application of both procedures seemed to be quite natural for modeling our thinking. At that time, I supposed that it should be nonmonotonic but I was wrong. It turned out impossible to satisfy a definition of the nonmonotonic inference by reasoning composed both steps. To understand why this is impossible, I began to analyze how nonmonotonicity is obtainable in some well-known cases in the literature. I analyzed the problem from two points of view: non-formal examples for nonmonotonicity and formal constructions of nonmonotonic operations/relations. The result of those investigations was astonishing: none of the considered by me cases of nonmonotonicity belonging to point and almost none belonging to satisfies the definition of nonmonotonic inference. Arguments against the nonmonotonic character of well-known examples for nonmonotonicity of human thinking are more precisely presented in [6]. I present them below an abbreviated version of them. (shrink)

This proceedings volume contains a selection of revised and extended papers presented at the Second International Workshop on Nonmonotonic and InductiveLogic, NIL '91, which took place at Reinhardsbrunn Castle, December 2-6, 1991. The volume opens with an extended version of a tutorial on nonmonotonic logic by G. Brewka, J. Dix, and K. Konolige. Fifteen selected papers follow, on a variety of topics. The majority of papers belong either to the area of nonmonotonic reasoning or to the (...) field of inductive inference, but some papers integrate research from both areas. The first workshop in this series was held at the University of Karlsruhe in December 1990 and its proceedings were published as Lecture Notes in Artificial Intelligence Volume 543. The series of workshops was made possible by financial support from Volkswagen Stiftung, Hannover. This workshop was also supported by IBM Deutschland GmbH and Siemens AG. (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)

This book constitutes the refereed proceedings of the 7th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2004, held in Fort Lauderdale, Florida, USA in January 2004. The 24 revised full papers presented together with 8 system descriptions were carefully reviewed and selected for presentation. Among the topics addressed are declarative logic programming, nonmonotonic reasoning, knowledge representation, combinatorial search, answer set programming, constraint programming, deduction in ontologies, and planning.

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)

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)