# On the Logic of Theory Base Change: Reformulation of Belief Bases

Eduardo Fermé, Andreas Herzig, Maria Vanina Martinez

► To cite this version:

Eduardo Fermé, Andreas Herzig, Maria Vanina Martinez. On the Logic of Theory Base Change: Reformulation of Belief Bases. AAAI-25, Feb 2025, Philadelphia, United States. pp.14922-14929, 10.1609/AAAI.V39I14.33636. hal-05404062

HAL Id: hal-05404062

https://hal.science/hal-05404062v1

Submitted on 8 Dec 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
# On the Logic of Theory Base Change: Reformulation of Belief Bases

Eduardo L. Fermé<fnref n="1" />, Andreas Herzig<fnref n="2" />, Maria Vanina Martinez<fnref n="3" />

## Abstract

In the logic of theory change, the AGM model has acquired the status of a standard model. However, the AGM model does not seem adequate for some contexts and application domains. This inspired many researchers to propose extensions and generalizations to AGM. Among these extensions, one of the most important are belief bases. Belief bases have more expressivity than belief sets, as explicit and implicit beliefs have different statuses. In this paper, we present reformulation, a belief change operation that allows us to reformulate a belief base making some particular sentences explicit without modifying the consequences of the belief base. We provide a constructive method and its axiomatic characterization.

## 1 Introduction

The primary objective underlying research in the area of belief change is to identify appropriate methods for modeling belief states of rational agents and the changes that occur in these states when the agent receives new information as a result of its interaction with the world. What is now generally considered the standard model of belief change was proposed by Alchourrón, Gärdenfors, and Makinson (1985) and is commonly known as the AGM model. In this framework, the belief state of an agent is modeled by a belief set, i.e., a set of sentences that is closed under logical consequence. Furthermore, contractions are considered the primary type of belief change, that is, when one or more beliefs are to be eliminated from the agent's belief state.

In Alchourrón, Gärdenfors, and Makinson (1985), a set of conditions, commonly referred to as the AGM postulates for contraction, were defined as the properties that such operations should satisfy. Additionally, a constructive definition of contraction operations was presented, called partial meet contractions, and a representation theorem was established, proving that the AGM postulates for contraction exactly characterize this class of operations. Subsequently, several other constructive definitions have been proposed that yield the same class of operations, including safe and kernel contraction (Alchourrón and Makinson 1985; Hansson 1994).

Various extensions and generalizations of the AGM model have been proposed since then. One of the most significant

extensions is the use of belief bases (Hansson 1991) instead of belief sets. Belief bases consist of sets of sentences not necessarily closed under logical consequence. Belief bases have more expressive power than belief sets, as they allow to distinguish between basic beliefs and beliefs that are inferred from basic beliefs: a logical consequence *p* of *B* is explicitly believed if *p* ∈ *B*, and is implicitly believed otherwise (Levesque 1984; Lorini 2020). For example, consider the following two belief bases:

$$B1 = \{p, p \leftrightarrow q\};$$

$$B2 = \{p, q\}.$$

They have the same logical consequences, and, therefore, generate the same belief set. However, note that the difference between *B1* and *B2* is not just a “notational bondage” that should be straightened out by some process of “articulation”” (Belnap 1979), cited in (Rott 2000)): the fact that they are expressed differently adds to their semantics.

Several contraction models initially defined for belief sets have been adapted to belief states, such as partial meet and kernel contractions (Hansson 1991). Going back to the previous example, AGM contractions by *p* on *B1* and *B2* would yield the same result, the reason being that it is not *B1* and *B2* that are contracted, but rather the set of all logical consequences of *B1* and *B2*. However, in Hansson's tradition of belief bases, due to the postulate of inclusion ((B - *p* ⊆ B) the contraction by *p* can yield different results for *B1* and *B2* even when *B1* and *B2* have the same logical consequences.<fnref n="1" /> Under pseudo-contraction one would get the same result in both bases when contracting by *p*; however, this is a much more complex operation from a computational point of view.

A similar situation arises when we focus on revision. Consider the previous belief bases and let *B1* represent Abe's belief state and *B2* Bob's belief state; let also proposition *p* be “Liberal Party will support the proposal to subsidize the steel industry”, and let *q* be “Ms. Smith, who is a liberal party's member, will vote in favor of that proposal”. Now, Abe and Bob receive and accept the information that *p* is

<footnote n="1">¹Universidade da Madeira and NOVA-LINCS, Portugal</footnote>

<footnote n="2">²IRIT, CNRS, Univ. Toulouse, France</footnote>

<footnote n="3">³Artificial Intelligence Research Institute (IIIA-CSIC), Spain</footnote>

<footnote>ferme@uma.pt, andreas.herzig@irit.fr, vmartinez@iiia.csic.es</footnote>

<footnote n="1">¹In Santos et al. (2018), the authors define the operation of pseudo-contraction, which explores a different inclusion postulate, namely the set of logical consequences of *B* - *p* is included in the set of logical consequences of *B*.</footnote>
wrong, and they both revise their belief states to include $\neg p$. After that, Bob has the basic beliefs $\neg p$ and $q$, while Abe has the basic beliefs $\neg p$ and $p \leftrightarrow q$. Therefore Bob now implicitly believes that $q$ while Abe implicitly believes that $\neg q$.

From the examples described above, it can be considered that while $B1$ and $B2$ are statically equivalent, they fail to be dynamically equivalent (Hansson 2022) because their revision may lead to different outcomes. Both in the AGM framework and in the belief base framework there are no operations transforming $B1$ into the logically equivalent $B2$ (or the other way round). If we take belief bases seriously then such operations should however be of interest. We therefore propose in this article a new belief change operation for belief bases that we call reformulation. Such an operation has not been considered up to now in the belief revision literature. Through this operation, some implicit beliefs are converted into explicit beliefs and vice versa, while the resulting base remains logically equivalent to the initial base. In the most general case, reformulation is a function that typically takes a belief base $B1$ and a sentence $p \in Cn(B1)$ as input and returns a new belief base $B2$ that is logically equivalent to $B1$, but not necessarily equal to $B1$.

For the sake of simplicity, we start with a reformulation operation $R$ with two arguments: a belief base $B$ and a sentence $p$ that we want to make explicit, in the sense that its epistemic status should be “upgraded” from an implicit to an explicit belief. We generalize the operation to the case where $p$ is not a logical consequence of $B$: we stipulate that $R(B, p) = B$ in that case.

For a practical application of such operator, consider a piece of legal text, e.g. filled with legal terms like the ones we agree to when using an app or a service online. As important information may be kept buried in a large set of rules and statements, it is of interest to be able to make explicit some terms. Such terms are implied but not explicitly stated in the text, and the role of reformulation is to make things clearer from a user's perspective or from a legal advice point of view.

A straightforward candidate for the definition of $R$ is

$$R(B, p) = \{p\} \cup B.$$

However, we typically aim not only to expand $B$ but also to “clean it up,” i.e., in the pursuit of non-redundancy, we would like to eliminate those sentences or sets of sentences that render $p$ implicit. That is, we require that $R(B, p) \setminus \{p\} \nvDash p$ when $\nvDash p$. For example, for

$$B3 = \{q, q \to p\},$$

$p$ is merely a consequence of $q$ and $q \to p$. Therefore either $q$ or $q \to p$ must be eliminated. Going back to the legal text example, besides making some statements explicit, it may be important to remove all other redundant implications of them to both simplify the text and to facilitate future updates, as regulations and terms of services change quite often.

The aim of the paper is to define a constructive reformulation method and to study its axiomatic characterization.

The paper is organized as follows. In Section 2 we provide the necessary background. In Section 3 we present an

operation of reformulation that is based on AGM base contraction. In Section 4 we provide and analyse some postulates for reformulation operations. In Section 5 we axiomatically characterize the defined reformulation operation. In Section 6 we discuss some possible alternatives and extensions to our proposal. In Section 7 we relate our operation with other approaches in the literature and finally, conclusions and future work come in Section 8.

## 2 Background

In this section we recall some of the formal concepts of belief change operations for belief bases.

### 2.1 Formal Preliminaries

Beliefs are expressed in a language $\mathcal{L}$ that is called the object language of our model. We will assume that $\mathcal{L}$ is closed under truth-functional connectives: negation ($\neg$), conjunction ($\wedge$), disjunction ($\vee$), implication ($\to$) and equivalence ($\leftrightarrow$).

We shall make use of a consequence operation $Cn$ that takes sets of sentences to sets of sentences and satisfies the standard Tarskian properties (Tarski 1956), namely: (i) $B \subseteq Cn(B)$ (inclusion); (ii) If $B \subseteq B'$, then $Cn(B) \subseteq Cn(B')$ (monotony) and (iii) $Cn(B) = Cn(Cn(B))$ (iteration). Furthermore, we assume that $Cn$ satisfies supraclassicality and compactness. We will sometimes use $Cn(p)$ for $Cn(\{p\})$, $B \vdash p$ for $p \in Cn(B)$, $\vdash p$ for $p \in Cn(\emptyset)$, $B \nvDash p$ for $p \notin Cn(B)$, $\nvDash p$ for $p \notin Cn(\emptyset)$. Finally, we assume that $p \to q \in Cn(B)$ iff $q \in Cn(B \cup \{p\})$. The letters $p, q, \dots$ will be used for denoting sentences of $\mathcal{L}$. $B, B', \dots$ shall denote sets of sentences of $\mathcal{L}$.

### 2.2 Base Contraction Functions

In this subsection we recall two well-known constructive models of contraction operations on belief bases and their characterization in terms of postulates.

Partial meet contractions are obtained by means of a selection among the maximal subsets of $B$ that do not imply the sentence to be contracted (Alchourrón, Gärdenfors, and Makinson 1985). They were adapted to belief bases by Hansson (1992).

**Definition 1** (Alchourrón, Gärdenfors, and Makinson 1985; Hansson 1992) Let $B$ be a belief base. Let $B \perp p$ be the set of all maximal subsets of $B$ that do not imply $p$. Let $\gamma : (2^{\mathcal{L}} \times \mathcal{L}) \to 2^{2^{\mathcal{L}}}$ be a selection function<fnref n="2" /> that satisfies: $\gamma(B \perp p)$ is a non-empty subset of $B \perp p$ (unless $B \perp p$ is empty, in which case $\gamma(B \perp p) = \{B\}$). The partial meet contraction on $B$ that is generated by $\gamma$ is the operation $-\gamma$ such that for all sentences $p$:

$$B - \gamma p = \bigcap \gamma(B \perp p).$$

An operation $-$ on $B$ is a partial meet contraction if and only if there is a selection function $\gamma$ for $B$ such that for all sentences $p: B - p = B - \gamma p$.

Partial meet base contraction has been characterized in terms of the following postulates:

<footnote n="2">²We use the standard notation $\gamma(B \perp p)$ instead of $\gamma(B, p)$.</footnote>
**Observation 2** (Hansson 1992) Let B be a belief base. The operation – is an operation of partial meet base contraction if and only if it satisfies:

$$ (C1) \quad B - p \subseteq B. \qquad (C-Inclusion) $$

$$ (C2) \quad \text{If } \forall p, \text{ then } B - p \nvdash p. \qquad (C-Success) $$

$$ (C3) \quad \text{If } q \in B \text{ and } q \notin B - p, \text{ then there is a set } B' \text{ such that } B - p \subseteq B' \subseteq B \text{ and } B' \nvdash p \text{ but } B' \cup \{q\} \vdash p. \qquad (C-Relevance) $$

$$ (C4) \quad \text{If it holds for all subsets } B' \text{ of } B \text{ that } p \in Cn(B') \text{ if and only if } q \in Cn(B') \text{ then } B - p = B - q. \qquad (C-Uniformity) $$

Kernel base contraction (Hansson 1994) is based on identifying the minimal sets of sentences of a belief base B that contribute effectively to imply p, the p kernels. For each of them an incision is made so that they no longer imply p.

Formally:

**Definition 3** (Hansson 1994) Let $B \perp p$ be the set of all minimal subsets of B that imply p. An incision function $\sigma: 2^{\mathcal{L}} \to 2^{\mathcal{L}}$ for B is a function such that for all sentences p:

$$ 1. \sigma(B \perp p) \subseteq \bigcup (B \perp p). $$

$$ 2. \text{ If } \emptyset \neq B' \in B \perp p, \text{ then } B' \cap \sigma(B \perp p) \neq \emptyset. $$

Hansson characterized kernel base contraction through the following set of postulates:

**Definition 4** (Hansson 1994) Let B be a belief base and $\sigma$ an incision function for B. A kernel base contraction – is defined as follows:

$$ B - p = B \setminus \sigma(B \perp p). $$

Kernel base contraction has been characterized in terms of the following postulates:

**Observation 5** (Hansson 1994) Let B be a belief set. The operation – is an operation of kernel base contraction if and only if it satisfies C-Inclusion, C-Success, C-Uniformity, and

$$ (C5) \quad \text{If } q \in B \text{ and } q \notin B - p \text{ then there is some set } B' \text{ such that } B' \subseteq B \text{ and } B' \nvdash p \text{ but } B' \cup \{q\} \vdash p. \qquad (C-Core-retainment) $$

We now recall some other well known base contraction postulates; we refer to (Hansson 1999, Ch.2) and (Garapa 2017) for more details.

$$ (C7) \quad \text{If } \vdash p \text{ then } B - p = B. \qquad (C-Failure) $$

$$ (C8) \quad \text{If } B \nvdash p \text{ then } B - p = B. \qquad (C-Vacuity) $$

$$ (C9) \quad B \cap Cn(B - p) \subseteq B - p. \qquad (C-Relative Closure) $$

$$ (C10) \quad \text{If } \vdash p \leftrightarrow q \text{ then } B - p = B - q. \qquad (C-Extensionality) $$

$$ (C11) \quad \text{If } q \in B \text{ and } q \notin B - p \text{ then } B - p \nvdash p \lor q. \qquad (C-Disjunctive Elimination) $$

The following observation highlights some relations among the postulates presented above.

**Observation 6** (Hansson 1999; Fermé, Krevneris, and Reis 2008) Let – be a belief change operation. Then:

(a) If – satisfies C-Relevance, then it satisfies relative C-Relative Closure and C-Core-retainment.

(b) If – satisfies C-Inclusion and C-Core-retainment, then it satisfies C-Failure and C-Vacuity.

(c) If – satisfies C-Uniformity, then it satisfies C-Extensionality.

(d) If – satisfies C-Disjunctive Elimination, then it satisfies C-Relative Closure. If – also satisfies C-Inclusion then it satisfies C-Failure.

(e) If – satisfies C-Relevance, then it satisfies C-Disjunctive Elimination.

### 3 Construction of Reformulation Operations

As we mentioned in the introduction, the first candidate for a reformulation operation is nothing but an expansion, i.e.,

$$ R(B, p) = B \cup \{p\}. $$

In the case where p was already derived from B, this operation conserves p not only as an implicit belief but also as an explicit belief. We may however want to avoid redundancy and transform p into an explicit belief. Then we have to satisfy the following condition:

$$ R(B, p) \setminus \{p\} \nvdash p. $$

A natural way to do this could be to first completely eliminate p from B. This means that reformulation is based on a base contraction followed by explicitly adding back p. Formally:

$$ R(B, p) = B - p \cup \{p\} $$

As we want $Cn(R(B, p)) = Cn(B)$ to hold, the following condition should be satisfied by the contraction operation:

$$ (C6) \quad \text{If } q \in B \text{ and } q \notin B - p \text{ then } B - p \vdash p \rightarrow q. \qquad (C-Recovery) $$

C-Recovery is a well-known postulate in the literature: it was introduced by the AGM trio for minimal change in (belief set) contraction. None of the base contraction functions presented above satisfies recovery.<fnref n="3" />

However, one can transform any contraction function into a contraction function satisfying C-Recovery and C-Success.<fnref n="4" />

**Proposition 7** Let B be a belief base and – a contraction function that satisfies C-Success and C-Inclusion. The operation $\div$ defined by

$$ B \div p = B - p \cup \{p \rightarrow q : \nvdash q \leftrightarrow p \text{ and } q \in B \setminus B - p\} $$

satisfies C-Recovery.

<footnote n="3">³The postulate of recovery is the most debated postulate of classic AGM contraction. We refer to (Fermé 2001) and (Fermé and Hansson 2018, Section 5.1) for an overview of the discussion.</footnote>

<footnote n="4">⁴This construction was inspired by contraction functions defined in Nebel (1989).</footnote>
**Proof.** Trivial by definition of C-Recovery (C6).

<figure><img src="image_2.png" /></figure>

With this addition, it is possible to define a model of reformulation that fulfills our previous intuitions:

**Definition 8** Let $B$ be a belief base, $p$ a formula, and $-$ a base contraction function. The reformulation of $p$ in $B$ is:

$$R(B, p) = B - p \\ \cup \{p \to q : \nvdash q \leftrightarrow p \text{ and } q \in B \setminus B - p\} \\ \cup \{p\}$$

when $B \vdash p$, and $R(B, p) = B$ when $B \nvdash p$.

If $-$ is a partial meet base contraction then $R(B, p)$ is a partial meet-based reformulation operation, and if $-$ is a kernel base contraction then $R(B, p)$ is a kernel-based reformulation operation.

Basically, the operation eliminates all the implicit ways to obtain $p$ from the belief base via a contraction function and adds $p$ explicitly. All the explicit sentences that were erased in the contraction can be recovered, implicitly, thanks to the addition of $\{p \to q : \nvdash q \leftrightarrow p \text{ and } q \in B \setminus B - p\}$.

# 4 Postulates for Reformulation

In this section we introduce postulates that constitute desirable properties of reformulation operations.

We will start by setting minimum requirements. The first one is that reformulation produces only internal changes: no new beliefs are added or removed from the belief set.

$$ (\mathbf{R1}) \quad Cn(R(B, p)) = Cn(B). \quad (\text{Logical Equivalence}) $$

The second postulate claims that, after the reformulation by $p$, $p$ must be explicitly believed:

$$ (\mathbf{R2}) \quad \text{If } B \vdash p, \text{ then } p \in R(B, p). \quad (\text{Explicit Success}) $$

**Definition 9** Let $B$ be a belief base and $p$ a formula. An operation $R: 2^{\mathcal{L}} \times \mathcal{L} \to 2^{\mathcal{L}}$ is a basic reformulation operation if and only if it satisfies (R1) and (R2).

The following postulate claims that reformulating $B$ by $p$ eliminates $p$ as an implicit sentence:

$$ (\mathbf{R2b}) \quad \text{If } \nvdash p \text{ then } R(B, p) \setminus \{p\} \nvdash p. \quad (\text{Isolation Success}) $$

According to the criterion of minimal change, reformulating a belief base by $p$ only can change sentences in $B$ that are, in some sense, “related” to $p$. This is reflected by postulates (R3) and (R5), which are respectively inspired by the belief base contraction postulates C-Relevance (C3) and C-Core-retainment (C5).

$$ (\mathbf{R3}) \quad \text{If } q \in B \text{ and } q \notin R(B, p), \text{ then there exists } H \text{ such that } H \subseteq B \text{ such that } (B \cap R(B, p)) \setminus \{p\} \subseteq H \text{ and } H \nvdash p \text{ but } H \cup \{q\} \vdash p. \quad (\text{Relevance}) $$

$$ (\mathbf{R5}) \quad \text{If } q \in B \text{ and } q \notin R(B, p), \text{ then there exists } H \subseteq B \text{ such that } H \nvdash p \text{ but } H \cup \{q\} \vdash p. \quad (\text{Core-retainment}) $$

When $\vdash p \leftrightarrow p'$ then it is reasonable that the reformulations of $B$ by $p$ and $p'$ have the same outcome, with the exception of $p$ and $p'$:

$$ (\mathbf{R4a}) \quad \text{If } \vdash p \leftrightarrow p', \text{ then } Cn(R(B, p) \setminus \{p\}) = Cn(R(B, p') \setminus \{p'\}). \quad (\text{Weak Extensionality}) $$

$$ (\mathbf{R4b}) \quad \text{If } \vdash p \leftrightarrow p', \text{ then for each } r \in R(B, p) \text{ there exists } s \in R(B, p') \text{ such that } \vdash r \leftrightarrow s. \quad (\text{Extensionality}) $$

As in belief contraction, the notion of extensionality can be extended to sentences with the same status regarding $B$. Similar to what Hansson pointed out for base contraction (Hansson 1992, p.94), the next postulate ensures that the result of reformulating $B$ by $p$ depends only on which subsets of $B$ imply some element of $B$; that is, if two sentences have the same epistemic attitude regarding all the subsets of $B$, then their reformulations coincide (with the exception of the proper sentences). Formally, this is:

$$ (\mathbf{R4}) \quad \text{If } p \in Cn(B') \text{ if and only if } q \in Cn(B') \text{ for all subsets } B' \text{ of } B, \text{ then } B \cap (R(B, p) \setminus \{p, q\}) = B \cap (R(B, q) \setminus \{p, q\}). \quad (\text{Uniformity}) $$

The following postulate describes what happens when a sentence $q$ is eliminated from $B$ in a reformulation:

$$ (\mathbf{R6}) \quad \text{If } q \in B \setminus R(B, p), \text{ then } p \to q \in R(B, p). \quad (\text{Recovery}) $$

On the other hand, the following postulate is about what happens when $q$ is introduced by the reformulation.

$$ (\mathbf{R6b}) \quad \text{If } q \in R(B, p) \setminus (B \cup \{p\}), \text{ then there exists } r \text{ such that } r \in B \setminus R(B, p) \text{ and } \vdash q \leftrightarrow (p \to r). \quad (\text{Dual Recovery}) $$

If $p$ is not believed in $B$, then the minimal change to reformulate $B$ by $p$ is to do nothing.

$$ (\mathbf{R7}) \quad \text{If } B \nvdash p, \text{ then } R(B, p) = B. \quad (\text{Vacuity}) $$

**Observation 10** Let $R$ be a belief change operation. Then:

(a) If $R$ satisfies (R3), then it satisfies (R5).

(b) If $R$ satisfies (R6b), and (R7), then it satisfies (R1).

(c) If $R$ satisfies (R5) and (R6b), then it satisfies (R7).

**Proof.**

(a) Trivial.

(b) Due to idempotence of $Cn$ it is enough to prove that $R(B, p) \subseteq Cn(B)$ and $B \subseteq Cn(R(B, p))$.

Let $w \in R(B, p)$ and assume $w \notin Cn(B)$. If $w = p$, contradiction by (R7). Then it follows by (R6b) that there exists
$r : r \in B \setminus R(B, p)$ and $\vdash w \leftrightarrow (p \to r)$. $r \vdash w$, hence $w \in Cn(B)$. Contradiction.

(c) Let $B \nvdash p$. We will prove the two senses of the inclusion separately. Let $q \in B$ and assume $q \notin R(B, p)$. Then it follows by (R5) that there exists $H \subseteq B$ such that $H \nvdash p$, but $H \cup \{q\} \vdash p$, from which it follows that $B \vdash p$. Contradiction. Hence $q \in R(B, p)$, from which it follows that $B \subseteq R(B, p)$.

For the other direction, let $q \in R(B, p)$ and assume $q \notin B$. Then it follows by (R6b) that there exists $r$ such that $r \in B \setminus R(B, p)$ and $\vdash q \leftrightarrow (p \to r)$. But this is not possible, since $B \subseteq R(B, p)$. Then $q \in B$. Hence, $B = R(B, p)$. ■

The previous observation allows us to focus on a minimal set of postulates for reformulation.

## 5 Representation Theorem

In this section we present the representation theorems for the reformulation operation defined in **Definition 8**. We provide two results, each corresponding to the two possible constructions of base contraction operations, namely partial meet and kernel, respectively.

We start with the following lemma that intuitively establishes that from Definition 8, the definition of contraction by $p$ can be recovered considering exactly the set of formulas that belong to the reformulation and were originally in the belief base (minus $p$).

**Lemma 11** Let $B$ a belief base, $- : 2^L \times L \to 2^L$ a contraction function and $R : 2^L \times L \to 2^L$ a reformulation operation based on $-$ defined as in **Definition 8**. If $\vdash p$ and $-$ satisfies C-Inclusion, C-Success and C-Core-retainment, then $B-p = (R(B, p) \cap B) \setminus \{p\}$.

**Proof.**

We prove both senses of the inclusion. Let $w \in B-p$. By definition of $R$, $w \in R(B, p)$. By C-Inclusion, $w \in B$ and by C-Success, $w \neq p$. Hence, $w \in (R(B, p) \cap B) \setminus \{p\}$.

For the other sense, let $w \in (R(B, p) \cap B) \setminus \{p\}$ and assume by reductio that $w \notin B-p$. Then $w \in R(B, p)$, $w \in B$, and $w \neq p$. Then by definition of $R$, there exists $q$ such that $w = p \to q$. From C-Core-retainment, there exists $H \subseteq B$ such that $H \nvdash p$ but $H \cup \{w\} \vdash p$. By deduction $H \vdash w \to p$, then $H \vdash (p \to q) \to p$, hence $H \vdash p$. Contradiction. Hence $w \in B-p$, which concludes the proof. ■

**Theorem 12** characterizes reformulation when $-$ is a partial meet base contraction.

**Theorem 12** Let $B$ a belief base, $- : 2^L \times L \to 2^L$ a contraction function, and $R : 2^L \times L \to 2^L$ a reformulation operation based on $-$ defined as in **Definition 8**.

Then $R$ satisfies (R2), (R2b), (R3), (R4), (R6), and (R6b) if and only if $-$ is a partial meet base contraction function.

**Proof.**

**If part**

(R2): trivial by definition.

(R2b): Let $\vdash p$ and assume by reductio that $R(B, p) \setminus \{p\} \vdash p$. Then there exists $x_1...x_n \in R(B, p)$ s.th. $\{x_1...x_n\} \vdash p$. Assume (since $Cn$ is compact) that $X' \subset \{x_1...x_n\}$,

then $X' \nvdash p$. Let's take an arbitrary $x_i$ such that $x_i \in \{p \to q : q \in B \setminus B-p\}$ then $\{x_1...x_{i-1}, x_{i+1}...x_n\} \cup \{x_i\} \vdash p$. Note that such $x_i$ exists, otherwise, by Definition 8, $x_i$ would be either be $p$ or $\{x_1, ..., x_n\} \subseteq B-p$, which is impossible since $-$ satisfies C-Success. By deduction $\{x_1...x_{i-1}, x_{i+1}...x_n\} \vdash x_i \to p$. Let $x_i$ have the form $x_i = p \to q_j$ for some $q_j$, then $\{x_1...x_{i-1}, x_{i+1}...x_n\} \vdash (p \to q_j) \to p$, hence $\{x_1...X_{i-1}, x_{i+1}...x_n\} \vdash p$, contradiction. Since we prove it for a generic $x_i$ it follows that $\{x_1...x_n\} \cap \{p \to q : q \in B \setminus B-p\} = \emptyset$. Then $\{x_1...x_n\} \subseteq B-p$, from which it follows that $B-p \vdash p$ which contradicts C-Success. Contradiction.

(R3): Let $w \in B$ and $w \notin R(B, p)$, then by definition of $R(B, p)$ we have that $w \notin B-p$ and $w \neq p$. By C-Relevance there exists $H$ such that $B-p \subseteq H \subseteq B$, and $H \nvdash p$ but $H \cup \{w\} \vdash p$. By Observation 6 and Lemma 11 $B-p = (B \cap R(B, p)) \setminus \{p\}$.

(R4): We want to prove that if $B' \subseteq B$ and $B' \vdash p$ iff $B' \vdash q$, then $B \cap (R(B, p) \setminus \{p, q\}) = B \cap (R(B, q) \setminus \{p, q\})$.

Let $B' \subseteq B$ and $B' \vdash p$ iff $B' \vdash q$, by C-Uniformity we know that $B-p = B-q$. Now, let $w \in B \cap (R(B, p) \setminus \{p, q\})$. Due to the symmetry of the claim, it is enough to prove the following cases:

1. $w \in B-p$, then $w \in B-q \subseteq R(B, p)$. Hence, $B \cap R(B, p) \subseteq B \cap R(B, q)$.

2. $w \notin B-p$, then it must be the case that $w \in \{p \to r : r \neq p, r \notin B \setminus B-p\}$. Then, if $w \in B \setminus B-p$, let $H$ be such that $B-p \subseteq H \subseteq B$, we have that $H \nvdash p$, however, $H \cup \{w\} \vdash p$ then $p \to w \in Cn(H)$, $p \to (p \to p) \in Cn(H)$ and therefore $p \in Cn(H)$, which is a contradiction. On the other hand, if $w \notin B \setminus B-p$, then $w \notin B$, which is also a contradiction.

(R6): trivial by definition.

(R6b): We want to prove that if $q \in R(B, p) \setminus (B \cup \{p\})$, then there exists $r \in B \setminus R(B, p)$ and $\vdash q \leftrightarrow (p \to r)$.

Let $q \in R(B, p) \setminus B \cup \{p\}$, then $q \in R(B, p)$, but by definition $R(B, p) = B-p \cup \{p \to q : q \neq p, q \in B \setminus B-p\} \cup \{p\}$, then by C-Inclusion, we have that $q \notin B-p$ and $q \notin \{p\}$, then $q \in \{p \to q : q \neq p, q \in B \setminus B-p\}$.

**Only if part**

Let $-$ be defined as:

$$B-p = (R(B, p) \cap B) \setminus \{p\}$$

when $\vdash p$, and $B-p = B$ when $\vdash p$.

We will start by proving that $-$ is a partial meet base contraction function.

**C-Inclusion:** Trivial by definition of $-$.

**C-Success:** Let $\vdash p$. By (R2b) we have that $R(B, p) \setminus \{p\} \nvdash p$. Hence, by definition of $-$, we have that $B-p \nvdash p$.

**C-Uniformity:** Assume that if it holds for all subsets $B'$ of $B$ that $p \in Cn(B')$ iff $q \in Cn(B')$. Then $\vdash p$ iff $\vdash q$, from which it follows that if $\vdash p$, then $B-p = B-q = B$. Idem if $\vdash q$. Let $\vdash p$ and $\nvdash q$. Then, it follows that for all $w \in B$, $w \vdash p$ iff $w \vdash q$.
Let $w \in B-p$. By the previous proof of C-Success, we have that $w \nmid p$ and then $w \nmid q$. Therefore, $w \neq p$ and $w \neq q$. From which it follows, by (R4), that $w \in B-p$ iff $w \in (R(B,p) \cap B) \setminus \{p\}$ iff $w \in (R(B,p) \cap B) \setminus \{p,q\}$ iff $w \in (R(B,q) \cap B) \setminus \{p,q\}$ iff $w \in (R(B,q) \cap B) \setminus \{q\}$ iff $w \in B-q$. Hence $B-p = B-q$.

**C-Relevance:** We have that $w \in B$ and $w \notin B-p$. The case $w = p$ is trivial. Let $w \neq p$. Then by definition of $-$, $w \notin R(B,p)$; then by (R3) there exists $H$, such that $B-p = (R(B,p) \cap B) \setminus \{p\} \subseteq H \subseteq B$ and $H \nmid p$, $H \cup \{w\} \vdash p$.

The last step is to prove that for all $p$, $R(B,p) = R'(B,p)$, where $R'$ is a reformulation operation built from a partial meet contraction function – as stated in Definition 8:

$$R'(B,p) = B-p \cup \{p \to q : \nmid q \leftrightarrow p \text{ and } q \in B \setminus B-p\} \cup \{p\}$$

when $B \vdash p$, and $R'(B,p) = B$ when $B \nmid p$.

If $B \nmid p$, it follows by definition that $R'(B,p) = B$ and by (R7) (see Observation 10) that $R(B,p) = B$. Let $B \vdash p$, substituting – by its definition $(B-p = (R(B,p) \cap B) \setminus \{p\})$, we obtain

$$R'(B,p) = (R(B,p) \cap B) \setminus \{p\} \cup \{p \to q : \nmid q \leftrightarrow p \text{ and } q \in B \setminus ((R(B,p) \cap B) \setminus \{p\})\} \cup \{p\}.$$

We will prove the two senses of the inclusion.

Let $w \in R(B,p)$. If $w = p$, trivial. Let $w \neq p$. If $w \in B$, trivial. Let $w \notin B$. Then by (R6b), there exists $r : r \in B \setminus R(B,p)$ and $\vdash q \leftrightarrow (p \to r)$, hence $w \in \{p \to q : \nmid q \leftrightarrow p \text{ and } q \in B \setminus ((R(B,p) \cap B) \setminus \{p\})\}$.

In the other direction, let $w \in R'(B,p)$. If $w = p$, trivial by (R2). Let $w \neq p$. Assume (by reductio) that $w \notin R(B,p)$.

Then $w \in \{p \to q : \nmid q \leftrightarrow p \text{ and } q \in B \setminus ((R(B,p) \cap B) \setminus \{p\})\}$. Let $w = p \to q_i$. Since $q_i \in B \setminus ((R(B,p) \cap B) \setminus \{p\})$, it follows by (R6) that $p \to q_i = w \in R(B,p)$, contradiction. ■

**Theorem 13** characterizes reformulation assuming – is a kernel base contraction.

**Theorem 13** Let $B$ a belief base, $- : 2^L \times L \to 2^L$ a contraction function and $R : 2^L \times L \to 2^L$ a reformulation operation based on – defined as in **Definition 8**. Then $R$ satisfies (R2), (R2b), (R5), (R4), (R6), and (R6b) if and only if – is a kernel base contraction function.

**Proof.**

*If part*

In Theorem 12 we proved R2, R2b, R4, R6, and R6b without using C-Relevance.

(R5): Let $w \in B$ and $w \notin R(B,p)$, then by definition of

$R(B,p)$ we have that $w \notin B-p$ and $w \neq p$. By C-Core-retainment, there exists $H$, such that $H \subseteq B$, and $H \nmid p$ but $H \cup \{w\} \vdash p$. By Lemma 11, $B-p = (B \cap R(B,p)) \setminus \{p\}$. Only if part

We will use the same construction as defined in Theorem 12. We only need to prove that $-$ satisfies C-Core-retainment: We have that $w \in B$ and $w \notin B-p$. If $w = p$, trivial. Let $w \neq p$. Then by definition of $-$, $w \notin R(B,p)$, then by (R5), there exists $H$, such that $H \subseteq B$, such that $H \nmid p$, $H \cup \{w\} \vdash p$. ■

Theorems 12 and 13 establish the formal characterization of the two versions of reformulation that can be instantiated from our proposal in Section 4. In the following section we study other alternatives for the operation.

# 6 Other Versions of Reformulation

In this section we introduce some slight variants of the reformulation operation defined in **Definition 8**.

We start by noting that if $B-p \vdash p \to q$ then, again if we aim for non-redundancy, it is not necessary to reincorporate $p \to q$. We can thus refine the model as follows:

**Definition 14 (Reformulation Operation 2)** Let $B$ be a belief base, $p$ a formula, and $-$ a base contraction function. The reformulation Operation 2 of $p$ in $B$ is:

$$R_{M_2}(B,p) = B-p \cup \{p\} \cup \{p \to q : q \in B \setminus B-p \text{ and } B-p \nmid p \to q\}$$

when $B \vdash p$, and $R_{M_2}(B,p) = B$ when $B \nmid p$.

A further refinement we can make to the operation is to eliminate the direct consequences of $p$ present in $B-p$. By applying this to the reformulation operations respectively defined in Definition 8 and Definition 14 we obtain the following two operations:

**Definition 15 (Reformulation Operation 3)** Let $B$ be a belief base, $p$ a formula and $-$ a base contraction function. The weak non-redundant reformulation of $p$ in $B$ is:

$$R_{M_3}(B,p) = (B-p \setminus Cn(p)) \cup \{p\} \cup \{p \to q : q \in B \setminus B-p\}$$

when $B \vdash p$, and $R_{M_3}(B,p) = B$ when $B \nmid p$.

**Definition 16 (Reformulation Operation 4)** Let $B$ be a belief base, $p$ a formula, and $-$ a base contraction function. The non-redundant reformulation of $p$ in $B$ is:

$$R_{M_4}(B,p) = (B-p \setminus Cn(p)) \cup \{p\} \cup \{p \to q : q \in B \setminus B-p \text{ and } B-p \nmid p \to q\} \\ = (B-p \setminus Cn(p)) \cup \{p\} \cup \{(p \to q : q \in B \setminus B-p) \setminus Cn(B-p)\}$$
when $B \vdash p$, and $R_{M_4}(B, p) = B$ when $B \not\vdash p$.

The full characterization of these operations will be a task of future studies.

# 7 Related Work

To the best of our knowledge, this is the first work on the reformulation of belief bases within the area of belief change. In this section, we recall two other operators which, although different, we consider to be related to reformulation in the sense that they encompass an introspection of the belief base that is not provoked by an epistemic input (like AGM changes are).

Replacement is an operation that substitutes one sentence for another within a set of beliefs. A substitution operation involves two input sentences, such that in $B|_q^p$, $p$ is replaced by $q$. Consequently, the result is a set of beliefs that includes $q$ but not $p$. This operation may yield outcomes that cannot be achieved through partial contraction or partial revision by intersection. Replacement can also serve as a kind of Sheffer stroke for belief change, that is, an operation by which other operations may be defined. Contraction by $p$ can be defined as the replacement $|_p^p$ of $p$ by a tautology, revision by $p$ as the replacement $|_p^\perp$ of falsum by $p$, and expansion by $p$ as the replacement $|_q^\top$ of a tautology by $p$. (Tautologies are considered immovable, as is always the case in belief revision.) Partial meet replacement has been axiomatically characterized and a semantic explanation has been provided in terms of possible worlds in Hansson (2009).

Reconsideration, introduced by Johnson and Shapiro (2005) and Johnson (2006), is a non-prioritized operation based on beliefs. It formalizes changes that are performed in hindsight in order to eliminate negative effects of previously performed changes. Beliefs that were previously removed may be reintroduced if there are no longer valid reasons for their removal. This operation can be seen as an optimization that eliminates the negative effects of the order in which inputs were received. It may involve an examination of all current and past beliefs.

# 8 Conclusion and Future Work

Our aim in this paper was to introduce an operation that reformulates a belief base by making explicit a particular sentence that was originally implicit. Such an operation had not been investigated before in the theory of belief base change operations. We have defined this operation of reformulation in terms of a base contraction operator. We have studied its axiomatic characterization in two versions that are respectively based on partial meet contraction and kernel base contraction. We have also proposed three alternatives that further refine reformulation and that enhance non-redundancy. The precise axiomatic characterization for these alternatives is left to future work.

# Acknowledgments

We want to thank the anonymous referees for their suggestions on the previous version of the article.

MVM was partially supported by the Spanish project PID 2022-139835NB-C21 funded by MCIN/AEI/10.13039/501100011033, PIE 2023-5AT010 and iTrust (PCI 2022-135010-2) CHIST-ERA under grant 2022/04/Y/ST6/00001. EF was partially supported by FCT-Fundação para a Ciência e a Tecnologia, Portugal, through project PTDC/CCI-COM/4464/2020 and by NOVA LINCS ref. UIDB/04516/2020 and ref. UIDP/04516/2020 with the financial support of FCT.IP.
https://doi.org/10.54499/UIDP/04516/2020.

# References

Alchourrón, C.; Gärdenfors, P.; and Makinson, D. 1985. On the Logic of Theory Change: Partial Meet Contraction and Revision Functions. *Journal of Symbolic Logic*, 50: 510–530.

Alchourrón, C.; and Makinson, D. 1985. On the Logic of Theory Change: Safe Contraction. *Studia Logica*, 44: 405–422.

Belnap, N. 1979. Rescher's hypothetical reasoning: An amendment. In Sosa, E., ed., *The Philosophy of Nicholas Rescher: Discussion and Replies*, 19–28. Dordrecht: D. Reidel.

Fermé, E. 2001. Five faces of Recovery. In Rott, H.; and Williams, M.-A., eds., *Frontiers in Belief Revision, Applied Logic Series*, 247–259. Kluwer Academic Publishers.

Fermé, E.; and Hansson, S. O. 2018. *Belief Change: Introduction and Overview*. Springer Briefs in Computer Science Series. Springer. ISBN 978-3-319-60535-7.

Fermé, E.; Krevneris, M.; and Reis, M. D. L. 2008. An Axiomatic Characterization of Ensconcement-Based Contraction. *Journal of Logic and Computation*, 18(5): 739–753.

Garapa, M. 2017. *Advances on belief base dynamics*. Ph.D. thesis, Universidade da Madeira.

Hansson, S. O. 1991. *Belief Base Dynamics*. Ph.D. thesis, Uppsala University.

Hansson, S. O. 1992. A Dyadic Representation of Belief. In Gärdenfors, P., ed., *Belief Revision*, number 29 in Cambridge Tracts in Theoretical Computer Science, 89–121. Cambridge University Press.

Hansson, S. O. 1994. Kernel Contraction. *Journal of Symbolic Logic*, 59: 845–859.

Hansson, S. O. 1999. *A Textbook of Belief Dynamics. Theory Change and Database Updating*. Applied Logic Series. Dordrecht: Kluwer Academic Publishers.

Hansson, S. O. 2009. Replacement: A Sheffer stroke for belief revision. *Journal of Philosophical Logic*, 38: 127–149.

Hansson, S. O. 2022. Logic of Belief Revision. In Zalta, E. N., ed., *The Stanford Encyclopedia of Philosophy*. The Metaphysics Research Lab. Center for the Study of Language and Information. Stanford University. URL = http://plato.stanford.edu/entries/logic-belief-revision/.

Johnson, F. L. 2006. *Dependency-Directed Reconsideration: An Anytime Algorithm for Hindsight Knowledge-Based Optimization*. Ph.D. thesis, State University of New York at Buffalo.
Johnson, F. L.; and Shapiro, S. C. 2005. Dependency-directed reconsideration: Belief base optimization for truth maintenance systems. In *Proceedings of the Twentieth National Conference on Artificial Intelligence (AAAI-05)*, 313–320. AAAI Press.

Levesque, H. J. 1984. A Logic of Implicit and Explicit Belief. In Brachman, R. J., ed., *Proceedings of the National Conference on Artificial Intelligence*. Austin, TX, USA, August 6-10, 1984, 198–202. AAAI Press.

Lorini, E. 2020. Rethinking epistemic logic with belief bases. *Artif. Intell.*, 282: 103233.

Nebel, B. 1989. A knowledge level analysis of belief revision. In *Proceedings of the 1st International Conference of Principles of Knowledge Representation and Reasoning*, 301–311. Morgan Kaufmann.

Rott, H. 2000. "Just Because". Taking belief bases seriously. In Buss, S.; Hajek, P.; and Pudlak, P., eds., *Logic Colloquium '98: Proceedings of the Annual European Summer Meeting of the Association for Symbolic Logic*, volume 13 of *Lecture Notes in Logic*. Prague: Association for Symbolic Logic.

Santos, Y. D.; Matos, V. B.; Ribeiro, M. M.; and Wassermann, R. 2018. Partial meet pseudo-contractions. *International Journal of Approximate Reasoning*, 103: 11–27.

Tarski, A. 1956. *Logic, Semantics, Metamathematics. Papers from 1923 to 1938. Translated by J. H. Woodger*. Oxford: Clarendon Press.