\documentclass[12pt]{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{\reading}{        % !! Redefine this week's reading
Check the course website, on the 
\href{http://theory.lcs.mit.edu/classes/6.042/spring04/handouts}{handouts page}, 
under 
\href{http://theory.lcs.mit.edu/classes/6.042/spring04/handouts/\#week1}{``Week 1''}.
}


\begin{document}
\problemset{1}                  % !! Start the problem set with its number

% Source: Rosen 

Do the following problems from the
\href{http://theory.lcs.mit.edu/classes/6.042/spring04/courseinfo#textbooks}
{Rosen text}.

\begin{problem}                 % !! use the ``problem'' environment 

\bparts
\ppart 1.1.18.

\solution {\mbox{}\\
\begin{itemize}
\item[(a)]
If I remember to send you the address, 
then you will have sent me an e-mail message.
\item[(b)]
If you were born in the United States, 
then you are a citizen of this country.
\item[(c)]
If you keep your textbook, 
then it will be a useful reference in your future courses.
\item[(d)]
If the Red Wings' goalie plays well, 
then they will win the Stanley Cup.
\item[(e)]
If you get the job, 
then you will have had the best credentials.
\item[(f)]
If there is a storm, 
then the beach erodes.
\item[(g)]
If you logged on to the server, 
then you had a valid password.
\end{itemize}
}

\ppart 1.1.26.

\solution{\mbox{}\\
\begin{itemize}
\item[(a)]
\begin{tabular}[t]{c||c}
$p$ & $p \oplus p$  \\ \hline\hline
F   & F             \\ \hline
T   & F             
\end{tabular}

\item[(b)]
\begin{tabular}[t]{c||c}
$p$ & $p \oplus \neg p$ \\ \hline\hline
F   & T                 \\ \hline
T   & T
\end{tabular}

\item[(c)]
\begin{tabular}[t]{c|c||c}
$p$& $q$ & $p \oplus \neg q$ \\ \hline\hline
F  & F   & T                 \\ \hline
F  & T   & F                 \\ \hline
T  & F   & F                 \\ \hline
T  & T   & T
\end{tabular}

\item[(d)]
\begin{tabular}[t]{c|c||c}
$p$ & $q$ & $\neg p \oplus \neg q$ \\ \hline\hline
F   & F   & F                      \\ \hline
F   & T   & T                      \\ \hline
T   & F   & T                      \\ \hline
T   & T   & F
\end{tabular}

\item[(e)]
\begin{tabular}[t]{c|c||c}
$p$ & $q$ & $(p \oplus q) \lor (p \oplus \neg q)$ \\ \hline\hline
F   & F   & T                                     \\ \hline
F   & T   & T                                     \\ \hline
T   & F   & T                                     \\ \hline
T   & T   & T
\end{tabular}

\item[(f)]
\begin{tabular}[t]{c|c||c}
$p$ & $q$ & $(p \oplus q) \land (p \oplus \neg q)$ \\ \hline\hline
F   & F   & F                                      \\ \hline
F   & T   & F                                      \\ \hline
T   & F   & F                                      \\ \hline
T   & T   & F
\end{tabular}

\end{itemize}
}


\ppart 1.1.58.

\solution{
Let $K$, $V$, $A$, $H$, and $R$ be proposition variables representing
the statements that Kevin, Vijay, Abby, Heather, or Randy is chatting,
respectively. We know that 
$$
K\lor H,                             \quad
R\oplus V,                           \quad
A\implies R,                         \quad   
(V\land K) \lor (\neg V\land\neg K), \quad
H \implies A \land K. 
$$

From the first and last compound propositions, we can conclude
$K$. Because, if $H$, then we know $K$ from the last equation; and if
$\neg H$, then we know $K$ from the first equation. 

The fourth compound proposition implies $V$ because we know
$K$. We can now conclude $\neg R$ from the second proposition.

The contrapositive of the third proposition implies that $\neg A$, and 
finally the contrapositive of the last proposition implies $\neg H$.

So we have: $K$, $V$, $\neg R$, $\neg A$, $\neg H$.
}

\eparts
\end{problem} 


% \begin{gather*}
%  X = asdasdas
% \\
%  Y = sdfs df dfsdfsd sdf sdf
% \\
%  Z = sdfsdfsdf
% \end{gather*}
% 
%\begin{gather}
% X = asdasdas
%\\
% Y = sdfs df dfsdfsd sdf sdf
%\\
% Z = sdfsdfsdf
%\end{gather}
%%%%%%%%%
% \begin{align*}
% X &= asdasdas
%\\
% Y &= sdfs df dfsdfsd sdf sdf
%\\
% Z &= sdfsdfsdf
%\end{align*}
%
%\begin{multline*}
%X = 1 + 2 + 3 + 4 + 1 + 2 + 3 + 4 + 1 + 2 + 3 + 4 + 1 + 2 + 3 + 4 + 1
%\\
%+ 4 + 1 + 2 + 
%3 + 4 + 1 + 2 + 3 + 4
%\\
%+ 4 + 1 + 2 + 
%3 + 4 + 1 + 2 + 3 + 4
%\\
% + 1 + 2 + 3 + 4 + 1 + 2 + 3 + 4 
%\end{multline*}








% Source: Rosen 
\begin{problem}                 % !! use the ``problem'' environment 
\bparts
\ppart 1.2.12.  
\solution{
The only way the statement can be false is if $\neg p \land (p \implies q)$ is
true and $\neg q$ is false. Indeed this is possible with: $\neg p$ and $q$.
In this case, $\neg q$ is clearly false, however the first statement is 
true (recall from the first lecture that a false statement can imply anything).
}

\ppart 1.2.36.
\solution{
For every row of the truth table that is true, create a single conjunction
that is true iff the particular values of the $n$
propositional variables for that row hold. Note that this conjunction will
be the conjunction of $n$ elements. The disjunction of all such
compound statements will exactly replicate the given truth table. 
For example: 
\begin{center}
\begin{tabular}{c|c|c||c}
$p$ & $q$ & $r$ & result\\ \hline\hline
F   & F   & F   & F     \\ \hline
F   & F   & T   & F     \\ \hline
F   & T   & F   & T     \\ \hline
F   & T   & T   & T     \\ \hline
T   & F   & F   & F     \\ \hline
T   & F   & T   & T     \\ \hline
T   & T   & F   & F     \\ \hline
T   & T   & T   & F
\end{tabular}
\end{center}
This truth table becomes: 
$
(\neg p \land q \land \neg r) \lor
(\neg p \land q \land r)      \lor 
(p \land \neg q \land r)
$.
}

\ppart 1.2.54(c).

\solution{
The following sets of values satisfy the statement: 
$$\neg p, \neg q, s, r$$ 
$$p, q, s, \neg r$$
$$\neg p, q, \neg s, \neg r$$

These were found by trying all 4 combinations of values for $p$ and 
$q$ and then assigning values to $s$ and $r$ as the formula dictated.

}

\eparts
\end{problem}


% $\bigl( \Bigl( \biggl( \Biggl( $



% Source: Rosen 
\begin{problem}                 % !! use the ``problem'' environment 
\bparts
\ppart 1.3.10(e).

\solution{
$
\bigl( \exists x C(x) \bigr) \land    
\bigl( \exists x D(x) \bigr) \land 
\bigl( \exists x F(x) \bigr)
$.
}

\ppart 1.3.20(e).

\solution{
See solutions to the in class problems given out on Wednesday February 11th.

\begin{multline*}
$$
\bigl( 
	\neg P(-5) \lor 
	\neg P(-3) \lor 
	\neg P(-1) \lor 
	\neg P( 1) \lor 
	\neg P( 3) \lor 
	\neg P( 5)
\bigr) 
\land 
\\
\Bigl( 
	\bigl(-5 < 0 \implies P(-5) \bigr) \land  
	\bigl(-3 < 0 \implies P(-3) \bigr) \land  
	\bigl(-1 < 0 \implies P(-1) \bigr) \land
\\  
	\bigl(1 < 0 \implies P(1) \bigr) \land  
	\bigl(3 < 0 \implies P(3) \bigr) \land  
	\bigl(5 < 0 \implies P(5) \bigr)
\Bigr)
$$
\end{multline*}

Note that this solution isn't simplified at all, but is left in this
form to illustrate the literal translation of the quantifiers.

}

\ppart 1.3.46.
\solution{
This proof is taken from the solutions to the in class problems given out
on February 11th.

We describe a \emph{counter model}, that is, a model where
\begin{enumerate}
\item\label{az} 
$\forall x\ [P(x) \lor Q(x)]$ is true, but
\item\label{ax} 
$\forall x\ P(x) \lor \forall x\ Q(x)$ is not true.
\end{enumerate}
Namely, let the domain consist of just the two numbers $e$ and $\pi$:
$$
D \eqdef \set{e,\pi},
$$
and define
\begin{align*}
P(x) &\eqdef [x = \pi],
\\
Q(x) &\eqdef [x = e].
\end{align*}
Since $(x = e) \lor (x = \pi)$ is true if $x$ is $\pi$ and also if $x$
is $e$, we conclude that $(x = e) \lor (x = \pi)$ holds for all $x\in D$.
This proves~\ref{az}.

On the other hand, $Q(x)$ is not true for $x=\pi$, and therefore, 
$\forall x\ Q(x)$ is not true.  Similarly, $\forall x\ P(x)$ is not
true, so their disjunction (or) is not true, proving~\ref{ax}.
}

\ppart 1.3.58.
\solution{\mbox{}\\
\begin{itemize}
\item[(a)]
$\forall x \bigl( P(x) \implies \neg S(x) \bigr)$
\item[(b)]
$\forall x \bigl( R(x) \implies S(x) \bigr)$
\item[(c)]
$\forall x \bigl( Q(x) \implies P(x) \bigr)$
\item[(d)]
$\forall x \bigl( Q(x) \implies \neg R(x) \bigr)$
\item[(e)]
Yes, (d) does follow. From (c) and (a), we know that my poultry are not
willing to waltz. Then, turning (b) into it's contrapositive implies
that my poultry are not officers.
\end{itemize}
}
\eparts
\end{problem} 


\instatements{\newpage}

% Source: Rosen 
\begin{problem}                 % !! use the ``problem'' environment 
\bparts
\ppart 1.4.28, parts~(a), (b), (e), and~(f).

\solution{

\begin{itemize}
\item[(a)]
True. Every number has a square.
\item[(b)]
False. Not every number has a square root (negative numbers don't). 
\item[(e)]
True. Every number except for 0 has a multiplicative inverse.
\item[(f)]
False. There is no ``universal'' multiplicative inverse.
\end{itemize}
}


\ppart 1.4.34(c).  
For this part, your universe of discourse should be the set of
students in the class; in addition, the only predicates that you may
use are  
\begin{itemize}
\item
the predicate ``$x=y$'', meaning (as usual) that ``$x$ and $y$ are
the same (student)'',  and 
\item 
the predicate $E(x,y)$, meaning that ``$x$ has sent e-mail to $y$''.
\end{itemize}

\solution{

A good way to begin tackling this problem is by trying to translate parts of
the sentance. Begin by ignoring the negation (very easy to add in later).

Next, try to just translate one student has e-mailed 2 other students.

\begin{equation*}
\exists x \exists y \exists z \bigl(x\neq y \land x \neq z \land y \neq z 
\land E(x, y) \land E(x, z) \bigr)
\end{equation*}

Now, we must think of a way to say that $x$ has not e-mailed more than 2
people. Assume that $x$, $y$, $z$ are as defined above.

\begin{equation*}
\forall q \bigl(q \neq x \land q \neq y \land q \neq z \implies 
\neg E(x, q) \bigr)
\end{equation*}
Or, perhaps in a simpler form:

\begin{equation*}
\forall q \bigl(E(x, q) \implies q = x \lor q = y \lor q = z \bigr)
\end{equation*}

The complete translation is as follows:
\begin{multline*}
\neg \Biggl( \exists x \exists y \exists z \biggl(x \neq y \land x \neq z \land y \neq z \land
E(x, y) \land E(x, z) \land
\\
\Bigl(\forall q \bigl(E(x, q) \implies  q = z \lor q = y \lor q = x \bigr) \Bigr) \biggr) \Biggr) 
\end{multline*}

The English translation of the NEGATION of that statement is: There exists a
student who has e-mailed exactly two distinct other people in the class, 
and possibly herself, but no one else in the class.

}

\ppart 1.4.50.
\solution{  
To say that $\lim_{n\to\infty} a_n = L$ is to say that the numbers of 
the sequence $a_1,a_2,a_3,\dots$ can eventually get as close to
$L$ as we want them, and then stay so close to $L$ for ever. In other
words, no matter how small we want their distance from $L$ to be, the
numbers will eventually get within that distance and stay so close to
$L$ for ever after that. 

One way to express this formally is the following:
$$
(\forall\epsilon>0)
(\exists N)
(\forall n>N)
\bigl(
	|a_n - L| < \epsilon
\bigr).
$$
Again, no matter how small we require the distance ($\epsilon$) of our
numbers from $L$ to be, there is an index $N$ in the sequence, after
which ($\forall n>N$) all numbers will get within that particular
distance from $L$ ($|a_n-L|<\epsilon$). 
}

%  \ppart
%  The English is as follows. There exists no real number, $L$ such
%  that for every positive real number $\epsilon$, there is a positive
%  integer N such that $|a_n - L| < \epsilon$ whenever $n > N$. 
%  THIS NEEDS TO BE PROOFREAD
%  This can be expressed as follows: $\nexists L \in \reals (\forall
%  \epsilon \in \reals \exists N \in {\mathbb{N}^+} 
%  (\forall n>N (|a_n - L|)))$
%  \eparts

\eparts
\end{problem} 


% Source: Rosen 
\begin{problem}                 % !! use the ``problem'' environment 
1.5.22(b).  And don't worry about the (unimportant) distinction between
    ``indirect proof'' and ``proof by contradiction.''
\end{problem} 

\solution{                      % !! use \solution
 Assume $n$ is odd. Thus, $3n$ is odd because the product of two odd numbers is odd. We see $3n + 2$ must be
 odd because the sum of an odd number ($3n$) and an even number (2) is always odd. This contradicts the fact
 $3n + 2$ is even.
}

\begin{problem}
1.6.16.
\end{problem}

\solution{                      % !! use \solution
  We solve this by proving the contrapositive. Suppose $A \neq B$. 
Thus, there must be some element, $x$ that is
in one set and not the other. Without Loss Of Generality (WLOG), 
assume that there is an $x$ such that $x \in A$ and $x \notin B$. Then $\{x\} \in P(A)$, 
  but $\{x\} \notin P(B)$. Thus, $P(A) \neq P(B)$. 

Without Loss Of Generality is a common principle used in proofs.
Because we know nothing about sets $A$ and $B$, other than that
one of the sets must have an element $x$ that is not in the other
set, we can name the set that has that element $A$.  
}

% Source: Rosen 
\begin{problem}                 % !! use the ``problem'' environment 
1.7.14(d).
\end{problem} 

\solution{                      % !! use \solution
  We prove this by contradiction. Assume $(A - C) \cap (C - B)$ is nonempty and contains some element $x$.
  We see $x \in (C - B)$ which implies $x \in C$ and $x \notin B$. Similarly, we see $x \in (A - C)$ which implies
  $x \in A$ and $x \notin C$. The conclusions $x \in C$ and $x \notin C$ are contradictory, thus
  $(A - C) \cap (C - B)$ is empty. 
}

\end{document}                            





