\documentclass[11pt,twoside]{article}    
\usepackage{latex-macros/course}% !! use the macros 

%\backwardscompatibility        % !! use for backwards compatibility
%\showsolutions                 % !! use to force solutions & skip query
%\hidesolutions                 % !! use to force no solutions & skip query
%\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}

\begin{document} 
\inclassproblems{1}                    % !! start the paper

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{problem}
Generalize the proof from lecture (see Appendix) that $\sqrt{2}$ is
irrational, \eg how about $\sqrt[3]{2}$?

\solution{We prove that for any $n>1$, $\sqrt[n]{2}$ is irrational by
contradiction.

Assume that $\sqrt[n]{2}$ is rational.  Under this assumption, there
exist integers $a$ and $b$ with $\sqrt[n]{2} = a/b$, where $a$
and $b$ have no common factors (so that the fraction $a/b$ is in lowest
terms).  Now we prove that $a$ and $b$ are both even, which contradicts
the existence of $a,b$.
\begin{eqnarray*}
\sqrt[n]{2} & = & \frac{a}{b}\\
2 & = & \frac{a^{n}}{b^{n}}\\
2b^{n} & = & a^{n}.
\end{eqnarray*}
The lefthand side of the last equation is even, so $a^{n}$ is even.  This
implies that $a$ is even as well (see below for justification).

In particular, $a = 2c$ for some integer $c$.  Thus, 
\begin{eqnarray*}
2b^{n} & = & (2c)^n = 2^{n}c^{n},\\
b^{n} & = & 2^{n-1}c^{n}.
\end{eqnarray*}
Since $n-1>0$, the righthand side of the last equation is an even number,
so $b^{n}$ is even.  But this implies that $b$ must be even as well,
contradicting the fact that $m/n$ is in lowest terms.

\medskip
Now we justify the claim that if $a^n$ is even, so is $a$.

There is a simple proof by contradiction: suppose $a$ was not even, \ie
$a$ is odd.  It's a familiar (and easily verified) fact that the product
of \emph{any} number of odd numbers is odd, so $a^n$ would also be odd,
contradicting the fact that $a^n$ is even.

But more generally for \emph{any} integers $m,k >0$, if $m^k$ is divisible
by a prime number, $p$, then $m$ must be divisible by $p$.  This follows
from the factorization of an integer into primes (which we'll discuss
further in a coming lecture): the primes in the factorization of $m^k$ are
precisely the primes in the factorization of $m$ repeated $k$ times, so if
there is a $p$ in the factorization of $m^k$ it must be one of $k$ copies
of a $p$ in the factorization of $m$.

\begin{optional}
%From S99 Tutorial 1 Notes:

Here's a somewhat broader generalization of the proof that $\sqrt{2}$ is
irrational.

\begin{lemma*}
Let the coefficients of the polynomial
$a_0+a_1x+a_2x^2+\cdots + a_{n-1}x^{n-1} + x^n$ be
integers.  Then any real root of the polynomial is either integral or
irrational.
\end{lemma*}

Notice that this Lemma directly implies that $\sqrt{2}$ is irrational:
$x^2 - 2$ has no integer root because 2 is not a perfect square, so the
real roots, namely, $\pm\sqrt{2}$, must be irrational.  Similarly, if $m
\in \naturals$ is not the $k$th power of an integer, then $x^k - m$ has no
integer roots, so $\sqrt[k]{m}$ will be irrational.

\begin{proof}

Let $r\in \reals$ be a root of the polynomial, that is,
\[
a_0+a_1r+a_2r^2+\cdots+  a_{n-1}r^{n-1}+ r^n = 0.
\]
There are three cases for $r$: it is either integral, irrational, or the
ratio of two integers with no common divisors where the denominator is
greater than one.  We want to eliminate the last case.

So assume to the contrary that $r = s/t$ for integers $s$ and $t$ which
have no common divisors and such that $t >1$.  Now $t$ must have a prime
divisor, $p$.

Substituting $s/t$ for $r$ and multiplying both sides of the above
equation by $t^n$ yields:
\begin{eqnarray}
a_0t^n+a_1st^{n-1}+a_2s^2t^{n-2}+\cdots+a_{n-1}s^{n-1}t+s^n & = & 0,\\
a_0t^n+a_1st^{n-1}+a_2s^2t^{n-2}+\ldots+s^{n-1}t & = & -s^n.\label{e2}
\end{eqnarray}
Then $p$ divides each term of the lefthand side of equation~(\ref{e2}),
and therefore also divides the righthand side, viz., $p \divides -s^n$.
But this means that $p$ must also divide $s$.  So $p$ is a common divisor
of $s$ and $t$, contradicting our choice of $s$ and $t$.

\end{proof}

\end{optional}
}

\end{problem}

\iffalse

\begin{problem}
In some computer architectures, the basic computer operation is ``NAND'',
denoted~$\nand$, where $A \nand B$ means $\neg (A \conj B)$.  Show that
all the basic boolean operations can be defined solely in terms of the
NAND operation (and parentheses), \eg $\neg A$ can be defined as $A \nand
A$.

\begin{problemparts}

\problempart $A \disj B$
\solution{
       $(A \nand A) \nand (B \nand B)$
}

\problempart $A \conj B$
\solution{
  $(A \nand B) \nand (A \nand B)$ 
}

\problempart $A \implies B$
\solution{
  $A \nand (B \nand B)$
}
\end{problemparts}

\end{problem}
\fi

\begin{problem}  %source: spring00 ps1

Translate the parts of the following deductive arguments into
propositional logic notation using logical operators:
\begin{eqnarray*}
\conj & \eqdef & \text{AND},\\
\disj & \eqdef & \text{OR},\\
\neg & \eqdef & \text{NOT},\\
\implies & \eqdef & \text{IMPLIES},\\
\bicond & \eqdef & \text{IFF (if and only if)}
\end{eqnarray*}
This may require that you ``pin down'' a statement that could be
interpreted in more than one way.

Identify the antecedents and conclusions of the arguments, and determine
which are sound deductions and which are not.  If the deduction is
unsound, demonstrate a possible scenario in which all the antecedents hold
but the conclusion does not.

\textbf{Note:} There are several inequivalent, reasonable ways to
interpret several of these statements.

\begin{problemparts}

\iffalse
\problempart Jane and Pete won't both win the math prize.  Pete will win
either the math prize or the chemistry prize.  Jane will win the math
prize.  Thus, Pete will win the chemistry prize.

\solution{
The deduction is:
\Rule{\neg (J \conj M),\quad M \smor C, \quad J}{C}
where 
\begin{eqnarray*}
J & \eqdef & \mbox{``Jane will win the math prize.''} \\
M & \eqdef & \mbox{``Pete will win the math prize.''} \\
C & \eqdef & \mbox{``Pete will win the chemistry prize.''}
\end{eqnarray*}
This deduction is valid.  
}
\fi

\problempart The main course will be beef or fish.  The vegetable will be
peas or corn.  We will not have both fish as a main course and corn as
a vegetable.  Therefore, we will not have both beef as a main course
and peas as a vegetable.

\solution{
The deduction is:
\Rule{B \disj F, \quad C \disj P, \quad \neg (F \conj C)}{\neg (B \conj P)}
where 
\begin{eqnarray*}
        B  & \eqdef & \mbox{``The main course will be beef.''} \\
        F  & \eqdef & \mbox{``The main course will be fish.''} \\
        C  & \eqdef & \mbox{``The vegetable will be corn.''} \\
        P  & \eqdef & \mbox{``The vegetable will be peas.''} 
\end{eqnarray*}
This deduction is invalid.  For example, $B \conj \neg F \conj C \conj
P$ is consistent with the antecedents but not with the conclusion.  Note
that as formalized, there need not be only one main course and only
one vegetable; it is possible, for example, for the vegetable to be
both corn and peas, as in the scenario given.

If we wished to exclude the possibility of multiple courses we could have
used \emph{exclusive-or}, \cf Rosen, p.5, instead of inclusive-or.  So our
antecedent about the main course would then read $B \oplus F$ or,
equivalently, $(B \disj F) \conj \neg (B \conj F)$.  The antecedent about
the vegetable could be changed similarly.  The deduction is still invalid
with this formalization.}

\problempart Either John or Bill is telling the truth.  Either Sam or Bill
is lying.  Thus, either John is telling the truth or Sam is lying.

\solution{
We interpret ``John is lying,'' to be the negation of ``John is
telling the truth.''  Similarly for the corresponding propositions
involving Bill and Sam.  The deduction is:
\Rule{J \disj B, \quad \neg S \disj \neg B}{J \disj \neg S}
where
\begin{eqnarray*}
        J & \eqdef & \mbox{``John is telling the truth.''} \\
        B & \eqdef & \mbox{``Bill is telling the truth.''} \\
        S & \eqdef & \mbox{``Sam is telling the truth.''}
\end{eqnarray*}
This deduction is valid.  It is an example of a common ``cancellation'' or
\emph{cut} rule that lets us get rid of the proposition $B$ in the
conclusion.}

\problempart Either sales will go up and the boss will be happy, or expenses
will go up and the boss won't be happy.  Therefore, sales and expenses
will not both go up.

\solution{
The deduction is:
\Rule{(S \conj H) \disj (E \conj \neg H)}{\neg (S \conj E)}
where 
\begin{eqnarray*}
        S & \eqdef& \mbox{``Sales will go up.''} \\
        H & \eqdef& \mbox{``The boss will be happy.''} \\
        E & \eqdef& \mbox{``Expenses will go up.''} 
\end{eqnarray*}
This deduction is invalid.  For example, $S \conj E \conj H$ is consistent
with the antecedent but not with the conclusion.}

\end{problemparts}

\end{problem}

\instatements{\newpage}
\begin{problem}\label{sys}  Are the following
specifications\footnote{Rosen, Exercise 1.1.36} consistent?

\begin{enumerate}

\item If the file system is not locked, then

   \begin{enumerate}

   \item new messages will be queued.

   \item new messages will be sent to the messages buffer.

   \item the system is functioning normally, and conversely.

   \end{enumerate}

\item  If new messages are not queued, then they will be sent to
the messages buffer.

\item  New messages will not be sent to the message buffer.

\end{enumerate}

\bparts

\ppart Begin by translating the parts of the specification into
propositional formulas using four propositional variables:
\begin{eqnarray*}
L   & \eqdef &   \text{file system locked}, \\
Q   & \eqdef &   \text{new messages are queued}, \\
B   & \eqdef &   \text{new messages are sent to the message buffer}, \\
N   & \eqdef &   \text{system functioning normally}.
\end{eqnarray*}

\solution{
The translations of the specifications are:
\begin{align}
\neg L  \implies & Q & \tag{Spec.\ 1.(a)}\\
\neg L  \implies & B & \tag{Spec.\ 1.(b)}\\
\neg L  \bicond  & N & \tag{Spec.\ 1.(c)}\\
\neg Q  \implies & B & \tag{Spec.\ 2.}\\
\neg B           &   & \tag{Spec.\ 3.}
\end{align}}

\ppart The specification is consistent if there is an assignment of truth
values to the variables that makes every expression true.  \emph{Use a
truth table} to determine whether the specification is consistent.

\solution{ We can construct a truth table with sixteen lines---one for
each way of assigning truth values to the four variables $L$, $N$, $Q$,
and $B$.  For each line, we could record the truth values of these five
statements above.

If all five statements are true for some assignment of truth values to the
variables, then the system is consistent.  If for every one of the
sixteen possible truth assignments, at least one of the five statements
is false, then the system is inconsistent.  Carrying out the calculation
shows that there is a unique assignment of True/False values to $L$, $N$,
$Q$, and $B$ (see below) that satisfies all the specifications.}

\ppart Use \emph{simple reasoning by cases} to find a truth assignment
that confirms that this system specification is consistent.  Explain why
there is only one such assignment.

\solution{
We can avoid the full truthtable calculation if we reason by
cases.

\textbf{Case 1} ($B$ is True):  Then the last formula, (Spec.\ 3.), is false,
and the whole specification is false.

\textbf{Case 2} ($B$ is False): Now (Spec.\ 2.) and (Spec.\ 1.(b)) can be
true only if $Q$ and $L$ are true.  Since $L$ is true, (Spec.\ 1.(c)) can
be true only if $N$ is false.  Thus, we have deduced that in order to be
consistent, we must have
\begin{eqnarray*}
L       & = &   \text{True} \\
N       & = &   \text{False} \\
Q       & = &   \text{True} \\
B       & = &   \text{False}.
\end{eqnarray*}

From the way this assignment was constructed, we know it ensures that
formulas from (Spec.\ 1.(b)) on are true.  So all that remains is to check
formula (Spec.\ 1.(a)), and indeed it is also true under this assignment.

So the system is consistent, and this is the only assignment that will
satisfy it.}

\eparts
\end{problem}

\begin{problem} %S00, ps1.6

Consider the following theorem: Suppose $x$ is a real number
and $\dfrac{2x-5}{x-4}=3$ then $x=7$.

What is wrong with the following proof?
\begin{falseproof}
Suppose $x=7$.  Then
\[
\frac{2x-5}{x-4}=\frac{2(7)-5}{7-4}=\frac{9}{3}=3.
\]
Thus, if $\dfrac{2x-5}{x-4}=3$ then $x=7$.
\end{falseproof}

\solution{This proof is a typical example of circular reasoning.  We
suppose $x=7$ and then conclude that $x=7$.

In particular, the proof can be understood as having the form:
\Rule{Q, \quad P}{Q \implies P}
or equally well the form:
\Rule{Q,\quad P}{P}
where
\begin{eqnarray}
P &\eqdef& \paren{x=7},\\
Q &\eqdef& \paren{\frac{2x-5}{x-4}=3}.
\end{eqnarray}
But the antecedent, $P$, shouldn't be there.  What's needed is a proof
of the form
\Rule{Q}{P}.

The calculation in the proof does demonstrate that $P \implies Q$ is
true.}

\iffalse

\problempart Give a correct proof of this theorem.

\solution{
There are many ways to properly construct this proof.  We demonstrate a direct
proof using \emph{modus ponens}.

\begin{center}
\begin{tabular}{l}
        $Q(x)$ \\
        $Q(x) \implies P(x)$ \\ \hline
        $\therefore P(x)$
\end{tabular}
\quad where 
\begin{tabular}{l}
        $P(x) \;\; \equiv \;\; x=7$ \\
        $Q(x) \;\; \equiv \;\; \frac{2x-5}{x-4}=3$ \\
\end{tabular}
\end{center}
Proposition $Q(x)$ is given.  To complete the proof, we must now show that the
second premise (the implication) is a tautology.  
We do this using basic algebra and arithmetic:
\begin{align*}
Q(x) \equiv \frac{2x-5}{x-4} = 3 \;\;
        & \:\Longrightarrow \;\; 2x-5 = 3(x-4) \\ 
        & \Longleftrightarrow \;\; 2x-5 = 3x-12 \\
        & \Longleftrightarrow \;\; -5+12 = 3x-2x \\
        & \Longleftrightarrow \;\; 7 = x                &\equiv P(x) 
\end{align*}
}
\end{problemparts}
\fi

\end{problem}

\iffalse

\begin{problem}   %source: spring00 ps1.7
Suppose $x$ is a real number.  Prove \textbf{by cases}
that there is a real $y$ such that $\dfrac{y+1}{y-2}=x$ if and only if $x
\ne 1$.

\solution{
We consider the cases $x \neq 1$ and $x = 1$ separately. 
\begin{description}

\item[Case 1: $x \neq 1$]
We need to prove that there exists $y \in \reals$ such that
$\dfrac{y+1}{y-2}=x$.  In particular, consider $y = \dfrac{2x+1}{x-1}$ (derived
by algebraic manipulation), which is a well-defined real number because $x \neq
1$.  Then:  
\begin{eqnarray*}
\frac{y+1}{y-2}  & = & \frac{((2x+1)/(x-1))+1}{((2x+1)/(x-1))-2} \\
        & = & \frac{\dfrac{2x+1 + (x-1)}{x-1}}{\dfrac{2x+1-2(x-1)}{x-1}}\\
        & = & \frac{\dfrac{3x}{x-1}}{\dfrac{2x+1-2x+2}{x-1}}\\
        & = & \frac{3x}{3}\\
        & = & x.
\end{eqnarray*}

Therefore, (by the inference rule called \emph{existential
generalization}) $\exists y \in \reals$ such that $\dfrac{y+1}{y-2} = x.$

\item[Case 2: $x = 1$]
We need to prove that no $y \in \reals$ exists such that $\dfrac{y+1}{y-2}=x$. 
Suppose, for contradiction, that such a $y$ did exist.  Then:
\begin{align*}
\frac{y+1}{y-2} = x 
        &\equivalent \;\; \frac{y+1}{y-2} = 1 
                & \text{(because $x = 1$)} \\
        &\:\implies \;\; y+1 = y-2 
                & \text{(multiply both sides by $y-2$)} \\
        &\equivalent \;\; 1 = -2 
                & \text{(subtract $y$ from both sides)},
\end{align*}
a contradiction.  Therefore our supposition is wrong, 
and there is no $y$ such that $\dfrac{y+1}{y-2}=x$. 

\end{description}
}
\end{problem}
\fi

\instatements{\newpage}
\begin{problem}
Albert \& Eric announce that they plan a surprise 6.042 quiz next week.
Their students wonder if the quiz could be next Friday.  The students
realize that it obviously cannot, because if it hadn't been given before
Friday, everyone would know that there was only Friday left on which to
give it, so it wouldn't be a surprise any more.

So the students ask whether Albert \& Eric could give the surprise quiz
Thursday?  They observe that if the quiz wasn't given \emph{before}
Thursday, it would have to be given \emph{on} the Thursday, since they
already know it can't be given on Friday.  But having figured that out, it
wouldn't be a surprise if the quiz was on Thursday either.  Similarly, the
students reason that the quiz can't be on Wednesday, Tuesday, or Monday.
Namely, it's impossible for Albert \& Eric to give a surprise quiz next
week.  All the students now relax having concluded that Albert \& Eric
must have been bluffing.

And since no one expects the quiz, that's why, when Albert \& Eric give
it on Tuesday next week, it really is a surprise!

What do you think is wrong with the students' reasoning?  Can you fix it?

\solution{The basic problem is that ``surprise'' is not a mathematical
concept, nor is there any sure, clear way to give it a mathematical
definition.  The ``proof'' above assumes some plausible axioms about
surprise, whatever that is, and the paradox is that these axioms are
inconsistent.  But that's no surprise \texttt{:-)}, since we don't know
what we're talking about.

Mathematicians and philosophers have had a lot more to say about what
might be wrong with the students' reasoning, (see Chow, Timothy Y.
\href{http://theory.lcs.mit.edu/classes/6.042/spring02/handouts/surprise-paradox.pdf} 
{\emph{The surprise examination or unexpected hanging paradox}}, American
Math. Monthly (January 1998), pp.41--51.)}

\end{problem}

\section*{Appendix}

\begin{theorem*}
$\sqrt{2}$ is an irrational number.
\end{theorem*}

Remember that an irrational number is a number that can not be
expressed as a ratio of two integers.

\begin{proof}
The proof is by contradiction.  Assume for purpose of contradiction that
$\sqrt{2}$ is rational.

Then we can write $\sqrt{2} = m/n$ where $m$ and $n$ are integers and the
fraction is in lowest terms.  Squaring both sides gives $2 = m^2 / n^2$,
so $2 n^2 = m^2$.  This implies that $m^2$ is even, and hence that $m$ is
even; that is, $m$ is a multiple of $2$.  But that means $m^2$ is actually
a multiple of 4, say $m^2 = 4k$.

Now we have $2 n^2 = m^2 = 4k$, so $n^2 = 2k$.  So $n^2$ is even, and
hence $n$ is even. But since $m$ and $n$ are both even, the fraction $m/n$
is not in lowest terms, a contradiction.
\end{proof}

\end{document}
