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.

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)

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)

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.

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)

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)

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)

In Gärdenfors and Makinson :197–245, 1994) and Gärdenfors it was shown that it is possible to model nonmonotonic inference using a classical consequence relation plus an expectation-based ordering of formulas. In this article, we argue that this framework can be significantly enriched by adopting a conceptual spaces-based analysis of the role of expectations in reasoning. In particular, we show that this can solve various epistemological issues that surround nonmonotonic and default logics. We propose some formal (...) criteria for constructing and updating expectation orderings based on conceptual spaces, and we explain how to apply them to nonmonotonic reasoning about objects and properties. (shrink)

Since the earliest formalisation of default logic by Reiter many contributions to this appealing approach to nonmonotonic reasoning have been given. The different formalisations are here presented in a general framework that gathers the basic notions, concepts and constructions underlying default logic. Our view is to interpret defaults as special rules that impose a restriction on the juxtaposition of monotonic Hubert-style proofs of a given logicL. We propose to describe default logic as a logic where (...) the juxtaposition of default proofs is subordinate to a restriction condition . Hence a default logic is a pair (L, ) where properties of the logic , like compactness, can be interpreted through the restriction condition . Different default systems are then given a common characterization through a specific condition on the logicL. We also prove cumulativity for any default logic (L, ) by slightly modifying the notion of default proof. We extend, in fact, the language ofL in a way close to that followed by Brewka in the formulation of his cumulative default system. Finally we show the existence of infinitely many intermediary default logics, depending on and called linear logics, which lie between Reiter's and ukaszewicz' versions of default logic. (shrink)

ABSTRACT Reiter's default logic is one of the most prominent and well-studied approaches to nonmonotonic reasoning. Its evolution has resulted in diverse variants enjoying many interesting properties. This process however seems to be diverging because it has led to default logics that are difficult to compare due to different formal characterizations—sometimes even dealing with different objects of discourse. This problem is addressed in this paper in two ways. One the one hand, we elaborate on the relationships (...) between different types of default logics and discuss their differences wrt some basic properties. In particular, we show how two recently proposed variants, namely rational and CA-default logic, are related to each other and existing default logics. As an interesting byproduct, we obtain a cumulative counterpart to Lukasiewicz' variant of default logic. The resulting system is insofar surprising since it necessitates to refine the canonical way of assuring cumulativity in default logics. On the other hand, we pursue an integrating approach. We give a translation embedding rational and CA-default logic into a recently developed framework for default logics. This allows us not only to classify these variants, but it moreover provides us with semantical underpinnings that have been lacking so far. (shrink)

We propose a combination of probabilistic reasoning from conditional constraints with approaches to default reasoning from conditional knowledge bases. In detail, we generalize the notions of Pearl's entailment in system Z, Lehmann's lexicographic entailment, and Geffner's conditional entailment to conditional constraints. We give some examples that show that the new notions of z-, lexicographic, and conditional entailment have similar properties like their classical counterparts. Moreover, we show that the new notions of z-, lexicographic, and conditional entailment (...) are proper generalizations of both their classical counterparts and the classical notion of logical entailment for conditional constraints. (shrink)

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)

This article tests human inference rationality when dealing with default rules. To study human rationality, psychologists currently use classical models of logic or probability theory as normative models for evaluating human ability to reason rationally. Our position is that this approach is convincing, but only manages to capture a specific case of inferential ability with little regard to conditions of everyday reasoning. We propose that the most general case to be considered is inference with imperfect knowledge - (...) in the present case restricted to uncertain knowledge - and that a natural framework for testing the rationality of plausible reasoning is System P. This system provides rational postulates for nonmonotonic inference. The semantic of the nonmonotonic inference is given by a possibilistic constraint introduced by Dubois and Prade (1991). This constraint states that a rule p ( q is a plausible rule if "the degree to which p ( q is possible" is greater than "the degree to which p ( (q is possible". Given the choice of this constraint, we study two supplementary postulates of rationality. Eighty-eight subjects participated in an experiment whose results confirm - provided that reflexivity and left logical equivalence would be tested in a further experiment - the rationality of human nonmonotonic inference according to the rational postulates of System P. (shrink)

Reasoning is a goal-oriented activity. The logical steps are at best the median part of a full reasoning: before them, a language has to be defined, and a model of the goal in this language has to be developed; after them, their result has to be checked in the real world with respect to the goal. Both the prior and the subsequent steps can be conducted rationally; none of them has a logical counterpart. Furthermore, Logic aims at prescribing (...) what a correct reasoning is. But correct with respect to what? If the answer is: with respect to truth, the next question is whether the truth in everyday life, physics, economy, is the same as the truth that logicians have in mind. Resorting to Logic is justified only if an idealization in terms of true propositions in the logical sense is compatible with the goal. If such an idealization is legitimate, so is the use of classical Logic. If not, there is no authority forbidding to skew Logic in order to better reflect the nature of the reasoning required for the task. (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)

This thesis analyzes from a philosophical perspective different models for nonmonotonic inference, belief revision and the handling of inconsistencies. ;The first chapter serves as an introduction to the subject, giving examples and analyzing the main concepts. As a result of these discussions, this thesis tries to: produce a refined map of the main notions related to this subject, maintain that there can be a fault tolerant logic that stands in support of fault tolerant reasoning, and defend the use (...) of deductive databases as models for changes of belief. ;The second chapter explores monotonic proposals to deal with uncertain reasoning. These include logics based on a classical notion of consequence, interpretations of defeasible reasoning as containing implicit premises, and systems in which temporal change is an integral part of the representation of states of affairs, via temporal indices or more elaborate devices. ;The third chapter explores quantitative approaches to nonmonotonic reasoning like dispositional logic, and theories of probabilistic reasoning including Bayesian, certainty factors, and Dempster-Shafer. ;The fourth chapter explores qualitative approaches. Here we mention conditional, default, and nonmonotonic logics, and the circumscription and autoepistemic formalisms. ;The fifth chapter studies different proposals to deal with contradictions. It starts with a review of the types of belief inconsistencies, and then it presents mechanisms to prevent, control or correct them. I explore paraconsistent logics, specially relevance logics, to "bracket" the area of conflict and allow inferences about non-related topics to continue unaffected. Then I examine different methods to get rid of the inconsistencies, including the use of dependency-directed backtracking and of relevance logic. ;Finally, I present my conclusions, and mention some of the open problems. (shrink)

Reasoning almost always occurs in the face of incomplete information. Such reasoning is nonmonotonic in the sense that conclusions drawn may later be withdrawn when additional information is obtained. There is an active literature on the problem of modeling such nonmonotonic reasoning, yet no category of method-let alone a single method-has been broadly accepted as the right approach. This paper introduces a new method, called sweeping presumptions, for modeling nonmonotonic reasoning. The main goal (...) of the paper is to provide an example-driven, nontechnical introduction to the method of sweeping presumptions, and thereby to make it plausible that sweeping presumptions can usefully be applied to the problems of nonmonotonic reasoning. The paper discusses a representative sample of examples that have appeared in the literature on nonmonotonic reasoning, and discusses them from the point of view of sweeping presumptions. (shrink)

We consider the connections between belief revision, conditional logic and nonmonotonic reasoning, using as a foundation the approach to theory change developed by Alchourrón, Gärdenfors and Makinson (the AGM approach). This is first generalized to allow the iteration of theory change operations to capture the dynamics of epistemic states according to a principle of minimal change of entrenchment. The iterative operations of expansion, contraction and revision are characterized both by a set of postulates and by Grove's construction based (...) on total pre-orders on the set of complete theories of the belief logic. We present a sound and complete conditional logic whose semantics is based on our iterative revision operation, but which avoids Gärdenfors's triviality result because of a severely restricted language of beliefs and hence the weakened scope of our extended postulates. In the second part of the paper, we develop a computational approach to theory dynamics using Rott's E-bases as a representation for epistemic states. Under this approach, a ranked E-base is interpreted as standing for the most conservative entrenchment compatible with the base, reflecting a kind of foundationalism in the acceptance of evidence for a belief. Algorithms for the computation of our iterative versions of expansion, contraction and revision are presented. Finally, we consider the relationship between nonmonotonic reasoning and both conditional logic and belief revision. Adapting the approach of Delgrande, we show that the unique extension of a default theory expressed in our conditional logic of belief revision corresponds to the most conservative belief state which respects the theory: however, this correspondence is limited to propositional default theories. Considering first order default theories, we present a belief revision algorithm which incorporates the assumption of independence of default instances and propose the use of a base logic for default reasoning which incorporates uniqueness of names. We conclude with an examination of the behavior of an implemented system on some of Lifschitz's benchmark problems in nonmonotonic reasoning. (shrink)

Nonmonotonic logics allow—contrary to classical (monotone) logics— for withdrawing conclusions in the light of new evidence. Nonmonotonic reasoning is often claimed to mimic human common sense reasoning. Only a few studies, though, have investigated this claim empirically. system p is a central, broadly accepted nonmonotonic reasoning system that proposes basic rationality postulates. We previously investigated empirically a probabilistic interpretation of three selected rules of system p. We found a relatively good agreement of human (...) reasoning and principles of nonmonotonic reasoning according to the coherence interpretation of system p. This study reports an experiment on the cautious monotonicity Rule and its “incautious” counterpart that is not contained in system p, namely the monotonicity Rule. In accordance with our previous results, the data suggest that people reason nonmonotonically: the subjects in the cautious monotonicity condition infer significantly tighter intervals close to the coherence interpretation of system p compared with the subjects in the incautious monotonicity condition where rather wide (and hence non-informative) intervals are inferred. (shrink)

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

Consistency-based approaches in nonmonotonic reasoning may be expected to yield multiple sets of default conclusions for a given default theory. Reasoning about such extensions is carried out at the meta-level. In this paper, we show how such reasoning may be carried out at the object level for a large class of default theories. Essentially we show how one can translate a default theory Δ, obtaining a second Δ', such that Δ has a (...) single extension that encodes every extension of _. Moreover, our translated theory is only a constant factor larger than the original. We prove that our translation behaves correctly. In the approach we can now encode the notion of extension from within the framework of standard default logic. Hence one can encode notions such as skeptical and credulous conclusions, and can reason about such conclusions within a single extension. This result has some theoretical interest, in that it shows how multiple extensions of semi-monotonic default theories are encodable with manageable overhead in a single extension. (shrink)

We present an epistemic default logic, based on the metaphore of a meta-level architecture. Upward reflection is formalized by a nonmonotonic entailment relation, based on the objective facts that are either known or unknown at the object level. Then, the meta (monotonic) reasoning process generates a number of default-beliefs of object-level formulas. We extend this framework by proposing a mechanism to reflect these defaults down. Such a reflection is seen as essentially having a temporal flavour: defaults (...) derived at the meta-level are projected as facts in a next object level state. In this way, we obtain temporal models for default reasoning in meta-level formalisms which can be conceived as labeled branching trees. Thus, descending the tree corresponds to shifts in time that model downward reflection, whereas the branching of the tree corresponds to ways of combining possible defaults. All together, this yields an operational or procedural semantics of reasoning by default, which admits one to reason about it by means of branching-time temporal logic. Finally, we define sceptical and credulous entailment relations based on these temporal models and we characterize Reiter extensions in our semantics. (shrink)

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)

When reasoning about complex domains, where information available is usually only partial, nonmonotonic reasoning can be an important tool. One of the formalisms introduced in this area is Reiter's Default Logic (1980). A characteristic of this formalism is that the applicability of default (inference) rules can only be verified in the future of the reasoning process. We describe an interpretation of default logic in temporal epistemic logic which makes this characteristic explicit. It is (...) shown that this interpretation yields a semantics for default logic based on temporal epistemic models. A comparison between the various semantics for default logic will show the differences and similarities of these approaches and ours. (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)

Philosophical applications of familiar paracomplete and paraconsistent logics often rely on an idea of . With respect to the paraconsistent logic LP (the dual of Strong Kleene or K3), such is standardly cashed out via an LP-based nonmonotonic logic due to Priest (1991, 2006a). In this paper, I offer an alternative approach via a monotonic multiple-conclusion version of LP.

We present new probabilistic generalizations of Pearl’s entailment in System Z and Lehmann’s lexicographic entailment, called Zλ- and lexλ-entailment, which are parameterized through a value λ ∈ [0,1] that describes the strength of the inheritance of purely probabilistic knowledge. In the special cases of λ = 0 and λ = 1, the notions of Zλ- and lexλ-entailment coincide with probabilistic generalizations of Pearl’s entailment in System Z and Lehmann’s lexicographic entailment that have been recently introduced by the author. We show (...) that the notions of Zλ- and lexλ-entailment have similar properties as their classical counterparts. In particular, they both satisfy the rationality postulates of System P and the property of Rational Monotonicity. Moreover, Zλ-entailment is weaker than lexλ-entailment, and both Zλ- and lexλ-entailment are proper generalizations of their classical counterparts. (shrink)

The motivation of this study is that Reiter’s default theory as well as assumption-based argumentation frameworks corresponding to default theories have difficulties in handling disjunctive information, while a disjunctive default theory (ddt) avoids them. This paper presents the semantic correspondence between generalized assumption-based argumentation (ABA) and extended disjunctive logic programming as well as the correspondence between ABA and nonmonotonic reasoning approaches such as disjunctive default logic and prioritized circumscription. To overcome the above-mentioned difficulties of (...) ABA frameworks corresponding to default theories, we propose an assumption-based framework (ABF) translated from an extended disjunctive logic program (EDLP) since an EDLP can be translated into a ddt. Our ABF incorporates explicit negation and the connective of disjunction “|” to Heyninck and Arieli’s ABF induced by a disjunctive logic program. In this paper, first, we show how arguments are constructed from disjunctive rules in our proposed ABF. Then, we show the correspondence between answer sets of an EDLP P and stable extensions of the ABF translated from P with trivialization rules. After defining rationality postulates, we show answer sets of a consistent EDLP are captured by consistent stable extensions of the translated ABF with no trivialization rules. Finally, we show the correspondence between ABA and disjunctive default logic (resp. prioritized circumscription). The relation between ABA and possible model semantics of EDLPs is also discussed. (shrink)

Default reasoning occurs whenever the truth of the evidence available to the reasoner does not guarantee the truth of the conclusion being drawn. Despite this, one is entitled to draw the conclusion “by default” on the grounds that we have no information which would make us doubt that the inference should be drawn. It is the type of conclusion we draw in the ordinary world and ordinary situations in which we find ourselves. Formally speaking, ‘nonmonotonic (...) class='Hi'>reasoning’ refers to argumentation in which one uses certain information to reach a conclusion, but where it is possible that adding some further information to those very same premises could make one want to retract the original conclusion. It is easily seen that the informal notion of default reasoning manifests a type of nonmonotonic reasoning. Generally speaking, default statements are said to be true about the class of objects they describe, despite the acknowledged existence of “exceptional instances” of the class. In the absence of explicit information that an object is one of the exceptions we are enjoined to apply the default statement to the object. But further information may later tell us that the object is in fact one of the exceptions. So this is one of the points where nonmonotonicity resides in default reasoning. (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 conditionals (A |∼ B) are formalizations of common sense expressions of the form “if A, normally B”. The nonmonotonic conditional is interpreted by a “high” coherent conditional probability, P(B|A) > .5. Two important properties are closely related to the nonmonotonic conditional: First, A |∼ B allows for exceptions. Second, the rules of the nonmonotonic system p guiding A |∼ B allow for withdrawing conclusions in the light of new premises. This study reports a series of (...) three experiments on reasoning with inference rules about nonmonotonic conditionals in the framework of coherence. We investigated the cut, and the right weakening rule of system p. As a critical condition, we investigated basic monotonic properties of classical (monotone) logic, namely monotonicity, transitivity, and contraposition. The results suggest that people reason nonmonotonically rather than monotonically. We propose nonmonotonic reasoning as a competence model of human reasoning. (shrink)

Statistical Default Logic (SDL) is an expansion of classical (i.e., Reiter) default logic that allows us to model common inference patterns found in standard inferential statistics, e.g., hypothesis testing and the estimation of a population‘s mean, variance and proportions. This paper presents an embedding of an important subset of SDL theories, called literal statistical default theories, into stable model semantics. The embedding is designed to compute the signature set of literals that uniquely distinguishes each extension on (...) a statistical default theory at a pre-assigned error-bound probability. (shrink)

: Claus Oetke, in his "Ancient Indian Logic as a Theory of Non-monotonic Reasoning," presents a sweeping new interpretation of the early history of Indian logic. His main proposal is that Indian logic up until Dharmakirti was nonmonotonic in character-similar to some of the newer logics that have been explored in the field of Artificial Intelligence, such as default logic, which abandon deductive validity as a requirement for formally acceptable arguments; Dharmakirti, he suggests, was the first to (...) consider that a good argument should be one for which it is not possible for the property identified as the "reason" (hetu) to occur without the property to be proved (sadhya)-a requirement akin to deductive validity. Oetke's approach is challenged here, arguing that from the very beginning in India something like monotonic, that is, deductively valid, reasoning was the ideal or norm, but that the conception of that ideal was continually refined, in that the criteria for determining when it is realized were progressively sharpened. (shrink)

We present two approaches to investigate the validity of connexive principles and related formulas and properties within coherence-based probability logic. Connexive logic emerged from the intuition that conditionals of the form if not-A, thenA, should not hold, since the conditional’s antecedent not-A contradicts its consequent A. Our approaches cover this intuition by observing that the only coherent probability assessment on the conditional event $${A| \overline{A}}$$ A | A ¯ is $${p(A| \overline{A})=0}$$ p ( A | A ¯ ) = 0. (...) In the first approach we investigate connexive principles within coherence-based probabilistic default reasoning, by interpreting defaults and negated defaults in terms of suitable probabilistic constraints on conditional events. In the second approach we study connexivity within the coherence framework of compound conditionals, by interpreting connexive principles in terms of suitable conditional random quantities. After developing notions of validity in each approach, we analyze the following connexive principles: Aristotle’s theses, Aristotle’s Second Thesis, Abelard’s First Principle, and Boethius’ theses. We also deepen and generalize some principles and investigate further properties related to connexive logic (like non-symmetry). Both approaches satisfy minimal requirements for a connexive logic. Finally, we compare both approaches conceptually. (shrink)

This dissertation is intended to provide a formalism for those generics that trigger nonmonotonic inferences. The formalism is to reflect intentionality and exception-tolerating features of generics, and has an emphasis on the axiomatization of generic reasoning that encodes nonmonotonicity. ;A modal conditional approach is taken to formalize the nonmonotonic reasoning in general at the level of object language. A serial of logic systems---MN, NID, NCUM, N STCUM---are constructed in an increasing strength of the characterized nonmonotonic (...) inference relation. In these systems, two binary modal operators ⩾ and > are introduced in their syntax, and a ⊛ function lifted from the traditional * function is deployed in their semantics. These systems are shown to be sound and complete with respect to certain classes of frames defined in the semantics. They are decidable as well. The nonmonotonic inference is argued to be a ternary relation "[phi], Gamma |∼ alpha", and is defined in the system NSTCUM. Many widely discussed nonmonotonic inference patterns such as Defeasible Modus Ponens, Defeasible Transitivity, the Penguin Principle etc. are justified. The specificity rule is proved to be a theorem of the system N STCUM. The impact of negated defaults on an inference is also investigated and accounted for. ;A canonical form to read off generics is proposed: All generic sentences with subject-predicate structure can be re-written into their canonical form S . If S is a plural noun phrase, it can be further refined to be . Normal objects are selected based on the "meaning" of the subject and predicate terms. The second parameter provides an aspect with respect to which certain objects of a kind are considered normal. Due to such a way to select normal objects, the drowning problem is solved. ;The inference behaviors of generics are axiomatized in the system G, which is a quantificational extension of the system NSTCUM. It is proved to be sound and complete with respect to the class of L⩾,G -frames. Those benchmark examples of generic inferences are examined in the system G. (shrink)

ABSTRACT Two levels of description of nonmonotonic reasoning are distinguished. For these levels semantical formalizations are given. The first level is defined semantically by the notion of belief state frame, the second level by the notion of reasoning frame. We introduce two specification languages to describe nonmonotonic reasoning at each of the levels: a specification language for level 1, with formal semantics based on belief state frames, a fragment of infinitary temporal logic as a general (...) specification language for level 2, with formal semantics based on reasoning frames. In our framework every level 2 description can be abstracted to level 1, and for every level 1 description there are level 2 descriptions which are a specialization of it. (shrink)

This paper is an attempt to bring together two separated areas of research: classical mathematics and metamathematics on the one side, non-monotonic reasoning on the other. This is done by simulating nonmonotonic logic through antitonic theory extensions. In the first half, the specific extension procedure proposed here is motivated informally, partly in comparison with some well-known non-monotonic formalisms. Operators V and, more generally, U are obtained which have some plausibility when viewed as giving nonmonotonic theory extensions. (...) In the second half, these operators are treated from a mathematical and metamathematical point of view. Here an important role is played by U -closed theories and U -fixed points. The last section contains results on V-closed theories which are specific for V. (shrink)

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

We study a probabilistic logic based on the coherence principle of de Finetti and a related notion of generalized coherence (g-coherence). We examine probabilistic conditional knowledge bases associated with imprecise probability assessments defined on arbitrary families of conditional events. We introduce a notion of conditional interpretation defined directly in terms of precise probability assessments. We also examine a property of strong satisfiability which is related to the notion of toleration well known in default reasoning. In our framework we (...) give more general definitions of the notions of probabilistic consistency and probabilistic entailment of Adams. We also recall a notion of strict p-consistency and some related results. Moreover, we give new proofs of some results obtained in probabilistic default reasoning. Finally, we examine the relationships between conditional probability rankings and the notions of g-coherence and g-coherent entailment. (shrink)

This book presents adaptive logics as an intuitive and powerful framework for modeling defeasible reasoning. It examines various contexts in which defeasible reasoning is useful and offers a compact introduction into adaptive logics. The author first familiarizes readers with defeasible reasoning, the adaptive logics framework, combinations of adaptive logics, and a range of useful meta-theoretic properties. He then offers a systematic study of adaptive logics based on various applications. The book presents formal models for defeasible reasoning (...) stemming from different contexts, such as default reasoning, argumentation, and normative reasoning. It highlights various meta-theoretic advantages of adaptive logics over other logics or logical frameworks that model defeasible reasoning. In this way the book substantiates the status of adaptive logics as a generic formal framework for defeasible reasoning. (shrink)

“Since today is Saturday, the grocery store is open today and will be closed tomorrow; so let’s go today”. That is an example of everyday practical reasoning—reasoning directly with the propositions that one believes but may not be fully certain of. Everyday practical reasoning is one of our most familiar kinds of decisions but, unfortunately, some foundational questions about it are largely ignored in the standard decision theory: (Q1) What are the decision rules in everyday practical (...) class='Hi'>reasoning that connect qualitative belief and desire to preference over acts? (Q2) What sort of logic should govern qualitative beliefs in everyday practical reasoning, and to what extent is that logic necessary for the purposes of qualitative decisions? (Q3) What kinds of qualitative decisions are always representable as results of everyday practical reasoning? (Q4) Under what circumstances do the results of everyday practical reasoning agree with the Bayesian ideal of expected utility maximization? This paper proposes a rigorous decision theory for answering all of those questions, which is developed in parallel to Savage’s (1954) foundation of expected utility maximization. In light of a new representation result, everyday practical reasoning provides a sound and complete method for a very wide class of qualitative decisions; and, to that end, qualitative beliefs must be allowed to be closed under classical logic plus a well-known nonmonotonic logic—the so-called system ℙ. (shrink)

Alternative logics have been invoked periodically to explain the systematically different modes of thought of the subjects of ethnography: one logic for ‘us’ and another for ‘them’. Recently anthropologists have cast doubt on the tenability of such an explanation of difference. In cognitive science, [Stenning and van Lambalgen, 2008] proposed that with the modern development of multiple logics, at least several logics are required for making sense of the cognitive processes of reasoning for different purposes and in different contexts. (...) Alongside Classical logic — the logic of dispute), there is a need for a nonmonotonic logic which is a logic of cooperative communication. Here we propose that all people with various cultural backgrounds make use of multiple logics, and that difference should be captured as variation in the social contexts that call forth the different logics’ application. This contribution illustrates these ideas with reference to the ethnography of divination. (shrink)

Description logics refer to a family of formalisms concentrated around concepts, roles and individuals. They belong to the most frequently used knowledge representation formalisms and provide a logical basis to a variety of well known paradigms. The main reasoning tasks considered in the area of description logics are those reducible to subsumption. On the other hand, any knowledge representation system should be equipped with a more advanced reasoning machinery. Therefore in the current paper we make a step towards (...) integrating description logics with second-order reasoning. One of the important motivations behind introducing second-order formalism follows from the fact that many forms of commonsense and nonmonotonic reasoning used in AI can be modelled within the second-order logic. To achieve our goal we first extend description logics with a possibility to quantify over concepts. Since one of the main criticisms against the use of second-order formalisms is their complexity, we next propose second-order quantifier elimination techniques applicable to a large class of description logic formulas. Finally we show applications of the techniques, in particular in reasoning with circumscribed concepts and approximated terminological formulas. (shrink)