Merging

The problem of merging knowledge bases with possibly conflicting pieces of information could arise if different sources, such as sensor data or reports of multiple agents, must be combined. In contrast with revision and contraction, one normally does not have the knowledge that one source is preferred over the others.

Although a simple solution would be to take the disjunction of all the sources, this may result in so much information loss that we may get a resulting knowledge base with too many models. Rather, we want to find a resulting knowledge base whose only models are those common to the source knowledge bases.

Consider merging knowledge bases $K_1 = \{p, \neg r\}$ and $K_2 = \{p, r, s\}$, with $R = \{\neg s\}$ and $C = \{p\}$. COBA 2.0 has two different merging operators: $\triangle$ (symmetric merge) and $\nabla$ (projected merge).

We first show how COBA 2.0 computes the symmetric merge of the multi belief change scenario $(\{~\{p, \neg r\},~\{p, r, s\}~\},\{\neg s\}, \{p\})$.

1. Find the common atoms appearing in at least two of the knowledge bases to be merged.
   $KCA = \{p,r\}$
2. Find the common atoms any knowledge base shares with the revision formula or with any contraction formula.
   $CA = \{p,s\}$
3. Create a conjunction $K$ of all new formulas $K_i^i$ obtained from $K_i$ by numbering any atom $b$ in $K_i$ with $i$ if $b \in KCA$, and by priming any atom $d$ in $K_i$ if ( $d \notin KCA$ and $d \in CA$).
   $K = K_1^1 \wedge K_2^2 = (p^1 \wedge \neg r^1) \wedge (p^2 \wedge r^2 \wedge s')$
4. Create a disjunction $K'$ of all new formulas $K_i'$ obtained from $K_i$ by priming any atom $d$ in $K_i$ if $d \in CA$.
   $K' = K_1' \vee K_2' = (p' \wedge \neg r) \vee (p' \wedge r \wedge s')$
5. Create a conjunction $AllKB$ of $K$ with $K'$.
   $AllKB = K \wedge K' = p^1 \wedge \neg r^1 \wedge p^2 \wedge r^2 \wedge s' \wedge ((p' \wedge \neg r) \vee (p' \wedge r \wedge s'))$
6. Find all maximal equivalence sets $EQ = (\{b^i \equiv b' \mid b \in KCA\} \cup \{b' \equiv b \mid b \in CA\})$ such that $\{$AllKB $\} \cup R \cup \{\neg \phi\} \cup EQ$ is satisfiable for every $\phi \in (C \cup \{\bot\})$.
   $EQ_1 = \{p^1 \equiv p', p^2 \equiv p', r^1 \equiv r'\}$
   $EQ_2 = \{p^1 \equiv p', p^2 \equiv p', r^2 \equiv r'\}$
7. For each $EQ_i$, create a belief change extension by (a) replacing in $AllKB$ every numbered atom $p^i$ with $p'$ if $(p^i \equiv p') \in EQ_i$, (b) replacing every numbered atom $p^i$ with $\neg p'$ if $(p^i \equiv p') \notin EQ_i$, (c) replacing every primed atom $p'$ with $\neg p$ if ( $(p' \equiv p) \notin EQ_i$ and $p \in CA$), (d) unpriming every remaining primed atom $p'$, (e) (iff $C \not= \emptyset$) taking the disjunction of all possible substitutions of $\top$ or $\bot$ into those atoms in $AllKB$ that are in $CA$ but whose corresponding equivalences are not in $EQ_i$, and finally (f) conjoining the result with $(\bigwedge R)$.
   
   For $EQ_1$, we have $AllKB = (p' \wedge \neg r' \wedge s' \wedge ((p' \wedge \neg r) \vee (p' \wedge r \wedge s')))$ after steps (a) and (b), and $AllKB = (\neg p \wedge \neg r \wedge \neg s \wedge ((\neg p \wedge \neg r) \vee (\neg p \wedge r \wedge \neg s)))$ after steps (c) and (d). After step (e) of taking the disjunction of applying all $2^2$ possible truth assignments $\{p,s\} \to \{\top,\bot\}$ to $AllKB$, we get $AllKB = \neg r$.
   $K_1 \triangle_{c_1}^{\{\neg s\}, \{p\}} K_2 = \neg r \wedge \neg s$ after step (f).
   
   For $EQ_2$, we have $AllKB = (p' \wedge r' \wedge s' \wedge ((p' \wedge \neg r) \vee (p' \wedge r \wedge s')))$ after steps (a) and (b), and $AllKB = (\neg p \wedge r \wedge \neg s \wedge ((\neg p \wedge \neg r) \vee (\neg p \wedge r \wedge \neg s)))$ after steps (c) and (d). After step (e) of taking the disjunction of applying all $2^2$ possible truth assignments $\{p,s\} \to \{\top,\bot\}$ to $AllKB$, we get $AllKB = r$.
   $K_1 \triangle_{c_2}^{\{\neg s\}, \{p\}} K_2 = r \wedge \neg s$ after step (f).
8. 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_1 \triangle^{\{\neg s\}, \{p\}} K_2 = Cn((\neg r \wedge \neg s)\vee(r \wedge \neg s))$

We now show how COBA 2.0 computes the projected merge of the multi belief change scenario $(\{~\{p, \neg r\},~\{p, r, s\}~\},\{\neg s\}, \{p\})$.

1. Find the common atoms appearing in at least two of the knowledge bases to be merged.
   $KCA = \{p,r\}$
2. Find the common atoms any knowledge base shares with the revision formula or with the contraction formula.
   $CA = \{p,s\}$
3. Create a conjunction $AllKB$ of all new formulas $K_i^i$ obtained from $K_i$ by numbering any atom $b$ in $K_i$ with $i$ if $b \in KCA$, and by priming any atom $d$ in $K_i$ if ( $d \notin KCA$ and $d \in CA$).
   $AllKB = K_1^1 \wedge K_2^2 = (p^1 \wedge \neg r^1) \wedge (p^2 \wedge r^2 \wedge s')$
4. Find all maximal equivalence sets $EQ = (\{b^i \equiv b' \mid b \in KCA\} \cup \{b' \equiv b \mid b \in CA\})$ such that $\{$AllKB $\} \cup R \cup \{\neg \phi\} \cup EQ$ is satisfiable for every $\phi \in (C \cup \{\bot\})$.
   $EQ_1 = \{r^1 \equiv r',p^1 \equiv p',p^2 \equiv p'\}$
   $EQ_2 = \{r^1 \equiv r',p' \equiv p\}$
   $EQ_3 = \{r^2 \equiv r',p^1 \equiv p',p^2 \equiv p'\}$
   $EQ_4 = \{r^2 \equiv r',p' \equiv p\}$
5. For each $EQ_i$, create a belief change extension by (a) replacing in $AllKB$ every numbered atom $p^i$ with $p'$ if $(p^i \equiv p') \in EQ_i$, (b) replacing every numbered atom $p^i$ with $\neg p'$ if $(p^i \equiv p') \notin EQ_i$, (c) replacing every primed atom $p'$ with $\neg p$ if ( $(p' \equiv p) \notin EQ_i$ and $p \in CA$), (d) unpriming every remaining primed atom $p'$, (e) (iff $C \not= \emptyset$) taking the disjunction of all possible substitutions of $\top$ or $\bot$ into those atoms in $AllKB$ that are in $CA$ but whose corresponding equivalences are not in $EQ_i$, and finally (f) conjoining the result with $(\bigwedge R)$.
   
   For $EQ_1$, we have $AllKB = (p' \wedge \neg r' \wedge s')$ after steps (a) and (b), and $AllKB = (\neg p \wedge \neg r \wedge \neg s)$ after steps (c) and (d). After step (e) of taking the disjunction of applying all $2^2$ possible truth assignments $\{p,s\} \to \{\top,\bot\}$ to $AllKB$, we get $AllKB = \neg r$.
   $K_1 \nabla_{c_1}^{\{\neg s\}, \{p\}} K_2 = \neg r \wedge \neg s$ after step (f).
   
   For $EQ_2$, we have $AllKB = (\neg p' \wedge \neg r' \wedge s')$ after steps (a) and (b), and $AllKB = (\neg p \wedge \neg r \wedge \neg s)$ after steps (c) and (d). After step (e) of taking the disjunction of applying both possible truth assignments $\{s\} \to \{\top,\bot\}$ to $AllKB$, we get $AllKB = \neg p \wedge \neg r$.
   $K_1 \nabla_{c_2}^{\{\neg s\}, \{p\}} K_2 = \neg p \wedge \neg r \wedge \neg s$ after step (f).
   
   For $EQ_3$, we have $AllKB = (p' \wedge r' \wedge s')$ after steps (a) and (b), and $AllKB = (\neg p \wedge r \wedge \neg s)$ after steps (c) and (d). After step (e) of taking the disjunction of applying all $2^2$ possible truth assignments $\{p,s\} \to \{\top,\bot\}$ to $AllKB$, we get $AllKB = r$.
   $K_1 \nabla_{c_3}^{\{\neg s\}, \{p\}} K_2 = r \wedge \neg s$ after step (f).
   
   For $EQ_4$, we have $AllKB = (\neg p' \wedge r' \wedge s')$ after steps (a) and (b), and $AllKB = (\neg p \wedge r \wedge \neg s)$ after steps (c) and (d). After step (e) of taking the disjunction of applying both possible truth assignments $\{s\} \to \{\top,\bot\}$ to $AllKB$, we get $AllKB = \neg p \wedge r$.
   $K_1 \nabla_{c_4}^{\{\neg s\}, \{p\}} K_2 = \neg p \wedge r \wedge \neg s$ after step (f).
6. 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_1 \nabla^{\{\neg s\}, \{p\}} K_2 = \\ Cn(\neg s \wedge ((\neg p \wedge r) \vee r \vee \neg r \vee (\neg p \wedge \neg r))) = Cn(\neg s)$