1. r is of the form a ← B \ I . Then there is a 
hoi
e rule {A} ← B, ∼C ∈ P ,
su h that B ∩ I ⊆ M , C ∩ M = ∅, and a ∈ M ∩ A. Now, B ∩ I ⊆ M implies B ∩ I ⊆ N , C ∩ M = ∅ implies C ∩ N = ∅, and a ∈ M implies a ∈ N
and a 6∈ N . Together with {A} ← B, ∼C ∈ P these imply r ∈ RN,I. Sin
e M′ 6|= r, we have a 6∈ M′ and B \ I ⊆ M′. But, sin
e N′ ∩ At(P) = M′, this implies N′ 6|= r, a 
ontradi
tion to N′|= RN,I.

2. r is of the form a ← w
′ ≤ {B \ I = WB\I }. Then there is a weight rule a ← w ≤ {B = WB, ∼C = WC } ∈ P su
h that

$$w^{\prime}=\operatorname*{max}(0,w-\sum_{b\in B\cap I\cap M}w_{b}-\sum_{c\in C\setminus M}w_{c}).$$

Sin e M′ 6|= r, we have a 6∈ M′ and w
′ ≤Pb∈(B\I)∩M′ wb . Dene B′ =
(B ∩I ∩M)∪((B \I)∩M′) and C
′ = C \M , and re
all that N′∩At(P) = M′.

Now w ≤Pb∈B′ wb +Pc∈C′ wc , C
′ ∩ N = ∅, B′ ∩ I ⊆ N , B′ \ I ⊆ N′ and a 6∈ N′, whi
h implies that there is a rule r
′ = a ← B′ \ I ∈ RN,I su
h that N′ 6|= r
′ whi h is in ontradi tion with N′|= RN,I.

Thus assuming that there is N′ ⊂ N \ I su
h that N′|= RN,I leads to a 
ontradi
-
tion, and it holds that N \ I = LM(RN,I ), that is, N ∈ SM(TrNLP(P)).

(ii) We show that f : SM(P) → SM(TrNLP(P)) is a bije
tion:
Clearly f is an inje
tion: M 6= M′implies f(M) 6= f(M′). To show that f is a surje tion, we onsider an arbitrary N ∈ SM(TrNLP(P)) and show N ∩ At(P) =
M ∈ SM(P) and f(M) = f(N ∩ At(P**)) =** N .

 Assume rst M 6|= P M,I, that is, there is a rule r ∈ P M,I that is not satised.

Noti e that all the rules in P M,I 
orresponding to a 
hoi
e rule in P are always satised in M . Thus we need to 
onsider only rules that 
orrespond to a weight rule in P . Now, r = a ← w
′ ≤ {B \ I = WB\I } ∈ P M,I, if there is a weight rule a ← w ≤ {B = WB, ∼C = WC } ∈ P su
h that w
′ =
max(0, w−Pb∈B∩M∩I wb−Pc∈C\M wc). Sin
e M 6|= r, then a 6∈ M and w
′ ≤
Pb∈(B\I)∩M wb . Dene B′ = B ∩ M and C
′ = C \ M . Sin
e N ∩ At(P) = M
and w ≤Pb∈B′ wb +Pc∈C′ wc , there is a normal rule a ← B′, ∼C
′ ∈ R.

Furthermore, C
′ ∩ N = ∅ and B′ ∩ I ⊆ N imply r
′ = a ← B′ \ I ∈ RN,I.

Sin e a 6∈ M , also a 6∈ N . Furthermore, B′ \ I ⊆ M ⊆ N . These imply N 6|= r
′
whi h leads to a ontradi tion. Thus M |= r, and moreover M |= P M,I.

 Next, assume that there is M′ ⊂ M \ I su
h that M′|= P M,I and dene N′ = M′ ∪ (N \ At(P)) ⊂ N \ I . Sin
e N′ \ At(P) = N \ At(P) by denition, ea h rule of the form a ∈ RN,I is satised in N′. Other rules in RN,I are of the form r = a ← B′ \ I where a ∈ At(P). There are now two possibilities.
1. There is a hoi e rule {A} ← B′, ∼C ∈ P , su
h that a ∈ A, B′ ∩ I ⊆ N ,
C ∩ N = ∅, and a 6∈ N . Now, M ∩ At(P) = N ∩ At(P) implies r ∈ P M,I, and furthermore, M′|= P M,I implies M′|= r. Re
alling M′ ∩ At(P) =
N′ ∩ At(P), we get N′|= r.

2. There is a rule a ← B′, ∼C
′ ∈ R 
orresponding to a weight rule a ← w ≤
{B = WB, ∼C = WC } ∈ P su
h that B′ ⊆ B , C
′ ⊆ C , w ≤Pb∈B′ wb +
Pc∈C′ wc , B′ ∩ I ⊆ N and C
′ ∩ N = ∅. If B′ \ I 6⊆ N′, then N′|= r.