A decomposition based algorithm for maximal contractions

This paper proposes a decomposition based algorithm for revision problems in classical propositional logic. A set of decomposing rules are presented to analyze the satisfiability of formulas. The satisfiability of a formula is equivalent to the satisfiability of a set of literal sets. A decomposing function is constructed to calculate all satisfiable literal sets of a given formula. When expressing the satisfiability of a formula, these literal sets are equivalent to all satisfied models of such formula. A revision algorithm based on this decomposing function is proposed, which can calculate maximal contractions of a given problem. In order to reduce the memory requirement, a filter function is introduced. The improved algorithm has a good performance in both time and space perspectives.     

Infobase Change: A First Approximation

Generalisations of theory change involving operations on arbitrary sets ofwffs instead of on belief sets (i.e., sets closed under a consequencerelation), have become known as base change. In one view, a base should bethought of as providing more structure to its generated belief set, whichmeans that it can be employed to determine the theory contraction operationassociated with a base contraction operation. In this paper we follow suchan approach as the first step in defining infobase change. We think of an infobase as a finite set of wffs consisting of independently obtainedbits of information. Taking AGM theory change (Alchourrón et al. 1985) as the general framework, we present a method that uses the structure of aninfobase B to obtain an AGM theory contraction operation for contractingthe belief set Cn(B). Both the infobase and the obtained theory contraction operation then play a role in constructing a unique infobasecontraction operation. Infobase revision is defined in terms of an analogueof the Levi Identity, and it is shown that the associated theory revisionoperation satisfies the AGM postulates for revision. Because every infobaseis associated with a unique infobase contraction and revision operation, the method also allows for iterated base change.     

A Power Algebra for Theory Change

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.     

A sound and complete R-calculi with respect to contraction and minimal change

AGM postulates are for belief revision （revision by a single belief）, and DP postulates are for iterated revision （revision by a finite sequence of beliefs）. R-calculus is given for R-configurations △｜Г, where △ is a set of atomic formulas or the negations of atomic formulas, and Г is a finite set of formulas. We shall give two R-calculi C and M （sets of de- duction rules） such that for any finite consistent sets Г, △of formulas in the propositional logic, there is a consistent set ⊙ Г C of formulas such that △IГ → △, ⊙ is provable and⊙ is a contraction of F by A or a minimal change of F by A; and prove that C and M are sound and complete with respect to the contraction and the minimal change, respectively.     

Refined Epistemic Entrenchment

Epistemic entrenchment, as presented by Gärdenfors and Makinson (1988) and Gärdenfors (1988), is a formalisation of the intuition that, when forced to choose between two beliefs, an agent will giveup the less entrenched one. While their formalisation satisfactorilycaptures the intuitive notion of the entrenchment of beliefs in a number ofaspects, the requirement that all wffs be comparable has drawn criticismfrom various quarters. We define a set of refined versions of theirentrenchment orderings that are not subject to the same criticism, andinvestigate the relationship between the refined entrenched orderings,the entrenchment orderings of Gärdenfors and Makinson, and AGM theorycontraction (Alchourrón et al., 1985). To conclude, we compare refinedentrenchment with two related approaches to epistemic entrenchment.     

一种基于遗忘理论的信念收缩方法

针对在经典信念理论框架下,信念收缩后可能出现信息损失的问题,本文提出了一种利用遗忘理论来构建收缩算子的信念收缩方法。本文先通过理论证明来说明该收缩算子能够满足AGM理论中信念收缩的假定,然后用实例说明,与命题逻辑表示的信念遗忘收缩相比,一阶谓词逻辑表示的信念遗忘收缩保留了更多的原有信息,避免了不必要的信息损失,遵循最小修改原则。     

Agent信念的遗忘修正方法

为了使信念修正能够满足最小改变原则,首先基于遗忘理论定义遗忘收缩算子,并且证明该算子满足必要AGM收缩假定;然后通过Levi Identity构建遗忘修正算子;最后给出遗忘修正方法和多次遗忘修正算法。实例分析表明,算法具有可行性和有效性,能够得到较满意的修正结果。     

A Note on Partial Meet Package Contraction

It was shown that finite P-recovery holds for partial meet package contraction in Furhmann and Hansson (1994). However, it is not known if recovery holds for partial meet package contraction in the infinite case. In this paper, I show that recovery does not hold for partial meet package contraction in the infinite case.     

弱化矛盾信息的一种修正方法

信念修正中一个关键的问题就是对不一致信息的处理。文中提出一种新的策略，在对不一致信息的处理过程中，通过弱化矛盾信息而不是完全丢弃来维护知识库的一致性。这种方法遵循了最小改变原则，使信息丢失尽可能小从而保留了更多的有用信息。并讨论了其性质及满足AGM公设的情况。     

信念修正的完全和可操作的方法

给出了命题逻辑上信念修正的两种可操作的完全方法.首先对R-演算的规则进行了修改,使得对任何一个极大协调的子集都通过这组规则得到.然后,给出了求得所有的极小不协调子集的一组规则.最后,给出一个过程,该过程能求得所有的极大协调子集.因为这两种方法都能求得所有的极大协调子集,所以把它们称为完全的.     

一种广义信念修正的计算方法

AGM理论中新知识为单个语句,而实际上新知识通常是以多语句甚至无穷语句的形式出现．广义信念修正从理论上扩充了AGM系统,但在具体实现上还缺乏有效的算法．通过构造优序划分的方法解决信念间的关系问题,采用新知识的信度与冲突知识相关的方法解决新知识的信度问题．给出了一种基于链表的计算方法,从而解决了广义信念修正理论的信念库维护操作问题．     

多Agent信念修正研究

Belief Revision is a theory that studies how to integrate new information into original belief set.Classical BR theory uses AGM frame,but it only resolves problems in single agent BR system.Multi-agent BR faces problems such as the collision of many information sources and how to maximize the logic consistence of multi-agent system.On the basis of game theory model,we form profit matrix under different BR strategies in muhi-agent system and try to get the best strategy that satisfies logic consistence of the system through negotiation.     

Belief Revision: A Critique

We examine carefully the rationale underlying the approaches to belief change taken in the literature, and highlight what we view as methodological problems. We argue that to study belief change carefully, we must be quite explicit about the “ontology” or scenario underlying the belief change process. This is something that has been missing in previous work, with its focus on postulates. Our analysis shows that we must pay particular attention to two issues that have often been taken for granted: the first is how we model the agent's epistemic state. (Do we use a set of beliefs, or a richer structure, such as an ordering on worlds? And if we use a set of beliefs, in what language are these beliefs are expressed?) We show that even postulates that have been called “beyond controversy” are unreasonable when the agent's beliefs include beliefs about her own epistemic state as well as the external world. The second is the status of observations. (Are observations known to be true, or just believed? In the latter case, how firm is the belief?) Issues regarding the status of observations arise particularly when we consider iterated belief revision, and we must confront the possibility of revising by φ and then by ¬ φ.     

Changes of disjunctively closed bases

An operator of contraction for a belief set (a theory) can be obtained by assigning to it a belief base and an operator of partial meet contraction for that base. It is argued that closure of the base under disjunction is an intuitively reasonable condition. Axiomatic characterizations are given of the contractions of belief sets that can be generated by (various types of) partial meet contraction on disjunctively closed bases. The corresponding revision operators are also characterized. Finally, some results are reported on operations on bases that are closed under material implication.I would like to thank Hans Rott and two anonymous referees for valuable comments and the Swedish Council for Research in the Humanities and Social Sciences for financial support.     

Dynamic belief revision operators

The AGM approach to belief change is not geared to provide a decent account of iterated belief change. Darwiche and Pearl have sought to extend the AGM proposal in an interesting way to deal with this problem. We show that the original Darwiche-Pearl approach is, on the one hand excessively strong and, on the other rather limited in scope. The later Darwiche-Pearl approach, we argue, although it addresses the first problem, still remains rather permissive. We address both these issues by (1) assuming a dynamic revision operator that changes to a new revision operator after each instance of belief change, and (2) strengthening the Darwiche-Pearl proposal. Moreover, we provide constructions of this dynamic revision operator via entrenchment kinematics as well as a simple form of lexicographic revision, and prove representation results connecting these accounts.     

Recovery and Epistemic Residue

Two recent defences of the recovery postulate for contraction of belief sets are analyzed. It is concluded that recovery is defensible as a by-product of a formalization that is idealized in the sense of being simplified for the sake of clarity. However, recovery does not seem to be a required feature of the doxastic behaviour of ideal (perfectly rational) agents. It is reasonable to expect that there should be epistemic residues (remnants of rejected beliefs), but not that these should always suffice to recover all the original beliefs if the discarded belief is reinstated.     

AN INTUITIVE MOTIVATION OF BAYESIAN BELIEF MODELS

The general use of subjective probabilities to model beliefs has been justified using many axiomatic schemes. This paper presents a rationale for probability models based on intuitive properties of belief orderings and the effect of evidence on beliefs. Qualitative probability, which imposes stringent constraints on belief representation schemes, is derived from four simple assumptions about beliefs and evidence. Properties shown to be sufficient for the adoption of probability proper by Cox (1978) are derived here from qualitative probability and a principle of plausible reasoning advanced by Polya (1954). Models based on complete orderings of beliefs extend easily to motivate set-valued representations of partial orderings as well.     

On the Logic of Theory Change: Contraction without Recovery

The postulate of Recovery, among the six postulates for theory contraction, formulated and studied by Alchourrón, Gärdenfors and Makinson is the one that has provoked most controversy. In this article we construct withdrawal functions that do not satisfy Recovery, but try to preserve minimal change, and relate these withdrawal functions with the AGM contraction functions.