
06046395
b
06046395
Ribeiro, M\'arcio Moretto
Belief revision in nonclassical logics.
SpringerBriefs in Computer Science. New York, NY: Springer (ISBN 9781447141853/pbk; 9781447141860/ebook). xi, 120~p. EUR~39.95/net; SFR~53.50; \sterling~35.99/pbk (2013).
2013
New York, NY: Springer
EN
belief contraction
belief revision
Tarskian logics
partial meet contraction
kernel contraction
internal revision
external revision
belief revision without negation
recovery
relevance
coreretainment
doi:10.1007/9781447141860
The book is an adaptation of the author's PhD thesis. It generalises belief revision to a broad range of logics, defined in Chapter II from a Tarskian consequence relation $Cn$ on a language $\cal L$, which maps subsets of $\cal L$ to subsets of $\cal L$ with the properties that $A\subseteq Cn(A)=Cn(Cn(A))$, and if $A\subseteq B$ then $Cn(A)\subseteq Cn(B)$. A number of possible key properties of $Cn$\ are listed, in particular: compactness, closure under standard language ($\cal L$ is closed under the application of standard Boolean operators), deduction ($\alpha\in Cn(A\cup\{\beta\})$ iff $\beta\rightarrow\alpha\in Cn(A)$), supraclassicality ($Cn(A)$ contains all classical logical consequences of $A$)  these four properties being referred to as the AGMassumptions , distributivity ($Cn(A\cup B)\cap Cn(A\cup C)\subseteq Cn(A\cup(Cn(B)\cap Cn(C)))$), closure under complement (for all $A\subseteq\cal L$, there exists $A'\subseteq\cal L$ with $Cn(A\cup A')=\cal L$ and $Cn(A)\cap Cn(A')=\emptyset$), and $\alpha$local noncontravention (if $\alpha\notin Cn(A)$ then $\alpha\notin Cn(A\cup\{\neg\alpha\})$). Relations between these properties and others are stated and proved. Chapter III provides an overview of logics: classical propositional logic, which satisfies all the properties listed in Chapter II; intuitionistic propositional logic, shown to be compact and distributive but not satisfying the AGMassumptions; propositional Horn logic (whose formulas are implications of atoms from conjunctions of atoms, so whose syntax is too restricted to let it satisfy the AGMassumptions), shown to be compact but not distributive; the description logic ${\cal{ALC}}$ and some of its extensions (again, the syntax is too restricted to let them satisfy the AGMassumptions), shown to be compact and distributive. Many other properties are listed and proved, and for both classical and intuitionistic logic, a proof theory is presented and a completeness result is proved. Chapter IV provides an overview of classical belief revision. The first half of the chapter presents the AGM framework, where belief sets are closed under ${Cn}$. It is defined in terms of the AGM postulates of closure, success, inclusion, vacuity, and extensionality for both contraction and revision, with recovery (contracting a belief set $K$ by a formula $\alpha$ and then adding $\alpha$ and closing under ${Cn}$\ yields a belief set $(K\alpha)+\alpha$ which expands $K$) and consistency (revising a belief set $K$ by a consistent formula $\alpha$ yields a consistent set $K\ast\alpha$) added for contraction and revision, respectively. For logics that satisfy the AGM postulates, contraction is characterised in terms of partial meet contraction: $K\alpha$ is the intersection of a selection of members of $K\bot\alpha$, the set of all maximal subsets of $K$ that do not imply $\alpha$. Revision is characterised in terms of contraction from the Levi identity: $K\ast\alpha$ is of the form $(K\neg\alpha)+\alpha$. Contraction is characterised in terms of revision from the Harper identity: $K\alpha$ is of the form $(K\ast\neg\alpha)\cap K$. The second half of the chapter presents the belief base theory, where sets of beliefs are arbitrary. With the contraction of belief bases, recovery is problematic, and can be replaced by relevance (if $\beta\in B\setminus(B\alpha)$ then there is $B'\subseteq B$ with $B\alpha\subseteq B'$ and $\alpha\in{Cn}(B'\cup\{\beta\})\setminus{Cn}(B')$) or coreretainment (same as relevance without requiring that $B\alpha\subseteq B'$). For compact logics, partial meet contraction is characterised by the properties of success, inclusion, uniformity ($B\alpha=B\beta$ if $\alpha$ and $\beta$ are two formulas which belong to ${Cn}(B')$ for precisely the same subsets $B'$ of $B$), and relevance. With kernel meet contraction, $K\alpha$ is obtained from $B$ by removing at least one formula from each member of $B{\amalg}\alpha$, the set of all minimal subsets of $K$ that imply $\alpha$. Kernel meet contraction is characterised by the properties of success, inclusion, uniformity and coreretainment. Revision can be defined from contraction either via the Levi identity, in which case it is called internal revision, or via a reversed version of it ($B\ast\alpha$ is of the form $(B+\alpha)\neg\alpha$), in which case it is called external revision. For compact logics that satisfy $\alpha$local noncontravention, internal and external kernel meet revision are characterised by properties one of which is coreretainment. Internal and external partial meet revision are characterised by properties one of which is relevance. The chapter ends with a presentation of belief base semi revision, where the input is first added to the belief base but might be removed when consistency is restored (success is dropped). The contributions of the author start with Chapter V, with a presentation of AGM contraction in nonclassical logics, where relevance and recovery are not equivalent properties. As the logics considered do not have to be closed under standard language (and in particular, under conjunction), a belief base is contracted or revised by a finitely representable set of formulas $A$ (i.e., for which there exists a finite $A'$ with ${Cn}(A)={Cn}(A')$) rather than by a single formula. It is shown that a logic is AGMcompliant, that is, guarantees that contraction satisfying the AGM postulates, trivially generalised to deal with finitely representable sets of formulas rather than single formulas as inputs, is possible from any belief set iff the logic is decomposable, a property defined in Chapter II which captures the existence of a kind of logical complement for logics without a syntactic negation. It is also shown that compact logics are relevancecompliant, that is, guarantee that contraction satisfying the AGM postulates generalised as before and with recovery replaced by relevance, is always possible. Moreover, those postulates characterise partial meet contraction. The message is therefore that relevance is a good alternative to recovery to develop belief contraction in nonclassical logics. The chapter ends with a generalisation of the result that relevance and recovery are equivalent in classical logic in the presence of the other AGM postulates: it is enough that the logic satisfies closure under complement and distributivity. Chapter VI covers AGM revision in logics without negation, ruling out the option of defining revision from contraction via the Levi identity. Belief set revision without negation (RwN) of a belief set $K$ by a finitely representable and consistent set $A$ of formulas is defined as the intersection of a selection of maximally subsets of $K$ consistent with $A$, adding $A$ and closing under ${Cn}$. The AGM postulates for revision, trivially generalised to deal with finitely representable sets of formulas rather than single formulas as inputs, as well as adapted forms of relevance and uniformity, are shown to hold for any RwN in a compact logic. These properties actually characterise RwN in the case of a logic which satisfies the AGM assumptions. Also, RwN is shown to be fully characterised by only closure, success, inclusion, consistency, relevance and uniformity in a logic which is closed under compact and distributive logic. Chapter VII covers base revision in logics without negation. With a given set $\Omega$ of ``undesirable'' formulas, a set $A$ of formulas is said to be $\Omega$consistent if ${Cn}(A)\cap\Omega$ is empty. Six versions of revision are presented: three cases of kernel revision, and three cases of partial meet revision. For both families of three cases, revision can be internal or external, and in the latter case, it can impose either strong success ($A\subseteq B\ast A$, whereas weak success guarantees this only for an $\Omega$consistent $A$), or strong consistency ($B\ast A$ is $\Omega$consistent, whereas weak consistency guarantees only that $B\ast A$ is $\bot$consistent for an $\Omega$consistent $A$). Each of these six forms of revision is shown to enjoy a characterisation in terms of some of the properties of strong or weak success, strong or weak consistency, inclusion, preexpansion ($(B+A)\ast A=B\ast A$), coreretainment, relevance, and uniformity. Chapter VIII describes algorithms to compute the sets involved in the definition of partial meet and kernel contraction. They are shown to be closely related, and examples are given where one set can be exponentially large while the other is only linearly large. With the background provided up to Chapter IV, the book is truly selfcontained, and the reader will appreciate that the proofs of all results, including the most wellknown ones, are given in detail. The proposed generalisation of belief contraction and belief revision to classes of logics defined by properties of their consequence relations is a valuable addition to the field, with natural concepts and significant results. It is just a pity that there are so many grammatical and syntactic errors that nobody bothered to fix or require to fix, even for the most blatant ones, and that the typography is slack in some places.
\'Eric Martin (Sydney)