\magnification=\magstep1
\centerline{Mathematics 243, section 2 -- Mathematical Structures}
\centerline{Information on Exam 1}
\centerline{September 22, 2017}
\bigskip
\noindent
{\it General Information}
\bigskip
As announced in the course syllabus and the schedule on
the course homepage, the first exam this semester will be
given Friday, September 29 (or possibly Thursday evening, September 28).  The exam will cover the
material we have discussed since the start of the semester, through
the material on mathematical induction proofs from class on September 20 and 22.  
The topics to review are:
\bigskip
\item{1)}  Logic:  truth tables for ``not,'' ``and,'' ``or,'' ``implies,'' ``iff,'' and their use
in finding truth tables for compound statements, establishing tautologies, etc.   
\item{2)}  Sets, set operations: union, intersection, complement, set
difference, and their properties; proving or disproving set containment, equality, etc.
(This might include some material about partitions of sets as well)
\item{3)}  The natural numbers, know the Peano axioms, be able to do
 proofs by mathematical induction  
\bigskip
\noindent
{\it Practice Problems}
\bigskip
The exam will consist of 4 or 5 problems (each possibly having
several parts).  Some questions will ask you to find sets by using set operations or 
compute a truth table, some will ask for definitions and/or (short) proofs.  
\bigskip
\noindent
{\it Suggestions on How To Prepare}
\bigskip
Read over your notes from class (several times, if necessary!). 
Make sure you can follow all the steps in proofs and examples. 
Review the problems from the problem sets, and pay particular 
attention to any problems you missed the first time.  Then try the 
following review questions:
\bigskip
\noindent
Note:  This list is longer than the actual exam will be to 
show the range of different kinds of questions that might appear.  
\bigskip
\noindent
I.  Construct the truth tables for the following statements.
\item{A)}  $(P\ {\rm and}\ (P\ {\rm implies}\ Q))\ {\rm implies}\ Q$.
\item{B)}  $(({\rm not}\ Q)\ {\rm and}\ (P\ {\rm implies}\ Q))\ {\rm implies}\ ({\rm not}\ P)$.
\item{C)}  $(P\ {\rm or}\ (Q\ {\rm and}\ R))\ {\rm if\ and\ only\ if}\ ((P\ {\rm or}\ Q)\ {\rm and}\ (P\ {\rm or}\ R))$.
\item{D)} Which of A,B,C are tautologies?
\bigskip 
\noindent 
II.   Let 
$$\eqalign{U &= {\bf Z}\cr
           A &= \{ x \in {\bf Z} : x {\rm\ is\ even\ and\ } -3 \le x \le 10\}\cr
           B &= \{1,2,3,4,5\}\cr
           C &= \{x \in {\bf Z} : x < -4 {\rm\ or\ } x > 7\}\cr}$$
\item{A)}  What is the set $A \cap B$.
\item{B)}  What is the set $A^c \cap (B\cup C)$?
\item{C)}  What is the set $C^c$?
\bigskip
\noindent
III.  Let $A, B$ be any two subsets of a universal set $U$.
Prove that $(A \cap B)^c = A^c \cup B^c$ (where $X^c$ is the complement of $X$ in $U$). 
\bigskip 
\noindent
IV.  Consider the following statement, where $A,B$ are nonempty sets of real numbers.
``If $A \cap [0,1] = \emptyset$, and $B \cap [0,1] = B$, then $A \cap B = \emptyset$. 
\item{A)} Give the contrapositive form of this statement.
\item{B)} Give the converse of the statement.  
Is the contrapositive statement true or false?  Explain.
\bigskip
\noindent
V.  Prove or disprove:
\item{A)}  $12 {\bf Z} \subseteq 6 {\bf Z}$
\item{B)}  $24 {\bf Z} \cap 30 {\bf Z} = 120 {\bf Z}$
\item{C)}  For any three sets $A,B,C$, $A \cap (B \cup C) = (A \cap B) \cap (A \cap C)$.  
\item{D)}  If $n^2$ is an odd integer, then $n$ is an odd integer.   
\bigskip 
\noindent
VI.  
\item{A)}  Prove: If $m,n$ are integers with no common factors, then ${m\over n} \ne \sqrt{3}$.
(Prove by contradiction.  You may use without justification the following plausible statement
that we will prove later:  If $k$ is an integer and $k^2$ is a multiple of $3$ then 
$k$ is a multiple of $3$.)
\item{B)}  Investigate this question:  For which integers $m$ is it true that
if $k$ is an integer and $k^2 \in m {\bf Z}$, then $k \in m {\bf Z}$?  Is it true for $m = 4, 5, 6, 7, 8, 9$, etc. ?   
(Note: this is too open-ended to be an exam question, but it is interesting to look at!)
\bigskip
\noindent
VII.  Prove by mathematical induction:
\item{A)}  For all $n \ge 1$ in ${\bf N}$, 
$$1 \cdot 2 + 2 \cdot 2^2 + 3\cdot 2^3 + \cdots + n \cdot 2^n = (n-1)2^{n+1} + 2$$
\item{B)}  For all $n \ge 1$ in ${\bf N}$,
$$1^2 + 3^2 + 5^2 + \cdots + (2n-1)^2 = {n(2n-1)(2n+1)\over 3}$$
\item{C)}  For all $n \ge 6$, $n^3 < n!$  
\bye
