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

\addtolength{\textheight}{.05in}
\begin{document}

\psol{1}{February 13, 1997}

\begin{problems}

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

Let $p$, $q$, and $r$ be the following propositions:
\begin{center}
\begin{tabular}{cc}
$p:$ & You are a good water-polo player. \\
$q:$ & You are a good swimmer. \\
$r:$ & You are in the water-polo team. \\
\end{tabular}
\end{center}

Write the propositions using $p$, $q$, and $r$ and logical
connectives (e.g.  $\vee$, $\wedge$, $\neg$, $\Rightarrow$).

\begin{problemparts}

\problempart 
{\it To be in the water-polo team, it is sufficient for you to be a good water-polo player.}

We can rephrase this as ``If you are a good water-polo player,  you will be in the water-polo team.''

\( p \Rightarrow r \)


\problempart 
{\it Being a good swimmer and a good water-polo player is necessary
for getting into the water-polo team. }

\( r \Rightarrow p \wedge q \)
\problempart 
{ \it You will get in the water polo team if and only if you 
are a good swimmer or you are a good water-polo player. }

\( r \Leftrightarrow p \vee q \)
\problempart
{ \it You are neither a good swimmer nor a good water-polo player, yet you are in the water-polo team. }

\( \neg p \wedge \neg q \wedge r \)
\end{problemparts}

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

It is easiest to negate the proposition that is true when exactly two
are false.  This in turn asks for exactly one variable to be true.  So
we or three subclauses, one for each variable that might be the only
true one.  This gives us:
\[ \neg ((\neg p \wedge \neg q \wedge r) \vee (\neg p \wedge q \wedge \neg r) 
\vee (p \wedge \neg q \wedge \neg r)) \]
which is equivalent (using DeMorgan's laws; see Rosen) to
\[ ((p \vee q \vee \neg r ) \wedge (p \vee \neg q \vee r ) \wedge (\neg p \vee q \vee r ))
\]
which is also equivalent to
\[
((p \wedge q) \vee (q \wedge r) \vee (p \wedge r)  \vee (\neg p \wedge \neg q \wedge \neg r))
\]
(This last derives the proposition by first putting in 3 clauses that
are true when exactly 2 clauses are true, and then one clause when
exactuly 0 clauses are true (note that the third case, all 3 clauses
true, is already covered by the first 3 clauses).

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

\problem 
% 1.3 # 8

Let $T(x,y)$ be the statement ``$x$ has proven $y$.''
$x$ ranges over the set of all mathematicians, and $y$ over 
the set of all theorems.

\begin{description}
\item[a)] There is a mathematician who has never proven a theorem. 
\[ \exists x \forall y (\neg T(x,y)) \]

\item[b)] Every mathematician has proven a theorem.
\[ \forall x \exists y T(x,y) \]

\item[c)] Every theorem has been proven by a mathematician.
\[ \forall y \exists x T(x,y) \]

\item[d)] There is a mathematician who has proven the 
{\it Dominated Convergence Theorem} and the {\it Bounded Convergence Theorem}.
\[ \exists x (T(x, Dominated\_Conv.\_Thm) \wedge T(x, Bounded\_Conv.\_Thm)) \]

\item[e)] At least two mathematicians have proven the {\it Hahn-Banach
    Theorem} 
\[ \exists x_1, x_2 ((x_1 \neq x_2) \wedge T(x_1, Hahn-Banach\_Thm) \wedge
 T(x_2, Hahn-Banach\_Thm)) \]

\end{description}



\problem  Define predicates and formulas.

\begin{problemparts}
\problempart 

Let x be in the domain of creatures. \\
$F(x)$: x is a frog \\
$D(x)$: x is a duck \\
$P(x)$: x is poetic \\

\begin{tabular}{ll}
No frogs are poetical & \( \forall x F(x) \rightarrow \neg P(x)  \) \\
Some ducks are unpoetical & \( \exists x D(x) \wedge \neg P(x) \) \\
Thus, some ducks are not frogs & \( \exists x D(x) \wedge \neg F(x)  \) \\
\end{tabular}

The entire argument is stated by the formula
\[( \forall x F(x) \rightarrow \neg P(x)  ) \wedge
 (\exists x D(x) \wedge \neg P(x)) \Rightarrow
 (\exists x D(x) \wedge \neg F(x)). \]

\problempart 
$H(x)$: x is heavy (not light) \\
$S(x)$: x will silence him \\

\begin{tabular}{ll}
Gold is heavy. & \( H(gold) \) \\
Nothing but gold will silence him.  & 
\( \forall x ((x = gold) \leftrightarrow S(x)) \) \\
Thus, nothing light will silence him. & \( \forall x (\neg H(x) \rightarrow 
\neg S(x)) \) \\
\end{tabular}

The entire argument is stated by the formula
\[ H(gold) \wedge 
(\forall x ((x = gold) \leftrightarrow S(x))) \Rightarrow
(\forall x (\neg H(x) \rightarrow \neg S(x))). \]

\problempart 
$L(x)$: x is  a lion \\
$F(x)$: x is fierce \\
$C(x)$: x drinks coffee \\

\begin{tabular}{ll}
All lions are fierce.  & \( \forall x L(x) \rightarrow F(x) \) \\
Some lions do not drink coffee. & \( \exists x L(x) \wedge \neg C(x) \) \\
Thus, some creatures that drink coffee are not fierce. & 
\( \exists x C(x) \wedge \neg F(x) \) \\
\end{tabular}

The entire argument is stated by the formula
\[ (\forall x L(x) \rightarrow F(x))\wedge
   (\exists x L(x) \wedge \neg C(x)) \Rightarrow
   (\exists x C(x) \wedge \neg F(x)).\]

\problempart 
$P(x)$: x is a pillow \\
$K(x)$: x is a poker \\
$S(x)$: x is soft \\

\begin{tabular}{ll}
Some pillows are soft.  & \( \exists x P(x) \wedge S(x) \) \\
No pokers are soft.   & \( \forall x K(x) \rightarrow \neg S(x) \) \\
Thus, some pokers are not pillows. & \( \exists x K(x) \wedge \neg P(x) \) \\
\end{tabular}

The entire argument is stated by the formula
\[ (\exists x P(x) \wedge S(x))\wedge
   (\forall x K(x) \rightarrow \neg S(x)) \Rightarrow
   (\exists x K(x) \wedge \neg P(x))\]


\end{problemparts}


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

\problem Prove the correct arguments from the previous problem and
show the incorrect ones are false.

\begin{problemparts}
\problempart 
We prove that the argument 
\[(\forall x F(x) \rightarrow \neg P(x)  ) \wedge
 (\exists x D(x) \wedge \neg P(x)) \Rightarrow
 (\exists x D(x) \wedge \neg F(x))\]
is wrong by exibiting a model in which the formula 
is false. 
The universe of discourse contains a single element
{\em dog} which is both a duck and a frog and 
it is not poetical, i.e., $D(dog)$, $F(dog)$ and $\neg P(dog)$.
The formula $\forall x F(x) \rightarrow \neg P(x)$ is true
because $\neg P(dog)$.
Also  $\exists x D(x) \wedge \neg P(x)$ is  true because
$D(dog)$ and $\neg P(dog)$.
However the conclusion $\exists x D(x) \wedge \neg F(x)$
is false because $F(dog)$, so the argument is not valid.

\problempart 
The argument 
\[ H(gold) \wedge 
( \forall x ((x = gold) \leftrightarrow S(x)))  \Rightarrow
(\forall x (\neg H(x) \rightarrow \neg S(x)))\]
is correct.
Assume $H(gold)$ and
$\forall x ((x = gold) \leftrightarrow S(x))$
are true.
We prove that $\forall x (\neg H(x) \rightarrow \neg S(x))$ is 
false by contradiction: \\
Assume \(\neg (\forall x (\neg H(x) \rightarrow \neg S(x))) \) \\


\begin{tabular}{ll}
\(\neg (\forall x (\neg H(x) \rightarrow \neg S(x))) \) &
  assumption \\
\(\neg ( \neg \exists x \neg (\neg H(x) \rightarrow \neg S(x))) \) &
  \( \forall x Q(x) \leftrightarrow \neg \exists x \neg Q(x) \) \\
\(\exists x \neg (\neg H(x) \rightarrow \neg S(x)) \) & 
  Double negation law \\
\(\exists x \neg (H(x) \vee \neg S(x)) \) & 
  Defintion of $\rightarrow$ \\
\(\exists x \neg H(x) \wedge S(x) \) & 
  DeMorgan's law \\
\(\exists x \neg H(x) \wedge (x=gold)\) & 
  Logical equivalence \\
\end{tabular}

If we split this up into cases, $x=gold$ and $x \neq gold$, we find 
\begin{itemize}
\item case 1:  $x=gold$ \\
\( \neg H(x) \wedge (x = gold) =
\neg H(gold) \wedge (gold = gold) = 
(\neg True) \wedge True = False \wedge True = 
False
\)
  
\item case 2:  $x \neq gold$ \\
\( \neg H(x) \wedge (x = gold) =
\neg H(x \neq gold) \wedge (x = gold) = ? \wedge False = 
False
\)
\end{itemize}

Since neither case proves true, we know that our original assumption, 
\(\neg (\forall x (\neg H(x) \rightarrow \neg S(x))) \), must be 
untrue, so \(\forall x (\neg H(x) \rightarrow \neg S(x))) \).



\problempart 
We prove that the argument
\[ (\forall x L(x) \rightarrow F(x))\wedge
   (\exists x L(x) \wedge \neg C(x)) \Rightarrow
   (\exists x C(x) \wedge \neg F(x))\]
is wrong by exibiting a model in which the formula 
is false.
The universe of discourse contains a single element
{\em loffy}, which satisfies $L(loffy)$, $F(loffy)$ and $\neg C(loffy)$.
We have $\forall x L(x) \rightarrow F(x)$ and
$\exists x L(x) \wedge \neg C(x)$.
However $\exists x C(x) \wedge \neg F(x)$ is false,
so the argument is not valid.

\problempart 
We prove that the argument
\[ (\exists x P(x) \wedge S(x))\wedge
   (\forall x K(x) \rightarrow \neg S(x)) \Rightarrow
   (\exists x K(x) \wedge \neg P(x))\]
is wrong by exibiting a model in which the formula 
is false.
The universe of discourse contains a single element
{\em poft} such that $P(poft)$, $S(poft)$ and 
$\neg K(poft)$.
The formula $\exists x P(x) \wedge S(x)$ is true.
Also  $\forall x K(x) \rightarrow \neg S(x)$ is  true
because there exists no $x$ such that $K(x)$.
For the same reason the conclusion $\exists x K(x) \wedge \neg P(x)$
is false, proving the the argument is not valid.

\end{problemparts}



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


\problem 
\begin{problemparts}
\problempart
{\it {\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$. }

Given the propositions
p: $n>1$ and 
q: $n^2>1$, 
the argument says that $p \rightarrow q$, so if q then p.
This is the fallacy of affirming the conclusion.

\problempart
{ \it {\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. }

Fallacy: Circular reasoning.  The statement following the
``therefore'' is precisely the one we want to prove.  And it doesn't
follow from anything before, so the therefore has no justification for
being there.

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

Given the propositions
p:  $n^2 \leq 4$ and
q: $n \leq 2$,
the argument says $\neg q \rightarrow \neg p$, so $p \rightarrow q$.  This is the
correct argument of disjunctive syllogism.

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

Given the propositions 
p: $n\leq 3$ and 
q: $n^2\leq 9$,
the argument says $ \neg p \rightarrow \neg q $.  This is the fallacy of denying
the hypothesis.

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
{ \it Prove by contradiction: the square root of an irrational number 
is irrational. }

Let $x$ be an irrational number.  Prove that \( \sqrt{x} \) is 
irrational.  

Proof by contradiction:

Assume that \( \sqrt{x} \) is rational.  
Then we know that there exist integers $p$ and $q$ such that
\[ \sqrt{x} = \frac{p}{q}. \]   
Squaring both sides we get \[ x = \frac{p^2}{q^2} \]
Since the square of an integer is an integer, $p^2/q^2$ is a ratio of
integers, and therefore a rational number, making x a rational number.  
This, however, contradicts our original assertion that x is an irrational
number, so the theorem must be true.


\problem

Prove that $\sqrt[3]{5}$ is irrational.

Proof by contradiction:

Assume $\sqrt[3]{5}$ is rational.  It can then be represented as a fraction
in lowest terms, $p/q$, where $p$ and $q$ are integers:
\[ \sqrt[3]{5} = \frac{p}{q} \]
Rearranging the equation we get
\[ 5 = \frac{p^3}{q^3} \]
and
$ 5 q^3 = p^3 $ 
Since 5 is prime (has no divisors other than 1 and 5) and p is an integer, 
we know that 
$p = 5 c$ 
where c is also an integer.  However, using similar reasoning, we find that 
\[ 5 q^3 = p^3 = 5^3 c^3\]
and therefore $q^3 = 5^2c^3$,
so q can also be represented as $q=5d$ where d is an integer.  Since both
$p$ and $q$ are multiples of 5, the fraction $p/q$ is not in lowest terms,
contradicting our hypothesis.
Thus  $\sqrt[3]{5}$ is irrational.  


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 3.1 - 19
\problem 
Prove by cases that if $x$ and $y$ are real numbers, then 
\[ \max(x,y) = { x + y \over 2} + { |x - y| \over 2 } \]

Split the proof into two cases: $x \geq  y $ where $x$ is the maximum, and
$x < y $ where $y$ is the maximum.

\begin{itemize}
\item Case 1: $x \geq  y $ , x is the maximum

Since $x \geq y$, $x-y \geq 0$, and $|x-y| = x-y$.  So 
\[ { x + y \over 2} + { |x - y| \over 2 } =
{ x + y \over 2} + { x - y \over 2 } =
{ 2 x \over 2} = x = \max(x,y).
\]

\item Case 2: $x < y $ , y is the maximum

Since $x < y$, $x-y < 0$, and $|x-y| = -(x-y) = y-x$.  So 
\[ { x + y \over 2} + { |x - y| \over 2 } =
{ x + y \over 2} + { y - x \over 2 } =
{ 2 y \over 2} = y = \max(x,y).
\]
\end{itemize}
Therefore 
\( \max(x,y) = { x + y \over 2} + { |x - y| \over 2 } \) is true,
because it is true in both cases.

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

\problem

Using the axioms and inference rules for equality given in class,
prove that 
\[
(\forall x y z) ((x = y) \wedge (y=z))\rightarrow (x=z)
\]

Recall that the equality rules are 
\begin{description}
\item [E1] $(\forall x) (x=x)$
\item[E2] For any formula $F$ with free variable x,
\[
(\forall xyz\ldots)(x=y \Rightarrow (F \rightarrow F[x/y])
\]
where $F[x/y]$ denotes substituting $y$ for some or all occurrences of
$x$.
\end{description}


Show that 
\(
(\forall x y z) ((x = y) \wedge (y=z))\rightarrow (x=z)
\).

Let $p$ be the proposition $((x=y) \wedge (y=z))$.

\begin{enumerate}
\item Let F = (x=z) in E2:
\(        \forall xyz. (x=y) \rightarrow ((x=z) \rightarrow (y=z))  \)
   in particular 
\( (b=a) \rightarrow (b=c) \rightarrow (a=c) \)
 
\item \(\forall xy. (y=x) \rightarrow (x=y) \) [proved in class, see
   lecture notes 2] 
   in particular
        \( (a=b) \rightarrow (b=a) \)
 
\item by transitivity of $ \rightarrow $, from 1) and 2) we get
        \( (a=b) \rightarrow ((b=c) \rightarrow (a=c)) \)
 
\item $ (a=b)$  and $ (b=c) $ by hypothesis
 
\item modus ponens: \( (b=c) \rightarrow (a=c) \)

\item modus ponens: \( (a=c) \)

\end{enumerate}
 
We proved for fixed $a$,$b$,$c$, so by universal generalization holds for all.
 


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

\end{problems}
\end{document}
% Local Variables: 
% mode: latex
% TeX-master: t
% End: 
% LocalWords:  Carrol
