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. ⊓⊔
Theorem 7. Every rule r is SE*-equivalent to the canonical rule* can(r).

Proof. This can be shown by a careful iterative application of Lemmas 2 to 4. First observe that if can(r) is equal to ε, then by Lemma 2 the rule r is indeed SE-equivalent to ε.

In the principal case we can use Lemma 23 on all atoms shared between the positive head and negative body of r and remove them one by one from the positive head of r while preserving SE-equivalence. Similar situation occurs with atoms shared between the negative head and positive body of r, which can be, according to Lemma 24, removed from the negative head of r while preserving SE-equivalence. After these steps are performed, we obtain the rule
(H(r)
+ \ B(r)
−); ∼(H(r)
− \ B(r)
+) ← B(r)
+, ∼B(r)
−. (5)
This is also the result of the defined transformation, unless the set H(r)
+ \ B(r)
− is empty. In that case, one can repeatedly apply Lemma 4 to move the atoms from the negative head of rule (5) into its positive body. In this case, the transformation returns the canonical rule
← (B(r)
+ ∪ H(r)
−), ∼B(r)
−. ⊓⊔
Lemma 8. Let r be a rule. An SE*-interpretation* h**I, J**i is not an SE-model of r if and only if the following conditions are satisfied:
1. H(r)
− ∪ B(r)
+ ⊆ J and J **⊆ L \** B(r)
−.

2. Either J **⊆ L \** H(r)
+ *or both* B(r)
+ ⊆ I and I **⊆ L \** H(r)
+.

Proof. Suppose first that the above conditions hold. We will show that h**I, J**i is not an SE-model of r. Due to the first condition, r Jis equal to H(r)
+ ← B(r)
+ and due to the second condition, either J is not a C-model of r, or I contains the body of r J
but does not contain any atom from its head, which means I is not a C-model of r J.

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

Now suppose **I, J** are two interpretations such that the above conditions do not hold.

We will show that h**I, J**i is an SE-model of r. We need to consider the following four cases:

a) If J does not contain some atom from the negative head of r or it contains an atom from the negative body of r, then J is a C-model of r and r Jis ε, so I is a C-model of r J. Consequently, h**I, J**i is an SE-model of r.

b) If J does not contain some atom from the positive body of r, then J is a C-model of r and I is a C-model of r J due to the fact that I is a subset of J. Consequently, h**I, J**i is an SE-model of r.

c) If J contains an atom from the positive head of r and I does not include the positive body of r, then J is a C-model of r and I is a C-model of r J. Consequently, h**I, J**i is an SE-model of r.

d) If J contains some atom from the positive head of r and I also contains some atom from the positive head of r, then J is a C-model of r and I is a C-model of r J.

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