1 \documentclass[a4paper, 10pt, pagesize, smallheadings]{article}
3 %\usepackage[latin1]{inputenc}
4 \usepackage{amsmath, amsthm, amssymb}
7 \usepackage{algorithmic}
11 \addtolength{\voffset}{-40pt}
12 \title{CSP Exercise 01 Solution}
14 \renewcommand{\familydefault}{\sfdefault}
15 \newcommand{\E}{\mathcal{E}}
16 \newcommand{\R}{\mathcal{R}}
18 %\include{pythonlisting}
24 \section*{Exercise 1.1}
25 \begin{tabular}{|c|c|c||c|c|c||c|c|c|}
27 5&3&6 &4&7&2 &8&1&9 \\ \hline
28 4&2&1 &6&9&8 &5&7&3 \\ \hline
29 7&8&9 &1&5&3 &4&6&2 \\ \hline\hline
31 8&6&3 &9&2&4 &1&5&7 \\ \hline
32 1&7&5 &8&3&6 &9&2&4 \\ \hline
33 2&9&4 &5&1&7 &6&3&8 \\ \hline\hline
35 3&1&8 &2&4&5 &7&9&6 \\ \hline
36 9&4&7 &3&6&1 &2&8&5 \\ \hline
37 6&5&2 &7&8&9 &3&4&1 \\ \hline
39 I have applied following strategies to solve the puzzle:
41 \item look for most contrained blocks, rows and columns
42 \item look for values with most resolved positions
43 \item annotate cells with consistent values
44 \item look for inconsistent connections between cell annotations
47 \section*{Exercise 1.2}
48 (a) $R_{x,y} \bowtie S_{y,z} = \{(a,b,a),(a,b,c)\}$\\\\
49 (b) $\sigma_{z=c}(R_{x,y} \bowtie S_{y,z}) = \{(a,b,c)\}$\\\\
50 (c) $\pi_x(R_{x,y}) = \{(a)\}$\\\\
51 (d) $R_{x,y} \circ S_{y,z} = \{(a,a),(a,c)\}$
53 \section*{Exercise 1.3}
54 (a) By definition holds
56 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)\}\\
57 R \circ S &= \{(x,z) \in X^2 \mid \exists{y \in X}: (x,y) \in R \text{ and } (y,z) \in S\}\\
58 R \circ T &= \{(x,z) \in X^2 \mid \exists{y \in X}: (x,y) \in R \text{ and } (y,z) \in T\}
59 \end{align}\setcounter{equation}{0}\\
60 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\\\\
61 (b) By definition holds
63 -R &= \{(x,y) \in X^2 \mid (x,y) \notin R\}\\
64 (-R)^{-1} &= \{(y,x) \in X^2 \mid (x,y) \in -R\}\\
65 -(R^{-1}) &= \{(x,y) \in X^2 \mid (x,y) \notin R^{-1}\}\\
66 -(R^{-1}) &= \{(x,y) \in X^2 \mid (y,x) \notin R\}
67 \end{align}\setcounter{equation}{0}\\
68 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\\\\
69 (c) By definition holds
71 (R \circ S)^{-1} &= \{(z,x) \in X^2 \mid \exists{y \in X}: (x,y) \in R \text{ and } (y,z) \in S\}\\
72 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}\}\\
73 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\}
74 \end{align}\setcounter{equation}{0}\\
75 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\\\\
76 (d) By definition holds
78 R \circ S &= \{(x,z) \in X^2 \mid \exists{y \in X}: (x,y) \in R \text{ and } (y,z) \in S\}\\
79 (R \circ S) \cap T^{-1} &= (R \circ S) \cap \{(y,x) \in X^2 \mid (x,y) \in T\}\\
80 (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\}\\
81 (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\}
83 We've obtained (3) by directly applying intersection within the set comprehension of (2). It follows that\\
85 (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\\
86 \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
88 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