\documentclass[12pt]{article}
\textwidth = 6.5 in
\textheight = 9 in
\oddsidemargin = 0.0 in
\evensidemargin = 0.0 in
\topmargin = 0.2 in
\headheight = 0.0 in
\headsep = 0.0 in
\parskip = 0.2in
\parindent = 0.0in

\usepackage{amsmath,amssymb,enumerate}
%\def\rmdefault{bch} % Use Charter for main text font.

% =========================================================
\begin{document}

\begin{center}
{\LARGE
\textbf{CS 173: Discrete Structures, Fall 2009}
\\
\textbf{Homework 2}
\\[1ex]}

This homework contains 6 problems worth a total of 50 points.
It is due on Friday, September 11th at noon.   For this week, homeworks
can be turned in at class or, after class, at Margaret's office
(3214 Siebel).   If the door is shut, push the homework under the door.
This is a temporary arrangement until they work out the last few
details so we can use the newly installed dropboxes.  

\end{center}


\bigskip\hrule

\begin{enumerate}

%----------------------------------------------------------------------
\item \textbf{[3 points] Translating notation into English}

Suppose we define:

\begin{itemize}
\item{} $C(x)$ is ``x grew up in Chicago.'' 
\item{} $D(x)$ is ``x drives well.''
\item{} $M(x)$ is ``x is taking CS 173.''
\item{} $K(x)$ is ``x is taking CS 225.''
\item{} $S$ is the set of all students.
\end{itemize}

Translate the following into English:  

$$\forall y \in S, (M(y) \wedge \neg K(y)) \rightarrow (D(y) \vee \neg C(y))$$

%----------------------------------------------------------------------
\item \textbf{[9 points] Proofs with propositional equivalences}

Prove that the following pairs of expressions are logically equivalent,
using the known equivalences given in Table 6 of Rosen, plus the fact
that $p \rightarrow q$ is logically equivalent to $\neg p \vee q$.   
(Table 6 is reproduced on
the handout for lecture 4.)   

\begin{enumerate}
\item $(p\rightarrow q) \vee (p \rightarrow r)$ and $p \rightarrow (q \vee r)$
\item $\neg p \rightarrow (q \rightarrow \neg r)$ and
$r \rightarrow (q \rightarrow p)$
\item $(\neg p \vee q) \wedge (r \vee \neg q) \wedge (p \vee q)$
and $q \wedge r$
\end{enumerate}

Be picky about how you apply the known equivalences, e.g. use an
explicit step to simplify double negations, notice that
the distributive
laws as written
in the table require the item being distributed to come before the
complex item its being distributed over.
However, if you
need to rearrange your expression using a sequence of applications of
the commutative and associative laws, you don't have to show all the
intermediate steps.   Just do the rearrangement in one step justified
by something like ``commutative/associative laws.''


\newpage

%----------------------------------------------------------------------
\item \textbf{[8 points] Negating things}

Give the negation of the following logical expressions, using
logical equivalences to move the ``not'' operators onto the smallest
elements possible.  For example,
to negate $\forall x, [P(x) \to Q(x)]$, we first negate the whole thing
$\neg \forall x [P(x) \to Q(x)]$, then convert this to
$\exists x [\neg (P(x) \to Q(x))]$, and
finally to $\exists x [P(x) \land \neg Q(x)]$.
(For simplicity, we've omitted the domains for the quantified variables.)

\begin{enumerate}

\item $\forall x [\neg M(x) \to Q(x)]$

\item $\exists y [P(y) \land (\neg M(y) \lor R(y))]$

\item $\exists x [\neg (P(x) \land Q(x)) \lor (F(x) \to P(x)]$

\item $\forall z [(P(z) \land \neg M(z)) \to \neg P(z)]$

\end{enumerate}

%----------------------------------------------------------------------
\item \textbf{[10 points] Direct proof and disproof}

\begin{enumerate}

\item 
Prove the following claim:  

\begin{quote}
Claim:  For any integer $k$, if $k$ is odd, then $k^3$ is odd.
\end{quote}

\item 
Disprove the following claim, by giving a concrete counter-example.
(You must use a specific counter-example.   Don't try to write a general
or abstract story about why this equation can't possibly hold.)

\begin{quote}
Claim: For any integers $p$ and $q$, $(p+q)^2 = p^2 + q^2$.
\end{quote}

\end{enumerate}

%----------------------------------------------------------------------
\item \textbf{[10 points] Another direct proof}

Suppose that $(x,y)$ and $(p,q)$ are two intervals of the real line.
Let's define $(x,y)$ to {\it contain} $(p,q)$ if and only if 
$x \le p$ and $q \le y$.
Using this definition, prove the following claim:

\begin{quote}
Claim: For any intervals of the real line $(a,b)$, $(c,d)$, and $(e,f)$,
if $(a,b)$ contains $(c,d)$ and 
$(c,d)$ contains $(e,f)$, then $(a,b)$ contains $(e,f)$.
\end{quote}

%----------------------------------------------------------------------
\item \textbf{[10 points] Son of direct proof}

\begin{enumerate}

\item Prove the following claim:

\begin{quote}
Claim 1: For any integer $k$, if $k > 4$ then $2k+1 < k^2$.
\end{quote}

\item Using your result from part (a), prove the following claim:

\begin{quote}
Claim 2: For any integer $k$, if  $k > 4$ and $k^2 < 2^k$, then 
$(k+1)^2 < 2^{k+1}$.
\end{quote}

\end{enumerate}

Be sure to show the intermediate steps of your algebra carefully, working
from the facts you are given towards the facts you are trying to prove.
However, you don't have to write justifications for steps that are easy
high-school algebra (i.e. most steps in these examples).


%----------------------------------------------------------------------
\end{enumerate}
\end{document}

