\documentstyle[12pt,twoside]{article}
\input{macros-course}

%	\addtolength{\topmargin}{-.35in}
%	\setlength{\textheight}{9in}

\begin{document}

\pset{1}{September 7, 1995}{Start of Class, September 12}

{\bf Reading:} Sections 1.1 to 1.3 and 3.1 of {\it Discrete Mathematics and its Applications}
by Kenneth H. Rosen.

\bigskip

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 1.1 - 8
\problem

Let $p$, $q$, and $r$ be the following propositions:
\begin{center}
\begin{tabular}{cc}
$p:$ & You get an A on the final exam. \\
$q:$ & You do every exercise in this book. \\
$r:$ & You get an A in this class. \\
\end{tabular}
\end{center}

Write the following propositions using $p$, $q$, and $r$ and logical
connectives (e.g. {\em $\vee$, $\wedge$, $\neg$, $\implies$}).

\begin{problemparts}

\problempart 
To get an A in this class, it is necessary for you to get an A on the final.

\problempart 
You get an A on the final, but you don't do every exercise in this book;
nevertheless, you get an A in this class.

\problempart 
Getting an A on the final and doing every exercise in this book is sufficient
for getting an A in this class.

\problempart You will get an A in this class if and only if you either
do every exercise in this book or you get an A on the final.

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 1.2 - 25
\problem Find a compound proposition involving the propositions $p$,
$q$, and $r$ that is true when exactly two of $p$, $q$, and $r$ are
true.  The compound propositon is false otherwise. 


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

\problem 
% 1.3 # 7

Let $P(x)$ be the statement ``$x$ can speak Russian'' and let $Q(x)$
be the statement ``$x$ knows the computer language C++.'' Express each
of the following sentences in terms of $P(x), Q(x)$, quantifiers, and
logical connectives. For the universe of discourse for quantifiers use
the set of all students in your school.
\begin{description}
\item[a)] There is a student at your school who can speak Russian and 
who knows C++.
\item[b)] There is a student at your school who can speak Russian but 
who doesn't know C++.
\item[c)] Every student at your school either can speak Russian or 
knows C++.
\item[d)] No student at your school can speak Russian or knows C++.
\item[e)] No Russian speaking student knows C++.
\end{description}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%RAVI: remove 4 of the more boring ones.
\problem
% 1.3 # 9

Let $L(x,y)$ be the statement ``$x$ loves $y$,'' where the universe of
discourse for both $x$ and $y$ is the set of all people in the world.
Use quantifiers to express each of the following statements:
\begin{description}
%\item[a)] Everybody loves Jerry.
\item[a)] Everybody loves somebody.
\item[b)] There is somebody whom everybody loves.
\item[c)] Nobody loves everybody.
%\item[d)] There is somebody whom Lydia does not love.
%\item[f)] There is somebody whom no one loves.
\item[d)] There is exactly one person whom everybody loves.
\item[e)] There are exactly two people whom Lynn loves
%\item[i)] Everyone loves himself or herself.
\item[f)] There is someone who loves no one besides himself or herself.
\end{description}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
% 1.3 # 17

Let $P(x), Q(x),$ and $R(x)$ be the statements ``$x$ is a professor,''
``$x$ is ignorant,'' and ``$x$ is vain,'' respectively. Express each
of the following statements using quantifiers; logical connectives;
and $P(x), Q(x),$ and $R(x)$, where the universe of discourse is the
set of all people.
\begin{description}
\item[a)] No professors are ignorant.
\item[b)] All ignorant people are vain.
\item[c)] No professors are vain.
\item[d)] Does c) follow from a) and b)? If not, is there a correct 
conclusion?
\end{description}

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

% 1.3 - 28
\problem

Show that $\forall x P(x) \vee \forall x Q(x)$ and $\forall x \forall
y (P(x) \vee Q(y))$ are logically equivalent.  (The new variable $y$
is used to combine the quantifications correctly.)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 3.1 - 3
%%RAVI: go through each proposition, and precede it with the statement
%%that is trying to get proved, as i did for the first.
\problem
Determine whether each of the following arguments is valid.  If an
argument is correct, what rule of inference (from Rosen, section 3.1)
is being used?  If it is not, what fallacy (from Rosen) occurs?

\begin{problemparts}
\problempart
{\em Theorem:} if $n^2>1$, then $n>1$.  {\em Proof:}
If $n$ is a real number such that $n>1$, then $n^2>1$.  Suppose that
$n^2>1$, then $n>1$.

\problempart
{\em Theorem:} The number $\log_2 3$ is irrational. {\em Proof:} A number is irrational if it is not the ratio of two integers.
Therefore, since $\log_2 3$ cannot be written in the form $a/b$ where
$a$ and $b$ are integers, it is irrational.

\problempart
{\em Theorem:} If $n^2 \leq 9$ then, $n \leq 3$.  {\em Proof:} Because
if $n$ is a real number with $n>3$, then $n^2 >9$.

\problempart
{\em Theorem} If $n\leq 2$, then $n^2\leq 4$. {\em Proof:} Because if $n$ is a real number with $n>2$, then $n^2>4$.

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 3.1 - 11
\problem
Prove that the sum of an irrational number and a rational number is irrational
using a proof by contradiction.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 3.1 - 21
\problem 
Prove by cases that if $x$ and $y$ are real numbers, then $|x+y| \le
|x|+|y|$, (where $|x|$ denotes the absolute value of $x$, which is $x$
when $x\ge 0$ and $-x$ when $x < 0$).

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

\problem
%Kleinberg

Consider an $8 \times 8$ checkerboard in which each square is colored
red or black.  Prove that regardless of how it is colored, there are
two squares at distance exactly 4 apart that have the same color
(distance here is measured in city-block style: squares that share an
edge are at distance 1, squares that share only a corner are at
distance 2; a ``knight move'' is distance 3).

\def\naturals{N}

\problem
%Karger

Using the level of rigor applied in the section on Peano's Axioms, 
prove the {\em cancellation law}:
\[
\forall m,n,p \in \naturals, (m+p=n+p) \implies m=n
\]



\problem
%koods

What is wrong with the following proof that $2=1$?

\[ x^2 = \overbrace{x + x + \ldots + x}^x\]
Differentiating both sides with respect to $x$, we get
\[ 2x =  \overbrace{1 + 1 + \ldots + 1}^x = x\]
Hence $2=1$.

\end{problems}
\end{document}







