\documentclass{article}
\usepackage{amsmath,amsthm,amssymb,amsfonts,fancyhdr,epic,eepic,multicol}

\renewcommand{\baselinestretch}{1.1}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\theoremstyle{definition}
\newtheorem{problem}{Problem}
\newtheorem{remark}{Remark}
\newtheorem{definition}{Definition}
\newcommand{\bp}{\begin{problem}}
\newcommand{\ep}{\end{problem}}

\newtheorem*{answer}{Answer}
\newtheorem*{lemma*}{Lemma}
\newtheorem*{theorem*}{Theorem}
\newcommand{\ba}{\begin{answer}}
\newcommand{\ea}{\end{answer}}

\newcommand{\ds}{\displaystyle}
\newcommand{\ben}{\renewcommand{\theenumi}{\alph{enumi}}\renewcommand{\labelenumi}{(\theenumi)}\begin{enumerate}}
\newcommand{\een}{\end{enumerate}}

\newcommand{\Z}{\mathbb{Z}} 
\newcommand{\N}{\mathbb{N}} 
\newcommand{\R}{\mathbb{R}} 
\newcommand{\C}{\mathbb{C}} 



\fancyhead[L]{\Large \textbf{Math 157 Fall 2013}}
\fancyhead[R]{\large \textbf{Homework 3 - answers}}


\begin{document}
\pagestyle{fancy}
\fancyfoot[R,L,C]{}


\bp Let $A$, $B$ and $X$ be sets.  Prove that $$X-(A\cup
B)=(X-A)\cap (X-B).$$
\ba
Suppose that $x\in X -(A\cup B)$.  This means $x\in X$ and
$x\notin (A\cup B)$.  Note $x \in A \cup B$ means $x\in A$ or $x\in
B$.  Therefore, the negation $x\notin A \cup B$ is equivalent to
$x\notin A$ and $x\notin B$.
So, we have $x\in X$ and $x\notin A$; i.e. $x\in X - A$ and we
have $x\in X$ and $x\notin B$; i.e. $x\in X - B$.  Since we
have $x\in X- A$ and $x\in X- B$, we have $x\in
(X- A) \cap (X- B)$.  This proves $X- (A\cup
B)\subseteq (X- A)\cap(X- B)$.

On the other hand, if $x\in (X- A)\cap(X- B)$, we have
$x\in X- A$ and $x\in X- B$.  Having $x\in X-
A$ means $x\in X$ and $x\notin A$.  Also, $x\in X- B$ means
$x\in X$ and $x\notin A$.  Summarizing, we have $x\in X$ and $x\notin
A$ and $x\in X$ and $x\notin B$.  Putting $x\notin A$ and $x\notin B$
together, we have $x$ is not in either $A$ or $B$.  That is, $x\notin
(A\cup B)$.  Since $x\in X$, we have $x\in X - (A\cup B)$.
This proves $(X- A)\cap(X- B)\subseteq X -
(A\cup B)$.

Since we've proved $X- (A\cup
B)\subseteq (X- A)\cap(X- B)$ and $(X- A)\cap(X- B)\subseteq X -
(A\cup B)$, we conclude that $(X- A)\cap(X- B)= X -
(A\cup B)$.

\ea
\ep


\bp Construct a truth table for the following compound propositions.
\ben
\item $(p\wedge q)\Rightarrow r$
\begin{center}
\begin{tabular}{c|c|c|c|c}
$p$ & $q$ & $r$ & $p\wedge q$ & $(p\wedge q)\Rightarrow r$ \\
\hline
T & T & T & T & T \\
\hline 
T & T & F & T & F \\
\hline
T & F & T & F & T \\
\hline
T & F & F & F & T \\
\hline
F & T & T & F & T \\
\hline
F & T & F & F & T \\
\hline
F & F & T & F & T \\
\hline
F & F & F & F & T \\
\end{tabular}
\end{center}

\item $(p\vee q)\Rightarrow r$
\begin{center}
\begin{tabular}{c|c|c|c|c}
$p$ & $q$ & $r$ & $p\vee q$ & $(p\vee q)\Rightarrow r$ \\
\hline
T & T & T & T & T \\
\hline 
T & T & F & T & F \\
\hline
T & F & T & T & T \\
\hline
T & F & F & T & F \\
\hline
F & T & T & T & T \\
\hline
F & T & F & T & F \\
\hline
F & F & T & F & T \\
\hline
F & F & F & F & T \\
\end{tabular}
\end{center}

\item $(p\Rightarrow q)\Rightarrow r$

\begin{center}
\begin{tabular}{c|c|c|c|c}
$p$ & $q$ & $r$ & $p\Rightarrow q$ & $(p\Rightarrow q)\Rightarrow r$ \\
\hline
T & T & T & T & T \\
\hline 
T & T & F & T & F \\
\hline
T & F & T & F & T \\
\hline
T & F & F & F & T \\
\hline
F & T & T & T & T \\
\hline
F & T & F & T & F \\
\hline
F & F & T & T & T \\
\hline
F & F & F & T & F \\
\end{tabular}
\end{center}

\item $\left((p\vee q)\Rightarrow r\right) \Leftrightarrow \left((p \wedge
  \neg q) \Rightarrow r\right)$

\begin{center}
\begin{tabular}{c|c|c|c|c|c|c|c|c}
$p$ & $q$ & $r$ & $p\vee q$ & $(p\vee q)\Rightarrow r$ & $\neg q$ &
$p\wedge \neg q$ & $(p \wedge \neg q) \Rightarrow r$ & $\left((p\vee q)\Rightarrow r\right) \Leftrightarrow \left((p \wedge
  \neg q) \Rightarrow r\right)$\\
\hline
T & T & T & T & T & F & F & T & T  \\
\hline 
T & T & F & T & F & F & F & T & F \\
\hline
T & F & T & T & T & T & T & T & T  \\
\hline
T & F & F & T & F & T & T & F & T \\
\hline
F & T & T & T & T & F & F & T & T \\
\hline
F & T & F & T & F & F & F & T & F \\
\hline
F & F & T & F & T & T & F & T & T \\
\hline
F & F & F & F & T & T & F & T & T \\
\end{tabular}
\end{center}

\een
\ep

\bp We say two propositions $p$ and $q$ are logically equivalent if
they have the same truth values and write $p \equiv q$.  This is the
same as saying that the biconditional $p\Leftrightarrow q$ is a
tautology, i.e., always true.   
Prove or disprove each of the following logical equivalences.  You may
use truth tables, or you may use various laws of Boolean algebra (see
for example, the monotone and nonmonotone laws at
\texttt{http://en.wikipedia.org/wiki/Boolean\_algebra\_(logic)} .)
\ben
\item $p\Rightarrow q \equiv \neg p \vee q$

\begin{center}
\begin{tabular}{c|c|c|c|c}
$p$ & $q$ & $p\Rightarrow r$ & $\neg p$ & $\neg p \vee q$ \\
\hline
T & T & T & F & T \\
\hline 
T & F & F & F & F \\
\hline
F & T & T & T & T \\
\hline
F & F & T & T & T \\
\end{tabular}
\end{center}

\item $(p \Rightarrow q) \vee (p\Rightarrow r)\equiv p\Rightarrow (q
  \vee r)$
\begin{proof}
First note that $(a\vee b) \vee (c \vee d) \equiv (a \vee c) \vee (b
\vee d)$ for any propositions $a,b,c,d$.  Here's the proof
\begin{align*}
(a\vee b) \vee (c \vee d) & \equiv ((a\vee b) \vee c) \vee d &
\text{associativity} \\
& \equiv (a\vee (b \vee c)) \vee d &
\text{associativity} \\
& \equiv (a\vee (c \vee b)) \vee d &
\text{commutativity} \\
& \equiv ((a\vee c) \vee b) \vee d &
\text{associativity} \\
& \equiv (a\vee c) \vee (b \vee d) &
\text{associativity} 
\end{align*}
Now, to prove the logical equivalence
\begin{align*}
(p \Rightarrow q) \vee (p\Rightarrow r) & \equiv (\neg p \vee q) \vee
(\neg p \vee r) & \text{ by part (a)}\\
& \equiv ( \neg p \vee \neg p)  \vee ( q \vee r) & \text{by the lemma above}\\
& \equiv  \neg p   \vee ( q \vee r) & \text{by the idempotent law}\\
& \equiv  p\Rightarrow  ( q \vee r) & \text{by part (a)}
\end{align*}
\end{proof}

\item $(p \Rightarrow r) \vee (q\Rightarrow r)\equiv (p\wedge
  q)\Rightarrow r$
\begin{proof}
\begin{align*}
(p \Rightarrow r) \vee (q\Rightarrow r) & \equiv (\neg p\vee r )\vee
(\neg q \vee r) &\text{by part (a)}\\
& \equiv (\neg p\vee \neg q )\vee
(r \vee r) &\text{by lemma in part (b)}\\
& \equiv (\neg p\vee \neg q )\vee
r &\text{by idempotent law}\\
& \equiv \neg (p\wedge q )\vee
r &\text{by DeMorgan's law}\\
& \equiv (p\wedge q )\Rightarrow r &\text{by part (a)}\\
\end{align*}
\end{proof}
\item $(p \Rightarrow q) \Rightarrow  (r\Rightarrow s) \equiv (p\Rightarrow r)\Rightarrow (q
  \Rightarrow  s)$
\ba This one is false.  To prove it, consider the case when $p$ is
false, $q$ is false, $r$ is true and $s$ is false.  Then $p\Rightarrow
q$ is true and $r\Rightarrow s$ is false, making the lefthand side
false.  On the righthand side, $p\Rightarrow r$ is true and $q
\Rightarrow s$ is true, making the righthandside true.
\ea

\een

\ep

\bp Find a compound proposition involving propositions $p$, $q$, and
$r$ that is true when exactly one of them is true and false otherwise.
\ba
First, note that the compound proposition $(p\vee s)\wedge (\neg
p \vee \neg s)$ is true when exactly one of $p$ or $s$ is true and
false otherwise:

\begin{center}
\begin{tabular}{c|c|c|c|c|c|c}
$p$ & $s$ & $p\vee s$ &  $\neg p$ & $\neg s$ & $ \neg p \vee \neg s$ &
$(p\vee s)\wedge (\neg
p \vee \neg s)$\\
\hline
T & T & T & F & F & F  & F \\
\hline 
T & F & T & F & T & T  & T \\
\hline
F & T & T & T & F & T  & T \\
\hline
F & F & F & T & T & T  & F\\
\end{tabular}
\end{center}

Now, let $s=(q\vee r)\wedge (\neg
q \vee \neg r)$.  The proposition $s$ is true when exactly one of $q$
or $r$ is true and false otherwise.  Substituting $s$ in above, we
obtain
$$(p\vee \left((q\vee r)\wedge (\neg
q \vee \neg r))\right)\wedge (\neg
p \vee \neg \left((q\vee r)\wedge (\neg
q \vee \neg r)\right))$$
which is true when exactly one of $p$, $q$, or $r$ is true, and false otherwise.
\ea

\ep

\bp Let $\R$ be the set of real numbers, $[0,1]=\{x\in \R: 0 \leq x
\leq 1\}$, and $\N=\{1,2,3,4,\ldots\}$ be
the set of natural numbers.  Negate the following propositions:
\ben
\item $\forall x \in \R \exists y\in \N (y>x)$
\ba $\exists x\in \R \forall y \in \N (y \leq x)$
\ea
\item $\exists y\in \R \forall x \in \N (y>x)$
\ba $\forall y \in \R \exists x \in \N (y \leq x)$
\ea
\item $\forall \epsilon >0 \exists N \in \N \forall n\in \N (n>N
  \Rightarrow \frac{1}{n}<\epsilon)$
\ba
$\exists \epsilon >0 \forall N \in \N \exists n \in \N (n>N \wedge
\frac{1}{n}\geq \epsilon)$
\ea
\item $\forall x\in [0,1] \forall \epsilon >0 \exists N \in \N \forall
  n\in \N (n>N \Rightarrow x^n<\epsilon)$
\ba
$\exists x\in [0,1] \exists \epsilon >0 \forall N \in \N \exists
  n\in \N (n>N \wedge x^n\geq \epsilon)$
\ea
\een
\ep

\bp Decide whether each of the propositions in the previous problem 
is true or false.
\ben
\item $\forall x \in \R \exists y\in \N (y>x)$
\ba True.  This says for every real number $x$, there exists a natural
number $n$ that is larger than $x$.
\ea
\item $\exists y\in \R \forall x \in \N (y>x)$
\ba False. This says that there is a real number $y$ that is larger
than or equal to every natural number, which is false.
\ea
\item $\forall \epsilon >0 \exists N \in \N \forall n\in \N (n>N
  \Rightarrow \frac{1}{n}<\epsilon)$
\ba True.  This says that $\frac{1}{n}$ becomes arbitrarily small as
$n$ grows.
To see this, suppose $\epsilon >0$ has been given.  Choose
$N$ to be an integer larger than $\ds \frac{1}{\epsilon}$.  Then, if
$n>N$, we have $n>\ds \frac{1}{\epsilon}$ and $\ds \frac{1}{n}<\epsilon.$
\ea
\item $\forall x\in [0,1] \forall \epsilon >0 \exists N \in \N \forall
  n\in \N (n>N \Rightarrow x^n<\epsilon)$
\ba This is false.  For example, if $x=1$ and $\epsilon=\frac{1}{2}$,
then no matter what $N\in \N$ is chosen, you can find an $n>N$ with 
$x^n=1^n=1 \geq \frac{1}{2}=\epsilon.$

\emph{Remark} If we exclude $x=1$, this proposition becomes
true.  That is, $\forall x\in [0,1] \forall \epsilon >0 \exists N \in \N \forall
  n\in \N (x\neq 0 \text{ and }n>N \Rightarrow x^n<\epsilon)$ is a true statement.
\ea
\een
\ep

\bp Compare the following algebraic structures:  
\begin{itemize}
\item \emph{Sets} together with the binary operations $\cup$ and
  $\cap$.
\item \emph{The real numbers $\R$} together with the binary operations
  $+$ and $\times$.
\item \emph{Propositions} together with the binary operations $\vee$
  and $\wedge$.
\end{itemize}
\ba All the operations $\cup, \cap, +, \times, \vee, \wedge$
are commutative and associative.

In $\R$, we have identities $0$ and $1$ for the operations $+$ and
$\times$, respectively.  

For \emph{Sets}, the empty set $\emptyset$ works as
an identity for $\cup$ since for all sets $X$, $X\cup
\emptyset=X=\emptyset \cup X$.
The universal set $S$ serves as an identity for $\cap$ since $X\cap
S=X=S\cap X$ for all sets $X$. 


Now consider \emph{Propositions}.  Let $T$ stand for a proposition that is
always true (called a tautology) and let $F$ stand for a proposition
that is always false (called a contradiction).
Then $F$ works 
an identity for $\vee$ since $F\vee p\equiv p\equiv p\vee F$ for all propositions
$p$.  
The proposition $T$ serves as an identity for $\wedge$ since $p\wedge
T\equiv p \equiv T\wedge p$ for all propositions
$p$.  

Once we have operations and identity elements, one can ask about
inverses.  In $\R$, we have additive inverses for every
$a\in \R$.  That is, for every element
$a\in \R$, there exists an element $b\in \R$ so that $a+b=0$.
Also, every nonzero $a\in \R$ has a multiplicative inverse.  That is,
for every $a\in \R$ with $a\neq 0$, there exists a $b\in \R$ so that
$a\times b =1.$  Things 
work differently in \emph{Sets} and \emph{Propositions}.  For
example, the question of whether there exist inverses for $\cup$ is
the question of whether for any set $A$, there exists another set $B$
so that $A\cup B=\emptyset$, the identity for $\cup.$  This is false.
What one has instead is a statement that mixes the identities and the
operations.  For every set $A$, there is a set $B$ so that $A\cap
B=\emptyset$.  Also, for every set $A$, there is a set $B$ so that
$A\cup B=S$.  In both of these cases, for any set $A$, the set 
$B=S-A$ works.  The situation is the same in \emph{Propositions}.
For every proposition $p$, there exists a proposition $q$ so that
$p\vee q \equiv T$ and for every proposition $p$, there exists a
proposition $q$ so that $p\wedge q\equiv F$.  In both cases, 
the negation $\neg
p$ works for the proposition $q$.

There are important differences in the compatibilities
between the operations.  In $\R$, we have the distributive law
$$a\times (b+c)=(a\times b)+(a\times c).$$
But one does not have the ``other'' distributive law:
$$a+(b\times c)=(a+b)\times (a+c).$$
In \emph{Sets}, however, one has both
 $$A\cap (B\cup C)=(A\cap B) \cup (A\cap C)$$
and
 $$A\cup (B\cap C)=(A\cup B) \cap (A\cup C).$$
Likewise, in \emph{Proposition}, one has both
$$p\vee (q\wedge r)\equiv (p\vee q)\wedge (p\vee r)$$
and 
$$p\wedge(q\vee r)\equiv (p\wedge q)\vee (p\wedge r)$$

This discussion doesn't describe every difference between $(\R, +,
\times)$ , $(Sets, \cup,\cap)$, and $(Propositions, \vee, \wedge)$,
but it should give you a good idea about some of them.


\ea
\ep



\end{document}

