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 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)

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)

Various representation results have been established for logics of belief revision, in terms of remainder sets, epistemic entrenchment, systems of spheres and so on. In this paper I present another representation for logics of belief revision, as an algebra of theories. I show that an algebra of theories, enriched with a set of rejection operations, provides a suitable algebraic framework to characterize the theory change operations of systems of belief revision. The theory change operations arise as power operations of the (...) conjunction and disjunction connectives of the underlying logic. (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)

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] is greater than or equal (...) to r. Thus, each conditional in a given family behaves like conditional probability above some specific support level. (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.

The concept of relevance between classical propositional formulae, defined in terms of letter-sharing, has been around for a very long time. But it began to take on a fresh life in 1999 when it was reconsidered in the context of the logic of belief change. Two new ideas appeared in independent work of Odinaldo Rodrigues and Rohit Parikh. First, the relation of relevance was considered modulo the belief set under consideration, Second, the belief set was put in a canonical form, (...) known as its finest splitting. In this paper we explain these ideas; relate the approaches of Rodrigues and Parikh to each other; and briefly report some recent results of Kourousias and Makinson on the extent to which AGM belief change operations respect relevance. Finally we suggest a further refinement of the notion of relevance by introducing a parameter that allows one to take epistemic as well as purely logical components into account. (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)

Nonmonotonic reasoning is often claimed to mimic human common sense reasoning. Only a few studies, though, have investigated this claim empirically. We report four experiments which investigate three rules of SYSTEMP, namely the AND, the LEFT LOGICAL EQUIVALENCE, and the OR rule. The actual inferences of the subjects are compared with the coherent normative upper and lower probability bounds derived from a non-infinitesimal probability semantics of SYSTEM P. We found a relatively good agreement of human reasoning and principles of nonmonotonic (...) reasoning. Contrary to the results reported in the ‘heuristics and biases’ tradition, the subjects committed relatively few upper bound violations (conjunction fallacies). (shrink)

Proceedings of the 2008 AAAI Spring Symposium on Architectures for Intelligent Theory-Based Agents. “OSCAR is a fully implemented architecture for a cognitive agent, based largely on the author’s work in philosophy concerning epistemology and practical cognition. The seminal idea is that a generally intelligent agent must be able to function in an environment in which it is ignorant of most matters of fact. The architecture incorporates a general-purpose defeasible reasoner, built on top of an efficient natural deduction reasoner for first-order (...) logic. It is based upon a detailed theory about how the various aspects of epistemic and practical cognition should interact, and many of the details are driven by theoretical results concerning defeasible reasoning.”. (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)

An introduction to the motivations and mechanics of John Pollock's theory of defeasible reasoning, from a lecture at the Northern Institute of Philosophy in 2010.

This paper presents statistical default logic, an expansion of classical (i.e., Reiter) default logic that allows us to model common inference patterns found in standard inferential statistics, including hypothesis testing and the estimation of a populations mean, variance and proportions. The logic replaces classical defaults with ordered pairs consisting of a Reiter default in the first coordinate and a real number within the unit interval in the second coordinate. This real number represents an upper-bound limit on the probability of accepting (...) the consequent of an applied default and that consequent being false. A method for constructing extensions is then defined that preserves this upper bound on the probability of error under a (skeptical) non-monotonic consequence relation. (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)

We start with Fodor's critique of cognitive science in "The mind doesn't work that way: The scope and limits of computational psychology": he argues that much mental activity cannot be handled by the current methods of cognitive science because it is nonmonotonic and, therefore, is global in nature, is not context-free, and is thus not capable of being formalized by a Turing-like mental architecture. We look at the use of nonmonotonic logic in the artificial intelligence community, particularly with the discussion (...) of the so-called frame problem. The mainstream approach to the frame problem is, we argue, probably susceptible to Fodor's critique; however, there is an alternative approach, due to McCain and Turner, which is, when suitably reformulated, not susceptible. In the course of our argument, we give a proof theory for the McCain-Turner system and show that it satisfies cut elimination. We have two substantive conclusions: first, that Fodor's argument depends on assumptions about logical form which not all nonmonotonic theories satisfy and, second, that metatheory plays an important role in the context of evolutionary accounts of rationality. (shrink)