Consistency-based revision of structured belief bases (Q2805411)

The technical part of the paper starts in Section 3 and presents the belief change framework introduced in [\textit{J. P. Delgrande} and \textit{T. Schaub}, Artif. Intell. 151, No. 1--2, 1--41 (2003; Zbl 1082.68818)], as it provides the foundation for the proposed formalism. Given a set of atoms PROP and LANG, the propositional language over PROP, a \textit{belief change scenario} is a triple \(\langle K,R,C\rangle\) of subsets of LANG with \(K\) representing a belief set meant to be modified into a set denoted \(K\dotplus R\mathrm{CONT } C\) that contains all members of \(R\) and no member of \(C\) (with \(K\dotplus R\) and \(K\mathrm{CONT } C\) as particular cases of revision or contraction, when \(C\) or \(R\) are empty, respectively): formally, \(K\dotplus R\mathrm{CONT }C\) is defined as the intersection of all \textit{belief change extensions} of \(\langle K,R,C\rangle\), namely, all sets of the form \(\mathrm{CN}(K'\cup\mathrm{EQ}\cup R)\cap\mathrm{LANG}\) that do not intersect \(C\) where: {\parindent=0.6cm\begin{itemize}\item[--] CN is closure under logical consequence, \item[--] \(K'\) is \(K\) with each atom \(p\) in \(K\) replaced by a distinguished copy \(p'\), and \item[--] EQ is a \(\subseteq\)-maximal set of equivalences between an atom and its copy. NEWLINENEWLINE\end{itemize}}NEWLINENEWLINESection 3 presents a number of easy results, and in particular a characterisation of \(K\dotplus R\mathrm{CONT }C\) as the set of logical consequences of a disjunction of formulas denoted \(K\oplus R\ominus C\), each of whose disjuncts corresponds to a belief change extension of \(\langle K,R,C\rangle\) that closely follows its definition.NEWLINENEWLINEIn Section 4, the authors propose a belief revision operator, defined on the basis of a \textit{belief base}, namely, a triple \(K=\langle \mathrm{OB},\mathrm{DS},\mathrm{DA}\rangle\) of subsets of LANG meant to represent \textit{observations}, \textit{defeasible statements}, and \textit{domain axioms}, respectively; \(K\) determines a belief set, denoted \(B_K\), defined as \(\mathrm{DS}\dotplus(\mathrm{OB}\cup\mathrm{DA})\). Given a formula \(\alpha\) representing a new observation, the revision of \(K\) by \(\alpha\), denoted by \(K\ast\alpha\), is defined as \(\langle \mathrm{OB}_1,\mathrm{DS},\mathrm{DA}\rangle\) with \(\mathrm{OB}_1=\mathrm{OB}\oplus\{\alpha\}\ominus\{\neg\bigwedge\mathrm{DA}\}\), making \(B_{K\ast\alpha}\) equal to NEWLINE\[NEWLINE\mathrm{DS}\dotplus\bigl[(\mathrm{OB}\oplus\{\alpha\}\ominus\{\neg\bigwedge\mathrm{DA}\})\cup\mathrm{DA}\bigr] NEWLINE\]NEWLINE (hence, the observation set OB is revised so as to contain the new observation while maintaining the domain axioms, and the result is then used to revise the defeasible pieces of knowledge).NEWLINENEWLINESection 5 establishes that the proposed revision operator satisfies 6 of the 8 AGM postulates and a weaker version of one of the remaining two, whereas the last one (if \(\neg\beta\notin B_{K\ast\alpha}\) then \(B_{K\ast\alpha}+\beta\subseteq B_{K\ast(\alpha\wedge\beta)}\)) is not satisfied.NEWLINENEWLINESection 6 illustrates the approach with many examples.NEWLINENEWLINESection 7 briefly considers prioritised belief bases, breaking DS into disjoint sets \(\mathrm{DS}_1\), \dots, \(\mathrm{DS}_n\) (listed in increasing order of priority), and redefining \(B_K\) as NEWLINE\[NEWLINE \mathrm{DS}_1\dotplus(\mathrm{DS}_2\oplus\dots(\mathrm{DS}_n\oplus(\mathrm{OB}_1\cup\mathrm{DA}))\dots). NEWLINE\]NEWLINE Section 8 redefines the revision operator so that revision is triggered by a piece of knowledge rather than by an observation.NEWLINENEWLINESection 9 proposes a model-theoretic characterisation of the belief revision operator based on a notion of distance between two interpretations, defined as the number of atoms that are true in one interpretation and false in the other.NEWLINENEWLINESection 10 discusses related work.