%%PSET1-PROBS.TEX, 6042 F01

\begin{problems} 

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


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

\solspace{We'll just negate a compound proposition that is \emph{true}
when exactly two of the variables $p,q$ and $r$ are false.  But exactly
two variables are false iff exactly one variable is true.  So we divide
the proposition in three subclauses, one for each variable that might be
the only true one.  Altogether 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)).\]

Using DeMorgan's laws (see Rosen), we could rewrite this formula equivalently
as
\[((p \vee q \vee \neg r ) \wedge (p \vee \neg q \vee r ) \wedge 
   (\neg p \vee q \vee r )).
\]

Another equivalent formula is
\[
((p \wedge q) \vee (q \wedge r) \vee (p \wedge r)  \vee (\neg p \wedge \neg q \wedge \neg r)).
\]
The disjunction ($\vee$) of the first three clauses is true exactly when
some pair of variables are both true.  The last clause is true precisely
when no variables are true.  So the formula is false exactly when only one
variable is true.
}

%PROOFS
%from Fall 99
\problem %From Fall 95 ps1, prob 7

Determine whether each of the following arguments is valid.  If an
argument is correct, what rule of inference (from Rosen, \S~3.1) is
being used?  If it is not, what fallacy (again from Rosen \S~3.1)
occurs?

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

\solnospace{Invalid: fallacy of affirming the conclusion.}

\problempart
\emph{Claim}: The number $\log_2 3$ is irrational. \\
{\em Suggested 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.

\solnospace{Invalid: fallacy of affirming the conclusion.}

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

\solnospace{Valid: modus tollens.}

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

\solnospace{Invalid: fallacy of denying the hypothesis.}

\end{problemparts}      
                               
%spring00
\problem 
\begin{claim*}
If every element of a set, $A$, is nonzero, and $A \subseteq B$, then
every element of $B$ is nonzero.
\end{claim*}

\bparts
\ppart Give a counterexample to the Claim.

\solnospace{Let $A = \mathbb{N^+}$ and $B = \ints$.}

\ppart What is wrong with the following proof of the Claim?  (It is not
sufficient merely to observe that a proof is wrong because its conclusion
is wrong---you have to say where.  A proof could be wrong regardless of
whether its conclusion is correct; some famous historical examples of
wrong ``proofs'' whose conclusions eventually turned out to be right are
mentioned in the Lecture Notes.)

\begin{falseproof}
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
that $\forall x \in B \; (x \ne 0)$.
\end{falseproof}

\solspace{We selected $x$ arbitrarily from set $A$, but are generalizing
to all $x$ over a different, larger set $B$.}

\eparts

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

%QUANTIFIERS and SETS
\problem
\bparts

The standard notation for the proposition that a set, $x$, is a member of
a set, $y$, is
\[
x \in y.
\]
Formulas built up from membership propositions of this form using logical
connectives and quantifiers are called the logical \emph{formulas of set
theory}.  For example, to say $x \neq y$ with a formula of set theory, we
could write
\[
\exists z\; (z \in x) \iff \neg (z \in y).
\]

\ppart Write a formula of set theory that means that $x$ is the
empty set.
\solnospace{$\forall y\; \neg (y \in x)$.}

\ppart Write a formula of set theory that means that $x \subset y$, that
is, $x$ is a \emph{proper} subset of $y$.

\solnospace{$(\forall z\; (z \in x) \implies z \in y)$ means that $x$ is a
subset of $y$, that is, $x \subseteq y$.  To say $x \subset y$, form the
conjuction ($\land$) of this formula that means $(x \subseteq
y)$ and the formula above that means $(x \neq y)$.}

\ppart Write a formula of set theory that means that $y$ is the powerset
of $x$.

\solnospace{$\forall z\; P \implies (z \in y)$, where $P$ is a formula
of set theory that means $(z \subseteq x)$.
}

\ppart Write a formula of set theory that means that $y$ has at least
three elements.

\solnospace{$\exists u \exists v \exists w\; (u \in y) \land (v \in y)
\land (w \in y) \land (u \neq v) \land (u \neq w) \land (v \neq w).$}

\ppart Write a formula of set theory that means that $y$ has exactly two
elements.

\solnospace{It is easy to write a formula, $T(y)$, that means that $y$ has
at least two elements.  The desired formula is just the conjunction of
$T(y)$ and the formula that says that $y$ does \emph{not} have at least
three elements.}

\eparts


\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 in 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 be 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, Alice might be able to reach the
top shelf, say by using a ladder, even she is short.
That is, $R \land \neg T$ is consistent with
the premises but not with 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.
\solspace{
The deduction is:
\begin{center}
\begin{tabular}{l}
        $\neg (J \land M)$ \\
        $M \lor C$ \\ 
        $J$ \\ \hline
        $\therefore C$
\end{tabular}
\quad where 
\begin{tabular}{l}
        $J \equiv \mbox{``Jane will win the math prize.''}$ \\
        $M \equiv \mbox{``Pete will win the math prize.''}$ \\
        $C \equiv \mbox{``Pete will win the chemistry prize.''}$
\end{tabular}
\end{center}
This deduction is valid.    
}

\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.
\solspace{
The deduction is:
\begin{center}
\begin{tabular}{l}
        $B \lor F$ \\
        $C \lor P$ \\
        $\neg (F \land C)$ \\ \hline
        $\therefore \neg (B \land P)$
\end{tabular}
\quad where 
\begin{tabular}{l}
        $B \equiv \mbox{``The main course will be beef.''}$ \\
        $F \equiv \mbox{``The main course will be fish.''}$ \\
        $C \equiv \mbox{``The vegetable will be corn.''}$ \\
        $P \equiv \mbox{``The vegetable will be peas.''}$ 
\end{tabular}
\end{center}
This deduction is invalid.  For example, $B \land \neg F \land C \land
P$ is consistent with the premises but not with the conclusion.  Note
that as formalized, there need not be only one main course and only
one vegetable; it is possible, for example, for the vegetable to be
both corn and peas, as in the scenario given.  If we wished to exclude
the possibility of multiple courses we could have used exclusive-or
instead of inclusive-or. So our premise about the main course would
then read $B \oplus F$ or, equivalently, 
$(B \lor F) \land \neg (B \land F)$. 
The premise about the vegetable could be changed similarly.  
The deduction is still invalid with this formalization. 
                                                         
}

\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.
\solspace{
We interpret ``John is lying,'' to be 
the negation of ``John is telling the truth.'' 
Similarly for the corresponding propositions involving Bill and Sam.
The deduction is:
\begin{center}
\begin{tabular}{l}
        $J \lor B$ \\
        $\neg S \lor \neg B$ \\ \hline
        $\therefore J \lor \neg S$
\end{tabular}
\quad where 
\begin{tabular}{l}
        $J \equiv \mbox{``John is telling the truth.''}$ \\
        $B \equiv \mbox{``Bill is telling the truth.''}$ \\
        $S \equiv \mbox{``Sam is telling the truth.''}$
\end{tabular}
\end{center}
This deduction is valid.  It is an example of a common
``cancellation'' rule that lets us get rid of the proposition $B$.   
}

\iffalse
\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.
\solspace{The deduction is:
\begin{center}
\begin{tabular}{l}
        $(S \land H) \lor (E \land \neg H)$ \\ \hline
        $\therefore \neg (S \land E)$
\end{tabular}
\quad where 
\begin{tabular}{l}
        $S \equiv \mbox{``Sales will go up.''}$ \\
        $H \equiv \mbox{``The boss will be happy.''}$ \\
        $E \equiv \mbox{``Expenses will go up.''}$ 
\end{tabular}
\end{center}
This deduction is invalid. 
For example, $S \land E \land H$ is consistent 
with the premises but not with the conclusion.}
\fi

\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.
\solspace{The deduction is:
\begin{center}
\begin{tabular}{l}
        $T \land U \implies R$ \\
        $G \implies \neg R$ \\
        $G \land T$ \\ \hline
        $\therefore \neg R$
\end{tabular}
\quad where 
\begin{tabular}{l}
        $T \equiv \mbox{``The tax rate goes up.''}$ \\
        $U \equiv \mbox{``Unemployment goes up.''}$ \\
        $G \equiv \mbox{``GNP goes up.''}$ \\
        $R \equiv \mbox{``There will be a recession.''}$
\end{tabular}
\end{center}
This deduction is valid. 
(The first premise is superfluous.)    
}
\end{problemparts}


%PROOFS

%spring00
\problem Suppose $x$ is a real number.  Prove \textbf{by cases} 
of whether $x=1$ or $x \neq 1$, that there is a
$y \in \reals$ such that $(y+1)/(y-2)=x$ if and only if $x \ne 1$.

\solspace{\begin{description}

\item[Case 1 ($x \not = 1$): ] We need to prove that there exists $y \in
\reals$ such that $(y+1)/(y-2)=x$.  In particular, we can solve for $y$
algebrically and conclude that $(2x+1)/(x-1)$ is the desired $y$.  This
$y$ is a well-defined real number because $x \neq 1$.  Therefore, $\exists
y \in \reals\; ((y+1)/(y-2) = x)$ by existential generalization.

\item[Case 2 ($x = 1$): ]
We need to prove that no $y \in \reals$ exists 
such that $(y+1)/(y-2)=x$. 
Suppose, for contradiction, that such a $y$ did exist.  Then:
\begin{align}
\frac{y+1}{y-2} & =  1  &\tag{because $x = 1$} \\
y+1 & = y-2  &\tag{multiply both sides by $y-2$} \\
1 & =  -2 &\tag{subtract $y$ from both sides},
\end{align}
a contradiction.

\end{description}
}     

%%Example from Spring99, tutorial 2

\problem Consider the following proof that the square root of 2 is
irrational.

\begin{proof}
The proof is by contradiction.

Assume that the square root of 2 is rational.  Then $\sqrt{2}$ is equal to
$m / n$ for some positive integers $m$ and $n$.  So $n$ has the property
that
\[
n \text{ and } n\sqrt{2} \text{ are positive integers}.
\]
Now assume that $n$ is the \emph{smallest} positive integer with this
property, and let $n_0 \eqdef n (\sqrt{2} - 1)$.  But then $n_0$ is
smaller than $n$, and $n_0$ and $n_0\sqrt{2}$ are positive integers, a
contradiction.
\end{proof}

\bparts
\ppart Are you convinced by this proof?  Briefly explain.

In particular, why is $n_0$ an integer?

\solnospace{Because it equals $n\sqrt{2} - n$
and $n$ and  $n\sqrt{2}$ are integers by hypothesis.}

Why is $n_0$ positive?

\solnospace{Because $(\sqrt{2} -1) \approx 0.414\dots$ is positive.}

Why is $n_0$ smaller than $n$?

\solnospace{Because $(\sqrt{2}-1) < 0.415 < 1$.}

Why is $n_0\sqrt{2}$ a positive integer?

\solnospace{It's an integer because $n_0\sqrt{2} = (n\sqrt{2} - n)\sqrt{2}
= 2n - n\sqrt{2}$, which is again an integer because both terms are
integers.  It's positive because $2n - n\sqrt{2} = (2 - \sqrt{2})n > 0.58
n > 0$.}

\eparts

\medskip
We can generalize this proof to prove that $\sqrt{k}$ is irrational for
integers $k$ other than 2.  Simply revise the next to last sentence to
read, ``\dots and let $n_0 \eqdef (\sqrt{k} - \floor{\sqrt{k}})$''.  (For
any real number, $r$, the expression $\floor{r}$ denotes $r$ rounded
\emph{down} to the nearest integer.)

\bparts

\ppart Are you convinced by this argument?  Explain.

\solnospace{You shouldn't be convinced because the conclusion is wrong,
For example, $\sqrt{k}$ is certainly rational if $k=4$.

The proof works for $\sqrt{k}$ as long as $k$ is not a perfect square.
But if $k$ is a perfect square, then the proof breaks down in the next to
last sentence: the number $n_0 (\sqrt{k} - \lfloor \sqrt{k} \rfloor)$ is
not positive in this case, but zero.}

\eparts

\end{problems}
