\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{1, Fri.}                    % !! start the paper

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

\begin{problem} Albert \& Ronitt announce that they plan a surprise 6.042
quiz next week.  Their students wonder if the quiz could be next Friday.
The students realize that it obviously cannot, because if it hadn't been
given before Friday, everyone would know that there was only Friday left on
which to give it, so it wouldn't be a surprise any more.

So the students ask whether Albert \& Ronitt could give the surprise quiz
Thursday?  They observe that if the quiz wasn't given \emph{before}
Thursday, it would have to be given \emph{on} the Thursday, since they
already know it can't be given on Friday.  But having figured that out, it
wouldn't be a surprise if the quiz was on Thursday either.  Similarly, the
students reason that the quiz can't be on Wednesday, Tuesday, or Monday.
Namely, it's impossible for Albert \& Ronitt to give a surprise quiz next
week.  All the students now relax having concluded that Albert \& Ronitt
must have been bluffing.

And since no one expects the quiz, that's why, when Albert \& Ronitt give
it on Tuesday next week, it really is a surprise!

What do you think is wrong with the students' reasoning?

\solution{The basic problem is that ``surprise'' is not a mathematical
concept, nor is there any generally accepted way to give it a mathematical
definition.  The ``proof'' above assumes some plausible axioms about
surprise, without defining it.  The paradox is that these axioms are
inconsistent.  But that's no surprise \texttt{:-)}, since---mathematically
speaking---we don't know what we're talking about.

Mathematicians and philosophers have had a lot more to say about what might
be wrong with the students' reasoning, (see Chow, Timothy Y.
\href{http://theory.lcs.mit.edu/classes/6.042/spring02/handouts/surprise-paradox.pdf}
{\emph{The surprise examination or unexpected hanging paradox}}, American
Math. Monthly (January 1998), pp.41--51.)}

\end{problem}

\instatements{\newpage}

\begin{problem}  %source: spring00 ps1

Identify the antecedents and conclusions of each of the following
deductions and translate them into propositional logic notation using
logical operators:
\begin{eqnarray*}
\conj & \eqdef & \text{AND},\\
\disj & \eqdef & \text{OR},\\
\neg & \eqdef & \text{NOT},\\
\implies & \eqdef & \text{IMPLIES},\\
\bicond & \eqdef & \text{IFF (if and only if)}
\end{eqnarray*}

This may require that you ``pin down'' a statement that could be
interpreted in more than one way.

Identify which of the deductions are sound ones.

\begin{problemparts}

\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:
\Rule{\neg (J \conj M),\quad M \smor C, \quad J}{C}
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 sound.  
}


\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:
\Rule{B \disj F, \quad C \disj P, \quad \neg (F \conj C)}{\neg (B \conj P)}
where 
\begin{eqnarray*}
        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{eqnarray*}
This deduction is not sound.  For example, $B \conj \neg F \conj C \conj
P$ is consistent with the antecedents 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} instead of inclusive-or.  So our
antecedent about the main course would then read $B \oplus F$ or,
equivalently, $(B \disj F) \conj \neg (B \conj F)$.  The antecedent about
the vegetable could be changed similarly.  The deduction is still unsound
in 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:
\Rule{J \disj B, \quad \neg S \disj \neg B}{J \disj \neg S}
where
\begin{eqnarray*}
        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{eqnarray*}
This deduction is sound.  It is an example of a common ``cancellation'' or
\emph{cut} rule that lets us get rid of the proposition $B$ in the
conclusion.}

\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:
\Rule{(S \conj H) \disj (E \conj \neg H)}{\neg (S \conj E)}
where 
\begin{eqnarray*}
        S & \eqdef& \mbox{``Sales will go up.''} \\
        H & \eqdef& \mbox{``The boss will be happy.''} \\
        E & \eqdef& \mbox{``Expenses will go up.''} 
\end{eqnarray*}
This deduction is not sound.  For example, $S \conj E \conj H$ is consistent
with the antecedent but not with the conclusion.}

\end{problemparts}

\end{problem}

\instatements{\newpage}

\begin{problem}
Boolean logic comes up in digital circuit design using the convention that
\true\ corresponds to 1 and \false\ to 0.  For example, suppose we want to
describe a circuit with $n+1$ inputs $a_n,a_{n-1},\dots, a_1,a_0$ which
are the $n+1$ bits of the binary representation of an integer, $k$,
between 0 and $2^{n+1} - 1$.  We want outputs $o_{n+1},o_n,\dots,o_1,o_0$
to be the bits of $k+b$ where $b$ is a single bit.

For example, for $n=1$, the formulas
\begin{align*}
o_0 & \eqdef a_0 \oplus b\\
c_1 & \eqdef a_0 \land b  & \text{the carry into column 1}\\
o_1 & \eqdef c_1 \oplus a_1\\
c_2 & \eqdef c_1 \land a_1   & \text{the carry into column 2}\\
o_2 & \eqdef c_2
\end{align*}
do the job.  Here $\oplus$ is the ``mod 2 sum'' operator: $a
\oplus b$ is 1 iff $a+b$ is even.

\bparts

\ppart Generalize the example above for any $n \geq 0$.  That is, give
simple formulas for $o_{i}$ and $c_{i}$ for $0 \leq i \leq n+1$.

\solution{
Define
\begin{align*}
o_0     & \eqdef a_0 \oplus b,\\
c_{i+1} &\eqdef a_i \land c_i & \text{for } 0 \leq i \leq n,\\
o_{i+1} & \eqdef c_{i+1} \oplus a_{i+1} & \text{for } 0 \leq i < n,\\
o_{n+1} & \eqdef c_{n+1}.
\end{align*}
}

\ppart Write similar definitions for the $n+1$ bits of the sum of two
binary numbers $a_n,a_{n-1},\dots, a_1,a_0$ and $b_n,b_{n-1},\dots,
b_1,b_0$.

\solution{Define
\begin{align*}
o_0     & \eqdef a_0 \oplus b_0,\\
c_{i+1} & \eqdef (a_i \land b_i) \lor (a_i \land c_i) \lor (b_i \land c_i)
                & \text{for } 0 \leq i \leq n,\\
o_{i+1} & \eqdef c_{i+1} \oplus a_{i+1} \oplus b_{i+1}
                & \text{for } 0 \leq i < n,\\
o_{n+1} & \eqdef c_{n+1}.
\end{align*}
}

\ppart How many Boolean operations does your system use to calculate the sum?
\solution{
The scheme above uses $3(n+1)$ AND'S, $2n+1$ MOD-2-SUMS and $2(n+1)$
OR's for a total of $7n+5$ operations.
}

\eparts

\end{problem}

\end{document}

