\documentclass[11pt, twoside]{article}

\input{macros-course}

\newcommand{\nand}{|}
\newcommand{\implies}{\longrightarrow}

\begin{document}
\pset{1}{February 1, 2000}{2:35pm in lecture, February 8, 2000}

\textbf{Background Reading:} Introduction and Chapter 1 of Velleman's
\textit{How to Prove It}. (For a different perspective: Sections
1.1--1.2, 1.4--1.5, and 2.3 of Rosen's \textit{Discrete Mathematics
  and Its Applications}.)

\textbf{Reading:} All of Chapters 2 and 3 and Sections 6.1--6.3 of
Velleman's \textit{How to Prove It}.  Skip the examples on relations
and partial orders in Section 6.2; we will get to them in a few
weeks.  (For a different perspective: Sections 1.3 and 3.1--3.3 of
Rosen's \textit{Discrete Mathematics and Its Applications}.)

The reading assignment for this problem set is about 150 pages---an
awful lot even by 6.042J/18.062J standards \texttt{:-)}.  Much of
this, especially the background reading, reviews elementary
mathematical topics that should be familiar to you; you can skim
these.  Do look more closely at any topics that seem unfamiliar, and
if there are many such topics, we encourage you to discuss this with
your TA so he can help you plan a catch-up strategy.

\medskip


{\bf Remember} to include a \emph{collaboration statement} on the
front page of your solutions.  
(See Handout 2, \emph{Course Information}.)


The following exercises are {\bf optional;} do them if you think you
need the practice.

\begin{enumerate}

\item Exercises from Velleman: 1.1.3 (that is, exercise 3 in section
  1.1), 1.2.7, 2.1.1, 2.1.3.

\item Exercises from Rosen (answers in the back of the book): Section
  1.1, numbers 1, 3, 5, 7, 15, 17, 19, 21, 23, Section 1.2, numbers 5,
  7, 11, 13, 15, 17.  Section 1.3, numbers 5, 7, 9.

\end{enumerate}

The following problems are {\bf required.}

\begin{problems}
\problem In some computer architectures, the basic computer operation
is ``NAND'', denoted $\nand$, where $A \nand B$ means $\neg (A \wedge
B)$.  Show that all the basic boolean operations can be implemented
using the single $\nand$ operation.  That is, rewrite each of the
following formulas as equivalent formulas using only the $\nand$
operator (and parentheses).
\begin{problemparts}
\ppart $\neg A$
\ppart $A \vee B$
\ppart $A \wedge B$
\ppart $A \implies B$
\end{problemparts}



\problem Identify the premises and conclusions of the following
deductive arguments and analyze their logical forms.  This may require
that you ``pin down'' a statement that could be interpreted many ways.
Determine which are valid deductions and which are not.  If the
deduction is invalid, demonstrate a possible scenario in which the all
the premises are met but the conclusion is not.

\emph{Example:} If Alice is tall then she can reach the top shelf.  Alice is
not tall. Therefore, Alice cannot reach the top shelf.

\emph{Solution:} The proposed deduction can written as a theorem
(with the premises above the line and the conclusions below).
\vspace{-1ex}
\begin{center}
\begin{tabular}{l}
        $ T \implies R$ \\
        $ \neg T$ \\ \hline
        $\therefore \neg R$
\end{tabular}
\quad where 
\begin{tabular}{l}
        $T = \mbox{``Alice is tall.''}$ \\
        $R = \mbox{``Alice can reach the top shelf.''}$
\end{tabular}
\end{center}
\vspace{-1ex}
This deduction is invalid.  For example, $\neg T \wedge R$ is consistent with
the premises but not the conclusion.
%For example, given the statements, ``If Alice is tall then she can reach the
%top shelf.  Alice is not tall. Therefore, Alice cannot reach the top shelf.''
%Let $T$ be the proposition that Alice is tall.  Let $R$ be the proposition that
%Alice can reach the top shelf.  The proposed deduction can written as a theorem
%(with the premises above the line and the conclusions below).
%\begin{center}
%\begin{tabular}{l}
%       $ T \implies R$ \\
%       $ \neg T$ \\ \hline
%       $\therefore \neg R$
%\end{tabular}
%\end{center}
%This deduction is invalid.  For example, $\neg T \wedge R$ is consistent with
%the premises but not the conclusion.

\begin{problemparts}
\ppart 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.
\ppart 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.
\ppart 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.
\ppart 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.
\ppart If the tax rate and unemployment both go up then there will be
a recession.  If the GNP goes up there will not be a recession.  GNP
and taxes are both going up.  Therefore, there will not be a
recession.
\end{problemparts}

\problem Let $F(x,y)$ be the predicate ``$x$ can fool $y$'' and the
universe of discourse be the set of all people.  Use quantifiers to
express the following statements.
\begin{problemparts}
\ppart Everybody can fool Fred.
\ppart Evelyn can fool everybody.
\ppart Everybody can fool somebody.
\ppart No one can fool everybody.
\ppart Everybody can be fooled by somebody.
\ppart Nancy can fool exactly two people. (Do not introduce any
notation about numbers; use only quantifiers and (in)equality.)
\ppart There is exactly one person whom everybody can fool.
\ppart There is someone who can fool exactly one person besides him- or
herself.
\end{problemparts}

\problem Are these statements true or false?  The universe of
discourse is the natural numbers.  
(The set of natural numbers is $\{0,1,2, \ldots\}$.)
\begin{problemparts}
\ppart $\forall x \exists y (2x-y=0)$
\ppart $\exists y \forall x (2x-y=0)$
%\ppart $\forall x \exists y (x-2y=0)$
\ppart $\forall x (x < 10 \implies \forall y (y < x \implies y < 9))$
%\ppart $\exists y \exists z (y+z=100)$
\ppart $\forall x \exists y (y > x \wedge \exists z (y+z=100))$
\end{problemparts}

\problem \mbox{}
\begin{problemparts} 

\ppart
Show that $\forall x P(x) \vee \forall x Q(x)$ is not logically
equivelent to $\forall x (P(x) \vee Q(x))$.

\ppart 
Show that $\exists x (P(x) \implies Q(x))$ is logically equivalent to
$\forall x P(x) \implies \exists x Q(x)$.

\end{problemparts}

\problem Consider the following theorem: Suppose $x$ is a real number
and $\frac{2x-5}{x-4}=3$ then $x=7$.
\begin{problemparts}
\ppart What is wrong with the following proof? Suppose $x=7$.  Then
\[
\frac{2x-5}{x-4}=\frac{2(7)-5}{7-4}=\frac{9}{3}=3.
\]
Thus, if $\frac{2x-5}{x-4}=3$ then $x=7$.
\ppart Give a correct proof of this theorem.
\end{problemparts}

\problem Suppose $x$ is a real number.  Prove {\bf by cases} that there is a
real $y$ such that $\frac{y+1}{y-2}=x$ if and only if $x \ne 1$.

\problem Consider the following incorrect theorem:  If $\forall x \in
A (x \ne 0)$ and $A \subseteq B$ then $\forall x \in B (x \ne 0)$.
\begin{problemparts}
\ppart What is wrong with the following proof of the theorem? Let $x$
be an arbitrary element of $A$.  Since $\forall x \in A(x \ne 0)$ we can
conclude $x \ne 0$.  Also, since $A \subseteq B$ we have $x \in B$.
Since $x \in B$, $x \ne 0$, and $x $ was arbitrary, we can conclude
(by universal generalization) that $\forall x \in B (x \ne 0)$.
\ppart Give a counterexample to the theorem.
\end{problemparts}


\problem
Find a closed-form formula for 
\[
\frac{1}{1*2} + \frac{1}{2*3} + \frac{1}{3*4} + \ldots + \frac{1}{n(n+1)}
\]
by examining the values of this expression for small values of $n$.
Use mathematical induction to prove your formula holds for all natural
numbers.

\problem Suppose you take a piece of paper and draw a bunch of
straight lines, each in its own arbitrary direction, that completely
cross the paper.  This divides the paper up into polygonal regions.
Prove by induction that you can always color the various regions using
only \emph{two} colors, so that any two regions that share a boundary
line are different colors.  Note that this need not be true of regions
that share only a boundary point.


\end{problems}

\end{document}

