# HG changeset patch
# User Eugen Sawin <sawine@me73.com>
# Date 1338478611 -7200
# Node ID f94c11c455e8d47a2eade18ba41158aedb730371
# Parent  5c6d1fbfd37a12a62d01e677058a751dfb72a404
Added ex4.2b.

diff -r 5c6d1fbfd37a -r f94c11c455e8 exercises/solutions/sol04.tex
--- a/exercises/solutions/sol04.tex	Thu May 31 04:12:51 2012 +0200
+++ b/exercises/solutions/sol04.tex	Thu May 31 17:36:51 2012 +0200
@@ -149,9 +149,9 @@
 \end{tikzpicture}
 \caption{(3.1b) primal constraint graph of $N$}
 \end{figure}\\
-(c) No, $N$ is not arc-consistent. We provide the arc-consistent constraint network $N^c=\langle V, D^c, C\rangle$ with
+(c) No, $N$ is not arc-consistent. We provide the arc-consistent constraint network $N'=\langle V, D', C\rangle$ with
 \begin{align*}
-  D^c_{v}=\left\{
+  D'_{v}=\left\{
     \begin{array}{l l}
       \{1\} & v = norwegian\\
       \{3\} & v = milk\\
@@ -174,6 +174,17 @@
 
 Let $\C=\langle V,D,C\rangle$ and $\C'=\langle V,D',C\rangle$. By definition each variable assignment $a(v_i)$ must be in its variable domain $D_i$, i.e., $a(v_i)\in D_i$. Therefore, a reduction of domains can only yield a network with less solutions. Since AC3 reduces domains, there can not be more solutions for $\C'$, i.e., $Sol(\C') \subseteq Sol(\C)$.
 
-Assume that solution $a\in Sol(\C)$ is lost after the domain reduction by AC3, i.e., $a\notin Sol(\C')$. WLOG it follows that at some iteration of AC3 the value $a(v_i)$ was removed from the domain $D_i'$, so it holds $a(v_i)\notin D_i'$. By the definition of the revise function of AC3, it holds that $D_i'\leftarrow D_i\cap\pi_i(R_{ij} \bowtie D_j)$. Since $a(v_i)$ is in $D_i$ but not in $D_i'$, it follows that $a(v_i)\notin\pi_i(R_{ij}\bowtie D_j) \implies (a(v_i),a(v_j))\notin(R_{ij}\bowtie D_j)$. The join $R_{ij}\bowtie D_j$ represents the set of all consistent assignments of variable $v_j$ over the relation $R_{ij}$. With $(a(v_i),a(v_j))\notin (R_{ij}\bowtie D_j)$ it follows that variable assignments $(a(v_i),a(v_j))$ are not consistent with the constraint over $R_{ij}$. It contradicts with our assumption that $a\in Sol(\C)$, because a solution must satisfy all constraints of the network. We have shown that there is no solution $a\in Sol(\C)$, such that $a\notin Sol(\C')$. \qed\\\\
-(b) 
+Assume that solution $a\in Sol(\C)$ is lost after the domain reduction by AC3, i.e., $a\notin Sol(\C')$. WLOG it follows that at some iteration of AC3 the value $a(v_i)$ was removed from the domain $D_i'$, so it holds $a(v_i)\notin D_i'$. By the definition of the revise function of AC3, it holds that $D_i'\leftarrow D_i\cap\pi_i(R_{ij} \bowtie D_j)$. Since $a(v_i)$ is in $D_i$ but not in $D_i'$, it follows that $a(v_i)\notin\pi_i(R_{ij}\bowtie D_j) \implies (a(v_i),a(v_j))\notin(R_{ij}\bowtie D_j)$.
+
+The join $R_{ij}\bowtie D_j$ represents the set of all consistent assignments of variable $v_j$ over the relation $R_{ij}$. With $(a(v_i),a(v_j))\notin (R_{ij}\bowtie D_j)$ it follows that variable assignments $(a(v_i),a(v_j))$ are not consistent with the constraint over $R_{ij}$. It contradicts with our assumption that $a\in Sol(\C)$, because a solution must satisfy all constraints of the network. We have shown that there is no solution $a\in Sol(\C)$, such that $a\notin Sol(\C')$. \qed\\\\
+%
+(b) To show that AC3 produces an arc-consistent network $\C'$ we consider three cases. The first case is trivial, given an arc-consistent network the revise function does not remove any domain values and therefore does not modify the network.
+
+Let $\C$ be a network with some not arc-consistent $R_{ij}$, i.e., there is some assignment a with $a(v_i)\in D_i$, $a(v_j)\in D_j$ and $(a(v_i),a(v_j))\notin (R_{ij}\bowtie D_j)$. Initially, AC3 does revise all variable pairs $(v_i,v_j)$ and $(v_j,v_i)$ with $(v_i,v_j)$ in some constraint's scope ($R_{ij}$). It follows that AC3 does revise $(v_i,v_j)$ in respect of $R_{ij}$ in some iteration and reduces $D_i'\leftarrow D_i\cap\pi_i(R_{ij}\bowtie D_j)$. Because $(a(v_i),a(v_j))\notin (R_{ij}\bowtie D_j)$ implies $a(v_i)\notin\pi_i(R_{ij}\bowtie D_j)$, it holds that $a(v_i)\notin D_i'$. This reduces the initial arc-inconsitency of $v_i$ relative to $v_j$.
+
+By the domain value reduction, AC3 can introduce new not arc-consistent constraints. Let $a(v_i)\in D_i$ be a value, that was removed by the revise function for constraint $R_{ij}$. Since the revise function changed $D_i$, AC3 will again revise all variable pairs $(v_k,v_i)$ with $k\neq i,k\neq j$ for all constraints $R_{ki}$. This removes all inconsistent values for all domains $D_k$,i.e., all $a(v_k)\in D_k$ with $a(v_k)\notin\pi_k(R_{ki}\bowtie D_i)$ are removed from $D_k$. All other constraints $R_{lm}$ with $m\neq i$ are not directly affected by the reduced domain $D_i$ and can therefore not become not arc-consistent by the revisal of $(v_i,v_j)$. 
+
+We have shown, that all initial not arc-consistent constraints are made arc-consistent and the same holds for all newly introduced inconsistencies by the domain reduction. It follows that all remaining domains of $\C'$ form an arc-consistent network. \qed\\\\
+%
+(c)
 \end{document}