\documentclass[a4paper, 10pt, pagesize, smallheadings]{article}

\usepackage{graphicx}

%\usepackage[latin1]{inputenc}

\usepackage{amsmath, amsthm, amssymb}

\usepackage{typearea}

\usepackage{algorithm}

\usepackage{algorithmic}

\usepackage{fullpage}

\usepackage{mathtools}

\usepackage[all]{xy}

\addtolength{\voffset}{-40pt}

\title{CSP Exercise 01 Solution}

\author{Eugen Sawin}

\renewcommand{\familydefault}{\sfdefault}

\newcommand{\E}{\mathcal{E}}

\newcommand{\R}{\mathcal{R}}

%\include{pythonlisting}

\pagestyle{empty}

\begin{document}

\maketitle

\section*{Exercise 1.1}

\begin{tabular}{|c|c|c||c|c|c||c|c|c|}

  \hline

  5&3&6 &4&7&2 &8&1&9 \\ \hline

  4&2&1 &6&9&8 &5&7&3 \\ \hline

  7&8&9 &1&5&3 &4&6&2 \\ \hline\hline

  8&6&3 &9&2&4 &1&5&7 \\ \hline

  1&7&5 &8&3&6 &9&2&4 \\ \hline

  2&9&4 &5&1&7 &6&3&8 \\ \hline\hline

  3&1&8 &2&4&5 &7&9&6 \\ \hline

  9&4&7 &3&6&1 &2&8&5 \\ \hline

  6&5&2 &7&8&9 &3&4&1 \\ \hline

\end{tabular} \\\\

I have applied following strategies to solve the puzzle:

\begin{itemize}

  \item look for most contrained blocks, rows and columns

  \item look for values with most resolved positions

  \item annotate cells with consistent values

  \item look for inconsistent connections between cell annotations

\end{itemize}

\section*{Exercise 1.2}

(a) $R_{x,y} \bowtie S_{y,z} = \{(a,b,a),(a,b,c)\}$\\\\

(b) $\sigma_{z=c}(R_{x,y} \bowtie S_{y,z}) = \{(a,b,c)\}$\\\\

(c) $\pi_x(R_{x,y}) = \{(a)\}$\\\\

(d) $R_{x,y} \circ S_{y,z} = \{(a,a),(a,c)\}$

\section*{Exercise 1.3}

(a) By definition holds

\begin{align}

  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)\}\\

  R \circ S &= \{(x,z) \in X^2 \mid \exists{y \in X}: (x,y) \in R \text{ and } (y,z) \in S\}\\

  R \circ T &= \{(x,z) \in X^2 \mid \exists{y \in X}: (x,y) \in R \text{ and } (y,z) \in T\}

\end{align}\setcounter{equation}{0}\\

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\\\\

(b) By definition holds

\begin{align}

  -R &= \{(x,y) \in X^2 \mid (x,y) \notin R\}\\

  (-R)^{-1} &= \{(y,x) \in X^2 \mid (x,y) \in -R\}\\

  -(R^{-1}) &= \{(x,y) \in X^2 \mid (x,y) \notin R^{-1}\}\\

  -(R^{-1}) &= \{(x,y) \in X^2 \mid (y,x) \notin R\}

\end{align}\setcounter{equation}{0}\\

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\\\\

(c) By definition holds

\begin{align}

  (R \circ S)^{-1} &= \{(z,x) \in X^2 \mid \exists{y \in X}: (x,y) \in R \text{ and } (y,z) \in S\}\\

  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}\}\\

  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\}

\end{align}\setcounter{equation}{0}\\

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\\\\

(d) By definition holds

\begin{align}

  R \circ S &= \{(x,z) \in X^2 \mid \exists{y \in X}: (x,y) \in R \text{ and } (y,z) \in S\}\\

  (R \circ S) \cap T^{-1} &= (R \circ S) \cap \{(y,x) \in X^2 \mid (x,y) \in T\}\\

  (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\}\\

  (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\}

\end{align}\\

We've obtained (3) by directly applying intersection within the set comprehension of (2). It follows that\\

\begin{align}

  (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\\

  \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

\end{align}\\

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

\end{document}