\problem Cast the following into propositional symbols, and verify or
refute:\\

{\em \noindent If Superman were able and willing to prevent evil, he would do
  so. If Superman were unable to prevent evil, he would be impotent.
  If he were unwilling to prevent evil, he would be malevolent.
  Superman does not prevent evil. If Superman exists, he is neither
  impotent nor malevolent. Therefore, Superman does not exist.}\\


\problem {\bf (The Mystery)} The 6.042 mascot, Theory Pig, was
recently found squished under a pile of course handouts.  Fortunately,
Theory Pig is okay and is getting his stuffing sorted out.  However,
he demands that the culprit or culprits be found.  The only clue is a
crumpled paper found nearby scrawled over with logic notation:

\begin{enumerate}
\item Domain of discourse $= \{ Duran, Khurshid, Lehman, Gould, Sherman \}$.
\item $G(x) = \text{true}$ if and only if $x$ is guilty.
\item $(\exists x G(x)) \wedge (\exists x (\neg G(x)))$
\item $(G(\text{Duran}) \vee G(\text{Khurshid})) \rightarrow
                \neg G(\text{Sherman})$
\item $\neg (G(\text{Khurshid}) \wedge G(\text{Lehman}))$
\item $\neg G(\text{Sherman}) \rightarrow (\exists x \exists y (x \neq
y \wedge G(x) \wedge G(y))$

\item $(G(\text{Duran}) \rightarrow G(\text{Sherman})) \wedge
        (G(\text{Sherman}) \rightarrow G(\text{Duran}))$
\item $\neg (G(\text{Lehman}) \wedge G(\text{Gould}))$
\end{enumerate}

Who squished Theory Pig?  State your answer and sketch your deductive
process.


\problem Now you are given 12 identical looking balls, and told that
one of them is of different weight from the other 11, but you don't 
know in advance whether it is heavier or lighter. Can you
find the ball that is of different weight using only 3 weighings?

\solution{
Yes.

Step 1. Divide into groups of 4 balls. Place two of these groups
on two pans.

Two possible outcomes: 
\begin{enumerate}
\item Equal. So the 8 balls that were weighed must be of the same weight,
label them N (for ``normal'') and one of the other 4 is of different weight,
call them D.  

  Step 2. Place 3 D balls on one side and 3 N balls on the other side for
the second weighing.
Three possible outcomes again:
\begin{enumerate}
 \item Equal. The remaining D must be the ball of different weight.
 \item DDD side is heavier. So the ball of different weight is among these
three and heavier. Now we can finish in one more weighing using
the approach done in the tutorial.
 \item DDD side is lighter. Similar to previous case.
\end{enumerate}

\item Not Equal.  Call the heavier side balls H and the lighter side balls L.
Then there are 4 H's , 4 L's and 4 N's (the 4 that we didn't weigh are of
the same weight).

  Step 2. Place 3 H's and 1 L on one side and 1 H and 3 N's on the other side
for the second weighing. There are 3 possible outcomes:

\begin{enumerate}
\item Equal. The ball of different weight is among the remaining 3 L's
and is lighter. We can find it in one more weighing.

\item 3 H's , 1 L side is heavier. Then one of the three H's must be
heavier than the rest. We can find it in one more weighing.

\item 3 H's , 1 L side is lighter. Then either the L on this side is
lighter than the rest or the H on the other side is heavier than the rest.
We can compare one of them with an N ball and find the ball of different
weight!
\end{enumerate}

\end{enumerate}
}
\problem Use induction on $n$ to prove that for all $n \geq 0$, there
are $2 n^2 + 2n + 1$ solutions to the inequality $|x| + |y| \leq n$,
where $x$ and $y$ are integers.



\problem Find a formula for $\sum_{i=1}^n\frac{1}{i^2+1}$ and prove it
correct by induction.


\problem Ugh the caveman recently invented \emph{multiplication}, a
near new operation on the natural numbers.  He defined it in terms of
addition, which he understands very well:
\begin{itemize}
\item $(\forall n) n\cdot 0=0$
\item $(\forall n,m) n\cdot(m+1)=n\cdot m+n$.
\end{itemize}
Ugh has some conjectures about this new operation.  Help prove them,
using {\bf only} known facts about {\bf addition} and the proof
techniques we have studied.

\begin{problemparts}
\ppart Distributivity: $(\forall a,b,c)\ a(b+c)=ab+ac$
\ppart Associativity: $(\forall a,b,c)\ a(bc)=(ab)c$
\ppart Commutativity: $(\forall a,b)\ ab=ba$.  (This one is tricky;
you might want to prove and use the following lemma: $(\forall k)
(k+1)b=kb+b$.
\end{problemparts}


% Local Variables: 
% mode: latex
% TeX-master: t
% End: 
