Thus, we have proven that every SE-interpretation is an SE-model of r1 if and only if it is an SE-model of r2. In other words, r1 and r2 are SE-equivalent. ⊓⊔
Lemma 24. Let H and B be sets of literals and p be an atom. Then rules of the following forms are SE*-equivalent:*
H; ∼p ← p, B. H ← **p, B.**
Proof. Let the first rule be denoted by r1 and the second by r2. Suppose h**I, J**i is some SE-interpretation. If p is false under J, then J is a C-model of both r1 and r2. Furthermore, r J
1 is equal to ε and r J
2 is either equal to ε or its body contains p, and so is not true under I. In any case, I is a C-model of both r J
1 and r J
2
, so h**I, J**i is an SE-model of both r1 and r2.

On the other hand, if p is true under J, then J is a C-model of r1 if and only if it is a C-model of r2 because the extra literal ∼a in the head of r1 cannot be satisfied.

Also, r J
1 is identical to r J
2
, so I is a C-model of r J
1 if and only if it is a C-model of r J
2
.

Consequently, h**I, J**i is an SE-model of r1 if and only if it is an SE-model of r2.

Thus, we have proven that every SE-interpretation is an SE-model of r1 if and only if it is an SE-model of r2. In other words, r1 and r2 are SE-equivalent. ⊓⊔
Lemma 3. Let H and B be sets of literals and L be a literal. Then rules of the following forms are SE*-equivalent:*

$$H\leftarrow L,B.$$
$\neg\;L,\,D.$ . 
H; ∼L ← L, B. H ← **L, B.** (4)
Proof. Follows from Lemmas 23 and 24. ⊓⊔
Lemma 4. Let H− be a set of negative literals, B be a set of literals and p *be an atom.*
Then rules of the following forms are SE*-equivalent:*
∼p; H− ← B. H− ← **p, B.**

Proof. Let the first rule be denoted by r1 and the second by r2. Suppose h**I, J**i is some SE-interpretation. If p is false under J, then J is a C-model of both r1 and r2. Furthermore, r J
1 is equal to ε and the body of r J
2 cannot be satisfied by I because I is a subset of J and p is not in J. Thus, I is a C-model of both r J
1 and r J
2
, and h**I, J**i is an SE-model of both r1 and r2.

On the other hand, if p is true under J, then we need to consider two cases:
a) If J is not a C-model of r1, then it also cannot be a C-model of r2 because, as can easily be verified, r1 is C-equivalent to r2. Hence, h**I, J**i is an SE-model of neither r1 nor r2.

b) If J is a C-model of r1, then it must also be a C-model of r2 because r1 is C-equivalent to r2. Furthermore, r J
1 and r J
2 are either both equal to ε, or their heads are empty and r J
2 has the extra atom p in the body. In the latter case, if I were a model of the body of r J
1
, then J would be a model of the body of r1 but not of its head
(which contains only negative literals), which contradicts the assumption that J is a model of r1. Thus, I is not a model of the body of r J
1
, so it cannot be a model of the body of r J
2 either. So I is a C-model of both r J
1 and r J
2 and h**I, J**i is an SE-model of both r1 and r2.