% LaTex2e
\documentclass[12pt]{article}
\usepackage{amssymb,latexsym}

\usepackage{anysize}
%\marginsize{left}{right}{top}{bottom}
%\marginsize{1.25cm}{1.25cm}{1.75cm}{2.5cm} % this cuts off page numbers
\marginsize{2cm}{2cm}{1cm}{3cm} 

\pagestyle{myheadings}
\def\header{{\hfill Exam 1 \hfill A. Miller \hfill Spring 2005
                                       \hfill Math 240\hfill}}
\markboth\header\header
\newcount\probno
\newcount\total
\newwrite\examTBLFile

\probno=0

\def\prob#1{\advance\probno by 1 \par % \vfill \newpage
    \noindent\the\probno . (#1 pts)\advance\total by #1
    \immediate\write\examTBLFile{\the\probno
       \string& #1 \string&
       \string\qquad \string\\ \string\hline}}

\def\finishtbl{
    \immediate\write\examTBLFile{Total \string& \the\total
    \string& \qquad \string\\ \string\hline}
     }

\newwrite\ans
\immediate\openout\ans=answers
\outer\def\answer{\par\medbreak
  \immediate\write\ans{}
  \immediate\write\ans{\string\bigskip \the\probno . }
  \copytoblankline}
\outer\def\answerx{\par\medbreak
  \immediate\write\ans{}
  \immediate\write\ans{\string\bigskip \the\probno . }
  \copytoblankline}
\outer\def\putanswer{\par\medbreak
  \immediate\write\ans{}
  \copytoblankline}
\def\copytoblankline{\begingroup\setupcopy\copyans}
\def\setupcopy{\def\do##1{\catcode`##1=12}\dospecials
     \catcode`\|=12\obeylines}
{\obeylines \gdef\copyans#1
  {\def\next{#1}%
  \ifx\next\empty\let\next=\endgroup%
  \else\immediate\write\ans{\next}\let\next=\copyans\fi\next}}
\def\printanswers{\newpage\begin{center} Answers \end{center}
    \immediate\closeout\ans\input answers}

% \def\answer{\par\bigskip\bigskip\bigskip\noindent Answer: \par}
% \outer\def\answer{ {\par\bigskip Circle your answer.} \par\medbreak

\begin{document}

\bigskip

Show all work.  

% Simplify your answers.  

% Circle your answer.

\bigskip

No notes, no books, no calculators, no cell phones, no pagers, no
electronic devices of any kind. 


\par\vskip .25in
\begin{center}
Name\makebox[3in]{\hrulefill} \\
\end{center}

\bigskip
Circle your Discussion Section:
\begin{verbatim}

    DIS 303 12:05p T B235 VAN VLECK
    DIS 304 12:05p R B235 VAN VLECK
    DIS 307  2:25p T B139 VAN VLECK 
    DIS 308  2:25p R B309 VAN VLECK 

\end{verbatim}
\bigskip

\begin{center} \Large
 \begin{tabular}{||c|c|c||} \hline\hline
  Problem & Points & Score \\  \hline\hline
   \input{exam.tbl}
  \hline \hline
 \end{tabular}
\end{center}

\immediate\openout\examTBLFile=exam.tbl

\bigskip
 
Solutions will be posted shortly after the exam:
www.math.wisc.edu/$\sim$miller/m240

% \setcounter{page}{0}

\newpage 

\prob{4}
Construct a truth table for the compound proposition:
$$ (p\to q) \vee (\neg p \to  q)$$
\answer 1.1-27 \par
This is a tautology.


\vfill

\prob{4}
Use a truth table to verify:
$$(p \to q)\equiv (\neg q\to \neg p)$$
\answer 1.2-3 \par
This is the contrapositive.

\vfill

\newpage

\prob{6}
Let $P(x)$ be the statement $x+1>x^2$ and suppose that the universe
of discourse consists of the integers.  What are the truth values of
the following?
\begin{enumerate}
\item $P(0)$
\item $P(1)$
\item $P(-1)$
\item $\exists x \; P(x)$
\item $\forall x \; P(x)$
\item $\forall x \exists y \;\; ((y>x) \wedge P(y))$
\end{enumerate} 
\answer 1.3-11 \par
TTFTFF

\vfill 

\prob{6}
Determine the truth value of each of the following if the universe
of discourse for all variables consists of the positive integers
${\mathbb N}=\{1,2,3,\ldots\}$.
\begin{enumerate}
\item $\forall n\; \exists m \;\;\;\; n^2<m$
\item $\exists m\; \forall n \;\;\;\; n^2<m$
\item $\exists n\; \exists m \;\;\;n^2+m^2=5^2$
\item $\exists n\; \exists m \;\;\;n^2+m^2=6^2$
\item $\forall n\; \forall m \;\;\; ( n\leq m \;\vee\; m\leq n)$
\item $\forall n\; \forall m \;\;\;( n < m \;\vee\; m < n)$
\end{enumerate}
\answer 1.4-27 \par
TFTFTF

\vfill\newpage

\prob{8}
Determine if the following arguments are correct.  If it is correct, what
rule of inference is being used.  If it is not, what logical error 
occurs?
\par\bigskip (a) If $n$ is an integer with $n\geq 2$, then $n^3\geq 8$.  
Suppose $n<2$.  Then $n^3<8$.

\vfill
\par\bigskip (b) If $n$ is an integer with $n>2$, then $n^3>8$.  Suppose
$n^3\leq 8$.  Then $n\leq 2$.
\answer 1.5-13 
\par (a) The logical form of this argument is:
\par $P\to Q$
\par $\neg P$
\par ---------------
\par $\neg Q$.
\par \noindent
This is an incorrect inference even though it reaches a correct conclusion.
\par\bigskip
(b) The logical form of this argument is:
\par $P\to Q$
\par $\neg Q$
\par ---------------
\par $\neg P$.
\par\noindent This is a correct logical inference.
 

\vfill\newpage

\prob{7}
How many different elements does $A\times A\times A$ 
have if $A$ has $n$ elements?
\answer 1.6-25 \par
$n^3$.

\vfill
\prob{7}
What can we say about the sets $A$ and $B$ if $A\oplus B=\emptyset$.
The symbol $\oplus$ denotes the symmetric difference.
\answer 1.7-31 \par
$A=B$

\vfill\newpage

\prob{6}
Let $h(x)=\lceil x \rceil$.  Find
\begin{enumerate}
\item $h^{-1}(\{2\})$

\vfill

\item $h^{-1}(\{x \;:\; -1\leq x\leq 1\})$

\vfill

\item $h(\{x \;:\; -1\leq x\leq 1\})$
\end{enumerate}
\answer 1.8-35 
\par 1. $(1,2]$
\par 2. $(-2,1]$
\par 3. $\{-1,0,1\}$

\vfill\newpage

\def\u#1#2{\underline{#1#2}}

\prob{7}
Use the bubble sort to sort the list $3,2,4,5,1$ showing the lists obtained
at each step, i.e., after each time you do a comparison.
\answer 2.1-35\par
\par \u32451
\par 2\u3451
\par 23\u451
\par 234\u51
\par \u23415
\par 2\u3415
\par 23\u415
\par 231\u45
\par \u23145
\par 2\u3145
\par 21\u345
\par 213\u45
\par \u21345
\par  12345
\par followed by the end of this pass and one more pass to check that nothing
changes.


\vfill\newpage
\prob{8}
Find the least integer $n$ such that $f(x)$ is $O(x^n)$ where
$$f(x)={{2x^5+x^2+1}\over{3x^2+4x\ln(x)}}$$
\answer 2.2-7 \par
$O(x^3)$


\vfill\newpage
\prob{8}
Show that if $2^n-1$ is prime, then $n$ is prime.
\par\bigskip Hint: $(x^m-1)=(x-1)(x^{m-1}+x^{m-2}+\cdots+x+1)$
\answer 2.4-23 \par
Suppose that $n$ is not prime and let $n=km$ for integers
$k,m$ with $1<k,m<n$.  Put $x=2^k$ and using the hint
note that 
$$2^n-1=(2^k)^m-1=(x^m-1)=(x-1)(x^{m-1}+x^{m-2}+\cdots+x+1)$$
and so $2^n-1$ is not prime.

\vfill\newpage
\prob{7}
Convert the integer $1100 1111$ from binary notation to
decimal notation.
\answer 2.5-3\par
$207$

\vfill
\prob{7}
How much time does an algorithm using $2^{40}$ bit operations
take if each bit operation takes $10^{-9}$ seconds?
\answer 2.3-11 \par
$2^{40}10^{-9}$ seconds.  A good estimate is to
use $2^{10}=1024\approx 1000$ so 
$$2^{40}10^{-9}={2^{40}\over 10^{9}}={(2^{10})^4\over 10^{9}}
\approx {(1000)^4\over 10^{9}}={(10^3)^4\over 10^{9}}=
{10^{12}\over 10^{9}}=10^3
$$

\vfill\newpage
\prob{8}
Suppose that an integer $a$ is not divisible by the prime $p$.  Show that
no two of the integers: $$a,2a,3a,\ldots, (p-1)a$$ are congruent
modulo $p$.
\answer 2.6-17 \par
Suppose for contradiction that there are $i,j$ integers with
$1\leq i<j\leq p-1$ such that 
$$ia\equiv_p ja$$
Then 
$$0\equiv_p (j-i)a$$
and so $p$ divides $(j-i)a$.  Since $p$ is prime and does not divide
$a$ it must divide $j-i$.  But this is impossible because
$1\leq j-i<p$.


\vfill\newpage
\prob{7}
Find $AB$ if
$$A=\left[
\begin{array}{rrr}
 1  & -1  & -2 \\
-1  &  2  & 0\\
\end{array}\right]
\;\;\;\;\;\mbox{ and }\;\;\;\;\;\;
B=\left[
\begin{array}{rr}
 1  & -1  \\
-1  &  2  \\
 2  &  0 \\
\end{array}\right]
$$
\answer 2.7-3 \par
$$\left[
\begin{array}{rr}
-2  & -3  \\
-3  &  5  \\
\end{array}\right]$$

\finishtbl

\printanswers

\newpage
The following program was used to pick the problems on this test.  
In some cases the problem is identical and in others it is just similar.

\begin{verbatim}

#! /usr/ucb/python

import string
import sys
import random

f=open("hmwk1",'r')    # input file
lines=f.readlines()       

random.seed("the three stooges")

for line in lines:      
  s=string.split(line)                                           
  if len(s)> 4:                                                  
    section=s.pop(0)                                             
    print random.choice(s).rjust(2) + "  "+string.lstrip(line)   

\end{verbatim}


\end{document}


