
## 3.3 Distributive Property ⊗Lc Over ⊕Lc In Disjunctive Labeled Constraints

Operations ⊗ and ⊕ are distributive (i.e.: ⊗ distributes over ⊕) in non-disjunctive metric TCN, but this property does not hold in disjunctive metric constraints. Dechter, Meiri and Pearl (1991) show the following example. Given the disjunctive metric constraints:
a= {[0 1], [10 20]}, b= {[25 50]}, c= {[0 30], [40 50]},
we have:
(a ⊗ (b ⊕ c) = {[25 31], [35 70]} (a ⊗ b) ⊕ (a ⊗ c) = {[25 70]}.

Thus, clearly (a ⊗ (b ⊕ c) ≠ (a ⊗ b) ⊕ (a ⊗ c). However, the distributive property holds for operations ⊗lc and ⊕lc in labeled TCN.

Theorem 4. By using labeled constraints and I-L-Sets, ⊗lc distributes over ⊕lc.

Proof: Let's consider the labeled constraints lci, lcj and lck. Thus,
(lci ⊗lc lcj) ⊕lc (lci ⊗lc lck)
can be expressed, according to the definition of operation ⊗lc, as:
(∀lecp∈lci, ∀lecq∈lcj, ∪lc[(lecp ⊗lc lecq)]) ⊕lc (∀lecr∈lci, ∀lecs∈lck, ∪lc[(lecr ⊗lc lecs)]) =
∀lecp∈lci, ∀lecq∈lcj, ∀lecr∈lci, ∀lecs∈lck (∪lc[(lecp ⊗lc lecq)] ⊕lc ∪lc[(lecr ⊗lc lecs)])
which, according to the definition of ⊕lc, can be expressed as:
∀lecp∈lci, ∀lecq∈lcj, ∀lecr∈lci, ∀lecs∈lck (∪lc[(lecp ⊗lc lecq) ⊕lc (lecr ⊗lc lecs)]) *(e1)*
In this expression, lecp and lecr are elemental constraints of the same-labeled constraint lci.

However, the set-union of label sets associated to each pair of elemental constraints in any (input or derived) labeled constraint is an I-L-Set (*Definition 3*). That is, if lecp≠lecr, then {labelp}∪{labelr}
is an I-L-Set. Thus, if lecp≠lecr, the label set associated to (lecp ⊗lc lecq) ⊕lc (lecr ⊗lc lecs) is an I-LSet. In consequence, (lecp ⊗lc lecq) ⊕lc (lecr ⊗lc lecs) is rejected in operation ∪lc. That is,
∀lecp∈lci, ∀lecq∈lcj, ∀lecr∈lci, ∀lecs∈lck / lecp≠lecr (∪lc[(lecp ⊗lc lecq) ⊕lc (lecr ⊗lc lecs)]) = ∅.

Thus, the above expression (e1) results:
∀lecp∈lci, ∀lecq∈lcj, ∀lecs∈lck (∪lc [(lecp ⊗lc lecq) ⊕lc (lecp ⊗lc lecs)]).

In this expression, ⊗lc clearly distributes over ⊕lc for elemental constraints (i.e.: non-disjunctive constraints). Therefore:
∀lecp∈lci, ∀lecq∈lcj, ∀lecs∈lck (∪lc [(lecp ⊗lc (lecq ⊕lc lecs))]) =
∀lecp∈lci, ∪lc [lecp ⊗lc (∀lecq∈lcj, ∀lecs∈lck, ∪lc [lecq ⊕lc lecs])] = lci ⊗lc (lcj ⊕lc lck).

That is, ⊗lc distributes over ⊕lc for labeled constraints.◊
For instance, following the previous example:
a= {[0 1]{R1}, [10 20]{R2}}, b= {[25 50]{R0}}, c= {[0 30]{R3}, [40 50]{R4}}
and {R1 R2}, {R3 R4} are I-L-Sets. Thus, we have:
(a ⊗lc (b ⊕lc c) = {[0 1]{R1}, [10 20]{R2}} ⊗lc ({[25 50]{R0}} ⊕lc {[0 30]{R3}, [40 50]{R4}}) =
{[0 1]{R1}, [10 20]{R2}}⊗lc {[25 30]{R3 R0}, [40 50]{R4 R0}} =