\documentclass[11pt,twoside]{article}    
\usepackage{latex-macros/course}% !! use the macros 

%\backwardscompatibility        % !! use for backwards compatibility
%\showsolutions                 % !! use to force solutions & skip query
%\hidesolutions                 % !! use to force no solutions & skip query

\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}

\begin{document} 
\inclassproblems{1F}            % !! start the paper

\iffalse

\begin{problem}   %source: spring00 ps1

Suppose $x$ is a real number.  Prove \textbf{by cases} that there is a
real $y$ such that $\dfrac{y+1}{y-2}=x$ if and only if $x \ne 1$.

\solution{

We consider the cases $x \neq 1$ and $x = 1$ separately. 
\begin{description}

\item[Case 1 ($x \neq 1$): ]
We need to prove that there exists $y \in \reals$ such that
$\dfrac{y+1}{y-2}=x$.  In particular, consider $y = \dfrac{2x+1}{x-1}$ (derived
by algebraic manipulation), which is a well-defined real number because $x \neq
1$.  Then:  
\begin{eqnarray*}
\frac{y+1}{y-2}  & = & \frac{((2x+1)/(x-1))+1}{((2x+1)/(x-1))-2} \\
        & = & \frac{\dfrac{2x+1 + (x-1)}{x-1}}{\dfrac{2x+1-2(x-1)}{x-1}}\\
        & = & \frac{\dfrac{3x}{x-1}}{\dfrac{2x+1-2x+2}{x-1}}\\
        & = & \frac{3x}{3}\\
        & = & x.
\end{eqnarray*}

Therefore, by \emph{existential generalization}, $\exists y \in \reals$
such that $\dfrac{y+1}{y-2} = x.$

\item[Case 2 ($x = 1$): ]
We need to prove that no $y \in \reals$ exists such that $\dfrac{y+1}{y-2}=x$. 
Suppose, for contradiction, that such a $y$ did exist.  Then:
\begin{align*}
\frac{y+1}{y-2} = x 
        &\equivalent \;\; \frac{y+1}{y-2} = 1 
                & \text{(because $x = 1$)} \\
        &\:\implies \;\; y+1 = y-2 
                & \text{(multiply both sides by $y-2$)} \\
        &\equivalent \;\; 1 = -2 
                & \text{(subtract $y$ from both sides)},
\end{align*}
a contradiction.  Therefore our supposition is wrong, 
and there is no $y$ such that $\dfrac{y+1}{y-2}=x$. 

\end{description}
}
\end{problem}
\fi


\begin{problem}   Are the following specifications\footnote{Rosen, Exercise 1.1.36}
consistent?

\begin{enumerate}

\item If the file system is not locked, then

   \begin{enumerate}

   \item new messages will be queued.

   \item new messages will be sent to the messages buffer.

   \item the system is functioning normally, and conversely.

   \end{enumerate}

\item  If new messages are not queued, then they will be sent to
the messages buffer.

\item  New messages will not be sent to the message buffer.

\end{enumerate}

To make sense of these confusing conditions, let's introduce four Boolean
variables.
\begin{eqnarray}
L  & \eqdef &   \text{file system locked}\label{1} \\
Q  & \eqdef &   \text{new messages are queued}\label{1a} \\
B  & \eqdef &   \text{new messages are sent to the message buffer}\label{1b} \\
N  & \eqdef &   \text{system functioning normally}\label{1c}
\end{eqnarray}

Begin by translating the parts of the specification into propositional
logic notation:
\begin{eqnarray*}
\land & \eqdef & \text{AND},\\
\lor & \eqdef & \text{OR},\\
\neg & \eqdef & \text{NOT},\\
\implies & \eqdef & \text{IMPLIES},\\
\bicond & \eqdef & \text{IFF (if and only if)}
\end{eqnarray*}

The specification is consistent if there is an assignment of truth values
to the variables that makes every expression true.

\solution{
\begin{eqnarray}
\neg L & \implies & Q \label{start}\\
\neg L & \bicond & N \label{N}\\
\neg Q & \implies & B \label{Q}\\
\neg L & \implies & B \label{L}\\
\neg B \label{B}
\end{eqnarray}


There are several ways to approach this problem.  One is to construct a
truth table with sixteen lines---one for each way of assigning truth
values to the four variables $L$, $N$, $Q$, and $B$.  For each line, we
could record the truth values of the five statements above obtained from
the system description.  If all five statements are true for some
assignment of truth values to the variables, then the system is
consistent; otherwise, the system is inconsistent.

We can avoid the cumbersome truthtable if we reason by cases.  Case 1: $B$
is true.  Then the last formula~(\ref{B}) is false, and the whole
specification is false.  Case 2: $B$ is false.  Now formulas~(\ref{Q})
and~(\ref{L}) can be true only if $Q$ and $L$ are true.
Since $L$ is true, formula~(\ref{N}) can be true only if $N$ is false.  Thus,
we have deduced that in order to be consistent, we must have
\begin{eqnarray*}
L       & = &   \text{true} \\
N       & = &   \text{false} \\
Q       & = &   \text{true} \\
B       & = &   \text{false}.
\end{eqnarray*}
From the way this assignment was constructed, we know it ensures that
formulas~(\ref{N})--(\ref{B}) are true.  So all that remains is to check
formula~(\ref{start}), and indeed it is also true under this assignment.

So the system is consistent.
}

\end{problem}



\begin{problem}  %source: spring00 ps1

Identify the hypotheses 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 many ways.  Determine
which are valid deductions and which are not.  If the deduction is
invalid, demonstrate a possible scenario in which all the hypotheses are
met but the conclusion is not.

\textbf{Note:} There are several ways to formalize many of these statements in
logical notation.  We will accept any \emph{reasonable} reading of the English.
Below, we show one such solution for each part.

\begin{problemparts}

\iffalse
\problempart 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{array}{c}
        \neg (J \land M) \\
        M \smor C \\ 
        J \\ \hline
        C
\end{array}\]
where 
\begin{eqnarray*}
J & \eqdef & \mbox{``Jane will win the math prize.''} \\
M & \eqdef & \mbox{``Pete will win the math prize.''} \\
C & \eqdef & \mbox{``Pete will win the chemistry prize.''}
\end{eqnarray*}
This deduction is valid.  
}
\fi

\problempart 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{
The deduction is:

$\begin{array}{c}
        B \lor F \\
        C \lor P \\
        \neg (F \land C) \\ \hline
        \neg (B \land P)
\end{array}$
where 
$\begin{array}{rcl}
        B & \eqdef & \mbox{``The main course will be beef.''} \\
        F & \eqdef & \mbox{``The main course will be fish.''} \\
        C & \eqdef & \mbox{``The vegetable will be corn.''} \\
        P & \eqdef & \mbox{``The vegetable will be peas.''} 
\end{array}$
This deduction is invalid.  For example, $B \land \neg F \land C \land
P$ is consistent with the hypothesis 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 \emph{exclusive-or}, \cf Rosen, p.5, instead of inclusive-or.  So our
hypothesis about the main course would then read $B \oplus F$ or,
equivalently, $(B \lor F) \land \neg (B \land F)$.  The hypothesis about the
vegetable could be changed similarly.  The deduction is still invalid with
this formalization.  }

\problempart 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
        $J \lor \neg S$
\end{tabular}
\quad where 
\begin{tabular}{l}
        $J \eqdef\mbox{``John is telling the truth.''}$ \\
        $B \eqdef\mbox{``Bill is telling the truth.''}$ \\
        $S \eqdef\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$.
}

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

\iffalse

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

\end{problemparts}

\end{problem}

\end{document}
