1.1 Binary file exercises/solutions/sol01.pdf has changed

     2.1 --- a/exercises/solutions/sol01.tex	Fri Apr 27 02:02:08 2012 +0200
     2.2 +++ b/exercises/solutions/sol01.tex	Fri Apr 27 19:03:09 2012 +0200
     2.3 @@ -8,7 +8,7 @@
     2.4  \usepackage{fullpage}
     2.5  \usepackage{mathtools}
     2.6  \usepackage[all]{xy}
     2.7 -\addtolength{\voffset}{-25pt}
     2.8 +\addtolength{\voffset}{-40pt}
     2.9  \title{CSP Exercise 01 Solution}
    2.10  \author{Eugen Sawin}
    2.11  \renewcommand{\familydefault}{\sfdefault}
    2.12 @@ -48,7 +48,7 @@
    2.13  (a) $R_{x,y} \bowtie S_{y,z} = \{(a,b,a),(a,b,c)\}$\\\\
    2.14  (b) $\sigma_{z=c}(R_{x,y} \bowtie S_{y,z}) = \{(a,b,c)\}$\\\\
    2.15  (c) $\pi_x(R_{x,y}) = \{(a)\}$\\\\
    2.16 -(d) $R_{x,y} \circ S_{y,z} = \{(a,a),(a,c)\}$\\\\
    2.17 +(d) $R_{x,y} \circ S_{y,z} = \{(a,a),(a,c)\}$
    2.18  
    2.19  \section*{Exercise 1.3}
    2.20  (a) By definition holds
    2.21 @@ -56,15 +56,34 @@
    2.22    R \circ (S \cup T) &= \{(x,z) \in X^2 \mid \exists{y \in X}: (x,y) \in R \text{ and } (y,z) \in (S \cup T)\}\\
    2.23    R \circ S &= \{(x,z) \in X^2 \mid \exists{y \in X}: (x,y) \in R \text{ and } (y,z) \in S\}\\
    2.24    R \circ T &= \{(x,z) \in X^2 \mid \exists{y \in X}: (x,y) \in R \text{ and } (y,z) \in T\}
    2.25 -\end{align}
    2.26 +\end{align}\setcounter{equation}{0}\\
    2.27  The union of (2) and (3) gives us the set of all $(x,y) \in R$ with either $(y,z) \in S$ or $(y,z) \in T$, from which follows that $(y,z) \in (S \cup T)$, making it equal to (1). \qed\\\\
    2.28 -(b) $-R$ was nowhere defined yet.\\\\
    2.29 +(b) By definition holds
    2.30 +\begin{align}
    2.31 +  -R &= \{(x,y) \in X^2 \mid (x,y) \notin R\}\\
    2.32 +  (-R)^{-1} &= \{(y,x) \in X^2 \mid (x,y) \in -R\}\\
    2.33 +  -(R^{-1}) &= \{(x,y) \in X^2 \mid (x,y) \notin R^{-1}\}\\
    2.34 +  -(R^{-1}) &= \{(x,y) \in X^2 \mid (y,x) \notin R\}
    2.35 +\end{align}\setcounter{equation}{0}\\
    2.36 +We've obtained (4) by applying the converse definition on (3). From the definition of $-R$ (1) follows that $(x,y) \in -R$ iff $(x,y) \notin R$, and therefore we see that (2) and (4) define equal sets. \qed\\\\
    2.37  (c) By definition holds
    2.38  \begin{align}
    2.39    (R \circ S)^{-1} &= \{(z,x) \in X^2 \mid \exists{y \in X}: (x,y) \in R \text{ and } (y,z) \in S\}\\
    2.40    S^{-1} \circ R^{-1} &= \{(x,z) \in X^2 \mid \exists{y \in X}: (x,y) \in S^{-1} \text{ and } (y,z) \in R^{-1}\}\\
    2.41    S^{-1} \circ R^{-1} &= \{(x,z) \in X^2 \mid \exists{y \in X}: (y,x) \in S \text{ and } (z,y) \in R\}
    2.42 -\end{align}
    2.43 -where (6) is (5) transformed by application of the definition of the converse of a relation. After some variable juggling we see that (4) and (6) are equal sets. \qed\\\\
    2.44 -(d) Todo 
    2.45 +\end{align}\setcounter{equation}{0}\\
    2.46 +We've obtained (3) by applying the converse definition on (2). After some variable juggling we see that (1) and (3) define equal sets. \qed\\\\
    2.47 +(d) By definition holds
    2.48 +\begin{align}
    2.49 +  R \circ S &= \{(x,z) \in X^2 \mid \exists{y \in X}: (x,y) \in R \text{ and } (y,z) \in S\}\\
    2.50 +  (R \circ S) \cap T^{-1} &= (R \circ S) \cap \{(y,x) \in X^2 \mid (x,y) \in T\}\\
    2.51 +  (R \circ S) \cap T^{-1} &= \{(x,z) \in X^2 \mid \exists{y \in X}: (x,y) \in R \text{ and } (y,z) \in S \text{ and } (z,x) \in T\}\\
    2.52 +  (S \circ T) \cap R^{-1} &= \{(x,z) \in X^2 \mid \exists{y \in X}: (x,y) \in S \text{ and } (y,z) \in T \text{ and } (z,x) \in R\}
    2.53 +\end{align}\\
    2.54 +We've obtained (3) by directly applying intersection within the set comprehension of (2). It follows that\\
    2.55 +\begin{align}
    2.56 +  (R \circ S) \cap T^{-1} = \emptyset &\iff \forall{x,y,z \in X}: (x,y) \notin R \text{ or } (y,z) \notin S \text{ or } (z,x) \notin T\\
    2.57 +  \text{ and } (S \circ T) \cap R^{-1} = \emptyset &\iff \forall{x,y,z \in X}: (x,y) \notin S \text{ or } (y,z) \notin T \text{ or } (z,x) \notin R
    2.58 +\end{align}\\
    2.59 +As we can see, the intersections form a ring-like relationship between the sets' tuples $(...,R, S, T, R,...)$. After some variable reordering, we see that both intersections are empty iff there is no ring-like relationship between any tuples of the three sets. \qed
    2.60  \end{document}