Revision

The problem of revision arises when, for example, an intelligent agent has to modify her belief(s) because she has required more recent or preferred information. While she wants to incorporate the new information into her beliefs, she also wishes to retain as much of her existing knowledge as consistently possible.

Consider revising a knowledge base $K = \{p, q\}$ by a formula $\alpha = \neg p \vee \neg q$. Simply conjoining $K$ with $\alpha$ violates consistency as $\{p \wedge q \wedge (\neg p \vee \neg q)\} \vdash \bot$. On the other hand, the disjunction $(\bigwedge K) \vee \alpha$ has a model satisfying $(p \wedge q)$, although $\alpha$ asserts that at least one of $p$ and $q$ must be false.

We show how COBA 2.0 computes $K \dot + \alpha$.

1. Find the common atoms between the knowledge base and the revision formula.
   $CA = \{p,q\}$
2. Create a new formula $K'$ from $K$ by priming the common atoms appearing in $K$.
   $K' = (p'\wedge q')$
3. Find all maximal equivalence sets $EQ = \{b' \equiv b \mid b \in CA\}$ such that { $K'\} \cup \{\alpha\} \cup EQ$ is satisfiable.
   $EQ_1 = \{p' \equiv p\}$
   $EQ_2 = \{q' \equiv q\}$
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) conjoining $K'$ with the revision formula.
   $K \dot +_{c_1} \{\alpha \} = (p \wedge \neg q) \wedge (\neg p \vee \neg q) \equiv (p \wedge \neg q)$
   $K \dot +_{c_2} \{\alpha \} = (\neg p \wedge q) \wedge (\neg p \vee \neg q) \equiv (\neg p \wedge q)$
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.
   $K \dot+ \{\alpha \} = Cn((p \wedge \neg q) \vee (\neg p \wedge q))$