
## A Proofs

Lemma 2. Let H and B be sets of literals and p be an atom. Then a rule is SE*-tautological if it takes any of the following forms:*
p; H ← p, B. H; ∼p ← B, ∼p. H ← **B, p,** ∼p.

Proof. First assume that rule r is of the first form. We need to show that any SE-interpretation is an SE-model of r. Suppose h**I, J**i is some SE-interpretation. Rule r is C-tautological, so J is a C-model of r. Furthermore, r Jis either ε, or it inherits p in both its head and body from r. In any case, r is C-tautological, so I is a C-model of r J.

Consequently, h**I, J**i is an SE-model of r.

Now suppose r is of the second form. As before, given an SE-interpretation h**I, J**i, we see that J is a C-model of r because r is C-tautological. Furthermore, r J will necessarily end up being equal to ε because of the atom p common to H(r)
− and B(r)
−, regardless of how J interprets p. So I is a C-model of r J, and, consequently, h**I, J**i is an SE-model of r.

Finally, suppose r takes the third form and take an SE-interpretation h**I, J**i. Rule r can again easily be verified to be C-tautological, so J is a C-model of r. If all atoms from B(r)
− are false under J, then r Jcontains the atom p in its body that is false under J, thus also false under I since I is a subset of J. Consequently, I is a C-model of r J.

On the other hand, if at least one of atoms from B(r)
− is true under J, then r Jis equal to ε, so again, I is a C-model of r J. Consequently, h**I, J**i is an SE-model of r. ⊓⊔
Lemma 23. Let H and B be sets of literals and p be an atom. Then rules of the following forms are *SE-equivalent:*

## P; H ← B, ∼**P. H** ← B, ∼P.

Proof. Let the first rule be denoted by r1 and the second by r2 and suppose h**I, J**i is an SE-interpretation. We will show that h**I, J**i is an SE-model of r1 if and only if it is an SE-model of r2. We can easily see that rules r1, r2 are C-equivalent. So J is either not a C-model of any of them or it is a C-model of both of them. In the former case, h**I, J**i is not an SE-model of any of the two rules and we are finished. In the latter case, we need to distinguish two cases:
a) If J is a not a model of the bodies of r1 and r2 (the bodies are identical), then either r J
1 and r J
2 are equal to ε, or they contain an atom in their bodies that is false under J, thus also false under I because I is a subset of J. 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.

b) If J is a model of the bodies of r1 and r2, then p is false under J, and, since J is a C-model of r1, some literal from H must be true under J. Consequently, either both r J
1 and r J
2 are equal to ε and I is a C-model of both of them, or r J
1 and r J
2 only differ in the single extra atom p that r J
1 has in the head. However, since I is a subset of J and p is false under J, p cannot be true under I, so I is either not a C-model of any of r J
1
, r J
2
, or it is a C-model of both of them. In any case, h**I, J**i is a SE-model of r1 if and only if it is an SE-model of r2.