\documentclass[12pt]{article}

\begin{document}

\centerline{Homework 2, MORALLY Due Feb 11}
\newcommand{\implies}{\Rightarrow}

\centerline{\bf WARNING: THIS HW IS TWO PAGES LONG!!!!!!!!!!!!!!!!!}

\newif{\ifshowsoln}
\showsolntrue % comment out to NOT show solution inside \ifshowsoln and \fi blocks.

\begin{enumerate}

\item
(25 points)
\begin{enumerate}
\item
(15 points)
Write a truth table with 3 inputs and 2 outputs for the following function:

$f(x,y,z) = x+y+z \pmod 3$.

\item
(10 points)
Write a circuit for $f$ using AND, OR, and NOT using the method shown in class
(do not simplify- that would make it harder for the TA's to grade!)

\end{enumerate}

\item
(25 points)
\begin{enumerate}
\item
(10 points)
Use truth table so show that 

$$\neg (p \wedge q \wedge r) \equiv \neg p \vee \neg q \vee \neg r$$

(This is called {\it DeMorgan's law on three variables}.)

\item
(15 points)
Consider the statement:

$$\hbox{ for all $n$ }[\neg (p_1 \wedge \cdots \wedge p_n) \equiv \neg p_1 \vee \cdots \vee \neg p_n]$$

Prove it. Note that you cannot use Truth Table since we want it for all $n$.
Do not use Induction (later when we learn induction we will do that).
Use reasoning about what the truth table for both sides must look like.
\end{enumerate}

\centerline{GO TO NEXT PAGE FOR MORE PROBLEMS!!!!!!!!!!!!!}

\newpage

\item
(25 points -- 5 points each)
For each of the following statements write the negation without using any negations signs.
\begin{enumerate}
\item
$x\le 4$
\item
$1<x<2$
\item
$x_1 < x_2 < \cdots < x_n$ 
\item
$x\le 5$ OR $x\ge 10$
\item
$x\le 5$ AND $x\ge 10$ 
\end{enumerate}


\item
(25 points)
Look up the lyrics to the song {\it If this isn't love} from the musical Finian's Rainbow.
(You might also want to listen to it on  You Tube.)
Assume the song is true. 
For each simple proposition in the song assign a letter (try to make it mnemonic).
For example

$L$ is {\it This is Love}

so

$\neg L$ is {\it This isn't Love}

and

$W$ is {\it the whole world is crazy}

Write down a proposition that expresses what happens if this isn't love.
It will start:

$$\neg L \implies (W \wedge \hbox{ other stuff} ).$$

(Note- one of the parts of the sentence doesn't make sense to me,
we'll discuss later.)

\end{enumerate}
\end{document}