\documentstyle[12pt,twoside,amstex]{article}
\input{macros-course}

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

\psol{1}{September 12, 1997}

\begin{problems}

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

\bparts

\ppart
Establish the following set identity

$(B-A) \cup (C-A) = (B \cup C)-A$ \\

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

Let $x \in (B-A) \cup (C-A)$. Then either $(x \in B-A)$ or $(x \in C-A)$.

Case 1: $(x \in B \wedge x \not\in A)$. Then 
$(x \in B \cup C \wedge x \not\in A)$, so 
$(x \in B \cup C - A)$.

Case 2: $(x \in C \wedge x \not\in A)$. Then 
$(x \in B \cup C \wedge x \not\in A)$, so 
$(x \in B \cup C - A)$.


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

Let $x \in (B \cup C)-A$.  Then $x \in B \cup C$ and $x \not\in A$.
So $x$ is in $B$ but not in $A$, or $x$ is in $C$, but not in $A$. Therefore,
$x \in (B-A)$ or $x \in (C-A)$, thus $x \in (B-A) \cup (C-A)$.\\

We have established that $(B-A) \cup (C-A) \subseteq (B \cup C)-A$ and
 $(B \cup C)-A \subseteq (B-A) \cup (C-A)$. Therefore,
$(B-A) \cup (C-A) = (B \cup C)-A$

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

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.
  
%\begin{eqnarray*}
%A \oplus B = (A-B) \cup (B-A) & = (A \cap B^c)\cup (B \cap A^c) \\
%& = (A \cup B) \cap (B \cup B^c) \cap (A \cup A^c) \cap (B^c \cup A^c)  \\
%& = (A \cup B) \cap (B \cap A)^c  \\
%& = (A \cup B) - (A \cap B)
%\end{eqnarray*} 

\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 $[\neg p \wedge (p \vee q)] \rightarrow q$

\begin{center}
\begin{tabular}{||c|c|c|c|c||}\hline
$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 \\ \hline
T F & F & T & F & T \\ \hline
F T & T & T & T & T \\ \hline
F F & T & F & F & T \\ \hline
\end{tabular}
\end{center}

\ppart $[p \wedge (p \rightarrow q)] \rightarrow q$

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

\ppart $[(p \vee q) \wedge (p \rightarrow r) \wedge (q \rightarrow r)] 
\rightarrow r$

\begin{center}
\begin{tabular}{||c|c|c||}\hline
$p$ $q$ $r$ & $(p \vee q) \wedge (p \rightarrow r) \wedge (q \rightarrow r)$
& $[(p \vee q) \wedge (p \rightarrow r) \wedge (q \rightarrow r)] \rightarrow r
$ \\ \hline
T T T & T & T \\ \hline
T T F & F & T \\ \hline
T F T & T & T \\ \hline
T F F & F & T \\ \hline
F T T & T & T \\ \hline
F T F & F & T \\ \hline
F F T & F & T \\ \hline
F F 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 false when exactly two of $p$, $q$, and $r$ are
false.  The compound proposition is true otherwise. 

It is easier to negate the proposition so that it's true when exactly two
are false.  This in turn asks for exactly one variable to be true.  
So we divide the proposition in three subclauses, one for each variable 
that might be the only true one.  This gives us:

\[ \neg ((\neg p \wedge \neg q \wedge r) \vee (\neg p \wedge q \wedge \neg r) 
\vee (p \wedge \neg q \wedge \neg r)) \]
which is equivalent (using DeMorgan's laws; see Rosen) to
\[ ((p \vee q \vee \neg r ) \wedge (p \vee \neg q \vee r ) \wedge (\neg p \vee q \vee r ))
\]
which is also equivalent to
\[
((p \wedge q) \vee (q \wedge r) \vee (p \wedge r)  \vee (\neg p \wedge \neg q \wedge \neg r))
\]
(This last derives the proposition by first putting in 3 clauses that
are true when exactly $2$ clauses are true, and then one clause when
exactly $0$ clauses are true (note that the third case, all 3 clauses
true, is already covered by the first 3 clauses).

As an alternative solution, 
notice that the proposition is true if (1) All the $p.q,r$ are false
($\neg p \wedge \neg q \wedge \neg r$), (2) All of them are true 
($p \wedge q \wedge r$), or (3) 
only one is true (in which case we have the three
subcases $(\neg p \wedge \neg q \wedge r) \vee (\neg p \wedge q \wedge \neg r)
\vee (p \wedge \neg q \wedge \neg r))$.

Putting it all together:

\[(\neg p \wedge \neg q \wedge \neg r) \vee (p \wedge q \wedge r) \vee
(\neg p \wedge \neg q \wedge r) \vee (\neg p \wedge q \wedge \neg r)
\vee (p \wedge \neg q \wedge \neg r)
\]

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

Let $P(x,y)$ be the statement ``$x$ has written $y$.''
$x$ ranges over the set of all poets, and $y$ over 
the set of all poems.

\begin{description}
\item[a)] There is a poet who wrote ``The Raven''. 
\[ \exists x P(x,\text{``The Raven''}) \]

\item[b)] Every poet has written a poem.
\[ \forall x \exists y P(x,y) \]

\item[c)] Not every poem has been written by a poet.
\[ \neg \forall y \exists x P(x,y) = \exists y \forall x \neg P(x,y)\]

\item[d)] There is a poet who has written 
``The Lady of Shallot'' and the ``Lotus Eaters''.

\[ \exists x (P(x, \text{``The Lady of Shallot''}) \wedge 
P(x, \text{``The Lotus Eaters''})) \]

\item[e)] At least two poets have written a poem with the name ``Ulysses''.

\[ \exists x_1, x_2 ((x_1 \neq x_2) \wedge P(x_1, \text{``Ulysses''}) \wedge
 P(x_2, \text{``Ulysses''})) \]

\end{description}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%problem 5
\problem 
Show that $\exists z \forall x \exists y Q(x,y,z)$ implies but 
is not equivalent to $\forall x \exists y \exists z Q(x,y,z)$.


From $\exists z \forall x \exists y Q(x,y,z)$, we conclude that there exists
a $z_0$ such that the proposition $\forall x \exists y Q(x,y,z_0)$ is true.
Therefore $\forall x \exists y \exists z Q(x,y,z)$ is true.

To see that the statements are not equivalent we formulate a counterexample.
Let the universe of discourse for $x$ and $z$ be $\naturals$, and the universe
of discourse for $y$ be just the singe-element set $\{ 0 \}$. Let 
$Q(x,y,x)$ be the statement $x = y+z$.
Then $\forall x \exists y \exists z Q(x,y,z)$ is certainly true, since for any
$x$ we can set $y=0$ and $z=x$. However, there exists, no natural number $z$
such that for all $x \in \naturals$, $x = 0+z$.  

%Let $x$ belong to the set of positive integers that can be written as a sum
%of two squares.  Let $y,z$ belong to the set of positive integers.
%Let $Q(x,y,z)$ be the proposition $x = y^2+z^2$. Then 
%$\forall x \exists y \exists z Q(x,y,z)$ is certainly true by definition.
%However, there exists, no positive integer $z$ such that for all $x$, 
%there exists a $y$ such that $x = y^2+z^2$.
  
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 6
\problem  Define predicates and formulas.

\begin{problemparts}
\problempart 

Let x be in the domain of creatures and fruits. \\
$C(x)$: x is a lemon (Citrus) \\
$D(x)$: x is a Dragon \\
$F(x)$: x is Fierce \\

\begin{tabular}{ll}
No lemons are fierce & \( \forall x (C(x) \rightarrow \neg F(x))  \) \\
Some dragons are not fierce & \( \exists x (D(x) \wedge \neg F(x)) \) \\
Thus, some dragons are not lemons & \( \exists x (D(x) \wedge \neg C(x))  \) \\
\end{tabular}

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

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

\problempart 
$H(x)$: x is heavy (not light) \\
$G(x)$: x is gold\\
$S(x)$: x will silence him \\

\begin{tabular}{ll}
Gold is heavy. & \( \forall x (G(x) \rightarrow H(x)) \) \\
Nothing but gold will silence him.  & 
\( \forall x (G(x) \leftrightarrow S(x)) \) \\
Thus, nothing light will silence him. & \( \forall x (\neg H(x) \rightarrow 
\neg S(x)) \) \\
\end{tabular}

The entire argument is stated by the formula
\[ \forall x (G(x) \rightarrow H(x)) \wedge 
(\forall x (G(x) \leftrightarrow S(x))) \Rightarrow
(\forall x (\neg H(x) \rightarrow \neg S(x))). \]

From $\forall x (S(x) \leftrightarrow G(x))$ and  
$\forall x (G(x) \rightarrow H(x))$, we conclude that 
$\forall x (S(x) \rightarrow H(x))$, and taking the contrapositive
we obtain $ \forall x (\neg H(x) \rightarrow \neg S(x))$.


\end{problemparts}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 7
%Problem in the Superman spirit
\problem 
Cast the following into propositional symbols and answer the question.

\begin{it}
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{it}


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) \rightarrow \neg M(x)$.

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

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

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

$\forall x, H(x) \rightarrow \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''}) & \rightarrow &\neg P(\text{``Gandalf''}) \wedge F(\text{``Gandalf''}) \\
& \rightarrow & \neg P(\text{``Gandalf''}) \wedge \neg A(\text{``Gandalf''}) \\
& \rightarrow & \neg P(\text{``Gandalf''}) \wedge C(\text{``Gandalf''}) \\
\end{eqnarray*}

On the other hand:

\begin{eqnarray*}
M(\text{``Gandalf''}) & \rightarrow &\neg (C(\text{``Gandalf''}) \wedge W(\text{``Gandalf''}) \\
& \rightarrow & \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 
 Prove that a positive integer $n$ is a perfect square if and only if 
there are an odd number of positive integers (not necessarily just primes)
that divide $n$.  For example, there is one positive integer that divides 1.

We will prove the statement: ``A natural number has an even number of divisors
if and only if it not a perfect square''.

First we show that if $n$ is not a perfect square, then it has an even number 
of divisors.

Consider all the set $S$ of divisors of $n$ that are less than $\sqrt n$. 
$S = \{ x \in \naturals \text{ }| \text{ } (x | n) \wedge (x < \sqrt n) \}$.

For any element $p$ of $S$, there is exactly one divisor, namely $n/p$, 
that is greater than $\sqrt n$. It easy to see that there are no other 
divisors (each divisor of $n$ is either greater or less than $\sqrt n$).
So $n$ has $2|S|$ divisors.

Now we show the other direction: ``If $n$ has an even number of divisors,
then it not a perfect square''.  It is easier to show the contrapositive:
``If $n$ is a perfect square, then it has an odd number of divisors''.

Again we consider the set $S$ of divisors that are less than $\sqrt n$ and we
pair them with divisors that are greater than $\sqrt n$. So there are
$2|S|$ divisors as before.  However, $\sqrt n$ is also a divisor (which pairs
up with itself) therefore $n$ has a total of $2|S|+1$ divisors.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 9
\problem 
{ \it Prove by contradiction: the square root of an irrational number 
is irrational. }

Let $x$ be an irrational number.  Prove that \( \sqrt{x} \) is 
irrational.  

Proof by contradiction:

Assume for the purposes of contradiction, that \( \sqrt{x} \) is rational.  
Then we know that there exist integers $p$ and $q$ such that
\[ \sqrt{x} = \frac{p}{q}. \]   
Squaring both sides we get \[ x = \frac{p^2}{q^2} \]
Since the square of an integer is an integer, $p^2/q^2$ is a ratio of
integers, and therefore a rational number, making x a rational number.  
This, however, contradicts our original assertion that x is an irrational
number, so the theorem must be true.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 10
%by Santosh
\problem
You have a set of 5 identical-looking balls, and you are told that there
are only two possible values for the weight of each ball. 
You are allowed to compare the weights of (any) two balls (but only
two at a time). There are two possible outcomes of a comparison:
``equal'' or ``not equal'' ({\em not} which ball is heavier). 
Can you find a ball with the same weight as the majority of the  
balls in three comparisons?  
(For example if all five balls have the same weight, then any ball will do).

Label the balls with numbers 1 to 5.  
Consider the following weighting algorithm.


Compare balls 1 and 2.  

\begin{enumerate}
\item If 1 and 2 have different weight\\
\indent Compare 3 and 4.

  \begin{enumerate}
  \item If 3 and 4 have different weight pick 5.
  \item If 3 and 4 have the same weight, pick 3.
  \end{enumerate}

\item If 1 and 2 have the same weight\\
\indent Compare 2 and 3.

  \begin{enumerate}
  \item If 2 and 3 have the same weight, pick 3
  \item If 2 and 3 have different weights\\
        compare 2 and 4.

     \begin{enumerate}
     \item If 2 and 4 have the same weight, pick 4.
     \item If 2 and 4 have different weight, pick 5.
     \end{enumerate}

  \end{enumerate}

\end{enumerate}


Now we prove that this algorithm will always give a correct ball by considering
three cases.


\begin{description}
\item{case 1: } All the balls have the same weight.
 
In this case the algorithm works, because it returns ball 3 which has the 
weight of the majority.

\item{case 2: } Four balls have the same weigh. We have 3 subcases:

a) The ball with different weight is 1 or 2.\\
b) The ball with different weight is 3.\\
c) The ball with different weight is 4 or 5.\\


If the case is (a), then in step (1) of the algorithm, the weights are 
different and in step (1b) they are the same.  Therefore, the algorithm picks
ball 3 which is a correct choice.

If the case is (b), then in step (1) of the algorithm, the weights are 
the same and in step (2) they are different.  Then the algorithm 
compares 2 and 4 picks ball 4 which is a correct choice.

If the case is (c), then in step (1) of the algorithm, the weights are 
the same, and in step (2) they are also the same.  So the algorithm returns
ball 3 which is a correct choice.
  
\item{case 3: } Three balls have the same weight.  

A case analysis must distinguish 10 cases. We provide a simpler proof.
Let $M$ be the set of balls with the weight of the majority (containing 3
 balls), and $m$ the set of the remaining balls.

We go through the algorithm.  

Case 1: If 1 and 2 have different weight, they belong to 
different sets.  If 3 and 4 have different weight (1a of the algorithm) then 
they also belong to different sets, and since $M$ has to contain three balls,
ball 5 has
to be in $M$ so the algorithm returns a correct ball.  If 3 and 4 have the same
weight, then they also have the same weight with either 1 or 2, do they belong 
to a set of three elements, namely $M$.  The algorithm returns ball 3
 which is a correct choice.

Case 2: If 1 and 2 have the same weight they are in the same set. 
If 2 and 3 have the
same weight (step 1a) then $M = \{1,2,3 \}$, and the algorithm returns a 
correct choice.
If 2 and 3 have different weights, then 2 is compared to 4. If they have the 
same weight, then $M = \{1,2,4 \}$, and the algorithm returns a correct choice.
If 2 and 4 also have different weights, then we know that one of the sets
contains 1 and 2 and the other set contains 3 and 4. 
 In either case ball 5 has to be in $M$.

\end{description}


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