Contraction

Contraction is complementary to revision in that certain information is to be removed from a knowledge base. This means a contraction formula should not be a consequence of the resulting knowledge base. Contracting a knowledge base $K$ by a formula $\alpha$ does not necessarily mean that the $\neg \alpha$ is in the resulting knowledge base, as that would simply be revising $K$ with $\neg \alpha$. Rather, the resulting knowledge base should have at least one model falsifying $\alpha$.

Consider contracting a knowledge base $K = \{p \vee q\}$ by a contraction formula $\alpha = p \vee q$. $K$ has only models $\{p, q\}$, $\{\neg p ,q\}$, and $\{p, \neg q\}$, all consistent with $\alpha$. A reasonable belief change extension here could be a revision with $\neg \alpha$; however, any model of the resulting knowledge base would then satisfy $\neg \alpha$, and we may lose too much of $K$. We show how COBA 2.0 avoids this problem when computing $K \dot - \alpha$.

1. Find the common atoms between the knowledge base and the contraction formula.
   $CA = \{p,q\}$
2. Create a new formula $K'$ from $K$ by priming the common atoms appearing in $K$.
   $K' = (p'\vee q')$
3. Find all maximal equivalence sets $EQ = \{b' \equiv b \mid b \in CA\}$ such that { $K'\} \cup \{\neg \alpha\} \cup EQ$ is satisfiable.
   $EQ_1 = \{\}$
4. For each $EQ_i$, create a belief change extension by (a) unpriming in $K'$ every primed atom $p'$ if $(p' \equiv p) \in EQ_i$, (b) replacing every primed atom $p'$ with $\neg p$ if $(p' \equiv p) \notin EQ_i$, and finally (c) taking the disjunction of all possible substitutions of $\top$ or $\bot$ into those atoms in $K'$ that are in $CA$ but whose corresponding equivalences are not in $EQ_i$.
   $K \dot -_{c_1} \{\alpha \} = (\top)$
5. The resulting knowledge base is the deductive closure of either the disjunction of all belief change extensions for $skeptical$ change, or one belief change extension for $choice$ change.
   Here, there is only one resulting knowledge base for skeptical change and for choice change: $K \dot - \{\alpha\} = Cn((\neg\bot \vee \neg\bot) \vee (\neg\bot \vee \neg\top) \vee (\neg\top \vee \neg\bot) \vee (\neg\top \vee \neg\top)) = Cn(\top)$