\documentstyle[12pt,twoside,amstex]{article}
\input{/a/class/6.042/spring98/macros-course}

\addtolength{\textheight}{.05in}
\begin{document}

\psol{1}{February 12, 1998}

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 1
\problem\hfill

\bparts

\ppart

The {\em symmetric difference}, $A \oplus B$, of two sets
$A$ and~$B$, is defined by
\[A \oplus B = (A \cup B)-(A \cap B).\]

Show that $A \oplus B = (A-B) \cup (B-A)$.

First we show that  $(A-B) \cup (B-A) \subseteq (A \cup B)-(A \cap B)$.

Let $x \in (A-B) \cup (B-A)$. Then $x \in (A-B) \vee x \in (B-A)$.
So, $x \in A$, but $x \not\in B$, or $x \in B$, but $x \not\in A$
from which it follows that $x \in A \vee x \in B$, but $x$ is not in both
$A$ and $B$. So, $x \in A \cup B$, but $x \not\in A \cap B$, therefore
$x \in  (A \cup B)-(A \cap B)$.\\

Now we show that $(A \cup B)-(A \cap B) \subseteq (A-B) \cup (B-A)$.

Let $x \in (A \cup B)-(A \cap B)$.  Then $x \in A \cup B$, but
$x \not\in A \cap B$. So  $x \in A \vee x \in  B$, but $x$ is not in both
$A$ and $B$.
We take cases.
Case 1:
If $x \in A$, then since $x$ is not in $A \cap B$, we conclude that
$x$ is not in $B$.  Therefore $x \in A-B$.\\
Case 2:
If $x \in B$, then by the same argument, $x$ is not in $A$,
therefore $x \in B-A$. So $ x \in A-B \vee x \in B-A$, therefore
$x \in (A-B) \cup (B-A)$.\\

The two inclusions establish the set equality.

\ppart Prove that $\oplus$ is associative.\\

Using membership tables:

\begin{center}
\begin{tabular}{||c|c|c|c|c||}\hline
$A$ $B$ $C$& $A \oplus B$ & $B \oplus C$ & $A \oplus (B \oplus C)$ & $(A \oplus B) \oplus C$ \\ \hline
1 1 1 & 0 & 0 & 1 & 1 \\ \hline
1 1 0 & 0 & 1 & 0 & 0 \\ \hline
1 0 1 & 1 & 1 & 0 & 0 \\ \hline
1 0 0 & 1 & 0 & 1 & 1 \\ \hline
0 1 1 & 1 & 0 & 0 & 0 \\ \hline
0 1 0 & 1 & 1 & 1 & 1 \\ \hline
0 0 1 & 0 & 1 & 1 & 1 \\ \hline
0 0 0 & 0 & 0 & 0 & 0 \\ \hline

\end{tabular}
\end{center}

\eparts


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Truth Tables: problem 1.3-8
%Problem 2
\problem 
Show that each of the following implications is a tautology by using truth 
tables.

\bparts
\ppart $[(p \implies q) \wedge (q \implies r)] \implies 
(p \implies r)$

\begin{center}
\begin{tabular}{||c|c|c|c|c|c||}\hline
$p$ $q$ $r$ & $p \Rightarrow q$ & $q \Rightarrow r$ & $(p \Rightarrow q) \wedge (q \Rightarrow r)$ & $(p \Rightarrow r)$ &
$[(p \Rightarrow q) \wedge (q \Rightarrow r)] \Rightarrow 
(p \Rightarrow r)$\\ \hline
T T T & T & T & T & T & T \\ \hline
T T F & T & F & F & F & T \\ \hline
T F T & F & T & F & T & T \\ \hline
T F F & F & T & F & F & T \\ \hline
F T T & T & T & T & T & T \\ \hline
F T F & T & F & F & T & T \\ \hline
%corrected 2/13:
F F T & T & T & T & T & T \\ \hline
F F F & T & T & T & T & T \\ \hline
\end{tabular}
\end{center}

\ppart $[p \wedge q \wedge (p \Rightarrow r)] \Rightarrow 
(q \wedge r)$

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

\eparts 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%problem 3
% 1.2 - 25 modified 
\problem Find a compound proposition involving the propositions
$p$, $q$, and $r$ that is true exactly when {\em both}\\
(i) at least one of the propositions is true, {\em and also}\\
(ii) at least one of the propositions is false.\\
The compound proposition is false otherwise.

One simple expression is
%corrected 2/13
\[(p \vee q \vee r) \wedge (\neg p \vee \neg q \vee \neg r).\]
There are many other equivalent expressions.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 4
\problem 
% 1.3 # 8

Let $W(x,y)$ be the statement ``$x$ was one of the writers of
$y$,'' and $S(x)$ be the statement ``$x$ is a professional
screenwriter,'' where the universe of the discourse for $x$
is the set of all people and for $y$ is the set of all movies.
Express each of the following sentences in terms of $W(x,y), S(x)$,
quantifiers, and logical connectives,

\begin{description}
\item[a)] Someone who helped write ``Titanic'' was not a professional
screenwriter.
\[ \exists x (P(x,\text{``Titanic''}) \wedge \neg S(x)) \]

\item[b)] Every movie had a writer who was a professional screenwriter.
\[ \forall y \exists x (W(x,y) \wedge S(x)) \]

\item[c)] There is a professional screenwriter who has written
``Pulp Fiction'' and ``Jackie Brown.''
\[ \exists x (S(x) \wedge W(x,\text{``Pulp Fiction''}) \wedge
W(x,\text{``Jackie Brown''})) \]

\item[d)] There is only one movie which had exactly one writer who was
not a professional screenwriter. (Don't introduce numbers.  You will have
to add more standard variables ranging over people and over movies).\\

A good way to approach this problem is to break it down into smaller
parts.  Let Q(x, y) be an expression which means ``Movie $y$ had exactly
one writer, namely person $x$, who was not a professional screenwriter.''
Note that this language is ambiguous: it could mean (1) $x$ was the only
writer and $x$ was not a pro, or (2) $x$ was one of possibly many writers,
but $x$ was the only one who was not a pro.  We can express (1) as
\[Q(x, y) ::\equiv
W(x,y) \wedge [\forall x': W(x',y) \implies x' = x] \wedge \neg S(x),\]
and (2) as
 \[Q(x, y) ::\equiv W(x,y) \wedge \neg S(x) \wedge [\forall x': (W(x',y)
  \wedge \neg S(x'))\implies x' = x].\]
So an expression $R(y)$ which means ``Movie $y$ had exactly one writer who
was not a professional screenwriter'' is
 \[R(y) ::\equiv \exists x: Q(x, y).\]
Then finally the statement ``There is only one movie which had exactly one
writer who was not a professional screenwriter.'' can be written:\\
\[\exists y: R(y) \wedge [\forall y': R(y') \implies y' =y].\]
\end{description}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%problem 5
\problem 
Show that $\forall x P(x) \vee \forall x Q(x)$
and $\forall x (P(x) \vee Q(x))$ are not logically
equivalent.

In order to show that these two statements are not logically equivalent,
we must identify a situation in which one is true and the other is 
false.  Consider the following:\\

Let the universe of discourse for $x$ be the natural numbers.\\
Let $P(x)$ denote the statement ``x is an even number.''\\
Let $Q(x)$ denote the statement ``x is an odd number.''\\

The first statement, $\forall x P(x) \vee \forall x Q(x)$
then reads, ``Either every natural number is even OR every natural
number is odd''.   This is clearly not the case.  Not every natural
number is even, nor is every natural number odd. \\

The second statement, $\forall x (P(x) \vee Q(x))$ reads,
``Every natural number is either even or odd.''  This is certainly
true.  Given any natural number, either it is even or it is odd.
These two statements clearly have different meanings, and in this
example, one is true and the other is false, therefore they
are not equivalent.
  
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 6
\problem  Define predicates and state the following
arguments as predicate logic formulas.  Prove the
correct arguments and show the incorrect ones are
false.

\begin{problemparts}
\problempart Fairies are never fierce; some dragons are not
fierce.  Thus, some dragons are not fairies.

Let x be in the domain of objects. \\
$S(x)$: x is a Fairie (Sprite) \\
$D(x)$: x is a Dragon \\
$F(x)$: x is Fierce \\

\begin{tabular}{ll}
Fairies are never fierce & \( \forall x (S(x) \implies \neg F(x))  \) \\
Some dragons are not fierce & \( \exists x (D(x) \wedge \neg F(x)) \) \\
Thus, some dragons are not fairies & \( \exists x (D(x) \wedge \neg S(x))  \) \\
\end{tabular}

The entire argument is stated by the formula
\[( \forall x S(x) \implies \neg F(x)  ) \wedge
 (\exists x D(x) \wedge \neg F(x)) \implies
 (\exists x D(x) \wedge \neg S(x)). \]

We prove that the argument 
\[(\forall x: S(x) \implies \neg F(x)  ) \wedge
(\exists x: D(x) \wedge \neg F(x)) \implies
 (\exists x: D(x) \wedge \neg S(x))\]
is wrong by exhibiting a model in which the formula is false.  The
universe of discourse contains a single element {\em faerie-dragon} which
is both a fairie and a dragon and it is not fierce, i.e.,
$S(\mbox{faerie-dragon})$, $D(\mbox{faerie-dragon})$ and $\neg
F(\mbox{faerie-dragon})$.  The formula $\forall x S(x) \implies \neg F(x)$
is true because $\neg F(\mbox{faerie-dragon})$.  Also $\exists x D(x)
\wedge \neg F(x)$ is true because $D(\mbox{faerie-dragon})$ and $\neg
F(\mbox{faerie-dragon})$.  However the conclusion $\exists x D(x) \wedge
\neg S(x)$ is false because $S(\mbox{faerie-dragon})$, so the argument is
not valid.

\problempart Gold is a liquid asset, and he will be satisfied only with
gold.  Thus, no fixed asset will satisfy him.

\begin{tabular}{ll}
$L(x)$ & x is liquid, \\
$G(x)$ & x is gold,\\
$S(x)$ & x will satisfy him, \\
$F(x)$ & x is fixed.
\end{tabular}

\begin{tabular}{ll}
An asset is fixed iff it is not liquid. &  $\forall x: F(x)
\leftrightarrow \neg L(x)$ \\
Gold is a liquid asset. & $\forall x: G(x) \implies L(x)$ \\
He will be satisfied only with gold. & $\forall x: S(x) \leftrightarrow G(x)$ \\
Thus, no fixed asset will satisfy him. & $\forall x: F(x) \implies \neg S(x)$\\
\end{tabular}

The entire argument is captured by the formula
\[ \left([\forall x: \neg F(x) \leftrightarrow L(x)] \wedge
[\forall x: G(x) \implies L(x)] \wedge 
[\forall x: G(x) \leftrightarrow S(x)]\right)\]
\[ \implies  [\forall x: F(x) \implies \neg S(x)]. \]

We verify this formula as follows: from $\forall x: S(x) \leftrightarrow
G(x)$ and $\forall x: G(x) \implies L(x)$, we conclude that $\forall x:
S(x) \implies L(x)$.  Since $\forall x: \neg F(x) \leftrightarrow L(x)$,
we next conclude $\forall x: S(x) \implies \neg F(x)$.  Taking the
contrapositive of this last statement, we obtain $ \forall x: F(x)
\implies \neg S(x)$.

Note that it is not completely clear that gold will definitely satisfy
him.  Our formula corresponds to the interpretation that gold will satisfy
him.  With the interpretation that gold might not satisfy him, we would
use the formula $\forall x: S(x) \implies G(x)$.  The preceding proof
works with either interpretation.


\end{problemparts}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 7
%Problem in the Superman spirit
\problem 
Cast the following into propositional symbols, and explain whether 
Gandalf can be a hobbit.

\begin{quote}
Careless and weak people are not Wizards. People who are not careless are 
cautious.  Cautious people don't eat mushrooms. Weak people are not powerful.
Hobbits are not powerful and eat mushrooms. Gandalf is a Wizard.  Can Gandalf
be a Hobbit?
\end{quote}


Define the following predicates.

$C(x) = \text{$x$ is Careless}$.

$W(x) = \text{$x$ is Weak}$.

$M(x) = \text{$x$ is a wizard (Magician)}$ 

$A(x) = \text{$x$ is cautious (Alert)}$.

$F(x) = \text{$x$ eats mushrooms (Fungi)}$. 

$P(x) = \text{$x$ is Powerful}$.

$H(x) = \text{$x$ is a Hobbit}$.

The above statements translate into

$\forall x, C(x) \wedge W(x) \implies \neg M(x)$.

$\forall x, \neg C(x) \implies A(x)$.

$\forall x, A(x) \implies \neg F(x)$.

$\forall x, W(x) \implies \neg P(x)$.

$\forall x, H(x) \implies \neg P(x) \wedge F(x)$.

$M(\text{``Gandalf''})$.

The answer is yes, Gandalf may be a Hobbit.

We have:

\begin{eqnarray*}
H(\text{``Gandalf''}) & \implies &\neg P(\text{``Gandalf''}) \wedge F(\text{``Gandalf''}) \\
& \implies & \neg P(\text{``Gandalf''}) \wedge \neg A(\text{``Gandalf''}) \\
& \implies & \neg P(\text{``Gandalf''}) \wedge C(\text{``Gandalf''}) \\
\end{eqnarray*}

On the other hand:

\begin{eqnarray*}
M(\text{``Gandalf''}) & \implies &\neg (C(\text{``Gandalf''}) \wedge W(\text{``Gandalf''}) \\
& \implies & \neg C(\text{``Gandalf''}) \vee \neg W(\text{``Gandalf''}) \\
\end{eqnarray*}

Therefore, Gandalf can be both a Wizard and a Hobbit, provided that he is 
neither powerful, nor weak, and that he eats mushrooms.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%problem 8
\problem \hfill

\bparts

\ppart

Prove by contradiction: for all integers $n > 1$, the $n$th root of
a prime number is irrational.

Proof by contradiction:
Assume for the purposes of contradiction that the $n$th root
of a prime number, $p$, is rational.

$p ^ {1/n} = a/b$ where $a,b \in \naturals$ and $a,b$ are in lowest terms.\\
$p = a^n/b^n$\\
$b^np = a^n$ \\
therefore $a^n$ is divisible by $p$\\
therefore $a$ is divisible by $p$.\\
$a = pa_1$\\
$b^np=p^n(a_1)^n$\\
$b^n=p^{n-1}(a_1)^n$\\ 
therefore $b^n$ is divisible by $p^{n-1}$, and $n > 1$, \\
so $b^n$ is divisible by $p$\\
therefore $b$ is divisible by $p$\\
therefore $a$ and $b$ are both divisible by $p$, and so are not in lowest terms,
a contradiction. \qed

\ppart Your proof must depend on some property of prime numbers not
shared by all integers greater than one.  Why?  What property?

The property used is that $p | a^n$ for some $n > 0$, implies that $p$
divides $a$.

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 9
\problem 
Prove by cases: for every $n \in \naturals$, either $4 | n^2$ or
$4 | (n^2-1)$.\\

Case one: n is even.  Then $2 | n$ and therefore $4 | n^2$.\\

Case two: n is odd.  So $n = 2k+1$ for some $k \in \naturals$.  Then $n^2
-1 = (2k+1)^2 -1 = (4k^2 + 4k +1) - 1 = 4k^2 + 4k = 4(k^2 + k)$, so $4 |
n^2 -1$. \qed

\end{problems}
\end{document}
% Local Variables: 
% mode: latex
% TeX-master: t
% End: 
% LocalWords:  Carrol
