\documentclass[11pt, twoside]{article}

\usepackage{epsf} 

\input{macros-course}
 
\newcommand{\nand}{|}
\renewcommand{\implies}{\longrightarrow}

\begin{document}
\psol{1}{September 14, 2000}

\begin{problems}

\problem \textbf{Propositional logic}
\bparts
\ppart Rosen \S 1.1, Exercise 24 (f).

\bigskip
\textbf{Solution:}\\
\begin{tabular}{ccc|cc||c}
$p$ & $q$ & $r$ & $p \land q$ & $\lnot r$ & $(p \land q) \lor \lnot r)$ \\ \hline
t & t & t & t & f & t \\
t & t & f & t & t & t \\
t & f & t & f & f & f \\
t & f & f & f & t & t \\
f & t & t & f & f & f \\
f & t & f & f & t & t \\
f & f & t & f & f & f \\
f & f & f & f & t & t \\ 
\end{tabular}
  

\ppart Rosen \S 1.2, Exercise 8 (c),(d).

\bigskip
\textbf{Solution:}\\
We construct a truth table for each implication and see that the relevant column contains only t's

\medskip
{\mathversion{bold} $[p \land (p \rightarrow q)] \rightarrow q$ } \\
\begin{tabular}{cc|cc||c}
$p$ & $q$ & $(p \rightarrow q)$ & $[p \land (p \rightarrow q)]$ & $[p \land (p \rightarrow q)] \rightarrow q$ \\ \hline
t & t & t & t & t \\
t & f & f & f & t \\
f & t & t & f & t \\
f & f & t & f & t \\
\end{tabular}

\medskip
{\mathversion{bold} $[(p \lor q) \land (p \rightarrow r) \land (q \rightarrow r)] \rightarrow r$} \\
\begin{tabular}{ccc|cccc||c}
$p$ & $q$ & $r$ & $(p \lor q)$ & $(p \rightarrow r)$ & $(q \rightarrow r)$ & $[(p \lor q) \land (p \rightarrow r) \land (q \rightarrow r)]$ & $[(p \lor q) \land (p \rightarrow r) \land (q \rightarrow r)] \rightarrow r$ \\ \hline
t & t & t & t & t & t & t & t \\   
t & t & f & t & f & f & f & t \\
t & f & t & t & t & t & t & t \\
t & f & f & t & f & t & f & t \\
f & t & t & t & t & t & t & t \\
f & t & f & t & t & f & f & t \\
f & f & t & f & t & t & f & t \\
f & f & f & f & t & t & f & t \\
\end{tabular}

\ppart Velleman \S 1.5, Exercise 6.

\bigskip
\textbf{Solution:}\\
{\mathversion{bold} $P \rightarrow (Q \rightarrow R)$}\\
$P \rightarrow (\lnot Q \lor R)$ [equivalence] \\
$\lnot P \lor (\lnot Q \lor R)$ [equivalence] \\
$\lnot P \lor \lnot Q \lor R$ [associative and commutative laws] 

\smallskip
{\mathversion{bold} $Q \rightarrow (P \rightarrow R)$}\\
$Q \rightarrow (\lnot P \lor R)$ [equivalence] \\
$\lnot Q \lor (\lnot P \lor R)$ [equivalence] \\
$\lnot P \lor \lnot Q \lor R$ [associative and commutative laws] 

\smallskip
{\mathversion{bold} $(P \rightarrow Q) \land (P \rightarrow R)$}\\
$(\lnot P \lor Q) \land (\lnot P \lor R)$ [equivalence]

\smallskip
{\mathversion{bold} $(P \land Q) \rightarrow R$}\\
$\lnot(P \land Q) \rightarrow R$ [equivalence]\\
$\lnot P \lor \lnot Q \lor R$ [De Morgan's law]

\smallskip
{\mathversion{bold} $P \rightarrow (Q \land R)$}\\
$\lnot P \lor (Q \land R)$ [equivalence] \\
$(\lnot P \lor Q) \land (\lnot P \lor R)$ [distributive law] 

\medskip
For the values $P$ = true, $Q$ = false, $R$ = false, \\
$\lnot P \lor \lnot Q \lor R$ evaluates to true \\
$(\lnot P \lor Q) \land (\lnot P \lor R)$ evaluates to false \\
thus, these two expressions are not equivalent.

\smallskip
Thus, Parts (a), (b) and (d) are equivalent. Parts (c) and (e) are equivalent.

\eparts

\problem  \textbf{Set theory}
\bparts
\ppart Rosen \S 1.4, Exercise 16 (a),(b),(c),(d).  

\bigskip
\textbf{Solution:}\\
{\mathversion{bold} $\emptyset$ } \\
No. The power set of every set includes at least the empty set, so the power set cannot be empty. Thus $\emptyset$  is not the power set of any set.

\smallskip
{\mathversion{bold} $\{\emptyset, \{a\}\}$ } \\
Yes. This is the power set of $\{a\}$.

\smallskip
{\mathversion{bold} $\{\emptyset, \{a\}, \{\emptyset, a\}\}$ } \\
No. This set has three elements. Since 3 is not a power of 2, this set cannot be the power set of any set.

\smallskip
{\mathversion{bold} $\{\emptyset, \{a\}, \{b\}, \{a, b\}\}$ } \\
Yes. This is the power set of $\{a, b\}$.

\ppart Rosen \S 1.5, Exercise 12(c).

\bigskip
\textbf{Solution:}\\
Let $x \in (A - B) - C$. Then $x$ is in $A - B$ but not in $C$. Since $x \in A - B$, we know that $x \in A$ (we also know that $x \notin B$, but that won't be used here). Since we have established that $x \in A$ but $x \notin C$, we have proved that $x \in A - C$. Thus, $(A - B) - C \subseteq A - C$.


\ppart Rosen \S 1.5, Exercise 18 (a),(b),(c).

\bigskip
\textbf{Solution:}\\
\epsfxsize=2.1in
\mbox{\epsfbox{figures/ps1P2cParta.eps}}
\epsfxsize=2.1in
\mbox{\epsfbox{figures/ps1P2cPartb.eps}}
\epsfxsize=2.1in
\mbox{\epsfbox{figures/ps1P2cPartc.eps}}

\ppart Rosen \S 1.5, Exercise 36.

\bigskip
\textbf{Solution:}\\
$\bigcup_{i=1}^{n} A_{i}$ = \{1, 2, 3, ...\}

\medskip
$\bigcap_{i=1}^{n} A_{i}$ = \{$n$, $n$ + 1, $n$ + 2, ...\}

\eparts

\problem \textbf{Proofs or fallacies?}  %variant of fall99

Determine whether each of the following arguments is valid.
If it is not valid, then explain what the error is. (You may want to use the rules of inference and fallacies from Rosen in your solutions.)

\begin{problemparts}

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

\medskip
\textbf{Solution:}\\
Not valid. Given the propositions \\
p: $n>1$ \\
q: $n^3>1$ \\ 
the argument says that $p \rightarrow q$, so if q then p.
This is the 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.

\medskip
\textbf{Solution:}\\
Not valid. Fallacy: Circular reasoning.  The statement following the
``therefore'' is precisely the one we want to prove.  And it doesn't
follow from anything before, so the therefore has no justification for
being there.


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

\medskip
\textbf{Solution:}\\
Not valid. Given the propositions \\
p: $n > 3$ \\
q: $n^2 >9$ \\
the argument says that $p \rightarrow q$, so if q then p.
Again, this is the fallacy of affirming the conclusion.


\problem \textbf{Proofs}
Velleman \S 3.1, Exercise 6.

We prove the contrapositive i.e. if $x = 8$, $\frac{\sqrt[3]{x} + 5}{x^2 + 6} \ne \frac{1}{x}$.
\[\frac{\sqrt[3]{8} + 5}{8^2 + 6} = \frac{1}{10} \ne \frac{1}{x} = \frac{1}{8} \]\\
As we have shown the contrapositive to be true, the original hypothesis, that if $\frac{\sqrt[3]{x} + 5}{x^2 + 6} = \frac{1}{x}$ then $x \ne 8$, is true. This is an example of an indirect proof.  

\problem \textbf{And more proofs}
Rosen \S 3.1, Exercise 46.

\bigskip
\textbf{Solution:}\\
Proof by cases:
\begin{enumerate}
\item $m = 1$ 
\\
As $n$ is an integer, $\lfloor \lfloor x \rfloor + n \rfloor = \lfloor \lfloor x \rfloor \rfloor + n = \lfloor x \rfloor + n = \lfloor x + n \rfloor$\\
The hypothesis is proved to be true when $m = 1$.

\medskip
\item $m > 1$ 
\\
Proof by contradiction: \\
Assume that the hypothesis is false, that is $\lfloor \frac{\lfloor x \rfloor + n}{m} \rfloor \ne \lfloor \frac{x + n}{m} \rfloor$.\\
Let $x = z + y$, where $z$ is an integer and $0 \leqslant y < 1$.\\
Also, let  $k = \lfloor \frac{\lfloor x \rfloor + n}{m} \rfloor$.
\[k = \lfloor \frac{\lfloor x \rfloor + n}{m} \rfloor \ne \lfloor \frac{x + n}{m} \rfloor\]
\[k = \lfloor \frac{z + n}{m} \rfloor \ne \lfloor \frac{z + y + n}{m} \rfloor\]
As $m$ is an integer and is greater than 1, it follows that 
\[\frac{z + n}{m} \leqslant k + \frac{m - 1}{m} \]
and
\[\frac{z + n + y}{m} \geqslant k + \frac{m}{m}\]
\medskip
Thus, 
\[\frac{y}{m} \geqslant \frac{1}{m}\]
\[y \geqslant 1\]

This is a contradiction, as we defined $0 \leqslant y < 1$. Thus, our original hypothesis, $\lfloor \frac{\lfloor x \rfloor + n}{m} \rfloor = \lfloor \frac{x + n}{m} \rfloor$, is true when $m > 1$. 
\end{enumerate}

As we have proved that the hypothesis is true in both cases, the hypothesis is always true. 


\end{problems}

\end{document}


