\newcommand{\ig}[1]{}

\documentclass[12pt,letterpaper]{article}

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

\title{Recitation 4}
\author{Created by Taylor Spangler, Adapted by Beau Christ}
\date{\today}

\begin{document}
\maketitle

\begin{itemize}
\ig{\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.7: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
First, for the purposes of contradiction, 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
So ``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 Now a similar example: let's look at problem 1.7:27. Show that, given a positive integer $n$, then $n$ is odd if and only if (iff) $5n+6$ is odd.
\begin{itemize}
\item First we prove the $\rightarrow$ direction.
\begin{enumerate}
\item Let $n$ be a positive integer that is odd. So $n$ can be written $2k+1$ for some integer $k \geq 0$. So $5n+6 = 5\times (2k+1) + 6$.
\item This is $10k+5+6 = 10k + 11$
\item This can again be rewritten $2(5k+5)+1$
\item We can then substitute $b$ for $5k+5$, since we know $5k+5$ is still a positive integer.
\item So $5n+6$ = $2b+1$...clearly $2b+1$ has the form of an odd number.
\item So $5n+6$ is odd \hfill{$\Box$} 
\end{enumerate}
\item Now let's prove the $\leftarrow$ direction.
\begin{enumerate}
\item For the purposes of a contrapositive, let's assume that if $n$ is even, then $5n+6$ is even.
\item So, let $n$ = $2k$ for some positive integer $k$ \hfill{\emph{by definition}} (note this is $\neg p$.
\item Then $(5\times 2k) + 6 = 10k+6$.
\item But we can see that this is even, and can be rewritten $2(5k+3) = 2(b)$ for some positive integer $b$.
\item So $5n+6 = 2b$ ($\neg q$).
\item So if $n$ is even $5n+6$ is even. 
\item By contraposition, if $5n+6$ is odd, $n$ is odd. \hfill{$\Box$} 
\end{enumerate}
\end{itemize}

\item
1.6: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 Now problem 1.6:19 Determine whether the following argument is valid. If so, what rule of inference is being used, if not what logical error occurs:\\
b) If $n$ is a real number with $n \geq 3$, then $n^{2} \geq 9$. Suppose $n^{2} \leq 9$ then $n \leq 3$.
\begin{enumerate}
\item Is this true? Yes
\item Is this a valid argument? Yes, using the rule of inference \textit{modus tollence}.
\end{enumerate} 
c) If $n$ is a real number with $n \geq 2$, then $n^{2} \geq 4$. Suppose $n \leq 2$ then $n^{2} \leq 4$.
\begin{enumerate}
\item Is this a valid argument? No this is denying the hypothesis
\end{enumerate}

\item What rules of inference are used in Lewis Carroll's poem from example 26 in 1.4.
\begin{itemize}
\item
\begin{enumerate}
\item All lions are fierce.
\item Some lions do not drink coffee
\item Some fierce creatures do not drink coffee.
\end{enumerate}
\item By the second premise, we have that there is a lion that does not drink coffee, let that lion be \emph{Leo}.
\item Using \emph{simplification} we can tell that Leo is a lion.
\item Now using \emph{modus ponens} on the first premise we know that Leo is fierce.
\item So Leo is fierce and does not drink coffee
\item Now using existential generalization, we can say that there exists a creature that is fierce, and does not drink coffee.
\end{itemize}

\end{itemize}

\end{document}
