\documentclass[11pt]{article}
\def\Z{\mathbb{Z}}
\def\Q{\mathbb{Q}}
\usepackage{latexsym,amsmath,amssymb,epsfig}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{0in}
\setlength{\textheight}{8.0in}
\begin{document}
\centerline{MATH 243 -- Mathematical Structures}
\centerline{Solutions for Exam 1 Practice Problems -- September 28, 2017}
\vskip 10pt
\noindent
I.  
\begin{enumerate}
\item[(A)]  The truth table for  $(P\ {\rm and}\ (P\ {\rm implies}\ Q))\ {\rm implies}\ Q$
looks like this:
$$\begin{array}{llllll}
P & Q & (P\ &{\rm and}\ (P\ &{\rm implies}\ Q))\ &{\rm implies}\ Q \\ \hline
T & T &     &T              &T                   &T \\
T & F &     &F              &F                   &T \\
F & T &     &F              &T                   &T \\
F & F &     &F              &T                   &T\\
\end{array}$$
(The last column is the truth value of the whole statement.)
\item[(B)]    The truth table for  $(({\rm not}\ Q)\ {\rm and}\ (P\ {\rm implies}\ Q))\ {\rm implies}\ ({\rm not}\ P)$
looks like this:
$$\begin{array}{lllllllll}
P & Q & ((&{\rm not}\ Q)\ &{\rm and}\ (P\ &{\rm implies}\ Q))\ &{\rm implies}\ &({\rm not}\ P)\\ \hline
T & T &     &F              &F            &T     &T  &F \\
T & F &     &T              &F             &F    &T  &F \\
F & T &     &F              &F             &T    &T  &T \\
F & F &     &T              &T             &T    &T  &T\\
\end{array}$$
(The next to last column is the truth value of the whole statement.)
\item[(C)]  The truth table for  $(P\ {\rm or}\ (Q\ {\rm and}\ R))\ {\rm if\ and\ only\ if}\ ((P\ {\rm or}\ Q)\ {\rm and}\ (P\ {\rm or}\ R))$:
$$\begin{array}{lllllllllllllllllll}
P & Q & R & (P\ &{\rm or}\ (Q\ &{\rm and}\ R))\ &{\rm if\ and\ only\ if}\ ((P\ &{\rm or}\ Q)\ &{\rm and}\ (P\ &{\rm or}\ R))\\ \hline
T & T & T  &   &T              &T  &T   &T     &T  &T \\
T & T & F  &   &T              &F  &T   &T     &T  &T \\
T & F & T  &   &T              &F  &T   &T     &T  &T \\
T & F & F  &   &T              &F  &T   &T     &T  &T \\
F & T & T  &   &T              &T  &T   &T     &T  &T \\
F & T & F  &   &F              &F  &T   &T     &F  &F \\
F & F & T  &   &F              &F  &T   &F     &F  &T\\
F & F & F  &   &F              &F  &T   &F     &F  &F\\
\end{array}$$
(The overall truth value is given by the column lined up under the ``if and only if.'')
\item[(D)]  These are \emph{all} tautologies.
\end{enumerate}
\vskip 10pt 
\noindent
II.  
\begin{enumerate}
\item[(A)]  We have $A = \{-2,0,2,4,6,8,10\}$ and $B = \{1,2,3,4,5\}$ so 
$A \cap B = \{2,4\}$.
\item[(B)] $A^c$ consists of all integers not in $A$, so 
$$A^c = \{\ldots,-5,-4,-3,-1,1,3,5,7,9,11,12,13,\ldots\}$$
(all integers $\le -3$,  all integers $\ge 11$ and the odd numbers between
$-3$ and $11$.)  
$B \cup C$ consists of all the integers in the set
$$B \cup C = \{\ldots,-7,-6,-5, 1,2,3,4,5, 8,9,10,\ldots\}.$$
Hence $A^c \cap (B \cup C)$ consists of all elements of the set 
$$\{\ldots,-7,-6,-5,1,3,5,9,11,12,13,\ldots\}$$
(that is, all integers $\le -5$, all integers $\ge 11$, and $1,3,5,9$.)
\item[(C)]    $C^c = \{-4,-3,-2,-1,0,1,2,3,4,5,6\}$.  
\end{enumerate}
III.  There are several different ways you might show this.  One would be 
to construct a truth table for the statement
$$(x \notin A \cap B)\ {\rm if\ and\ only\ if}\ ((x \notin A)\ {\rm or}\ (x \notin B)).$$
What makes that work is the DeMorgan Law for negating an statement with an and.  So 
another sort of proof would be to use the definitions of complements, unions, and
intersections, plus the DeMorgan Law like this:
\begin{align*}
x \in (A\cap B)^c &\Leftrightarrow {\rm not}(x \in A\cap B) \quad {\rm (by\ definition\ of\ complement)}\\
&\Leftrightarrow {\rm not}((x \in A)\ {\rm and}\ (x\in B)) \quad {\rm (by\ definition\ of\ intersection)}\\
&\Leftrightarrow {\rm not}(x \in A)\ {\rm or}\ {\rm not}(x \in B) \quad {\rm (by\ DeMorgan)}\\
&\Leftrightarrow (x \in A^c)\ {\rm or}\ (x \in B^c) \quad {\rm (by\ definition\ of\ complement)}\\
&\Leftrightarrow x \in A^c \cup B^c \quad {\rm (by\ definition\ of\ union)}
\end{align*}
Therefore $(A \cap B)^c = A^c \cup B^c$.

\vskip 10pt
\noindent
IV.  
\begin{enumerate}
\item[(A)]  The contrapositive (with application of DeMorgan)
:  ``If $A \cap B \neq \emptyset$, then $A \cap [0,1] \ne \emptyset$ \emph{or} $B \cap [0,1] \ne B$.
\item[(B)]  The converse:  If $A \cap B = \emptyset$, then $A \cap [0,1] = \emptyset$ and $B \cap [0,1]=B$.  The contrapositive is \emph{true} because it is logically equivalent to the given
statement.  You can see that is true because if $A \cap [0,1] = \emptyset$ and 
$B \cap [0,1] = B$, then $B$ is entirely contained in $[0,1]$ and hence $A \cap B = \emptyset$. 
\end{enumerate}
\vskip 10pt
\noindent
V.
\begin{enumerate}
\item[(A)]  This is \emph{true} -- a proof would go like this.  If $x \in 12\mathbb{Z}$, then
$x = 12k$ for some $k \in \mathbb{Z}$.  Hence $x = 6\cdot (2k)$.  Since $k\in \mathbb{Z}$, 
$2k\in \mathbb{Z}$ as well, and this shows $x \in 6\mathbb{Z}$.  Hence 
$12\mathbb{Z} \subseteq 6\mathbb{Z}$.
\item[(B)]  This is \emph{also true}.  $\subseteq:$ The proof of the inclusion 
$120\mathbb{Z} \subseteq 24\mathbb{Z} \cap 30 \mathbb{Z}$ is similar to the proof in part (A).
If $x \in 120\mathbb{Z}$, then $x = 120k$ for some integer $k$.  Hence since $120 = 24 \cdot 5$
and $120 = 30 \cdot 4$, we can also write $x = 24 \cdot (5k)$ and $x = 30 \cdot (4k)$.  
Since $k$ is an integer, $4k$ and $5k$ are also integers, so this shows $x \in 24\mathbb{Z}$
and $x \in 30\mathbb{Z}$ and that shows $x \in 24\mathbb{Z} \cap 30\mathbb{Z}$.  
\item[] $\supseteq$: For the other inclusion, suppose $x \in 24\mathbb{Z}$ and $x \in 30\mathbb{Z}$.
Then $x = 24k$ for some integer $k$, and it is also true that $x = 30\ell$ for
some integer $\ell$.  (Note that $k$ cannot equal $\ell$ so we need two separate
names here :) )  If $24k = 30\ell$, then note that $5$ must divide the left hand side too, 
since it divides the $30$.  But that can only happen if $k = 5m$ for some integer
$m$, and hence 
$x = 24\cdot (5m) = 120m$.  Therefore $x \in 120\mathbb{Z}$.  (Note:  I'm using 
some facts about integers that we have not formally proved yet here.  In particular, 
I'm relying on the fact that each integer can be factored uniquely into a product
of primes.  Since $5$ is a prime and it appears in the factorization of the $30 = 2\cdot 3 \cdot 5$,
then it must appear in the factorization of the $24k$ as well.  But $24 = 2^3 \cdot 3$ 
does not contain a factor of $5$, so $k$ must contain a factor of $5$.) 
\item[(C)]  Full proof omitted.  You can get one proof by truth tables if
you reverse and's and or's in the truth table from I (C).
\item[(D)]  This is \emph{true}.  The contrapositive form is:  If $n$ is even, then
$n^2$ is even, and this follows like this:  If $n$ is even, then $n = 2k$ for 
some $k \in \mathbb{Z}$.  Hence $n^2 = 4k^2 = 2\cdot (2k)$.  Since $k$ is an
integer, so is $2k$, and this shows $n^2$ is even.  
\end{enumerate}
\vskip 10pt
\noindent
VI.  
\begin{enumerate}
\item[(A)]  (Proof by contradiction.)  Let $m,n$ be integers with no common factors, 
and assume that $\frac{m}{n}$ satisfies $\left(\frac{m}{n}\right)^2 = 3$.
Then $m^2 = 3n^2$.  This shows $m^2$ is divisible by $3$, and by the given fact
$m = 3k$ for some integer $k$.  But if we substitute that in for $m$ we get
$(3k)^2 = 9k^2 = 3n^2$.  This implies $3k^2 = n^2$ and hence $n^2$ is also divisible
by $3$.  By the given fact again, we see that $n$ must be divisible by $3$, and
that contradicts the assumption that $m,n$ had no common factors.  The thing
that produced the contradiction was assuming that  $\left(\frac{m}{n}\right)^2 = 3$, 
so that equation cannot be true, and hence $\frac{m}{n} \neq \sqrt{3}$.
\item[(B)]  If you thought about this, you might 
have seen that the statement $n^2 \in m\mathbb{Z}$ implies
$n\in m\mathbb{Z}$ is true when $m = 5,6,7$, but not for $m = 4,8,9$.  For instance
if $n = 2$, then $2^2 = 4 \in 4\mathbb{Z}$ even though $2 \notin 4\mathbb{Z}$.  
Similarly, if $n = 4$, then $4^2 = 16 \in 8\mathbb{Z}$, even though $4 \notin 8\mathbb{Z}$. 
The general pattern is that integers $m$ that are \emph{divisible by the square of
some prime number} do not have this property.  But integers $m$ that are ``square-free''
(i.e. not divisible by the square of any prime number) have this property.  
\end{enumerate}
\vskip 10pt
\noindent
VII.  
\begin{enumerate}
\item[(A)]  (Proof by induction on $n$):  When $n = 1$, we have $1\cdot 2 = 2 = (1 - 1)\cdot 2^2 + 2$.
So the base case is established.  For the induction step, we assume 
$$1 \cdot 2 + 2 \cdot 2^2 + 3\cdot 2^3 + \cdots + k \cdot 2^k = (k-1)2^{k+1} + 2$$
and consider the next integer $k + 1$.  The sum on the left of the formula to be proved is
$$(1 \cdot 2 + 2 \cdot 2^2 + 3\cdot 2^3 + \cdots + k \cdot 2^k) + (k+1)2^{k+1}.$$
By the induction hypothesis the terms in the parentheses add up to 
$(k-1)2^{k+1} + 2$.  So the sum becomes
$$(k-1)2^{k+1} + 2 + (k + 1)2^{k+1} = 2\cdot k \cdot 2^{k+1} + 2 = ((k+1) - 1)2^{k+2} + 2,$$
which is what we wanted to show.  
\item[(B)]  (Proof by induction on $n$):  When $n = 1$, we have
$$1^2 = 1 = \frac{(1)(2 - 1)(2 + 1)}{6},$$
so the base case is established.  Now assume 
$$1^2 + 3^2 + 5^2 + \cdots + (2k-1)^2 = {k(2k-1)(2k+1)\over 3}$$
and consider
$$(1^2 + 3^2 + 5^2 + \cdots + (2n-1)^2) + (2(n+1) - 1)^2.$$
By the induction hypothesis the terms in the parentheses add up to ${k(2k-1)(2k+1)\over 3}$, 
so this sum is 
$${k(2k-1)(2k+1)\over 3} + (2k+1)^2.$$
We can factor out the $2k+1$ to obtain
$$(2k+1)\cdot\left(\frac{k(2k-1)}{3} + (2k+1)\right).$$
By basic algebra, this equals
$$(2k+1)\cdot\left(\frac{2k^2 + 5k + 3}{3}\right) = \frac{(k+1)(2k+1)(2k+3)}{3},$$
which is what we wanted to prove.  
\item[(C)]  Here the base case is $n = 6$, and $6^3 = 216 < 720 = 6!$ is true so
the base case is established.  (Note that the inequality is \emph{not true} for $n = 5$!)
Now assume $k^3 < k!$ and consider $(k+1)^3$ and $(k+1)!$.  We have
$(k+1)! = (k+1)k!$, so by the induction hypothesis,
$$(k+1)! = (k+1)k! > (k+1)k^3$$
It suffices to show this is greater than $(k+1)^3$, and that is equivalent to 
$k^3 > (k+1)^2$ (canceling one factor of $k+1$).  Now if $k \ge 6$, then 
$(k+1)^2 = k^2 + 2k + 1 < k^2 + 2k^2 + k^2 = 4k^2 < k^3$, and turning these
inequalities around we get 
$$k^3 > (k+1)^2,$$ 
as desired. 


\end{enumerate}
\end{document}
