3. There exist convex sublattices L1, L2 of hI, ⊆i such that the complement of S *relative to* I
SE *is equal to*

$$\left\{\,\langle I,J\rangle\in{\mathcal I}^{\mathsf{SE}}\,\big|\,\,I\in L_{1}\wedge J\in L_{2}\,\right\}\cup\left\{\,\langle I,J\rangle\in{\mathcal I}^{\mathsf{SE}}\,\big|\,\,J\in L_{1}\cap L_{2}\,\right\}\ .$$
Proof. See Appendix A, page 24. ⊓⊔

## 4 Discussion

The presented results mainly serve to facilitate the transition back and forth between a rule and the set of its SE-models. They also make it possible to identify when a given set of SE-models is representable by a single rule. We believe that in situations where information on literal dependencies, expressed in individual rules, is essential for defining operations on logic programs, the advantages of dealing with rules on the level of semantics instead of on the level of syntax are significant. The semantic view takes care of stripping away unnecessary details and since the introduced notions and operators are defined in terms of semantic objects, it should be much easier to introduce and prove their semantic properties.

These results can be used for example in the context of program updates to define an update semantics based on the *rule rejection principle* [4] and operating on *sets of sets* of SE*-models*. Such a semantics can serve as a bridge between syntax-based approaches to rule updates, and the principles and semantic distance measures known from the area of Belief Change. The next steps towards such a semantics involve a definition of the notion of support for a literal by a set of SE-models (of a rule). Such a notion can then foster a better understanding of desirable properties for semantic rule update operators.

On a different note, viewing a logic program as the set of sets of SE*-models* of rules inside it leads naturally to the introduction of the following new notion of program equivalence:
Definition 18 (Strong Rule Equivalence). Programs P1,P2 are SR-equivalent, denoted by P1 ≡SR P2*, if*
{ modSE (r) | r ∈ P1 ∪ { ε } } = { modSE (r) | r ∈ P2 ∪ { ε } } .

Thus, two programs are SR-equivalent if they contain the same rules, modulo the SE-model semantics. We add ε to each of the two programs in the definition so that presence or absence of tautological rules in a program does not influence program equivalence. SR-equivalence is stronger than strong equivalence, in the following sense:
Definition 19 (Strength of Program Equivalence). Let ≡1, ≡2 *be equivalence relations on the set of all programs. We say that* ≡1 is at least as strong as ≡2*, denoted by*
≡1  ≡2, if P1 ≡1 P2 implies P1 ≡2 P2 for all programs P1,P2*. We say that* ≡1 is stronger than ≡2*, denoted by* ≡1 ≻ ≡2, if ≡1  ≡2 *but not* ≡2  ≡1.

Thus, using the notation of the above definition, we can write ≡SR ≻ ≡S, where ≡S
denotes the relation of strong equivalence. An example of programs that are strongly