\documentclass{article}
\usepackage{exam,epsf,amsmath,amssymb}
%%%% If you are not using LaTex2e, replace the first two lines 
%%%% with the following:
%\documentstyle[exam96,epsf,ams]{article}
%\input{amssym}
\paper{COMPSCI 225}  % <- do not include FC, FT etc
\version{0}                     % <- for multiple choice exams
\title{Discrete Mathematics}
\time{two}                      % <- number of hours: default is three
\semester{first semester}
\year{2001}                     % <- default is the current year
\campus{City}
\note{Answer {\bf All} questions.  The questions in Section A
  (multiple choice questions) are worth 1 mark each: the marks for
  each question in Section B are as shown.  Section A is worth a total
  of 20 marks and Section B is worth a total of 40 marks: you are
  advised to spend about one hour on Section A and two hours on
  Section B.\\
  Answer Section A (multiple choice questions) on the coloured answer
  sheet provided.}
\begin{document} 
\begin{center}
  \large{\bf SECTION A\\[5mm]
    MULTIPLE CHOICE QUESTIONS}\\[5mm]
  Circle the preferred choice {\bf on the coloured answer sheet
    provided.}
\end{center}
\begin{questions}
  \question Let $A$ and $B$ and $C$ be subsets of a universal set $U$.
  Which of the following sets is equal to the shaded region in the
  following Venn diagram?
  \[
  \epsfbox{figure.ps}
  \]

  \begin{answers}
  \item $(A\cup(B\cap C))\setminus(A\cap(B\cup C))$.
  \item $A\cup (B\cap C)$.
  \item $A\cap (B\cup C)$.
  \item $(A\setminus B)\cap(A\setminus C)$.
  \item $(A\setminus (B\cup C))\cup(B\cap C)$.
  \end{answers}
  
  \question Let $f:A\to B$ and $g:B\to C$ be functions.  Which of the
  following statements is NOT true?
  \begin{answers}
  \item if $g\circ f$ is 1--1 then $f$ and $g$ are both 1--1.
  \item if $g\circ f$ is 1--1 then $f$ is 1--1.
  \item if $g\circ f$ is onto then $g$ is onto.
  \item if $g\circ f$ is a bijection then $f$ is 1--1 and $g$ is onto.
  \item if $f$ and $g$ are both 1--1 then $g\circ f$ is 1--1.
  \end{answers}
  
  \question A multiple-choice exam has 20 question, and each question
  has 5 possible answers.  The same 5 answers for each question will
  appear on each exam paper, but they can appear in any order.  The
  questions will appear in the same order on every exam paper.  How
  many different exam papers can be printed?
  \begin{answers}
  \item $(5!)^{20}$.
  \item $\displaystyle{20\choose5}$.
  \item $\displaystyle{20+5-1\choose5}$.
  \item $P(20,5)$.
  \item $\displaystyle\frac{20!}{5!}$.
  \end{answers}

  \begin{center}
    \large\bf SECTION B
  \end{center}
  \question 
  \begin{enumerate}
  \item For each of the following propositions, determine whether it
    is a tautology, a contradiction or a contingent proposition.  You
    may find it helpful to refer to the list of standard taultologies
    in the ATTACHMENT on page~\pageref{tautologies}.
    \begin{enumerate}
    \item $p\to (q\land p)$.
    \item $p\to (q\lor p)$.
    \item $p\to \lnot(q\land p)$.
    \item $\lnot(q\lor(q\to p))$.
    \end{enumerate}
  \item Let $A_1,A_2,\dots,A_n,B$ be propositions.  What does it mean
    to say that the argument $A_1,A_2,\dots,A_n,\therefore B$ is {\em
      valid\/}?  Identify the simple propositions in the following
    argument and determine whether or not it is valid:
    \begin{quote}
      ``If interest rates are not high, then house prices will rise.
      If interest rates are high, then the exchange rate will be low.
      Therefore if the exchange rate is not low then house prices will
      rise.''
    \end{quote}
    \marks{5}
  \end{enumerate}


  \question 
  \begin{enumerate}
  \item Let $p(x,y)$ denote the predicate ``$x<y$'', with domain of
    definition $\Bbb Z\times\Bbb Z$.  Translate the following
    statements into predicate logic.
    \begin{enumerate}
    \item ``For every integer $x$ there is an integer $y$ with
      $x<y$.''
    \item ``For all integers $x$, $y$ and $z$, if $x<y<z$ then
      $x<z$.''
    \item ``For each integer $x$ there is an integer $y$ such that
      $x<y$ but there is no integer $z$ with $x<z<y$.''
    \end{enumerate}
  \item 
    \begin{enumerate}
    \item What does it mean to say that a proposition in predicate
      logic is a \emph{tautology}?
    \item Show that $\forall x\,p(x)\to\exists x\,p(x)$ is a
      tautology.
    \item Show that $\exists x\,p(x)\to\forall x\,p(x)$ is not a
      tautology.  \marks{7}
    \end{enumerate}
  \end{enumerate}

  \question 
  \begin{enumerate}
  \item Let $A$ and $B$ be sets, and let $f:A\to B$ be a function.
    Define a relation $\approx$ on $A$ by
    \[
    x\approx y\qquad\Leftrightarrow\qquad f(x)=f(y).
    \]
    Show that $\approx$ is an equivalence relation.
  \item Define the relation $\approx$ on $\Bbb R\times\Bbb R$ by
    \[
    (x,y)\approx(u,v)\qquad\Leftrightarrow\qquad x^2+y^2=u^2+v^2.
    \]
    By part (a) we know that this is an equivalence relation.  For
    $x,y\in\Bbb R$, we denote the equivalence class of $(x,y)$ by
    $[x,y]$.  Suppose we define the sum of two equivalence classes by
    \[
    [x,y]\oplus[u,v]=[\sqrt{\mathstrut x^2+u^2},\sqrt{y^2+v^2}\,].
    \]
    \begin{enumerate}
    \item What does it mean to say that $\oplus$ is {\em
        well-defined\/}?
    \item Show that $\oplus$ is well-defined.  \marks{10}
    \end{enumerate}
  \end{enumerate}

\end{questions}

\attachment
\label{tautologies}
\begin{center}
  \begin{tabular}{|c|l|}
    \hline
    $p\Leftrightarrow\lnot\lnot p$&Double Negation\\
    \hline
    $p\land q\Leftrightarrow q\land p$&Commutative\\
    \cline{1-1}
    $\lor q\Leftrightarrow q\lor p$&Laws\\
    \hline
    $\lnot(p\land q)\Leftrightarrow\lnot p\lor\lnot q$&De Morgan's\\
    \cline{1-1}
    $\lnot(p\land q)\Leftrightarrow\lnot p\lor\lnot q$&Laws\\
    \hline
  \end{tabular}\\
  Standard tautologies
\end{center}

\answersheet
\begin{center}
  \setlength{\tabcolsep}{5mm} \renewcommand{\arraystretch}{1.5}
  {\large\bf SECTION A}\\[5mm]
  Circle the preferred answer.\\[2mm]
  If you make a mistake, mark a cross through your wrong choice and circle your next alternative.\\[1cm]
  \begin{tabular}{l@{\hspace{10mm}}lllll}
    1.&a&b&c&d&e\\
    2.&a&b&c&d&e\\
    3.&a&b&c&d&e
  \end{tabular}
\end{center}


\end{document}

