Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

**Arc consistency**

Are two variables (u,v) arc consistent, if $C_{uv} \notin C$ and ($d_u = \emptyset$ or $d_v = \emptyset$)?

Yes, but only because the first condition C_{uv} \notin C is already sufficient. The second conjunct is not sufficient,

because d_v = \emptyset does not guarantee arc consistency.d_u = \emptyset is sufficient, since quantifying over an empty set is always true. Also note that d_v = emptyset conditions aren’t really relevant for arc consistency, because any algorithm should detect empty domains.

OBJECTION. Arc consistency is not symmetric - u can be arc consistent relative to v, v can be arc consistent relative to u, or both, or neither. Just to be clear

So the definition of u being arc consistent relative to v is that „For all x\in d_u, there exists some y \in d_v such that…“. A statement of the form „for all x\in S“ is always true if S is the empty set. So if d_u is empty, then u is arc consistent relative to every other variable.

A statement of the form „there exists some x\in S…“ is always false if S is the empty set. So if d_u is *not* empty, but d_v is, then u is *not* arc consistent relative to v.

Now, if neither d_u nor d_v are empty, but C_{uv} not in C, then there is no constraint between u and v, so so any pair of values from d_u and d_v is (in principle, barring other constraints) valid, so u is arc consistent relative to v and v is arc consistent relative to u