Proof. By monotonicity of ϕ and completeness of p**, we know that** ϕ
− ◦p◦ϕ(d) ⊆
ϕ
−(dom(c∩ϕ(d**))). We now use the fact that** ϕ
− **is dom injective and commutes**
with set intersection:
ϕ
−(dom(c ∩ ϕ(d**))) = dom(**ϕ
−(c ∩ ϕ(d**))) =**
dom(ϕ
−(c) ∩ ϕ
−(ϕ(d**))) = dom(**ϕ
−(c) ∩ d)

## 4 Boolean Variables: Transformation

This section discusses views and derived propagators for Boolean variables where Val = {0, 1}**. Not surprisingly, the only view apart from identity for Boolean**
variables captures negation. That is, using a negation view on x defines ϕx(v) =
1 − v for x ∈ Var and v ∈ Val.

Negation views are more widely applicable than one would initially believe.

They demonstrate how views can be used systematically to obtain implementations of constraint variants by **transformation**.

Boolean connectives. **The immediate application of negation views is to derive**
propagators for all Boolean connectives from just three propagators: A negation view for x in x = y yields a propagator for ¬x = y. From disjunction x∨y = z one can derive conjunction x∧y = z with negation views on x, y, z**, and implication** x → y = z with a negation view on x. From equivalence x ↔ y = z **one can**
derive exclusive or x ⊕ y = z **with a negation view on** z.

As Boolean constraints are widespread in models, it pays off to optimize frequently occurring cases. One important propagator is disjunction Wn i=1 xi = y for arbitrarily many variables; again conjunction can be derived with **negation**
views on the xi and on y**. Another important propagator is for the constraint**
Wn i=1 xi **= 1, stating that the disjunction must be true. A propagator for this**
constraint is essential as the constraint occurs frequently and as it can be implemented efficiently using watched literals, see for example [6]. With views and derived propagators all implementation work is readily reused for conjunction. This shows a general advantage of views: effort put into optimizing a **single** propagator directly pays off for all other propagators derived from it.

Boolean cardinality. **Like the constraint** Wn i=1 xi **= 1, the Boolean cardinality**
constraint Pn i=1 xi ≥ c **occurs frequently and can be implemented efficiently**
using watched literals (requiring c + 1 watched literals, Boolean disjunction corresponds to the case where c **= 1). But also a propagator for** Pn i=1 xi ≤ c can be derived using negation views with the following transformation:

$\sum_{i=1}^n x_i\leq c$ $\iff$ $-\sum_{i=1}^n x_i\geq-c$ $\iff$ $n-\sum_{i=1}^n x_i\geq n-c$ $\iff$ $\sum_{i=1}^n1-x_i\geq n-c$ $\iff$ $\sum_{i=1}^n\neg x_i\geq n-c$
7