\documentclass[twoside,12pt]{article}

\setlength{\textwidth}{6.5 in}
\setlength{\textheight}{8.5 in}
\setlength{\topmargin}{0 in}
\setlength{\headheight}{0.25 in}
\setlength{\headsep}{0.25 in}
\setlength{\evensidemargin}{0 in}
\setlength{\oddsidemargin}{0 in}
\setlength{\parskip}{1ex}

\newcommand{\heading}[1]{\vspace{3ex} {\Large {\em #1}}}
\newcommand{\subheading}[1]{\vspace{3ex} {\large {\em #1}}}

\usepackage{graphics}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{latexsym}

\newenvironment{comment}[1]{}{}
\newenvironment{proof}{\noindent {\em Proof.}}{$\Box$}

\newtheorem{theorem}{Theorem}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{claim}[theorem]{Claim}

\newcommand{\beqn}{\begin{eqnarray*}}
\newcommand{\eeqn}{\end{eqnarray*}}
\newcommand{\pr}[1]{\Pr\{#1\}}
\newcommand{\ex}[1]{\text{Ex} \left[ #1 \right] }

\begin{document}

\begin{center}
{\Large Notes for Tutorial 5} \\
6.042 - March 7 and March 10, 2003 \\
\bigskip
\end{center}

There are three topics.

\begin{itemize}
\item Address questions and concerns about the quiz.
\item Go over some examples of proofs and false proofs.
\item A bit about the relevance of logic notation.
\end{itemize}

For the first item, see the quiz solution set.  For the second, I've
put the problems on separate pages again, so you can photocopy and
distribute them if you want to.  Comments on the problems come after
all of them.  The third section has a couple easy problems that you
could put on the board.

\section{Proofs and False Proofs}

Challenge students to find the errors, if any, in the proofs on the
following pages.  Inevitably, they'll find many points of unclarity or
debatable validity beyond those intended.  Probably good to encourage
thoughtful discussion about those objections.

\newpage

\subsection{The Elephant and The Mouse}

\begin{theorem}
The weight of a mouse is equal to the weight of an elephant.
\end{theorem}

\begin{proof}
Let $m$ be the weight of a mouse, and let $e$ be the weight of an
elephant.  Let $v$ be the average of their weights; that is, let $v =
(m + e)/2$.  Now we reason as follows:

\begin{eqnarray}
2v & = & m + e \\
2v - m & = & e \\
m & = & 2v - e \\
(2v - m) m & = & (2v-e) e \\
2 v m - m^2 & = & 2 v e - e^2 \\
m^2 - 2 v m & = & e^2 - 2 v e \\
m^2 - 2 v m + v^2 & = & e^2 - 2 v e + v^2 \\
(m - v)^2 & = & (e - v)^2 \\
m - v & = & e - v \\
m & = & e
\end{eqnarray}

In the first step, we multiply both sides of the definition of $v$ by
2.  Equations 2 and 3 follow from equation 1 by rearranging terms.
Equation 4 is obtained by multiplying equations 2 and 3.  In equation
5, we expand both sides.  Negating both sides gives equation 6, and
adding $v^2$ to both sides gives equation 7.  The final steps are
simplification; we factor both sides, take square roots, and add $v$
to both sides.  We conclude that a mouse and an elephant weigh exactly
the same.
\end{proof}

\newpage

\subsection{An Inequality}

\begin{theorem}
For all nonnegative real numbers $a$ and $b$, the following inequality
holds:

\beqn
\sqrt{ab} & \leq & \frac{a + b}{2}
\eeqn
\end{theorem}

\begin{proof}
We reason as follows:

\beqn
\sqrt{ab} & \stackrel{?}{\leq} & \frac{a + b}{2} \\
2 \sqrt{ab} & \stackrel{?}{\leq} & a + b \\
4 a b & \stackrel{?}{\leq} & a^2 + 2 ab + b^2 \\
0 & \stackrel{?}{\leq} & a^2 - 2 a b + b^2 \\
0 & \leq & (a - b)^2
\eeqn

In the first step, we multiplied both sides by 2.  Then we square both
sides.  In the third step, we subtract $4ab$ from both sides.  Then we
rewrite the right side.  It is easy to see that the last inequality
holds, because the square of a real number cannot be negative.
\end{proof}

\newpage

\subsection{Roots}

\begin{theorem}
$1 = -1$
\end{theorem}

\begin{proof}
We transform the left side into the right as follows:

\setcounter{equation}{0}
\begin{eqnarray}
1	& = &	\sqrt{1} \\
	& = &	\sqrt{-1 \cdot -1} \\
	& = &	\sqrt{-1} \cdot \sqrt{-1} \\
	& = &	\left(\sqrt{-1}\right)^2 \\
	& = &	-1
\end{eqnarray}

All steps are elementary.
\end{proof}

\newpage

\subsection{Too Many Primes}

\begin{theorem}
There are infinitely many primes.
\end{theorem}

\begin{proof}
Suppose that the claim is false.  Then there exists some finite number
of primes $n$.  Call these primes $p_1, p_2, \ldots, p_n$.  Consider
the quantity $m = p_1 p_2 \cdots p_n + 1$.  Let $q$ be a prime factor
of $m$. (If $m$ is prime, then we can choose $q = m$.)  Then $q$ can
not be equal to $p_i$ for any $i$, since $q$ divides $m$ evenly, but
dividing $m$ by $p_i$ leaves a remainder of 1.  Therefore, $q$ is an
$(n+1)$-st prime, contradicting our supposition that there are only
$n$ primes.  Therefore, there are infinitely many primes.
\end{proof}

\newpage

\subsection{Four Men and a Boat}

Four castaways must escape from an island to the mainland on a
makeshift raft.  Their weights are 50, 100, 200, and 250.  The raft
can hold at most two people.  The number of minutes required to paddle
the raft between the island and the mainland is equal to the weight of
the heaviest passenger aboard.

Example: If 100 and 250 cross together, 250 minutes are used.  If 100
then returns alone, another 100 minutes are used.

\begin{claim}
It will take at least 650 minutes for all four castaways to escape.
\end{claim}

\begin{proof}
At least three trips and two return trips are required.  Since the
lightest person has weight 50, a minimum of 100 minutes are required
for the two return trips.  The three forward trips then require a
total of 550 minutes: 100 minutes for 50 and 100, 200 minutes for 50
and 200, and 250 minutes for 50 and 250.  Therefore, the total time
for all four people to cross is at least 100 + 550 = 650 minutes as
claimed.
\end{proof}

\newpage

% Commented out by Blaise because we are keeping this problem for later.
%
%\subsection{A Bag of Numbers}
%
%\begin{theorem}
%Suppose that a bag contains 25 slips of paper, each marked with an
%integer in the range 1 to a million.  Then there are two disjoint
%subsets of slips whose numbers have the same sum.
%\end{theorem}
%
%\begin{proof}
%There are $2^{25} - 1 \approx 32 \text{ million}$ different, nonempty
%subsets of slips.  The sum of the numbers on every subset is at most
%25 million.  Therefore some two subsets must have the same sum.  If
%these subsets are not disjoint, throw out the slips in common.  What
%remains are two disjoint subsets of slips whose numbers have the same
%sum.
%\end{proof}
%
%\newpage

\section{Comments on the Problems}

\subsection{The Elephant and the Mouse}

The error is the step from equation 8 to equation 9.  The fact that
$a^2 = b^2$ does not imply $a = b$.  It could be the case (and it is
here) that $a = -b$.

\subsection{An Inequality}

This ``proof'' is somewhere between rotten and wrong.  The problem is
that the argument works from the conclusion to a true assertion, and
not the other way around.  The fact that the assertion implies
something true does not mean that true things imply the assertion,
which is what you need to show.

Somewhere, a lot of students pick up this style of argument---
reasoning backward with ? over the relation until they get a true
statement.  If you find yourself doing this, pound your writing hand
several times with a heavy textbook to make it stop.  Maybe shout
``WRONG!  WRONG!'' with each blow.

Arguably, the proof is merely rotten, because in this case, the
argument can be run in reverse to give a valid proof of the
inequality.  (It is called the {\em arithmetic - geometric mean
inequality}, because one side is the arithmetic mean of $a$ and $b$
and the other side is the geometric mean).  But putting the steps in
the right order is the proof-writer's job.  A collection of cryptic
hints as to why the conclusion should be true is {\em not} a proof!

\subsection{Roots}

The error is in the step from equation 2 to equation 3.  The rule
$\sqrt{ab} = \sqrt{a} \cdot \sqrt{b}$ does not always hold when $a$
and $b$ are allowed to be negative.

\subsection{Too Many Primes}


This is a valid proof.  We showed that:

\beqn
\text{finitely many primes} & \implies & \text{false conclusion}
\eeqn

In order for this statement to be true, the hypothesis must be false;
that is, there cannot be finitely many primes.

This is a pretty common style of proof.  The general idea is that you
{\em assume} initially assume the negation of your proposition.  Then
you reason from that until you reach a false conclusion.  This implies
that your initial assumption was wrong, and thus your proposition was
true.  Rosen contains some examples of this as well; look in the index
under ``proof, by contradiction''.

\subsection{Four Men and a Boat}

This illustrates sloppy case analysis.  By not being systematic, we miss
the possibility that 10 makes a return trip.  Optimal:

\begin{center}
\begin{tabular}{lcr}
50, 100 cross, 100 returns &\hspace{0.75in}& 100 + 100 = 200 minutes \\
200, 250 cross, 50 returns && 250 + 50  = 300 minutes \\
50, 100 cross && 100 minutes \\ \hline
TOTAL  && 600 minutes
\end{tabular}
\end{center}

Intuitively, as long as we need 250 minutes to get the 250 guy across,
we might as well get the 200 guy across at the same time.

% Commented out by Blaise because we are keeping this exercise for later.
%
%\subsection{A Bag of Numbers}
%
%This is a valid proof that foreshadows the {\em pigeonhole principle}.
%You might just perform the experiment--- have each student write four
%or five numbers.  (Warn them to make them ``random''.)  Make the claim
%of the theorem.  Afterward, put the slips of paper out on the table,
%and challenge students to find the two disjoint subsets with the same
%sum.  While in principle they ought to be able to prove the claim for
%a specific set of numbers by construction, it is {\em very} hard.  And
%yet we know, by this nonconstructive proof, that it is true!

\section{Logic Manipulation}

The symbols $\wedge$, $\vee$, $\neg$, and so on may seem very
abstract.  However, you'll deal with equivalent symbols all the time
in programming lanuages such as C, C++, and Java.  Here is a
conversion table:

\begin{center}
\begin{tabular}{lcc}
and		& $p \wedge q$	&	$p\ \&\&\ q$ \\
or		& $p \vee q$	&	$p\ ||\ q$ \\
not		& $\neg p$	&	$!p$ \\
equivalence	& $p \leftrightarrow q$ &	$p == q$ \\
implication	& $p \rightarrow q$	& $!p\ ||\ q$
\end{tabular}
\end{center}

These programming languages lack a symbol for the implication
connective.  However, it turns out that:

\beqn
p \rightarrow q & = & \neg p \vee q
\eeqn

We can see this in the truth tables:

\[
\begin{array}{cccc}
p & q & p \rightarrow q & \neg p \vee q \\
F & F & T & T \\
F & T & T & T \\
T & F & F & F \\
T & T & T & T \\
\end{array}
\]

Therefore, we can write $p \rightarrow q$ in Java as $!p\ ||\ q$.

A common challenge while programming is writing complicated conditions
in a simple way.  This is equivalent to the problem of simplifying
propositions.  The same problem comes up when you're trying to
simplify a digital circuit.

Can you find nice or interesting ways to rewrite the following
expressions using traditional logic notation?

\begin{itemize}

\item $(p \wedge q) \vee (\neg q \wedge p) \vee (\neg p \wedge \neg q)$

\item $(r \wedge \neg p) \vee (r \wedge \neg q) \vee (\neg r \wedge p)
\vee (\neg r \wedge q)$

\end{itemize}

The first is just $\neg q \vee p$.

The second can be written in a million ways.  For example:

\[
(p \rightarrow q) \wedge (q \rightarrow r) \wedge (r \rightarrow p)
\]

\[
(p \wedge q \wedge r) \vee (\neg p \wedge \neg q \wedge \neg r)
\]

\end{document}
