have $v\in M$ because of the rules $v{\leftarrow}u$ and $v{\leftarrow}{{\mathit not}}\ u$ in (\[eq:red:fifth\]). In case $w\in M$, $Z\cup \overline{Z}\subseteq M$ by the rules in (\[eq:red:third\]). In case $w\notin M$, we have $K\cup \overline{(Z\setminus K)} \subseteq M$ for some $K\subseteq Z$, since $v\in M$ and by (\[eq:red:third\]). But then, since $w\notin M$, $u\in M$ holds (rules $u{\leftarrow}z,{{\mathit not}}\ w$ resp.$u{\leftarrow}\overline{z},{{\mathit not}}\ w$). Hence, also here $Z\cup \overline{Z}\subseteq M$. In both cases, we observe that by (\[eq:red:first\]) and (\[eq:red:second\]), $I\cup \overline{(X\setminus I)}\cup J\cup \overline{(Y\setminus J)}\subseteq M$, for some $I\subseteq X$ and $J\subseteq Y$. This yields the desired models, $M[I,J]$, $M'[I,J]$. It can be checked that no other model exists by showing that for $N\not\subseteq M[I,J]$, resp. $N\not\subseteq M'[I,J]$, $N=U$ follows.

We next show that, for each $I\subseteq X$ and $J\subseteq Y$, $P^{M[I,J]}$ and $P^{M'[I,J]}$ possess the required models. Let us start by showing that $O[I]$ is a model of $P^{M[I,J]}$. In fact, it can be observed that all of the rules of the form $x \vee \overline{x} \leftarrow$ in (\[eq:red:first\]) are satisfied because either $x$ or $\overline{x}$ belong to $O[I]$, while all of the other rules in $P^{M[I,J]}$ are satisfied because of a false body literal. We also note that each 