This paper presents an adaptive logic enhancement of conditional logics of normality that allows for defeasible applications of Modus Ponens to conditionals. In addition to the possibilities these logics already offer in terms of reasoning about conditionals, this way they are enriched by the ability to perform default inferencing. The idea is to apply Modus Ponens defeasibly to a conditional and a fact on the condition that it is ‘safe' to do so concerning the factual and conditional knowledge at hand. (...) It is for instance not safe if the given information describes exceptional circumstances: although birds usually fly, penguins are exceptional to this rule. The two adaptive standard strategies are shown to correspond to different intuitions, a skeptical and a credulous reasoning type, which manifest themselves in the handling of so-called floating conclusions. (shrink)

This paper develops a probabilistic analysis of conditionals which hinges on a quantitative measure of evidential support. In order to spell out the interpreta- tion of ‘if’ suggested, we will compare it with two more familiar interpretations, the suppositional interpretation and the strict interpretation, within a formal framework which rests on fairly uncontroversial assumptions. As it will emerge, each of the three interpretations considered exhibits specific logical features that deserve separate consideration.

Discussions of the issue of iterated belief revision are commonly accompanied by the presentation of three “concrete” operators: natural, restrained and lexicographic. This raises a natural question: What is so distinctive about these three particular methods? Indeed, the common axiomatic ground for work on iterated revision, the AGM and Darwiche-Pearl postulates, leaves open a whole range of alternative proposals. In this paper, we show that it is satisfaction of an additional principle of “Independence of Irrelevant Alternatives”, inspired by the literature (...) on Social Choice, that unites and sets apart our three “elementary” revision operators. A parallel treatment of iterated belief contraction is also given, yielding a family of elementary contraction operators that includes, besides the well-known “conservative” and “moderate” operators, a new contraction operator that is related to restrained revision. (shrink)

We introduce and explore the notion of duality for entailment relations induced by preference orderings on states. We discuss the relationship between these preferential entailment relations from the perspectives of Boolean algebra, inference rules, and modal axiomatisation. Interpreting the preference relations as accessibility relations establishes modular Gödel-Löb logic as a suitable modal framework for rational preferential reasoning.

Modal accounts of normality in non-monotonic reasoning traditionally have an underlying semantics based on a notion of preference amongst worlds. In this paper, we motivate and investigate an alternative semantics, based on ordered accessibility relations in Kripke frames. The underlying intuition is that some world tuples may be seen as more normal, while others may be seen as more exceptional. We show that this delivers an elegant and intuitive semantic construction, which gives a new perspective on defeasible necessity. Technically, the (...) revisited logic does not change the expressive power of our previously defined preferential modalities. This conclusion follows from an analysis of both semantic constructions via a generalisation of bisimulations to the preferential case. Reasoners based on the previous semantics therefore also suffice for reasoning over the new semantics. We complete the picture by investigating different notions of defeasible conditionals in modal logic that can also be captured within our framework. (shrink)

The foundations of probability are viewed through the lens of the subjectivist interpretation. This article surveys conditional probability, arguments for probabilism, probability dynamics, and the evidential and subjective interpretations of probability.

We investigate an aspect of defeasibility that has somewhat been overlooked by the non-monotonic reasoning community, namely that of defeasible modes of reasoning. These aim to formalise defeasibility of the traditional notion of necessity in modal logic, in particular of its different readings as action, knowledge and others in specific contexts, rather than defeasibility of conditional forms. Building on an extension of the preferential approach to modal logics, we introduce new modal osperators with which to formalise the notion of defeasible (...) necessity and distinct possibility, and that can be used to represent expected effects, refutable knowledge, and so on. We show how KLM-style conditionals can smoothly be integrated with our richer language. We also propose a tableau calculus which is sound and complete with respect to our modal preferential semantics, and of which the computational complexity remains in the same class as that of the underlying classical modal logic. (shrink)

The connections between nonmonotonic reasoning and belief revision are well-known. A central problem in the area of nonmonotonic reasoning is the problem of default entailment, i.e., when should an item of default information representing “if θ is true then, normally, φ is true” be said to follow from a given set of items of such information. Many answers to this question have been proposed but, surprisingly, virtually none have attempted any explicit connection to belief revision. The aim of this paper (...) is to give an example of how such a connection can be made by showing how the lexicographic closure of a set of defaults may be conceptualised as a process of iterated revision by sets of sentences. Specifically we use the revision method of Nayak. (shrink)

The notion of the rational closure of a positive knowledge base K of conditional assertions θ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$i$$ \end{document} |∼ φ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$i$$ \end{document} (standing for if θ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$i$$ \end{document} then normally φ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$i$$ \end{document}) was first introduced by Lehmann (1989) and developed by Lehmann and Magidor (...) (1992). Following those authors we would also argue that the rational closure is, in a strong sense, the minimal information, or simplest, rational consequence relation satisfying K. In practice, however, one might expect a knowledge base to consist not just of positive conditional assertions, θ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$i$$ \end{document} |∼ φ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$i$$ \end{document}, but also negative conditional assertions, θi φ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$i$$ \end{document} (standing for not if θ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$i$$ \end{document} then normally φ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$i$$ \end{document}. Restricting ourselves to a finite language we show that the rational closure still exists for satisfiable knowledge bases containing both positive and negative conditional assertions and has similar properties to those exhibited in Lehmann and Magidor (1992). In particular an algorithm in Lehmann and Magidor (1992) which constructs the rational closure can be adapted to this case and yields, in turn, completeness theorems for the conditional assertions entailed by such a mixed knowledge base. (shrink)

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

This paper first provides a brief survey of a possibilistic handling of default rules. A set of default rules of the form, "generally, from α deduce β", is viewed as the family of possibility distributions satisfying constraints expressing that the situation where α and β is true has a greater plausibility than the one where α and ⇁β is true. When considering only the subset of linear possibility distributions, the well-known System P of postulates proposed by Kraus, Lehmann and Magidor, (...) has been obtained. We also present two rational extensions: one based on the minimum specificity principle and the other is based on the lexicographic ordering. The second part of the paper presents an empirical study of three desirable properties for a consequence relation that capture default reasoning: Rationality, Property Inheritance and Ambiguity Preservation. An experiment is conducted to investigate 13 patterns of inference for the test of these properties. Our experimental apparatus confirms previous results on the relevance of System P, and enforces the psychological relevance of the studied properties. (shrink)

1. Real-world applications, such as monitoring urban wastewater networks, commonly process large volumes of multi-source, heterogeneous data to support reasoning, query answering and decision-makin...

An assertion of high conditional probability or, more briefly, an HCP assertion is a statement of the type: The conditional probability of B given A is close to one. The goal of this paper is to construct logics of HCP assertions whose conclusions are highly likely to be correct rather than certain to be correct. Such logics would allow useful conclusions to be drawn when the premises are not strong enough to allow conclusions to be reached with certainty. This goal (...) is achieved by taking Adams' (1966) logic, changing its intended application from conditionals to HCP assertions, and then weakening its criterion for entailment. According to the weakened entailment criterion, called the Criterion of Near Surety and which may be loosely interpreted as a Bayesian criterion, a conclusion is entailed if and only if nearly every model of the premises is a model of the conclusion. The resulting logic, called NSL, is nonmonotonic. Entailment in this logic, although not as strict as entailment in Adams' logic, is more strict than entailment in the propositional logic of material conditionals. Next, NSL was modified by requiring that each HCP assertion be scaled; this means that to each HCP assertion was associated a bound on the deviation from 1 of the conditional probability that is the subject of the assertion. Scaling of HCP assertions is useful for breaking entailment deadlocks. For example, it it is known that the conditional probabilities of C given A and of - C given B are both close to one but the bound on the former's deviation from 1 is much smaller than the latter's, then it may be concluded that in all likelihood the conditional probability of C given A ∧ B is close to one. The resulting logic, called NSL-S, is also nonmonotonic. Despite great differences in their definitions of entailment, entailment in NSL is equivalent to Lehmann and Magidor's rational closure and, disregarding minor differences concerning which premise sets are considered consistent, entailment in NSL-S is equivalent to entailment in Goldszmidt and Pearl's System-Z⁺. Bacchus, Grove, Halpern, and Koller proposed two methods of developing a predicate calculus based on the Criterion of Near Surety. In their randomstructures method, which assumed a prior distribution similar to that of NSL, it appears possible to define an entailment relation equivalent to that of NSL. In their random-worlds method, which assumed a prior distribution dramatically different from that of NSL, it is known that the entailment relation is different from that of NSL. (shrink)

The paper focuses on extending to the first order case the semantical program for modalities first introduced by Dana Scott and Richard Montague. We focus on the study of neighborhood frames with constant domains and we offer in the first part of the paper a series of new completeness results for salient classical systems of first order modal logic. Among other results we show that it is possible to prove strong completeness results for normal systems without the Barcan Formula (like (...) FOL + K)in terms of neighborhood frames with constant domains. The first order models we present permit the study of many epistemic modalities recently proposed in computer science as well as the development of adequate models for monadic operators of high probability. Models of this type are either difficult of impossible to build in terms of relational Kripkean semantics [40].We conclude by introducing general first order neighborhood frames with constant domains and we offer a general completeness result for the entire family of classical first order modal systems in terms of them, circumventing some well-known problems of propositional and first order neighborhood semantics (mainly the fact that many classical modal logics are incomplete with respect to an unmodified version of either neighborhood or relational frames). We argue that the semantical program that thus arises offers the first complete semantic unification of the family of classical first order modal logics. (shrink)

We introduce a family of preferential logics that are useful for handling information with different levels of uncertainty. The corresponding consequence relations are nonmonotonic, paraconsistent, adaptive, and rational. It is also shown that the formalisms in this family can be embedded in corresponding four-valued logics with at most three uncertainty levels, and that reasoning with these logics can be simulated by algorithms for processing circumscriptive theories, such as DLS and SCAN.

Non-deterministic matrices, a natural generalization of many-valued matrices, are semantic structures in which the value assigned to a complex formula may be chosen non-deterministically from a given set of options. We show that by combining non-deterministic matrices and distance-based considerations, one obtains a family of logics that are useful for reasoning with uncertainty. These logics are a conservative extension of those that are obtained by standard distance-based semantics, and so usual distance-based methods are easily simulated within our framework. We investigate (...) the basic properties of the distance-preferential non-deterministic logics, consider their application for reasoning with incomplete and inconsistent information, and show the correspondence between some particular entailments in our framework and well-known problems like max-SAT. (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 geo-logic, which fills the entire unit cube, and then we (...) project the upper surfaces of the geo-logical cube onto the plane of probabilistic credal states by means of standard, linear perspective, which may be interpreted as an extension of the classical principle 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)

The field of iterated belief change has focused mainly on revision, with the other main operator of AGM belief change theory, i.e. contraction, receiving relatively little attention. In this paper we extend the Harper Identity from single-step change to define iterated contraction in terms of iterated revision. Specifically, just as the Harper Identity provides a recipe for defining the belief set resulting from contracting A in terms of (i) the initial belief set and (ii) the belief set resulting from revision (...) by ¬A, we look at ways to define the plausibility ordering over worlds resulting from contracting A in terms of (iii) the initial plausibility ordering, and (iv) the plausibility ordering resulting from revision by ¬A. After noting that the most straightforward such extension leads to a trivialisation of the space of permissible orderings, we provide a family of operators for combining plausibility orderings that avoid such a result. These operators are characterised in our domain of interest by a pair of intuitively compelling properties, which turn out to enable the derivation of a number of iterated contraction postulates from postulates for iterated revision. We finish by observing that a salient member of this family allows for the derivation of counterparts for contraction of some well known iterated revision operators, as well as for defining new iterated contraction operators. (shrink)

We examine the closure conditions of the probabilistic consequence relation of Hawthorne and Makinson, specifically the outstanding question of completeness in terms of Horn rules, of their proposed (finite) set of rules O. We show that on the contrary no such finite set of Horn rules exists, though we are able to specify an infinite set which is complete.

Edited in collaboration with FoLLI, the Association of Logic, Language and Information, this book constitutes the 4th volume of the FoLLI LNAI subline; containing the refereed proceedings of the 15th International Workshop on Logic, Language, Information and Computation, WoLLIC 2008, held in Edinburgh, UK, in July 2008. The 21 revised full papers presented together with the abstracts of 7 tutorials and invited lectures were carefully reviewed and selected from numerous submissions. The papers cover all pertinent subjects in computer science with (...) particular interest in cross-disciplinary topics. Typical areas of interest are: foundations of computing and programming; novel computation models and paradigms; broad notions of proof and belief; formal methods in software and hardware development; logical approach to natural language and reasoning; logics of programs, actions and resources; foundational aspects of information organization, search, flow, sharing, and protection. (shrink)

This paper introduces valuation structures associated with preferential models. Based on KLM valuation structures, we present a canonical approach to obtain injective preferential models for any preferential relation satisfying the property INJ, and give uniform proofs of representation theorems for injective preferential relations appeared in the literature. In particular, we show that, in any propositional language (finite or infinite), a preferential inference relation satisfies INJ if and only if it can be represented by a standard preferential model. This conclusion generalizes (...) the result obtained by Freund. In addition, we prove that, when the language is finite, our framework is sufficient to establish a representation theorem for any injective relation. (shrink)

Preferential model is one of the important semantical structures in nonmonotonic logic. This paper aims to establish an isomorphism theorem for preferential models, which gives us a purely algebraic characterization of the equivalence of preferential models. To this end, we present the notions of local similarity and local simulation. Based on these notions, two operators Δ(·) and μ(·) over preferential models are introduced and explored respectively. Together with other two existent operators ρ(·) and ΠD(·), we introduce an operator ∂D(·). Then (...) the isomorphism theorem is obtained in terms of ∂D(·), which asserts that for any two preferential models M₁ and M₂, they generate the same preferential inference if and only if ∂D(M₁) and ∂D(M₂) are isomorphic. Based on ∂D(·), we also get an alternative model-theoretical characterization of the well-known postulate "Weaken Disjunctive Rationality". Moreover, in the finite language framework, we show that Δ(μ(·)) is competent for the task of eliminating redundancy, and provide a representation result for k-relations. (shrink)

This collection of essays is a Festschrift for Ernest W. Adams, and is based on a symposium that was held in his honor in 1993. As the title suggests, most of the essays focus on probability and the logic of conditionals, and the relationship between them; they draw their inspiration from Adams’s seminal work on the subject. As a computer scientist, I was struck by just how much the topics discussed play a major role in much recent work in computer (...) science, and how relevant much recent work in computer science is to some of the issues discussed here. (shrink)

This collection of essays is a Festschrift for Ernest W. Adams, and is based on a symposium that was held in his honor in 1993. As the title suggests, most of the essays focus on probability and the logic of conditionals, and the relationship between them; they draw their inspiration from Adams’s seminal work on the subject. As a computer scientist, I was struck by just how much the topics discussed play a major role in much recent work in computer (...) science, and how relevant much recent work in computer science is to some of the issues discussed here. (shrink)