\magnification = \magstep1
\centerline{Mathematics 243, section 1 -- Algebraic Structures}
\centerline{Exam 1 -- October 8, 2003}
\bigskip
\noindent
{\it Directions}
\bigskip
Do all the problems below in the blue exam booklet. 
Do not place anything you want to have considered for 
credit on the exam sheet.  There are 100 regular points and 10 Extra
Credit points. 
\bigskip
\noindent
I. 
\item{A)} (15) Show that the following proposition is true
for {\it all combinations} of truth values of $p,q,r$: 
$$ (p \Rightarrow (q \vee r)) \Leftrightarrow 
((p \wedge \sim q) \Rightarrow r)$$
You may use a truth table or any other applicable method.
\item{B)} (15) Let $A, B$ be any two subsets of a universal set $U$.
Show that $(A \cap B)' = A' \cup B'$ (where $X'$ is the complement of $X$). 
\bigskip
\noindent
II.  Consider the following statement, where $A$ is a nonempty set.
``If $f : A \to A$ is a one-to-one mapping, then for all $a\in A$, the
set $f^{-1}(\{a\})$ has at most one element.''
\item{A)} (10) Give the contrapositive form of this statement.
\item{B)} (10) Give the converse of the statement.  
Is the converse true or false?  Explain.
\bigskip
\noindent
III. 
Let $f,g : {\bf Z} \to {\bf Z}$ be the mappings
$$f = \cases{2x+1 & if $x$ is even\cr
             x-1 & if $x$ is odd\cr}
  \qquad
  g = \cases{x+1 & if $x$ is even\cr
             (x-1)/2 & if $x$ is odd\cr}$$
\item{A)} (10) Let $S = \{1,2,3\}$ and 
$T = \{0,3,6\}$.  What is $g^{-1}(T) \cap f(S)$?
\item{B)} (10) What is the mapping $f\circ g$?  
\bigskip
\noindent         
IV.  Let $M$ be the set of all $2\times 2$ matrices with 
integer entries, and write $Q = \pmatrix{0 & 1\cr 1& 0\cr} \in M$.
Define a relation $R$ on $M$ by saying $A\ R\ B$ if and only if 
the matrix product $QAQ$ is equal to $B$.
\item{A)} (5) Show that 
$$\pmatrix{4 & 7\cr 2 & 3}\ R\ \pmatrix{3& 2\cr 7& 4}$$
is true. (Hint:  The matrix product is associative.)
\item{B)} (10)  For which matrices $A$ is $A R A$ true? 
\bigskip
\noindent
V. (15) Prove by mathematical induction:
If $n\in {\bf Z}^+$, then 
$$a + (a + d) + (a + 2d) + \cdots + (a + (n-1)d) = {n\over 2}(2a + (n-1)d).$$
\bigskip
\noindent
{\it Extra Credit} (10)  Refer to question 
IV above.  Show that $R$ is a symmetric relation. 
\bye
 