\documentstyle[12pt,twoside,macpsfig,amssymb]{article}
\input{macros-course}
%	\addtolength{\topmargin}{-.35in}
%	\setlength{\textheight}{9in}

\begin{document}

\psol{1}{September 17, 1996}

\bigskip

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 

\bparts
\ppart $p \Rightarrow r.$
\ppart $\neg p \bigwedge q \bigwedge r.$
\ppart $(p \bigwedge q) \Leftarrow r.$
\ppart $(p \bigvee q) \Leftrightarrow r.$
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
$(p \bigvee \neg q \bigvee \neg r) \bigwedge (\neg p \bigvee \neg q \bigvee r) \bigwedge (\neg p \bigvee q \bigvee \neg r).$

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 

\bparts
\ppart $\exists x \exists y Q(x,y).$
\ppart $\neg \exists x \exists y Q(x,y)$ or $\forall x \forall y \neg Q(x,y)$ or $\forall x \neg \exists y Q(x,y)$
\ppart $\forall y \exists x Q(x,y).$
\ppart $\exists x[Q(x,Jeopardy) \bigwedge Q(x, Wheel~of~Fortune)].$
\ppart $\exists x_1 \exists x_2[Q(x_1,Jeopardy) \bigwedge Q(x_2,Jeopardy) \bigwedge x_1 \neq x_2].$
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 

\bparts
\ppart $\forall x \exists y \ F(x,y).$
\ppart $\neg \exists x \forall y \ F(x,y).$
\ppart $\forall y \exists x \ F(x,y).$
\ppart $\exists y_1 \exists y_2[F(Nancy,y_1)\bigwedge F(Nancy,y_2)\bigwedge (y_1\neq y_2)\bigwedge \forall y(F(Nancy,y)\Rightarrow (y=y_1\bigvee y=y_2))].$
\ppart $\exists y[\forall x F(x,y) \bigwedge \forall z(\forall x F(x,z)\Rightarrow z=y)].$
\ppart $\neg \exists x F(x,x).$
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 

\bparts
\ppart $\forall x (P(x) \Rightarrow Q(x)).$
\ppart $\exists x (R(x) \bigwedge \neg Q(x)).$
\ppart $\exists x (R(x) \bigwedge \neg P(x)).$
\ppart Yes. The unsatisfactory excuse guaranteed by part {\bf (b)} cannot
be a clear explanantion by part {\bf (a)}.
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 

As a counter example, let $P(x)$ denote the statement ``x is an even
number'', and $Q(x)$ be the statement ``x is an odd number''. Let the
universe of discourse be the set of positive integers.  Then $\forall
x P(x) \bigvee \forall x Q(x)$ is clearly false. But $\forall x (P(x)
\bigvee Q(x))$ is true, since every positive integer is either odd or
even.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 

\bparts
\ppart Fallacy of affirming the conclusion. Let $p:n>1, q:n^2>1$. Then
       $((p\Rightarrow q) \bigwedge q)\Rightarrow p.$
\ppart Fallacy of begging the question. {\bf Proof:} Suppose $\log_2 3$ is 
       rational. Then by definition of rational numbers we have: 
$\log_2 3 = a/b$, where $a$ and $b$ are integers, and $\gcd(a,b)=1$.
But then $3 = 2^{a/b} \Rightarrow 3^b = 2^a \Rightarrow$ an odd number = an
even number. Contradiction! Hence, $\log_2 3$ is irrational.
\ppart Valid argument using modus tollens. Let $p:n>2, q:n^2>4$.
Then $(p\Rightarrow q)\Leftrightarrow (\neg q\Rightarrow \neg p)$.
\ppart Fallacy of denying the hypothesis. As a counter example consider the
case when $n=-4$.
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
Proof by contradiction. Suppose that $a/b$ is a nonzero rational
number and that $x$ is an irrational number. Suppose also that $xa/b$
is rational. If so, then multiply this rational number by the rational
number $b/a$. We can do this because $a/b$ nonzero implies that $a$ is
nonzero, and hence $b/a$ is a nonzero rational number. Now $xa/b \cdot
b/a$ is also rational (see exercise 12, sec 3.1). But $xa/b \cdot b/a
= x$, which is irrational by hypothesis. This is a contradiction, so
in fact $xa/b$ must be irrational, as desired.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
{\bf Solution 1:} Suppose that $\sqrt{2}+\sqrt{3}$ is rational. Then
it can be written as $a/b$, where $a$ and $b$ are integers, and
$\gcd(a,b)=1$.  Moreover, $\sqrt{2}-\sqrt{3}$ is also rational since:
\[
 (\sqrt{2}+\sqrt{3})(\sqrt{2}-\sqrt{3})=a(\sqrt{2}-\sqrt{3})/b
\]
which implies 
\[
-1 = (\sqrt{2}-\sqrt{3})a/b \longrightarrow  -b/a = \sqrt{2}-\sqrt{3}
\]
and $-b/a$ is a nonzero rational number. Hence, it must be true 
that $(\sqrt{2}+\sqrt{3})+(\sqrt{2}-\sqrt{3})$ is rational, since the 
sum of two rational numbers is rational. But 
$(\sqrt{2}+\sqrt{3})+(\sqrt{2}-\sqrt{3}) = 2\sqrt{2}$, and 
$2\sqrt{2}$ is irrational by Problem 8. Contradiction! Therefore 
$\sqrt{2}+\sqrt{3}$ is irrational.

{\bf Solution 2:} First we prove the following lemma.

{\em Lemma 1}: Prove that $\sqrt{6}$ is irrational.

{\em Proof by contradiction:} Suppose it is rational. Then
$\sqrt{6}=a/b$, where $a$ and $b$ are integers, and $\gcd(a,b)=1$. Then
\[
6 = a^2/b^2 \longrightarrow 3(2b^2) = a^2
\]
But $a^2$ is even, which implies $a$ is even, which implies $a^2$ is 
divisible by 4. So write $a^2 = 4c^2$, which implies $3b^2=2c^2$. So
$b^2$ is even, and is divisible by 4. So write $b=2d$. Then we have
$a/b = {2c}/{2d}$. But $\gcd(a,b)=1$. contradiction! Hence,$\sqrt{6}$
is irratinal.

Now assume that $\sqrt{2}+\sqrt{3}$ is rational. Then
$(\sqrt{2}+\sqrt{3})^2 = 5+2\sqrt{6} = a^2/b^2$, implies that $\sqrt{6}
= (a^2/b^2 - 5)/2$, which makes $\sqrt{6}$ rational, since
$(a^2/b^2 - 5)/2$ is rational. But by {\em Lemma 1}, $\sqrt{6}$ is
irrational. Contradiction! Therefore, $\sqrt{2}+\sqrt{3}$ is
irrational.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem There are three cases to consider.
\begin{enumerate}
\item 
$x<y\Rightarrow max(x,y)=y$, and 
$x<y\Rightarrow min(x,y)=x$. Hence, $max(x,y)+min(x,y)=x+y$.
\item 
$x=y\Rightarrow max(x,y)=x \bigvee y$, and 
$x=y\Rightarrow min(x,y)=x \bigvee y$. Hence, $max(x,y)+min(x,y)=x+y$.
\item
$x>y\Rightarrow max(x,y)=x$, and 
$x>y\Rightarrow min(x,y)=y$. Hence, $max(x,y)+min(x,y)=x+y=y+x$.
\end{enumerate}
Therefore, $max(x,y)+min(x,y)=x+y$ for all real numbers $x, y$.

\end{problems}
\begin{center}
\large \bf Some common mistakes in your solutions
\end{center}

{\bf Problem 3:} Many people forgot to include $x_1 \neq x_2$ to signify the 
``at least''.

{\bf Problem 4, parts (d) and (e):} Almost everyone had trouble handling the
``exactly''.

{\bf Problems 8 and 9:} Almost everyone assumed something that should
have been proved, the most popular one being ``$\sqrt{6}$ is
irrational'' in problem 9, when people tried to show that
$(\sqrt{2}+\sqrt{3})^2=5+2\sqrt{6}$ is irratrional. A few people
realized they needed to prove it, but didn't know how to.

{\bf Problem 10:} Many students forgot that $x=y$ is also a case that had
to be considered.

In general, there seems to be a lot of confusion about concepts such
as universe of discourse, sets, and elements. Some people had statements
such as $\forall x P(x), \exists a \in x$.

\end{document}





