\documentclass[12pt]{article}
\input{macros-course}

%% Latex asks whether or not to include solutions
\askaboutsolutions

\begin{document}

%% Practice Problems 3: Relations, Equivalence (Rad, Fall01)
\ifshowsolutions
  \prsol{3}{September 20, 2001}{\stamp}
\else
  \prprob{3}{September 19, 2001}{Thursday, 9/20}{\stamp}
\fi

\textbf{Reading:} Rosen \S 6.1, 6.3--5 (ignore Warshall's algorithm in
\S 6.4). \emph{Supplementary reading:} Velleman \S 4.2--4.3.

\vspace{.1in}


\ifshowsolutions
 {}
\else
\emph{Optional Reading Comments:} (Optional because there is only a
Wednesday lecture this week.)  By 9am on the due date, send email
to
\begin{center}
\texttt{6042-probs@theory.lcs.mit.edu}
\end{center}
indicating in at most three
sentences one or more of the following: the passage in the
reading---\emph{including its page number}---you

\begin{itemize}

\item found most difficult,

\item found most surprising,

\item would like to have discussed in the next Lecture.

\end{itemize}

\vspace{.1in}

\textbf{Problem Submission:} We are trying out a \textbf{new online tutor
system} for submission of the pre-lecture practice problems.  You can
access the tutor from the course website.  The online tutor will tell you
if your answers to the problems are correct, and it will allow you to
change the incorrect ones.

This version of the tutor is a beta-release.  If you have trouble using
the online system, feel free to submit your problem solutions on paper at
the beginning of your tutorial section.  We would be grateful for a bug
report on any problems with the online tutor.
\fi

\begin{problems}

\ifshowsolutions
(For solutions to problems 2--4, see the online tutor.)
\else
{}
\fi

\problem (\emph{Optional, for a surprise demo in lecture.}) What is your
date of birth (month/day/year) and height (feet, inches)?

\problem Rosen Exercise 6.1.3 (a,b,c)

\problem Rosen Exercise 6.3.7

\problem Rosen Exercise 6.5.2 (a,b,e)

%-----------------------------------------------------------------%
% Source: Velleman Sec 4.2, Exercise 3 parts a,b and c.\\
% Used by Karger Spring 01, but changed sets slightly (Rad)

\problem Let
\begin{eqnarray*}
A & \eqdef & \set{1,2,3},\\
B & \eqdef & \set{4,5,6},\\
R & \eqdef & \set{(1,4), (1,5), (2,5), (3,6)},\\
S & \eqdef & \set{(4,5), (4,6), (5,4)}.
\end{eqnarray*}
Note that $R$ is a binary relation between $A$ and $B$, that is, $R \subseteq A
\cross B$.  Also, $S$ is a binary relation on $B$, that is, $S \subseteq B
\cross B$.

Find the following relations:
\bparts
\ppart $S\circ R$

\solnospace{
$S\circ R = \set{(1,5), (1,6), (1,4), (2,4)}$}

\ppart $S\circ S$

\solnospace{$S\circ S = \set{(4,4), (5,5), (5,6)}$}

\ppart $S^{-1}\circ R$

\solnospace{$S^{-1}\circ R = \set{(1,5), (1,4), (2,4), (3,4)}$}

\eparts

\end{problems}

\end{document}
