these conditions is satisfied, the positive parts of r are kept in the reduct, discarding the negative ones.

An SE*-interpretation* is a pair of interpretations h**I, J**i such that I is a subset of J.

The set of all SE-interpretations is denoted by I
SE. We say that an SE-interpretation h**I, J**i is an SE*-model* of a rule r if J is a C-model of r and I is a C-model of r J.

The set of all SE-models of a rule r is denoted by modSE (r). The SE-models of a program P are the SE-models of all rules in P. A set of SE-interpretations S is called rule-representable if there exists a rule r such that S = modSE (r).

We say that a rule r is SE**-tautological** if modSE (r) = I
SE. Note that the canonical tautology ε (c.f. Definition 1) is SE-tautological. We say that two rules **r, r**′are *strongly* equivalent, or SE*-equivalent*, if they have the same set of SE-models.

## 3 Rule Equivalence Classes And Their Canonical Rules

Our goal is to find useful insights into the inner workings of the SE-model semantics with respect to single rules. In order to do so, we first introduce a set of representatives of rule equivalence classes induced by SE-models and show how the representative of a class can be constructed given one of its members. Then we show how to reconstruct a representative from the set of its SE-models. Finally, we pinpoint the conditions under which a set of SE-interpretations is rule-representable.

## 3.1 Canonical Rules

We start by bringing out simple but powerful transformations that simplify a given rule while preserving its SE-models. Most of these results have already been formulated in various ways [20, 2, 21]. The following result summarises the conditions under which a rule is SE-tautological:
Lemma 2 (Consequence of Theorem 4.4 in [2]; part i) of Lemma 2 in [21]). 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. See Appendix A, page 16. ⊓⊔
Thus, repeating an atom in different "components" of the rule frequently causes the rule to be SE-tautological. In particular, this happens if the same atom occurs in the positive head and positive body, or in the negative head and negative body, or in the positive and negative bodies of a rule. How about the cases when the head contains a negation of a literal from the body? The following Lemma clarifies this situation:
Lemma 3 (Consequence of (3) and (4) in Lemma 1 in [21]). Let H and B *be sets of* literals and L be a literal. Then rules of the following forms are SE*-equivalent:*
H; ∼L ← L, B. H ← **L, B.** (3)