\documentclass[11pt,twoside]{article}	
\usepackage{latex-macros/course}
\usepackage{textcomp} % to get \textcent

\newcommand{\cent}{\text{\textcent}}

\renewcommand{\reading}{
\href{http://theory.lcs.mit.edu/classes/6.042/fall02/courseinfo}{Course
Overview \& Guide},
\href{http://theory.lcs.mit.edu/classes/6.042/fall02/objectives}{CourseObjectives and Outcomes},
\href{http://theory.lcs.mit.edu/classes/6.042/fall02/handouts/lectures/ln1.pdf}{Week
1 Notes}, Rosen \S\S 1.1--6; \S2.3; \S2.4 through Lemma 1; \S3.1 through
Example 26.

There is an unusually large amount of reading for this first problem set.
We expect that most of the reading in Rosen will be review, and you should
quickly skim material you are already familiar with.  However, you should
also note any important definitions and facts which seem unfamiliar and
then \emph{send email} not later than \textbf{11am next Monday} to
\begin{center}
                  \texttt{6042-probs@theory.lcs.mit.edu}
\end{center}
briefly indicating the names \emph{and page numbers} of the unfamiliar
material.

There are also a larger than usual number of problems on this problem set.
They are intended to be easy and short while highlighting the key material
in the reading.  We don't want you to spend more than five (5) hours on
this first assignment, including the reading.  Try to do most of the
problems, but don't worry if you run out of time to complete them all;
this first problem set will be graded very generously.
}

\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}

%\hidesolutions
%\showsolutions

\begin{document}
\problemset{1}

\begin{problem}
Identify exactly where the bugs are in each of the following false
proofs.

\begin{problemparts}

\problempart
\footnote{
Stueben, Michael and Diane Sandford. \emph{Twenty Years Before the
Blackboard}, Math. Assoc America, \copyright 1998, p.??.}
\begin{align*}
    3 &> 2 \\
    3 \log_{10} (1/2) &> 2 \log_{10}(1/2) \\
    \log_{10} (1/2)^3 &> \log_{10} (1/2)^2 \\
    (1/2)^3 &> (1/2)^2 \\
    \mbox{Therefore, }&
\end{align*}
\begin{falsethm}
\[
1/8 > 1/4.
\]
\end{falsethm}

\solution{$\log x < 0$, for $0<x<1$, so since both sides of the inequality
``$3 > 2$'' are being multiplied by the negative quantity
$\log_{10}(1/2)$, the ``$>$'' in the second line should have been
``$<$.''}

\problempart You are richer than you think:\footnote{Stueben, Michael and
Diane Sandford. \emph{ibid, p.27.}}

\begin{falsethm}
\[1 \cent = \$0.01 = (\$0.1)^2 = (10\cent)^2 = 100\cent = \$1.\]
\end{falsethm}

\solution{$\$0.01 = \$(0.1)^2 \neq (\$0.1)^2$ because the units $\$^2$ and
$\$$ don't match (just as in physics the difference between $sec^2$ and
$sec$ indicates the difference between acceleration and velocity).
Similarly, $(10\cent)^2 \neq 100\cent$.
}

%S00 ps1 circular reasoning false proof

\problempart

\begin{theorem}\label{f7}
If $x$ is a real number and $(2x-5)/(x-4)=3$, then $x=7$.
\end{theorem}

\begin{falseproof}
Suppose $x=7$.  Then
\[
\frac{2x-5}{x-4}=\frac{2(7)-5}{7-4}=\frac{9}{3}=3.
\]
Thus, if $(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$.  So, all we have done is not
contradict our supposition.  Unlike a proof by contradiction, which shows
our assumption is false, {\em not} arriving a contradiction does {\em not}
show our assumption is true.

In particular, the proof is of the form:
\Rule{P(x), \quad (P(x) \implies Q(x))}{Q(x) \implies P(x)}
where 
\begin{eqnarray*}
        P(x) & \eqdef & x=7,\\
        Q(x) & \eqdef & \frac{2x-5}{x-4}=3
\end{eqnarray*}
The given ``proof'' does demonstrate that the second premise is true.  
However, the conclusion does not follow.
}

\end{problemparts}
\end{problem}

\iffalse

\begin{problem}Give a correct proof of this Theorem~\ref{f7}.

\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{problem}
\fi

\begin{problem}
Rosen, Ex 1.2.8(b)

\solution {

We construct a truth table for each implication and note that the column for
the whole proposition contains only T's.  The truth value for each
sub-proposition is shown directly below the highest-level logical connective in
that expression.  The numbers at the bottom of each column show the order in
which the table is constructed.  Since $p,q$, and $r$ are given, the values are
filled in in step 0.  In step 1, we compute the values for the propositions $p
\rightarrow q$, $q \rightarrow r$, and $p \rightarrow r$. In step 2, we compute
the truth values for the proposition that has $\land$ as its highest-level
connective.  Finally, in step 3, we compute the truth values for the whole
expression.  Note, only the columns in \textbf{boldface} need appear in the
final table.

\begin{tabular}{cccccccccccccc}
  $p$&$q$&$r$&$[(p$&$\rightarrow$&$q)$&$\land$&$(q$&$\rightarrow$&$r)]$&$\rightarrow$&$(p$&$\rightarrow$ &$r)$\\
\textbf{T} & \textbf{T} & \textbf{T} && T && T && T && \textbf{T} && T\\
\textbf{T} & \textbf{T} & \textbf{F} && T && F && F && \textbf{T} && F\\
\textbf{T} & \textbf{F} & \textbf{T} && F && F && T && \textbf{T} && T\\
\textbf{T} & \textbf{F} & \textbf{F} && F && F && T && \textbf{T} && F\\
\textbf{F} & \textbf{T} & \textbf{T} && T && T && T && \textbf{T} && T\\
\textbf{F} & \textbf{T} & \textbf{F} && T && F && F && \textbf{T} && T\\
\textbf{F} & \textbf{F} & \textbf{T} && T && T && T && \textbf{T} && T\\
\textbf{F} & \textbf{F} & \textbf{F} && T && T && T && \textbf{T} && T\\
\textbf{0} & \textbf{0} & \textbf{0} && 1 && 2 && 1 && \textbf{3} && 1\\
\end{tabular}	
}
\end{problem}

\begin{problem}
Rosen, Ex 1.3.14(a,f,n,h)

\solution{ 
The answers to this exercise are not unique; there are many
ways of expressing the same propositions symbolically.  Note that $C(x,y)$
and $C(y,x)$ are equivalent.

%FORMAT USING align WITH \tag{a)}, tag{f)},...

a) $\lnot I(\textrm{Jerry})$

f) $\exists x \lnot I(x)$

n) $\exists x \exists y (x \neq y \land \forall z \lnot (C(x,z) \land C(y,z)))$

h) $\exists x \forall y (x=y \leftrightarrow I(y))$
}
\end{problem}

\begin{problem}
Rosen, Ex 1.4.14  %powerset

\solution{ The union of all the sets in the power set of a set $X$ must be
exactly $X$.  In other words, we can unambiguously recover $X$ from its
power set.  Therefore the answer is yes.  }
\end{problem}

\begin{problem}
Rosen, Ex 1.5.26 %Set-theory identity 

\solution{ 
There are precisely two ways that an element can be in
either $A$ or $B$ but not both.  It can be in $A$ but not in $B$,
which is equivalent to saying that it is in $A - B$.  Or it can be in
$B$ but not in $A$, which is equivalent to saying that it is in $B -
A$.  Therefore, an element is in $A \bigoplus B$ if and only if it
is in $(A-B)\union (B-A)$.
}
\end{problem}

\begin{problem}
Rosen, Ex 1.6.12  %create 1-1, onto examples

\solution{
a) $f(n)=n+17$

b) $f(n)=\lceil n/2 \rceil$

c) We let $f(n)=n-1$ whenever $n$ is even and $f(n)=n+1$ whenever $n$
is odd.  Thus we have $f(1)=2$,$f(2)=1$,$f(3)=4$,$f(4)=3$, and so on.
Note that $f$ is just one function, even though its definition uses
two formulas, depending on the parity of $n$.

d) $f(n) = 17$
}
\end{problem}

\begin{problem}
Prove that
\[
\gcd(a,b) = \gcd(b,a-b)
\]
for all $a,b \in \integers$.
\hint See Rosen, \S2.4 Lemma 1.

\solution {We show that the common divisors of $a$ and $b$ are the same
as the common divisors of $b$, $a-b$; then the result follows, since if
all of the common divisors of these two pairs are the same, so are the
greatest common divisors.

So suppose $d$ divides both $a$ and $b$.  Then $d$ also divides $a - b$,
and hence $d$ is a common divisor of $b$ and $a-b$.  Conversely, assume
$d$ divides both $b$ and $b-a$.  Then it divides $b - (a - b) = a$.  Hence
$d$ divides both $a$ and $b$ as required.  This shows that any common
divisor of $a$ and $b$ is a common divisor of $b$ and $a-b$ and vice
versa, hence completing the proof.}
\end{problem}

\begin{problem}
Rosen, Ex 3.1.18(b)  %odd/even proof by contradiction

\solution{ Suppose that $3n+2$ is even and that $n$ is odd.  Since $3n+2$
is even, so is $3n$.  Subtracting an odd number from an even number yields
an odd number, so we conclude that $2n = 3n-n$ is odd.  Since $2n$ clearly
cannot be odd, we have reached a contradiction.  Hence our supposition was
wrong, and the proof is now complete.  }
\end{problem}

\end{document}                            
