\problemdata     
{proofs-5}           
{logic}              
{}              
{S01 PS-1} 		
{S01 Karger}        	

\begin{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, $\neg T \wedge R$ 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.
\solution{

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.
\solution{
\medskip

 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.
\solution{

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$.   
}

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

\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.
\solution{



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}
\end{problem}
