We introduce a novel class of fully rational contraction operators that work by selecting models, which we call tracked contraction operators. These operators are founded on a plausibility relation on models, called a track, that allows distinguishing between suitable and unsuitable models. We show a representation theorem between tracked contraction operators and the basic rationality postulates of contraction. For the supplementary postulates (conjunction and intersection), we strengthen such operators by imposing the mirroring condition on the track relations. We consider logics that are both Tarskian and compact.
The eld of Belief Change [
Several classes of belief change operators were proposed that abide by such rationality
postulates, called rational belief change operators (see [
Theories, however, are very restrictive, as they do not distinguish between explicit and implicit
beliefs. One can achieve this distinction by dropping the logical closure requirement, and simply
representing an agent’s corpus of beliefs as a set of sentences, called a belief base [
In this work, we devise two novel classes of semantic operators for belief base contraction.
Our approach consists in imposing a pre-order, called a track, upon the models of the logics. A
track indicates the most plausible models, which in turn are selected to perform a contraction.
We show a representation theorem between the basic rationality postulate of belief base
contraction and such novel class of contraction operators. We then impose the mirroring condition
[
Road map: Section 2 introduces some basic notations and de nitions that will be used
throughout this work. In Section 3, we brie y review belief contraction, including both basic
and supplementary rationality postulates of contraction as well as the partial meet contraction
operators. For semantic operators, we review the faithful pre-orders of Katsuno and Mendelzon
[
The power set of a set A is denoted by P(A). We treat a logic as a pair hL, Cni, where L is a language, and Cn : P(L) → P(L) is a logical consequence operator that indicates all the formulae that are entailed from a set of formulae in L. We limit ourselves to logics whose consequence operator Cn satis es: monotonicity: if A ⊆ B then Cn(A) ⊆ Cn(B); idempotency: Cn(Cn(A)) = Cn(A); compactness: if ϕ ∈ Cn(A) then there is some nite set A0 ⊆ A such that ϕ ∈ Cn(A0).
Consequence operators that satisfy the rst three conditions above are called Tarskian. Some times we say that the logic itself is Tarskian. Throughout this work, unless otherwise stated, all the presented results regard logics whose consequence operators are Tarskian and satisfy compactness. A theory is a set of formulae X ⊆ L such that X = Cn(X).
As we are interested to de ne semantic operators, we exploit the semantic of the logics. Given a logic hL, Cni and a set of structures I, an interpretation or a model is an element of I that gives meaning to the formulae of L; I is called an interpretation domain of that logic, whereas each subset of I is called an interpretation set. For instance, an interpretation domain for the Propositional Logic is the power set of the propositional symbols of the language. A satisfaction relation |= ⊆ I × L is used to indicate on which interpretations a formula is satis ed. If M |= α, then we say that M is a model of α. If an interpretation M does not satisfy a formula α, denoted by M 6|= α, then we say that M is a counter-model of α. The set of all models of α is given by JαK, while the set of all counter-models of α is given by JαK.
In Tarskian logics, the consequence operator can be semantically de ned as: a formula
ϕ ∈ Cn(X) i every model that satis es all formulae in X also satis es ϕ [
Throughout this paper we will provide examples to support the intuition of the proposed contraction operators. Due to its simplicity, we will use classical propositional logics to construct such examples. Observe, however, that our results are not con ned to classical propositional logics. As usual, the formulae of classical propositional logics are Boolean formulae constructed from a set AP of atomic propositional symbols, via the operators of conjunction (∧), disjunction (∨) and classical negation (¬). The models are subsets of AP , and the satisfaction relation is de ned as usual.
A pre-order on a domain D is binary relation ⩽ ⊆ D × D that satis es transitivity and re exivity. The minimal elements of a set A ⊆ D w.r.t ⩽ is given by the set min⩽(A) = {a ∈ A | if b ⩽ a then a ⩽ b, for all b ∈ A}. We write a < b to denote that a ⩽ b but b a.
We assume that an agent’s corpus of beliefs is represented as a belief base, which will be denoted
by the letter K. The term belief base has been used in the literature with two main purposes:
(i) as a nite representation of an agent’s beliefs [13, 14, 15], and (ii) as a more general and
expressive approach that distinguishes explicit from implicit beliefs [
Let K be a belief base, a contraction function for K is a function −˙ : L → P(L) that given an
unwanted piece of information α, outputs a subset of K which does not entail α. A contraction
function is subject to the following basic rationality postulates [
For a discussion on the rationale of this postulates, see [
There are other two postulates, called supplementary postulates [
It is important to stress that the study of the supplementary postulates has been con ned to theories, and very little is known about their behaviours on belief bases. Rational contraction operators that satisfy the supplementary postulates will be dubbed fully rational.
Several rational contraction operators were proposed in the literature. One of the most in uential ones is partial meet (De nition 3, below), which makes use of remainders.
Each member of K ⊥ α is called a remainder, and it is a maximal subset of K that does not entail α. A partial meet operator works by selecting remainders and intersecting them. As a remainder set might have many remainders, a choice must be made about which ones are the best to perform the contraction. This choice is done via an extra-logical mechanism called a selection function: De nition 2. A selection function γ picks some remainder of K ⊥ α such that, (i) γ(K ⊥ α) 6= ∅, (ii) γ(K ⊥ α) ⊆ K ⊥ α, if K ⊥ α 6= ∅; and (iii) γ(K ⊥ α) = {K}, otherwise. A selection function γ is relational i there is some binary relation ⩽ on all remainders such that γ(K ⊥ α) = min⩽(K ⊥ α), for all K ⊥ α 6= ∅. If ⩽ is transitive then γ is called transitive relational.
A selection function works as an extra-logical mechanism that realises the agent’s epistemic
preferences. In the original work of [
Remainder sets and selection functions are used to de ne a contraction operator called partial meet contraction: De nition 3. Given a belief base K, and a selection function γ, the operation −˙γ de ned as K −˙γ α = T γ(K ⊥ ϕ) is a partial meet contraction function.
For theories, the transitive relational partial meet operators are characterised by all the rationality postulates of contraction.
As Hansson [18] shows, the transitive relational partial meet operators are not strong enough to satisfy the two supplementary postulates on belief bases. Hansson proposed to strengthen the transitive relations with a property called maximising. However, a representation theorem was not obtained.
We start by explaining how belief contraction works on models when the agent’s corpora of beliefs are represented as theories. After that, we show why such strategies do not work for belief bases.
In terms of models, in order to contract a formula α from a theory K, it su ces to obtain a theory that is a subset of K (due to the inclusion postulate) and it is satis ed by some countermodels of α. This can be formalised by taking a function σ : L → P(I) that picks, for every non-tautological formula α, some counter-models of α. For tautological formulae α, we make σ(α) = ∅, as tautologies have no counter-models. Moreover, if two formulae α and β are logically equivalent, then σ(α) = σ(β). This guarantees that the choice function is not syntax sensitive. We say that σ is a model choice function.
K −˙σ α = {ϕ ∈ K | σ(α) |= ϕ}.
Indeed, the basic rationality postulates of contraction characterise such class of semantic
contraction operators for theories:
Theorem 7. [
For full rationality, there are two main classes of belief operators: the revision operators
based on faithful pre-orders of Katsuno and Mendelzon (KM, for short) [
founded on ⩽K is the operation −˙⩽K such that JK −˙⩽K αK = JKK ∪ min⩽K (JαK). If ⩽K is total then −˙⩽K is a total faithful contraction operator.
A faithful pre-order works as an epistemic preference relation on models. In order to contract a formula α, the agent chooses exactly the most plausible counter-models of α. In the current presentation, KM operators are suitable only for theories, because, for belief bases, there is no guarantee that K −˙ ⩽K α outputs a subset of K, as the inclusion postulate demands. Towards this end, in order to satisfy the inclusion postulate we need only to rewrite faithful contraction in the spirit of De nition 6: get the greatest subset of K satis ed by the minimal counter-models of the formula α to be contracted. Indeed, within classical propositional logics, each KM operation is a special kind of contraction induced by a model choice function as per De nition 6. In classical propositional logics, for theories, the faithful contraction operators on total pre-orders are fully rational:
Caridroit et al. [20] obtain an analogous of Theorem 10 via Levi and Harper identities on the KM faithful revision operators. Observe that the representation theorems above (Theorem 7 and Theorem 10) are established only for theories. Indeed, as Example I below illustrates, both representation theorems breaks down for bases, which is due to violation of the relevance postulate.
Example I. Consider the belief base K = {p, q, p ∨ q, ¬q ∨ p}, expressed in classical propositional logics, with AP = {p, q}. We want to contract the formula p ∧ q. There are only three rational contraction results: A1 = {p, p ∨ q, ¬q ∨ p}, A2 = {q, p ∨ q} and A3 = {p ∨ q}. Not every model choice function, however, induces a rational contraction operator. To see this, note that we have only four models M1 = {p, q}, M2 = {p}, M3 = {q} and M4 = ∅. Observe that Jp ∧ qK = {M2, M3, M4}. Let ⩽K be the following faithful pre-order on K: M1 ⩽K M4 ⩽K M3 ⩽K M2. Let σ be a model choice function such that σ(p ∧ q) = min⩽K (Jp ∧ qK) = {M4}. The only formula of K that M4 satis es is ¬q ∨ p. Thus, K −˙ σ p ∧ q = {¬q ∨ p}. However, this does not correspond to any of the three possible rational contraction results listed above.
In this section, we provide a novel class of semantic contraction operators for belief bases.
In terms of models, contracting a formula α from a theory K consists in picking some countermodels of α and maintaining the formulae in K satis ed by all such picked counter-models. 1Originally, KM de nes an assignment that maps each formula to a pre-order, and de nes such an assignment to be faithful. This assignment has only the purpose to provide general contraction operators. As here we focus on local contraction, we opt to remove this complication and operate directly on the pre-orders. While this strategy yield rational contractions for theories (Theorem 7), it fails for belief bases as Example I illustrates. This occurs because some counter-models of α might satisfy less formulae than allowed by the relevance postulate. For instance, looking back at Example I, according to relevance the formula p ∨ q must be kept. Observe that this formula appears in all the three possible rational contraction results. The counter-model M4, however, does not satisfy p ∨ q, which makes it unsuitable for performing a rational contraction, as picking it would remove p ∨ q. The main hurdle is to properly distinguish between suitable and unsuitable models. To solve this problem, we establish a plausibility relation ⩽ on the models. Intuitively, a pair M ⩽ M 0 means that the model M is at least as plausible as M 0. Towards this end, in order to contract a formula α, only the most plausible counter-models of α w.r.t ⩽ should be chosen, that is, only models within min⩽(JαK). The question at hand is which properties a pre-order on models should satisfy in order to be an adequate plausibility relation that distinguish between suitable and unsuitable models.
Here, we propose such plausibility relations to be de ned upon the notion of information preservation. Intuitively, the more information from K a model preserves the more plausible it is. The set of all formulae from K satis ed by a model M is given by the set Pres(M | K) = {ϕ ∈ K | M |= ϕ}. De nition 11 below formalises a class of pre-orders based on this notion, which we call tracks.
1. If Pres(M | K) = Pres(M | K) then M 0 ⩽K M and M ⩽K M 0; and
0 2. If Pres(M | K) ⊂ Pres(M | K) then M 0 <K M
0
In short, a track relation imposes models that strictly preserve more information to be strictly more plausible (condition 2), while models that preserve the same set of information are equally plausible (condition 1). Thus, in every track for a belief a base K, the models of K are the most plausible ones, and they are also all equally plausible.
Proposition 12. If K is a consistent belief base and ⩽K is a track of K then min⩽K (I) = JKK.
The less pairs a track contains, the more permissive it is. A most permissive track of a belief base K will be called a least track of K. It is easy to see that each belief base has exactly one least track. − De nition 13. A least track of a belief base K is a track ⩽K such that for every track ⩽K of K, − ⩽K ⊆ ⩽K − Observation 14. Every belief base has a unique least track ⩽K.
Example II (continued from Example I). The beliefs in K = {p, q, p ∨ q, p ∨ ¬q} preserved by each of the four models are:
Pres(M1 | K) = K Pres(M3 | K) = {q, p ∨ q}
Pres(M2 | K) = {p, p ∨ q, p ∨ ¬q} Pres(M4 | K) = {¬q ∨ p} Fig. 1 (on the right ) illustrates the set inclusion relation between the preservation sets of each model, while Fig. 1 (on the left) depicts the least track relation of K. As M1 is the only model of
they preserve di erent beliefs in K. For the same reason, M4 and M3 are incomparable. However,
If we choose either M2 or M3 then we get a rational contraction: either A1 = {p, p ∨ q, ¬q ∨ p}, or A2 = {q, p ∨ q}. By picking both models we get the last rational contraction A3 = {p ∨ q}.
plausible one (the suitable ones). Also observe that other tracks exist: for instance augmenting the illustrated track by making M2 and M3 comparable or even M3 and M4 comparable. However, for any of the possible tracks, M4 is never among the suitable ones, as it must be strictly less plausible than M2, due to condition 2 of track’s de nition. This suggests that tracks can be used as an adequate class of plausibility relations to distinguish between suitable and unsuitable models.
M4 = ∅ ⩽K
⩽K
M1 = {p, q} M2 = {p}
K⩾
M3 = {q}
⊃ Pres(M2 | K) ⊂ Pres(M4 | K)
⊃ Pres(M1 | K) = K
Pres(M3 | K)
As tracks establish an adequate notion of plausibility between models, then most plausible ones to contract a formula α are the minimal counter-models of α. In classical propositional logics, such minimal models always exist, as there is only a nite number of models. However, for more expressive logics, such as First Order Logics and several Description Logics [21], there are formulae with an in nite number of (counter-)models. In the presence of an in nite amount of models, some tracks arrange the models through in nite chains. In general, these in nite chains prevents identifying the most plausible counter-models for some formulae. Thus, we need to constrain ourselves to tracks that do not present such bad behaviour, that is, tracks that are founded:
formula α. min⩽(JαK) 6= ∅ for every non-tautological
Relying on founded tracks guarantees that for every non-tautological formula α, there is at least one counter-model to be picked to perform such a contraction. In fact, as long as the underlying Tarskian logic satis es compactness, every belief base presents at least one founded track: its least track.
least track is founded.
We can then de ne a function that selects among the most plausible models:
δ⩽K : L → P(I) such that 1. δ⩽K (α) ⊆ min⩽K (JαK) 2. δ⩽K (α) 6= ∅, if α is not a tautology 3. if α and β are logically equivalent then δ⩽K (α) = δ⩽K (β).
A tracking selection function works similarly to the model choice function for theories. The main di erence is that model choice functions can choose any counter-model of a formula α, while tracking selection functions choose only among the most plausible (w.r.t a track relation) counter-models of α. Condition 3 is related to the postulate of uniformity, and guarantees that a tracking selection function is not syntax sensitive. When it is clear from context, we drop the subscript ⩽K and simply write δ.
Following the same strategy as for theories, a contraction on a belief base is performed by keeping the formulae from the current belief base that are satis ed by all the counter-models selected by a tracking selection function.
de ned as
K −˙δ α = {ϕ ∈ K | δ(α) |= ϕ}.
Example III (continued from Example II). Let ⩽K− be the least track of the belief base K = {p, q, p ∨ q, ¬q ∨ p}. Observe that min⩽K− (p ∧ q) = {M2, M3}. Then, we can choose any combination of M2 and M3 to contract p ∧ q. Let δ1, δ2 and δ3 be tracked selection functions − founded on ⩽K such that δ1(p ∧ q) = {M2}, δ2(p ∧ q) = {M3} and δ3(p ∧ q) = {M2, M3}. They induce the following tracked contraction operators: K −˙δ1 ¬q ∨ p = {p, p ∨ q, ¬q ∨ p}, K −˙ δ2 ¬q ∨ p = {q, p ∨ q}, and K −˙ δ3 ¬q ∨ p = {p ∨ q}. As one can easily check, each one of them is a rational contraction operator.
on relevance. Let β ∈ K \ (K −˙ δ⩽ α). Thus, there is some model M ∈ δ⩽K (α) such that M 6|= β. As M ∈ δ⩽K (α), we have that M |= K −˙ δ⩽ α and M ∈ min⩽K (JαK). Thus, K −˙ δ⩽ α ⊆ Pres(M | K) ⊆ K. Let us suppose for contradiction that α 6∈ Cn(Pres(M | K) ∪ {β}). Thus, there is some model M 0 ∈ JαK such that M 0 |= Pres(M | K) ∪ {β}. This means that, Pres(M | K) ⊂ Pres(M 0 | K) which implies that M 0 <K M . Therefore, M 6∈ min⩽K (JαK), which is a contradiction.
Since a track establishes a plausibility relation between models, it is natural to expect that a track also works as an epistemic preference relation. Therefore, instead of simply picking some of the most plausible models w.r.t a track, it would be rational to pick all such most plausible models. We will call contraction operators that follow this strategy full tracked contraction:
is the function μ⩽K such that μ⩽K (α) = min⩽K (JαK). Tracked contraction operators founded on full tracking selection functions are full tracked contraction operators.
Full tracked contraction operators do satisfy intersection, due to the transitivity of tracks.
Although tracks capture intersection, they are not strong enough to capture conjunction.
Observe that tracks form a special case of faithful pre-orders (De nition 9). It would be natural
then to simply impose totality upon the tracks in the hope of capturing conjunction. Totality,
however, has been criticised in the literature for being too demanding, as an agent might be
indi erent or ignorant on how to grade some of its beliefs [22]. Moreover, works such as [
According to mirroring, if two models are incomparable then they should agree upon their preferences. We will show here that by employing mirroring upon tracks, conjunction is also captured for belief bases.
While both syntactic and semantic operators are well known for belief theory contraction (and other forms of belief change), only syntactic operators are known to be rational on belief bases. In this work, we have introduced two new classes of semantic contraction operators for belief bases: tracked contraction operators and full tracked contraction operators on mirroring. These operators rely on plausibility relations between models, called tracks. In order to contract a formula α, the agent seeks the most plausible counter-models of α w.r.t a track relation, and chooses some of these counter-models (the ones the agent deems most reliable). We have established a representation theorem between tracked contraction operators and the basic rationality postulates of contraction. A track unveils an agent’s epistemic preferences: the most plausible models coincides with the most reliable ones, and the agent picks all these models. Tracked contractions following this strategy are called full tracked contraction. We have shown that tracks that satisfy the mirroring condition yield full tracked contraction satisfying the two supplementary postulates.
As future work we shall investigate if mirroring su ces to establish a representation theorem
between full tracked contractions and the supplementary postulates. This connection with the
supplementary postulates is important, because the study of such postulates has been restricted
to belief change operators on theories. Particularly, the connection between contraction
operators and the supplementary postulates has been established via epistemic preferences relations
such as Epistemic Entrenchment[
We shall extend our results for more expressive logics by dispensing with compactness and widening our results to Tarskian logics. Although we have focused on contraction, our results can be easily translated to revision: instead of selecting counter-models, one needs only to select models of the formulae α to be revised.
The author is supported by the German Research Association (DFG), project number 424710479. [13] B. Nebel, Reasoning and Revision in Hybrid Representation Systems, volume 422 of Lecture
Notes in Computer Science, Springer, 1990. [14] S. E. Dixon, Belief revision: A computational approach, Ph.D. thesis, University of Sydney, 1994. [15] M. Dalal, Investigations into a theory of knowledge base revision, in: Proceedings of the 7th National Conference on Arti cial Intelligence, AAAI Press / The MIT Press, 1988, pp. 475–479. [16] A. Fuhrmann, Theory contraction through base contraction, J. Philos. Log. 20 (1991) 175–203. [17] S. O. Hansson, Belief contraction without recovery, Stud Logica 50 (1991) 251–260. [18] S. O. Hansson, Reversing the levi identity, J. Philos. Log. 22 (1993) 637–669. [19] S. O. Hansson, R. Wassermann, Local change, Stud Logica 70 (2002) 49–76. [20] T. Caridroit, S. Konieczny, P. Marquis, Contraction in propositional logic, Int. J. Approx.
Reason. 80 (2017) 428–442. doi:10.1016/j.ijar.2016.06.010. [21] F. Baader, I. Horrocks, C. Lutz, U. Sattler, An Introduction to Description Logic, Cambridge
University Press, 2017. [22] T. A. Meyer, W. A. Labuschagne, J. Heidema, Re ned epistemic entrenchment, J. Log. Lang.
Inf. 9 (2000) 237–259. [23] J. S. Ribeiro, A. Nayak, R. Wassermann, Belief update without compactness in non- nitary languages, in: Proceedings of the Twenty-Eighth International Joint Conference on Arti cial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019, ijcai.org, 2019, pp. 1858–1864.