\documentclass[12pt,twoside]{article}
\usepackage{amsmath}
\usepackage{graphics}
\input{/pub/www/classes/6.042/fall99/inputs/macros-course}
\newcommand{\solution}[1]{\bigskip {\bf Solution:}\\ #1\bigskip}

\newcommand{\Nat}{\mathbb{N}}       % set of natural numbers
\newcommand{\Int}{{\mathbb{Z}}}      % set of integers
\newcommand{\Real}{{\mathbb{R}}}    % set of reals
\newcommand{\Complex}{{\mathbb{C}}}  % set of complex numbers

\begin{document}
\psol{1}{September 17, 1999 (revised 9/20)}

\begin{problems}

\problem \textbf{Logic}:
\bparts
\ppart \S 1.1, Exercise 24(b).

\solution{\(\begin{tabular}{lllcc}
$p$ & $q$ & $r$       &        $p \vee q$ & $(p \vee q)\wedge r$\\
\hline
t & t & t	& 	    t	  &      t\\
t & t & f	&	    t	  &      f\\
t & f & t	& 	    t	  &      t\\
t & f & f	& 	    t	  &      f\\
f & t & t	& 	    t     &      t\\
f & t & f	&	    t     &      f\\
f & f & t	&	    f	  &      f\\
f & f & f	&	    f	  &      f\\
\end{tabular}\)}

\ppart \S 1.2, Exercise 6.

\solution{We see that the fourth and seventh columns are identical.\\
\(\begin{tabular}{llccccc}
$p$ & $q$ & $p \wedge q$ & $\neg(p \wedge q)$ & $\neg p$ &  $\neg q$ & $\neg p\vee\neg q$\\
\hline
t & t &     t	    &	  f	&	f & f	&     f\\
t & f &     f	    &     t	&	f & t	&     t\\
f & t &     f	    &	  t	&	t & f	&     t\\
f & f &	    f	    &     t	&	t & t	&     t
\end{tabular}\)}

\ppart \S 1.2, Exercise 8(a).

\solution{We construct a truth table for each implication and see that the
relevant column contains only $t$'s.\\
\(\begin{tabular}{llcccc}
$p$ & $q$ &  $\neg p$ &  $p\vee q$ &  $\neg p\wedge(p\vee q)$ &  
                     $[\neg p\wedge(p\vee q)]\rightarrow q$\\
\hline
t & t &	f &	t	&	f	&		t\\
t & f & f &	t	&	f	&		t\\
f & t & t &	t	&	t	&		t\\
f & f & t &	f	&	f	&		t
\end{tabular}\)}

\ppart \S 1.3, Exercise 14 (d), (h), (i), (o).

\solution{(d) $\neg\exists x C(x,Bob)$ \\
          (h) $\exists x \forall y (x=y \leftrightarrow I(y))$\\
          (i) $\exists x \forall y(x\neq y \leftrightarrow I(y))$\\
          (o) $\exists x \exists y(x\neq y \wedge \forall z (C(x,z)\vee C(y,z)))$}

\ppart For each of the logical formulas in \S 1.3, Exercise 22(a), (c),
(d), (g), and (j), indicate whether or not it is true when the domain of
discourse is $\naturals$ (the natural numbers 0, 1, 2, \dots), $\integers$
(the integers), $\rationals$ (the rationals), $\reals$ (the real numbers), and
$\complex$ (the complex numbers).

\solution{\(\begin{array}{llllll}
Statement & \Nat & \Int & {\mathbb{Q}} & \Real & \Complex\\
\exists x(x^2=2) & f & f & f & t (x=\sqrt{2}) & t\\
\forall x \exists y (x^2 = y) & t & t & t & t (y=x^2)& t\\
\forall x \exists y (x=y^2) & f & f & f & f (take x<0) & t\\
\forall x\neq 0\exists y(xy=1) & f & f & t & t (y=1/x) & t\\
\exists x \exists y (x + 2y = 2 \wedge 2 x + 4 y = 5) & f & f & f & f & f
   \mbox{ (inconsistent system of equations)}
\end{array}\)}

\ppart \S 1.3, Exercise 42.

\solution{We need to show that each of these propositions implies the other.
Suppose that $\forall x P(x) \vee \forall x Q(x)$. We want to show
that $\forall x\forall y (P(x)\vee Q(y))$. By our hypothesis, one of the 
two things must be true. Either $P$ is universally true or $Q$ is universally
true. In the first case, $\forall x\forall y(P(x)\vee Q(y))$ is true, since
the first expression in the disjuction is true, no matter what $x$ and $y$ are;
and in the second case, $\forall x \forall y(P(x)\vee Q(y))$ is also true, since 
now the second expression in the disjunction is true, no matter what $x$ and 
$y$ are. Next we need to prove the converse. So suppose that 
$\forall x \forall y(P(x)\vee Q(y))$. We want to show that 
$\forall x P(x) \vee \forall x Q(x)$. If $\forall x P(x)$ is true then we are 
done. Otherwise, $P(x_0)$ must be false for some $x_0$ in the domain of 
discourse. For this $x_0$, then, the hypothesis tells us that $P(x_0)\vee Q(y)$
is true, no matter what $y$ is. Since $P(x_0)$ is false, it must be the case that 
$Q(y)$ is true for each $y$. In other words $\forall y Q(y)$ is true, or, to change
the name of the meaningless quantified variable, $\forall x Q(x)$ is true. This
certainly implies that $\forall x P(x) \vee \forall x Q(x)$ is true, as desired.}

\eparts

\problem  \textbf{Sets}
\bparts
\ppart \S 1.4, Exercise 14.  Prove it or give a counterexample.

\solution{The union of all the sets in the power set of a set $X$ must be exactly
$X$. In other words, we can recover $X$ from its power set, uniquely. 
Therefore the answer is yes.}

\ppart \S 1.5, Exercise 12(e).

\solution{To establish the equality, we need to prove inclusion in both
directions. To prove that $(B-A)\cup(C-A)\subseteq(B\cup C)-A$, 
suppose that $x\in(B-A)\cup(C-A)$.
Then either $x\in(B-A)$ or $x\in(C-A)$. Without loss of generality, assume the
former (the proof in the latter case is exactly parallel.) Then $x\in B$
and $x\not\in A$. From the first of these assertions, it follows that
$x\in B\cup C$. Thus we can conclude that $x\in (B\cup C)-A$, as desired. For the
converse, that is, to show that $(B\cup C) -A\subseteq (B-A)\cup (C-A)$, suppose that
$x\in (B\cup C)-A$. This means that $x\in (B\cup C)$ and $x\not\in A$. 
The first of these
assertions tells us that either $x\in B$ or $x \in C$. Thus either $x\in B-A$ or
$x\in C-A$. In either case, $x\in (B-A)\cup (C-A)$. (An alternative proof could be
given by using Venn diagrams, showing both sides represent the same
region.)}

\ppart \S 1.5, Exercise 14.

\solution{That $A\subseteq(A\cap B)\cup (A\cap \bar{B})$ follows from the 
fact that every element $x\in A$ is an
element of either $A\cap B$ (if $x\in B$) or $A\cap \bar{B}$ (if $x\not\in B$). 
On the other hand, if
$x\in (A\cap B)\cup (A\cap \bar{B})$, 
then either $x\in A\cap B$ or $x\in A\cap \bar{B}$. 
In either case, $x\in A$ by the definition of intersection.}

\ppart \S 1.5, Exercise 36.

\solution{We note that these sets are decreasing, that is 
$A_1\supseteq A_2 \supseteq A_3 \supseteq \ldots$.
Therefore the union of any collection of these sets is just the
one with the smallest subscript, and the intersection is just the one
with the largest subscript.\\
a) $A_1=\{1,2,3,\ldots\}$   \ \ \ b) $A_n=\{n, n+1, n+2,\ldots\}$}

\eparts

\problem \textbf{Proofs}  %From Fall 95 ps1, prob 7

Determine whether each of the following arguments is valid.  If an
argument is correct, what rule of inference (from Rosen, \S 3.1) is being
used?  If it is not, what fallacy (again from Rosen \S 3.1) occurs?

\begin{problemparts}
\problempart
{\em Theorem:} if $n^2>1$, then $n>1$.  {\em Proof:}
If $n$ is a real number such that $n>1$, then $n^2>1$.  Suppose that
$n^2>1$, then $n>1$.

\solution{Invalid. Fallacy of affirming the conclusion.}

\problempart
{\em Theorem:} The number $\log_2 3$ is irrational. {\em Proof:} A number is irrational if it is not the ratio of two integers.
Therefore, since $\log_2 3$ cannot be written in the form $a/b$ where
$a$ and $b$ are integers, it is irrational.

\solution{Invalid. Fallacy of affirming the conclusion.}

\problempart
{\em Theorem:} If $n^2 \leq 9$ then, $n \leq 3$.  {\em Proof:} Because
if $n$ is a real number with $n>3$, then $n^2 >9$.

\solution{Valid. Modus tollens.}

\problempart
{\em Theorem} If $n\leq 2$, then $n^2\leq 4$. {\em Proof:} Because if $n$ is a real number with $n>2$, then $n^2>4$.

\solution{Invalid. Fallacy of denying the hypothesis.}

\end{problemparts}

\problem \textbf{Simple Induction}
\bparts

\ppart \S 3.2, Exercise 18.

\solution{The base case, $n=2$, is the true statement that $5/4$ is less than $6/4$.
Assume the inductive hypothesis. Then we have
\begin{eqnarray*}
1+\frac{1}{4}+\ldots+\frac{1}{n^2}+\frac{1}{(n+1)^2}& < & 2-\frac{1}{n}
             +\frac{1}{(n+1)^2}\\
& = & 2 - \left(\frac{1}{n} - \frac{1}{(n+1)^2}\right)\\
& = & 2 - \left(\frac{n^2 + 2n + 1-n}{n(n+1)^2}\right)\\
& = & 2 - \frac{n^2 + n}{n(n+1)^2}-\frac{1}{n(n+1)^2}\\
& = & 2 - \frac{1}{n+1} - \frac{1}{n(n+1)^2}\\
& < & 2 - \frac{1}{n+1}.
\end{eqnarray*}}

\ppart \S 3.2, Exercise 32.

\solution{The answer is that we can form all multiples of $5$ cents greater than
or equal to $20$ cents, as well as $10$ cents. (The fact that $5$ cents and
$15$ cents cannot be obtained is clear.) To prove this by induction, we
check the base case, that $20$ cents can be formed (with two
dimes). Next assume the inductive hypothesis, that we can form $5k$
cents (where $k\ge 4$); we need to show how to obtain $5(k+1)=5k+5$ cents. If
a quarter is used to form $5k$ cents, then we can replace it by three
dimes, increasing the amount of money by the desired $5$ cents. On the
other hand, if a quarter is not used, then at least two dimes must be
used (since $5k\ge 20$), so we can replace two dimes by a quarter, again
increasing the amount of money by the desired $5$ cents.}

\ppart \S 3.2, Exercise 34.

\solution{We proceed by induction. The base case is true, since
$1\cdot 2^1 = (1-1)2^{1+1}+2$. We assume the inductive hypothesis, that
\[
\Sigma_{k=1}^{n}k\cdot 2^k = (n-1)2^{n+1}+2,
\]
and try to prove that 
\[
\Sigma_{k=1}^{n+1}k\cdot 2^k = n\cdot 2^{n+2}+2.
\]
Splitting the left-hand side into its first $n$ terms followed by its
last term and invoking the inductive hypothesis, we have
\begin{eqnarray*}
\Sigma_{k=1}^{n+1}k\cdot 2^k & = & \left(\Sigma_{k=1}^{n}k\cdot 2^k \right)+
        (n+1)2^{n+1}\\
& = & (n-1)2^{n+1} + 2 + (n+1) 2^{n+1}\\
& = & 2n\cdot 2^{n+1}+2\\
& = & n\cdot 2^{n+2}+2,
\end{eqnarray*} 
as desired.}

\eparts

\end{problems}

\end{document}
