We present a framework for understanding abduction within modal logic and Kripke semantics; worlds of a Kripke frame will represent possible theories, and a change in theory will be understood as a passage from one world to an adjacent possible world. Further, these steps may agree with the accessibility relation or may ‘backtrack’, accordingly as new information refutes or reinforces our present theory. Our formalism can be used to model not only abduction, but also to talk about the inner structure (...) of theories as well as relations between them, allowing us to interpret many ideas from philosophy of science within the well-understood framework of modal logic. (shrink)

Abductive problems have been widely studied in propositional logic. First order abduction, however, has been viewed as intractable, for the undecidability of logical consequence. In this paper, we propose a notion of abductive problem, N-abductive problem, which is relative to the cardinality of the minimal model satisfying the given theory. We use a notion of restricted satisfaction, also relative to a domain cardinality. Finally, we propose an effective procedure for the searching of abductive solutions, by means of a modification of (...) Beth's tableaux. (shrink)

We show how belief revision can be treated systematically in the format of dynamicepistemic logic, when operators of conditional belief are added. The core engine consists of definable update rules for changing plausibility relations between worlds, which have been proposed independently in the dynamic-epistemic literature on preference change. Our analysis yields two new types of modal result. First, we obtain complete logics for concrete mechanisms of belief revision, based on compositional reduction axioms. Next, we show how various abstract postulates for (...) belief revision can be analyzed by standard modal frame correspondences for model-changing operations. (shrink)

Abduction was first introduced in the epistemological context of scientific discovery. It was more recently analyzed in artificial intelligence, especially with respect to diagnosis analysis or ordinary reasoning. These two fields share a common view of abduction as a general process of hypotheses formation. More precisely, abduction is conceived as a kind of reverse explanation where a hypothesis H can be abduced from events E if H is a good explanation of E. The paper surveys four known schemes for abduction (...) that can be used in both fields. Its first contribution is a taxonomy of these schemes according to a common semantic framework based on belief revision. Its second contribution is to produce, for each non-trivial scheme, a representation theorem linking its semantic framework to a set of postulates. Its third contribution is to present semantic and axiomatic arguments in favor of one of these schemes, ordered abduction, which has never been vindicated in the literature. (shrink)

In this work, the problem of performing abduction in modal logics is addressed, along the lines of [3], where a proof theoretical abduction method for full first order classical logic is defined, based on tableaux and Gentzen-type systems. This work applies the same methodology to face modal abduction. The non-classical context enforces the value of analytical proof systems as tools to face the meta-logical and proof-theoretical questions involved in abductive reasoning.The similarities and differences between quantifiers and modal operators are investigated (...) and proof theoretical abduction methods for the modal systems K, D, T and S4 are defined, that are sound and complete. The construction of the abductive explanations is in strict relation with the expansion rules for the modal logics, in a modular manner that makes local modifications possible. The method given in this paper is general, in the sense that it can be adapted to any propositional modal logic for which analytic tableaux are provided. Moreover, the way towards an extension to first order modal logic is straightforward. (shrink)

he formalization of abductive reasoning is still an open question: there is no general agreement on the boundary of some basic concepts, such as preference criteria for explanations, and the extension to first order logic has not been settled.Investigating the nature of abduction outside the context of resolution based logic programming still deserves attention, in order to characterize abductive explanations without tailoring them to any fixed method of computation. In fact, resolution is surely not the best tool for facing meta-logical (...) and proof-theoretical questions.In this work the analysis of the concepts involved in abductive reasoning is based on analytical proof systems, i.e. tableaux and Gentzen-type systems. A proof theoretical abduction method for first order classical logic is defined, based on the sequent calculus and a dual one, based on semantic tableaux. The methods are sound and complete and work for full first order logic, without requiring any preliminary reduction of formulae into normal forms. In the propositional case, two different characterizations are given for abductive explanations, each of them being the declarative counterpart of a different algorithm for the generation of explanations. The first one corresponds the generation of the whole set of minimal and consistent explanations, where minimality is checked by comparison with the other elements of the set. The second characterization corresponds to a algorithm for generating a single minimal explanation that is consistent with the theory.The first order versions of the abductive systems make use of unification and dynamic herbrandization/skolemization of formulae. The construction of the abduced formula is pursued by means of de-skolemization. The first order methods are very loose in discarding explanations that are not minimal In fact, the question of minimality in first order abduction is a main issue. As usually defined, minimality is undecidable, for two different reasons: determining whether an explanation is better than another one is in general undecidable; the set of explanations may be infinite. Moreover, because of , a minimal element may not exist. Such problems suggest that the minimality requirement should be relaxed, possibly defining it w.r.t. a stronger relation than logical consequence. (shrink)

In ‘belief revision’ a theory is revised with a formula φ resulting in a revised theory . Typically, is in , one has to give up belief in by a process of retraction, and φ is in . We propose to model belief revision in a dynamic epistemic logic. In this setting, we typically have an information state (pointed Kripke model) for the theory wherein the agent believes the negation of the revision formula, i.e., wherein is true. The revision with (...) φ is a program *φ that transforms this information state into a new information state. The transformation is described by a dynamic modal operator [*φ], that is interpreted as a binary relation [ [*φ] ] between information states. The next information state is computed from the current information state and the belief revision formula. If the revision is successful, the agent believes φ in the resulting state, i.e., Bφ is then true. To make this work, as information states we propose ‘doxastic epistemic models’ that represent both knowledge and degrees of belief. These are multi-modal and multi-agent Kripke models. They are constructed from preference relations for agents, and they satisfy various characterizable multi-agent frame properties. Iterated, revocable, and higher-order belief revision are all quite natural in this setting. We present, for an example, five different ways of such dynamic belief revision. One can also see that as a non-deterministic epistemic action with two alternatives, where one is preferred over the other, and there is a natural generalization to general epistemic actions with preferences. (shrink)

In this paper we introduce Dynamic Epistemic Logic, which is alogic for reasoning about information change in a multi-agent system. Theinformation structures we use are based on non-well-founded sets, and canbe conceived as bisimulation classes of Kripke models. On these structures,we define a notion of information change that is inspired by UpdateSemantics (Veltman, 1996). We give a sound and complete axiomatization ofthe resulting logic, and we discuss applications to the puzzle of the dirtychildren, and to knowledge programs.

In ‘belief revision’ a theory\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\cal K}$$\end{document} is revised with a formula φ resulting in a revised theory \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\cal K}\ast\varphi$$\end{document}. Typically, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\neg\varphi$$\end{document} is in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\cal K}$$\end{document}, one has to give up belief in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\neg\varphi$$\end{document} by a process (...) of retraction, and φ is in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\cal K}\ast\varphi$$\end{document}. We propose to model belief revision in a dynamic epistemic logic. In this setting, we typically have an information state (pointed Kripke model) for the theory \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\cal K}$$\end{document} wherein the agent believes the negation of the revision formula, i.e., wherein \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$B\neg\varphi$$\end{document} is true. The revision with φ is a program *φ that transforms this information state into a new information state. The transformation is described by a dynamic modal operator [*φ], that is interpreted as a binary relation [ [*φ] ] between information states. The next information state is computed from the current information state and the belief revision formula. If the revision is successful, the agent believes φ in the resulting state, i.e., Bφ is then true. To make this work, as information states we propose ‘doxastic epistemic models’ that represent both knowledge and degrees of belief. These are multi-modal and multi-agent Kripke models. They are constructed from preference relations for agents, and they satisfy various characterizable multi-agent frame properties. Iterated, revocable, and higher-order belief revision are all quite natural in this setting. We present, for an example, five different ways of such dynamic belief revision. One can also see that as a non-deterministic epistemic action with two alternatives, where one is preferred over the other, and there is a natural generalization to general epistemic actions with preferences. (shrink)

We develop a conceptual and formal clarification of notion of surprise as a belief-based phenomenon by exploring a rich typology. Each kind of surprise is associated with a particular phase of cognitive processing and involves particular kinds of epistemic representations (representations and expectations under scrutiny, implicit beliefs, presuppositions). We define two main kinds of surprise: mismatch-based surprise and astonishment. In the central part of the paper we suggest how a formal model of surprise can be integrated with a formal model (...) of belief change. We investigate the role of surprise in triggering the process of belief reconsideration. There are a number of models of surprise developed in the psychology of emotion. We provide several comparisons of our approach with those models. (shrink)

Abduction or retroduction, as introduced by C.S. Peirce in the double sense of searching for explanatory instances and providing an explanation is a kind of complement for usual argumentation. There is, however, an inferential step from the explanandum to the abductive explanans . Whether this inferential step can be captured by logical machinery depends upon a number of assumptions, but in any case it suffers in principle from the triviality objection: any time a singular contradictory explanans occurs, the system collapses (...) and stops working. The traditional remedies for such collapsing are the expensive mechanisms of consistency maintenance, or complicated theories of non-monotonic derivation that keep the system running at a higher cost. I intend to show that the robust logics of formal inconsistency, a particular category of paraconsistent logics which permit the internalization of the concepts of consistency and inconsistency inside the object language, provide simple yet powerful techniques for automatic abduction. Moreover, the whole procedure is capable of automatization by means of the tableau proof-procedures available for such logics. Some motivating examples are discussed in detail. (shrink)

An agent-centered, goal-directed, resource-bound logic of human reasoning would do well to note that individual cognitive agency is typified by the comparative scantness of available cognitive resources—information, time, and computational capacity, to name just three. This motivates individual agents to set their cognitive agendas proportionately, that is, in ways that carry some prospect of success with the resources on which they are able to draw. It also puts a premium on cognitive strategies which make economical use of those resources. These (...) latter I callscant-resource adjustment strategies,and they supply the context for an analysis of abduction. The analysis is Peircian in tone, especially in the emphasis it places on abduction’signorance-preservingcharacter. My principal purpose here is to tie abduction’s scarce-resource adjustment capacity to its ignorance preservation. (shrink)