\documentstyle[fleqn,fullpage]{article}
\newcommand{\imply}{\rightarrow}
\newcommand{\dimply}{\leftrightarrow}
\newcommand{\lequiv}{\Leftrightarrow}
\newcommand{\exist}{\exists}
\newcommand{\Sum}{\sum}
\begin{document}
\begin{center}
CSE 20, Discrete Mathematics, Winter 1995\\
Section 1, 1 PM, First Practice Midterm
\end{center}

\begin{enumerate}

\item

Say that you know the following facts (parenthetical comments
are just to make the story coherrent and have no logical
importance):
\begin{itemize}
\item To be on time, you must be in New York by 5 PM and your
friend must meet you at the airport.
\item
To get to New York by 5 PM, you must either connect through
Chicago or through Dallas  .
\item 
To connect through Dallas , you must be at the San Diego
airport early.
\item If you connect through Chicago, your friend will not
meet you at the airport (because  the Chicago flight lands
at JFK and your friend hates to go to JFK because of the traffic.) 
\end{itemize}
Prove that to be on time,
you must be at the San Diego airport early, starting
by formalizing both the premises and conclusion in terms of 
Boolean algebra.


\noindent
Answer:
To say that $p$ must happen for $q$ to be true is to
say that $p$ is necessary for $q$ or that $q \imply p$.
This is somewhat counterintuitive,in that $p$ typically
causes $q$, not the other way.   However, what
$q \imply p$ means  is that : if we know q, we can deduce
$p$, not that $q$ causes $p$.  For example,consider
"To succeed you must work hard".  If you work hard, you may or may 
not succeed without being contrary to this maxim.   However,
if you succeed, it can be deduced from the maxim that you worked hard.
With this in mind, let $t \lequiv $"you are on time",
$n \lequiv$ "you are in New York by 5 PM", $f \lequiv$ "your
friend meets you at the airport, $c \lequiv$
"you connect through Chicago", $d \lequiv $ "you connect
through Dallas", $s \lequiv$ "you are at the San Diego airprot
early.  The premises then become
\begin{itemize}
\item
$t \imply (n \land f)$
\item
$n \imply (c \lor d)$
\item
$d \imply e$
\item
$c \imply \lnot f$
\end{itemize}
and what we want to show is $t \imply e$.
So in our proof we assume $t$, and try to prove $e$.
\begin{enumerate}
\item
$t \imply (n \land f)$
\item
$n \imply (c \lor d)$
\item
$d \imply e$
\item
$c \imply \lnot f$
\item
Assume $t$ (assumption, goal now becomes $e$)
\item 
$n \land f$ (5,1, Modus Ponens)
\item
$n$  (6, Conj. Simp.)
\item
$c \lor d$ (2, 7, MP)
\item 
$f$ (6, Conj. Simp.)
\item
$\lnot c$ (9, 4, Modus Tollens)
\item
$d$ (10, 8, Disj. Simp.)
\item
$e$ (11, 3, MP.)
\item
Therefore $t \imply e$ (Assumption 1 implies conclusion 12)
\end{enumerate}
\ 
\item
Let $A,B$ be sets from a common universe.
Prove that if $A \cup B = A \cap B$, then $A=B$.  
\noindent:
Discussion:  Many  people made the mistake of getting the
GOAL confused with the premises.  It is important to find
logically equivalent ways of stating the goal, but this
should be done ON SEPERATE PAPER, not as part of the proof.
Once you have a logically equivalent version of the goal,
you prove that logically equivalent version, and then
GO BACKWARDS through your reasoning on the seperate paper
to show that this indeed proves your goal.  VERY IMPORTANT:
NEVER ASSUME YOUR GOAL AS PART OF A PROOF.  If you assume
your goal to be true, then there is nothing to prove; your
argument is completely circular, in that all you are doing
is showing that if your goal is true, then your goal is true.
Here the goal is to show $A=B$.  That is the same as
$A \subseteq B \land B \subseteq A$.  So the proof should
have two parts, in the first we show $A \subseteq B$ , in
the second, vice versa.  (Of course, looking at the premises,
there is no difference between $A$ and $B$, so the proof for
the second part will be exactly the same as the proof for
the first part, swapping $A$ and $B$.  In a les formal proof,
we would just say, after proving $A \subseteq B$, ``the proof
for $B \subseteq A$ is identical".  However here we put it
in to be complete. )   In the first part, then, our goal is
to prove $A \subseteq B$ or $\forall x (x \in A \imply x \in
B)$.  Thus, since we are trying to prove a universal rule,
we should do a proof by universal generalization.  The
first step of this part should be to let $x_0$ be some
arbitrary element.  Then we want to prove $x_0 \in A \imply
x_0 \in B$, so our second step should be to assume $x_0 \in
A$.  Now our goal is to prove $x_0 \in B$.  This is not
reducible to anything logically simpler, so we start working
from what we are given.  The premise is that $A \cup B = A
\cap B$, so if we can show $x_0 \in A \cup B$ (as really is
true, since $x_0$ in $A$), we can conclued $x_0 \in A \cap B$,
so in particular, $x_0 \in B$, which was our goal.
This proof strategy translates to:
\begin{enumerate}
\item  $A \cup B = A \cap B$ (premise)
\item  Let $x_0$ be arbitrary.  (No reason needed, this just
introduces $x_0$; we are trying to prove $\forall x (x \in A
\imply x \in B)$ by universal generalization; by introducing
$x_0$, our goal becomes $x_0 \in A \imply x_0 \in B)$
\item Assume $x_0 \in A$  (assumption, our goal is now to
prove $x_0 \in B$)
\item $x_0 \in A \lor x_0 \in B$ (3, disj. amp.)
\item $x_0 \in A \cup B$ (4, definition of union)
\item $x_0 \in A \cap B$ (1,5 substitution)
\item $x_0 \in A \land x_0 \in B$ (6, definiton of
intersection)
\item $x_0 \in B$ (7, Conj. Simp.: this was our sub-goal, so
we start working backwards to show that we are actually done)
\item Therefore, $x_0 \in A \imply x_0 \in B$ (assume 3,
conclude 8)
\item Since $x_0$ was arbitrary, $\forall x (x \in A \imply x
\in B)$  (2,9, Universal generalization)
\item $A \subseteq B$ (10, definition of subset; this ends the
first part, we now prove $B \subseteq A$ in exactly the same
way.)
\item  Let $x_1$ be arbitrary.  (No reason needed, this just
introduces $x_1$; we are trying to prove $\forall x (x \in B
\imply x \in A)$ by universal generalization; by introducing
$x_1$, our goal becomes $x_1 \in A \imply x_1 \in B)$
\item Assume $x_1 \in B$  (assumption, our goal is now to
prove $x_1 \in A$)
\item $x_1 \in A \lor x_1 \in B$ (13, disj. amp.)
\item $x_1 \in A \cup B$ (1, definition of union)
\item $x_1 \in A \cap B$ (1,15 substitution)
\item $x_1 \in A \land x_1 \in B$ (16, definiton of
intersection)
\item $x_1 \in A$ (17, Conj. Simp.: this was our sub-goal, so
we start working backwards to show that we are actually done)
\item Therefore, $x_1 \in B \imply x_1 \in A$ (assume 13,
conclude 18)
\item Since $x_1$ was arbitrary, $\forall x (x \in B \imply x
\in A)$  (12,19, Universal generalization)
\item $B \subseteq A$ (20, definition of subset; this ends the
second part, we now can conclude $A=B$)
\item $A =B$ (11, 21, subset criterion for set equality)
\end{enumerate} 

\item
At a certain party, everyone there shook hands with at
least one other person there.
Of course, no one shook hands with him/herself.
Moreover, for every two people at the party, there was
someone they both shook hands with.
Formalize these statements using quantifiers (with the
universe being the set of people at the party)  and
the predicate $h(x,y)$ standing for ``$x$ shook hands
with $y$''.  Then formalize and prove from the above
that every person at the party shook hands with at
least two different people. 

Answer:  The first premise is a universal rule that
applies to every object (person) in our universe.
Thus, it should start $\forall x (something happens)$
The something that happens is that $x$ shakes hands with
someone, or that there exists someone $x$ shakes hands
with.  Thus, the first premise is $\forall x \exist y
[h(x,y)]$.  To say that no-one does something
is to either say that there does not exist someone who
does that thing, or, equivalently, that everyone does
not do the thing.  Here the thing is "x shakes own hand" or
$h(x,x)$, so we translate the second premise as $\forall x
[\lnot h(x,x)]$.  The third premise is again a general rule,
but since it applies to pairs of people rather than individual
people, we should start with two variables introduced with
universal quantifiers: $\forall x \forall y [something]$.
The something that happens is that there is some $z$ that
shakes hands with both $x$ and $y$.  Hence, the third
premise is $\forall x \forall y [\exists z [h(x,z) \land
h(y,z)]]$.  Our goal is to prove that something happens
for every person, so should start $\forall x[something]$.
The something that happens is that there exist two different
people $x$ shook hands with.  Thus, we should next have
two new variables introduced with existential quantifiers.
$\forall x \exist y \exist z (something)$.  What are we
told should be true of $y$ and $z$?  First they should both
shake hands with $x$, so $h(x,y)$ and $h(x,z)$.  Second,
and more subtly, they should be different, i.e., it wouldn't
count if $y=z$, so we must have $y \ne z$.  Thus our
goal is to prove $\forall x [\exist y \exist z [h(x,y) \land
h(x,z) \land y \ne z]]$.  

Since our goal is a universal statement, we should use
a proof by universal generalization,  Introduce $x_0$
in the first step, and then prove $\exist y \exist z [h(x_0,y)
\land h(x_0,z) \land y \ne z]$.  This subgoal is existential
so we need to prove it using existence by example. Thus, we need
to find values $y_0,z_0$ for $y$ and $z$, and  
then prove $h(x_0,y_0), h(x_0,z_0),$ and $y_0 \ne z_0$.
Looking at the premises, the first premise applied to $x_0$
gives a suitable value for $y$, and then we can apply the
third premise to the pair $x_0,y_0$ to get $z_0$.  Finally,
we can use the second premise to show $y_0 \ne z_0$/

This leads to the following proof:
\begin{enumerate}
\item $\forall x \exist y [h(x,y)] $ (premise)
\item $\forall x \lnot h(x,x)$ (premise)
\item $\forall x \forall y [\exist z [h(x,z) \land h(y,z)]$.(premise)
\item Let $x_0$ be an arbitrary person at the party (No reason
needed , goal becomes to prove $\exist y \exist z [h(x_0,y)
\land h(x_0, z) \land y \ne z]$.)
\item $\exist y [h(x_0,y)]$ (Univ. Spec., 1 , $x=x_0$)
\item Choose $y_0 $ so that $h(x_0,y_0)$ (Choice, 6)
\item $\exist z [h(x_0,z) \land h(y_0,z)]$ (3, U. S. ,
$x=x_0,y=y_0$)
\item Choose $z_0$ so that $h(x_0,z_0) \land h(y_0,z_0)$.
(Choice, 8; Note that our goal is to prove three things:
$h(x_0,z_0), h(x_0,y_0)$ and $y_0 \ne z_0$; only this
last hasn't been shown.)
\item Assume $y_0 =z_0$ (assumption, to prove $y_0 \ne z_0$ by
contradiction)
\item $h(y_0, y_0)$ (9, substitution)
\item $\lnot h(y_0,y_0)$ (2, US $x=y_0$)
\item From this contradiction, our assumption was incorrect,
so $y_0 \ne z_0$ (10,11,12)
\item $h(x_0,y_0) \land h(x_0,z_0) \land y_0 \ne z_0$ (7,9,
13)
\item $\exist y \exist z [(h(x_0, y) \land h(x_0, z) \land
y \ne z]$ (14, existence by example, $y=y_0,z=z_0$)
\item Since $x_0$ was arbitrary,
$\forall x \exist y \exist z [h(x,y) \land h(x,z) \land y \ne
z]$. (14, Univ. Gen.)
\end{enumerate} 

\end{enumerate}

\end{document}