\newcommand{\ig}[1]{}

\documentclass[12pt,letterpaper]{article}

\usepackage{epsfig}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{fullpage}

\title{Week 5 Recitation}
\author{Robert Woodward}

\begin{document}
\maketitle

\begin{itemize}
\item (3 min max) Go over quiz from last week
\item (3 min max) Go over homework from last week.
\item Questions about lecture / homework so far?

\item
1.6:23) Show that at least 10 of any 64 days chosen must fall on the
same day of the week.
\begin{itemize}
\item
We proceed with a proof by contradiction.

\item
We assume that it is not the case that ``at least 10 days of any 64
days chosen fall on the same day of the week.''

\item
This means that ``less than 10 days of any 64 days chosen fall on the
same day of the week.'' Assume, it is 9 days.  Then we have ``9 days
of any 64 days chosen fall on the same day of the week.''


\item
There are 7 days in a week.  If we choose 9 days out of every day of
the week, then we have chosen 9$\times$ 7days = 63 days, exactly.

\item
However, we need to choose 64 days.  Therefore, there is one extra day
that needs to be chosen.  Whichever day we choose, this choice will
bump up the `count' of chosen days to 10, which contradicts the
statement ``9 days of any 64 days chosen fall on the same day of the
week.''

\item
Therefore, at least 10 of any 64 days chosen must fall on the same day
of the week.
\end{itemize}

\item
Example from: http://marauder.millersville.edu/~bikenaga/mathproof/rules-of-inference/rules-of-inference.html

Given:
\begin{enumerate}
\item
$p \land q$
\item
$p \rightarrow \lnot(q \land r)$
\item
$s \rightarrow r$
\end{enumerate}
Prove $\lnot s$ using the rules of inference.

\begin{tabular}{rll}
    & {\bf Step} & {\bf Reason} \\
1. & $p \land q$ & Premise \\
2. & $p \rightarrow \lnot(q \land r)$ & Premise \\
3. & $s \rightarrow r$ & Premise \\
4. & $p$ & Simplification of (1) \\
5. & $q$ & Simplification of (1) \\
6. & $\lnot(q \land r)$ & Modus Ponens (2) and (4) \\
7. & $\lnot q \lor \lnot r$ & DeMorgan's Law (6) \\
8. & $\lnot r$ & Disjunctive syllogism (5) and (7) \\
9. & $\lnot s$ & Modus Tollens (3) and (8)
\end{tabular}

\item
1.5:15a) Given
\begin{enumerate}
\item
All students in this class understand logic.
\item
Xavier is a
student in this class.
\end{enumerate}
Prove that, Xavier understands logic.

\begin{itemize}
\item Define your predicates:
\begin{itemize}
\item
$Q(x)$: $x$ is in the class
\item
$P(x)$: $x$ understands logic
\end{itemize}
\item
Universe of Discourse: All students
\item
Theory:
\begin{enumerate}
\item $\forall x P(x) \rightarrow Q(x)$
\item $P(Xavier)$
\end{enumerate}
\item
We want to prove : $Q(Xavier)$
\item  Proof:\\
\begin{tabular}{rll}
    & {\bf Step} & {\bf Reason} \\
1. & $\forall x P(x) \rightarrow Q(x)$ & Premise \\
2. & $P(Xavier)$ & Premise \\
3. & $P(Xavier) \rightarrow Q(Xavier)$ & Universal instantiation from (1) \\
4. & $Q(Xavier)$ & Modus ponens from (2) and (3)
\end{tabular}
\end{itemize}


\item
1.6:27) Prove that for every $n$ a positive integer, $n$ is odd {\em
if and only if} $5n + 6$ is odd.

\paragraph{$\Rightarrow$} First, we prove: $n$ is odd  $\Rightarrow$ $5n+6$ is odd

\begin{enumerate}
\item
$n$ is odd  $\Rightarrow$ $n = 2k + 1$ \hfill{\em by definition} 

\item

Plugging in the value of $n$ into $5n + 6$, $5n + 6 = 5(2k + 1) + 6 =
10 k + 5 + 6 = 10 k + 11 = 2(5k + 2) + 1 = 2k'+1$

\item
Therefore, $5n + 6$ is odd. \hfill{$\Box$} 
\end{enumerate}


\paragraph{$\Leftarrow$} Next we prove: $5n + 6$ odd $\Rightarrow$ $n$ is odd.  We use a proof by contrapositive and establish that 
``$n$ is even $\Rightarrow$ $5n + 6$ even.''
\begin{enumerate}
\item $n$ is even $\Rightarrow$ $n = 2k$  \hfill{\em by definition} 

\item
Plugging in the value of $n$ into $5n + 6 = 5(2k) + 6 = 10k + 6 = 2(5k
+ 3)= 2k'$ 

\item
Therefore, $5n + 6$ is even. \hfill{$\Box$} 
\end{enumerate}

Therefore, $n$ is odd iff $5n + 6$ is odd.   \hfill{$\Box$} 

\item (Last 12 minutes) Give quiz

\end{itemize}

\end{document}