Almost finished ex01.
1.1 --- a/exercises/solutions/sol01.tex Thu Apr 26 00:25:00 2012 +0200
1.2 +++ b/exercises/solutions/sol01.tex Fri Apr 27 02:02:08 2012 +0200
1.3 @@ -8,10 +8,13 @@
1.4 \usepackage{fullpage}
1.5 \usepackage{mathtools}
1.6 \usepackage[all]{xy}
1.7 +\addtolength{\voffset}{-25pt}
1.8 \title{CSP Exercise 01 Solution}
1.9 \author{Eugen Sawin}
1.10 \renewcommand{\familydefault}{\sfdefault}
1.11 \newcommand{\E}{\mathcal{E}}
1.12 +\newcommand{\R}{\mathcal{R}}
1.13 +
1.14 %\include{pythonlisting}
1.15
1.16 \pagestyle{empty}
1.17 @@ -42,10 +45,26 @@
1.18 \end{itemize}
1.19
1.20 \section*{Exercise 1.2}
1.21 -(a) $R_{x,y} \bowtie S_{y,z} = \{(a,b,a),(a,b,c)\}$\\
1.22 -(b) $\sigma_{z=c}(R_{x,y} \bowtie S_{y,z}) = \{(a,b,c)\}$\\
1.23 -(c) $\pi_x(R_{x,y}) = \{(a)\}$\\
1.24 -(d) $R_{x,y} \circ S_{y,z} = \{(b,b)\}$\\
1.25 +(a) $R_{x,y} \bowtie S_{y,z} = \{(a,b,a),(a,b,c)\}$\\\\
1.26 +(b) $\sigma_{z=c}(R_{x,y} \bowtie S_{y,z}) = \{(a,b,c)\}$\\\\
1.27 +(c) $\pi_x(R_{x,y}) = \{(a)\}$\\\\
1.28 +(d) $R_{x,y} \circ S_{y,z} = \{(a,a),(a,c)\}$\\\\
1.29
1.30 -
1.31 +\section*{Exercise 1.3}
1.32 +(a) By definition holds
1.33 +\begin{align}
1.34 + 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)\}\\
1.35 + R \circ S &= \{(x,z) \in X^2 \mid \exists{y \in X}: (x,y) \in R \text{ and } (y,z) \in S\}\\
1.36 + R \circ T &= \{(x,z) \in X^2 \mid \exists{y \in X}: (x,y) \in R \text{ and } (y,z) \in T\}
1.37 +\end{align}
1.38 +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\\\\
1.39 +(b) $-R$ was nowhere defined yet.\\\\
1.40 +(c) By definition holds
1.41 +\begin{align}
1.42 + (R \circ S)^{-1} &= \{(z,x) \in X^2 \mid \exists{y \in X}: (x,y) \in R \text{ and } (y,z) \in S\}\\
1.43 + 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}\}\\
1.44 + 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\}
1.45 +\end{align}
1.46 +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\\\\
1.47 +(d) Todo
1.48 \end{document}