
$$(a)\ X\models[L\leq S]\ {\mathrm{iff}}\ X\models s u m\langle S\rangle\geq L,\ a n d L$$
$$(b)\ X\models[S\leq U]\ {\it i f\!f}\ X\models s u m\langle S\rangle\leq U.$$

Proposition 17. In presence of nonnegative weights only, [N ≤ S] is strongly equivalent to sumhSi ≥ N, and [S ≤ N] *is strongly equivalent to* sumhSi ≤ N.

Proof. We start with (a), with the special case when rule elements F1, . . . , Fn of S are distinct atoms. Since the aggregate is monotone then, by Lemma 13, we just need to show that [N ≤ S] is strongly equivalent to (15). As classical equivalence holds between [N ≤ S] and sumhSi ≥ N by Lemma 18, the same relationship holds between [N ≤ S] and (15). As both formulas are AND-OR combinations of atoms, the claim follows by Lemma 17. The most general case of (a) follows from the special case, by Lemma 16.

For part (b), we know, by Lemma 13, that antimonotone aggregate sumhSi ≤
U (written as a formula (6)) is strongly equivalent to formula

$$\bigwedge_{I\subseteq\{1,\ldots,n\}:\;\sum_{i\in I}w_{i}>U}{\binom{\neg\bigwedge_{i\in I}F_{i}}{i\in I}}.$$

By applying DeMorgan's law to this last formula (which preserves equivalence in the logic of here-and-there and then it is a strongly equivalent transformation by Proposition 5) we get S ≤ U.

## 4.11 Proof Of Proposition 18

Given a PDB-aggregate of the form (6) and a set X of literals, by IX we denote the set {i ∈ {1, . . . , n} : X |= Fi}.

Lemma 19. For each PDB-aggregate of the form (6), a set X of atoms satisfies a formula of the form G(I1,I2)iff I1 ⊆ IX ⊆ I2.

Proof.

$X\models G_{(I_{1},I_{2})}$ iff $X\models F_{i}$ for all $i\in I_{1}$, and $X\not\models F_{i}$ for all $i\in\{1,\ldots,n\}\setminus I_{2}$ iff $X\models F_{i}$ for all $i\in I_{1}$, and for every $i$ such that $X\models F_{i}$, $i\in I_{2}$ iff $I_{1}\subseteq I_{X}$ and $I_{X}\subseteq I_{2}$.  
Lemma 20. For every PDB-aggregate A, Atr *is classically equivalent to (9).*