sawine@2: \documentclass[a4paper, 10pt, pagesize, smallheadings]{article}
sawine@0: \usepackage{graphicx}
sawine@0: %\usepackage[latin1]{inputenc}
sawine@0: \usepackage{amsmath, amsthm, amssymb}
sawine@0: \usepackage{typearea}
sawine@0: \usepackage{algorithm}
sawine@0: \usepackage{algorithmic}
sawine@0: \usepackage{fullpage}
sawine@0: \usepackage{mathtools}
sawine@0: \usepackage[all]{xy}
sawine@4: \addtolength{\voffset}{-40pt}
sawine@0: \title{CSP Exercise 01 Solution}
sawine@0: \author{Eugen Sawin}
sawine@0: \renewcommand{\familydefault}{\sfdefault}
sawine@0: \newcommand{\E}{\mathcal{E}}
sawine@3: \newcommand{\R}{\mathcal{R}}
sawine@3: 
sawine@0: %\include{pythonlisting}
sawine@0: 
sawine@0: \pagestyle{empty}
sawine@0: \begin{document}
sawine@0: \maketitle
sawine@0: 
sawine@2: \section*{Exercise 1.1}
sawine@0: \begin{tabular}{|c|c|c||c|c|c||c|c|c|}
sawine@0:   \hline
sawine@1:   5&3&6 &4&7&2 &8&1&9 \\ \hline
sawine@1:   4&2&1 &6&9&8 &5&7&3 \\ \hline
sawine@1:   7&8&9 &1&5&3 &4&6&2 \\ \hline\hline
sawine@0: 
sawine@1:   8&6&3 &9&2&4 &1&5&7 \\ \hline
sawine@1:   1&7&5 &8&3&6 &9&2&4 \\ \hline
sawine@1:   2&9&4 &5&1&7 &6&3&8 \\ \hline\hline
sawine@0: 
sawine@1:   3&1&8 &2&4&5 &7&9&6 \\ \hline
sawine@1:   9&4&7 &3&6&1 &2&8&5 \\ \hline
sawine@1:   6&5&2 &7&8&9 &3&4&1 \\ \hline
sawine@2: \end{tabular} \\\\
sawine@2: I have applied following strategies to solve the puzzle:
sawine@2: \begin{itemize}
sawine@2:   \item look for most contrained blocks, rows and columns
sawine@2:   \item look for values with most resolved positions
sawine@2:   \item annotate cells with consistent values
sawine@2:   \item look for inconsistent connections between cell annotations
sawine@2: \end{itemize}
sawine@2: 
sawine@2: \section*{Exercise 1.2}
sawine@3: (a) $R_{x,y} \bowtie S_{y,z} = \{(a,b,a),(a,b,c)\}$\\\\
sawine@3: (b) $\sigma_{z=c}(R_{x,y} \bowtie S_{y,z}) = \{(a,b,c)\}$\\\\
sawine@3: (c) $\pi_x(R_{x,y}) = \{(a)\}$\\\\
sawine@4: (d) $R_{x,y} \circ S_{y,z} = \{(a,a),(a,c)\}$
sawine@2: 
sawine@3: \section*{Exercise 1.3}
sawine@3: (a) By definition holds
sawine@3: \begin{align}
sawine@3:   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)\}\\
sawine@3:   R \circ S &= \{(x,z) \in X^2 \mid \exists{y \in X}: (x,y) \in R \text{ and } (y,z) \in S\}\\
sawine@3:   R \circ T &= \{(x,z) \in X^2 \mid \exists{y \in X}: (x,y) \in R \text{ and } (y,z) \in T\}
sawine@4: \end{align}\setcounter{equation}{0}\\
sawine@3: 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\\\\
sawine@4: (b) By definition holds
sawine@4: \begin{align}
sawine@4:   -R &= \{(x,y) \in X^2 \mid (x,y) \notin R\}\\
sawine@4:   (-R)^{-1} &= \{(y,x) \in X^2 \mid (x,y) \in -R\}\\
sawine@4:   -(R^{-1}) &= \{(x,y) \in X^2 \mid (x,y) \notin R^{-1}\}\\
sawine@4:   -(R^{-1}) &= \{(x,y) \in X^2 \mid (y,x) \notin R\}
sawine@4: \end{align}\setcounter{equation}{0}\\
sawine@4: 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\\\\
sawine@3: (c) By definition holds
sawine@3: \begin{align}
sawine@3:   (R \circ S)^{-1} &= \{(z,x) \in X^2 \mid \exists{y \in X}: (x,y) \in R \text{ and } (y,z) \in S\}\\
sawine@3:   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}\}\\
sawine@3:   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\}
sawine@4: \end{align}\setcounter{equation}{0}\\
sawine@4: 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\\\\
sawine@4: (d) By definition holds
sawine@4: \begin{align}
sawine@4:   R \circ S &= \{(x,z) \in X^2 \mid \exists{y \in X}: (x,y) \in R \text{ and } (y,z) \in S\}\\
sawine@4:   (R \circ S) \cap T^{-1} &= (R \circ S) \cap \{(y,x) \in X^2 \mid (x,y) \in T\}\\
sawine@4:   (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\}\\
sawine@4:   (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\}
sawine@4: \end{align}\\
sawine@4: We've obtained (3) by directly applying intersection within the set comprehension of (2). It follows that\\
sawine@4: \begin{align}
sawine@4:   (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\\
sawine@4:   \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
sawine@4: \end{align}\\
sawine@4: 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
sawine@0: \end{document}