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

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

\psol{1}{September 17, 1998}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problems}

\problem
Let $A$, $B$, and $C$ be sets.  Assume that $A \cap
B \cap C = \emptyset$.  Prove that

\[
A \cup B \cup C = (A \setminus B) \cup (B \setminus C) \cup (C \setminus A).
\]

(Note: If $X$ and $Y$ are sets, then $X \setminus Y$ is the set of
elements in $X$ that are not in $Y$.)

\bigskip

\begin{proof}
We prove the equality by showing that the left set contains the right
set and vice versa.  Let $S$ be the set on the left, $A \cup B \cup
C$, and let $T$ be the set on the right, $(A \setminus B) \cup (B
\setminus C) \cup (C \setminus A)$.  Our objective is to prove that $S
= T$.

First, we show that $S$ is contained in $T$.  Let $x$ be an element of
$S = A \cup B \cup C$.  There are then six cases:

\begin{itemize}
\item $x \in A, x \not\in B, x \not\in C$: Since $x \in A$ and
$x \not\in B$, we have $x \in A \setminus B$, and so $x \in T$.

\item $x \not\in A, x \in B, x \not\in C$: Since $x \in B$ and
$x \not\in C$, we have $x \in B \setminus C$, and so $x \in T$.

\item $x \not\in A, x \not\in B, x \in C$: Since $x \in C$ and
$x \not\in A$, we have $x \in C \setminus A$, and so $x \in T$.

\item $x \in A, x \in B, x \not\in C$: Since $x \in B$ and
$x \not\in C$, we have $x \in B \setminus C$, and so $x \in T$.

\item $x \in A, x \not\in B, x \in C$: Since $x \in A$ and
$x \not\in B$, we have $x \in A \setminus B$, and so $x \in T$.

\item $x \not\in A, x \in B, x \in C$: Since $x \in C$ and
$x \not\in A$, we have $x \in C \setminus A$, and so $x \in T$.
\end{itemize}

In every case, $x \in T$ as well; therefore, every element of $S$ is
also an element of $T$, and so $S \subseteq T$.  (Note that the case
$x \in A, x \in B, x \in C$ does not exist, since $A \cap B \cap C =
\emptyset$ by assumption.)

Now we show that $T$ is contained in $S$.  Let $x$ be an element of $T
= (A \setminus B) \cup (B \setminus C) \cup (C \setminus A)$.  There
are then three cases:

\begin{itemize}
\item $x \in A \setminus B$:  This implies that $x \in A$, and so $x \in S$.
\item $x \in B \setminus C$:  This implies that $x \in B$, and so $x \in S$.
\item $x \in C \setminus A$:  This implies that $x \in C$, and so $x \in S$.
\end{itemize}

In every case, $x \in S$ as well; therefore, every element of $T$ is
also an element of $S$, and so $T \subseteq S$.  Since set $S$
contains set $T$ and vice versa, $S$ and $T$ must be the same set;
that is, $S = T$.
\end{proof}

\bigskip

The following alternative presentation of the proof may make the
structure of the argument more clear.

\begin{proof}
Goal: show that if $A \cap B \cap C = \emptyset$, then $A \cup B \cup
C = (A \setminus B) \cup (B \setminus C) \cup (C \setminus A)$.

\begin{enumerate}
\item Let $S = A \cup B \cup C$.
\item Let $T = (A \setminus B) \cup (B \setminus C) \cup (C \setminus A)$.
\item $S \subseteq T$
	\begin{enumerate}
	\item Let $x$ be an element of $S$.
	\item If $x \in A, x \not\in B, x \not\in C$,
		then $x \in A \setminus B \subseteq T$
		by definition of $\setminus$ and of $T$.
	\item If $x \not\in A, x \in B, x \not\in C$,
		then $x \in B \setminus C \subseteq T$
		by definition of $\setminus$ and of $T$.
	\item If $x \not\in A, x \not\in B, x \in C$,
		then $x \in C \setminus A \subseteq T$
		by definition of $\setminus$ and of $T$.
	\item If $x \in A, x \in B, x \not\in C$,
		then $x \in B \setminus C \subseteq T$
		by definition of $\setminus$ and of $T$.
	\item If $x \in A, x \not\in B, x \in C$,
		then $x \in A \setminus B \subseteq T$
		by definition of $\setminus$ and of $T$.
	\item If $x \not\in A, x \in B, x \in C$,
		then $x \in C \setminus A \subseteq T$
		by definition of $\setminus$ and of $T$.
	\item Q. E. D. by exhaustive case analysis.
	\end{enumerate}
\item $T \subseteq S$
	\begin{enumerate}
	\item Let $x$ be an element of $T$.
	\item If $x \in A \setminus B$, then $x \in A \subseteq S$
		by definition of $\setminus$ and of $S$.
	\item If $x \in B \setminus C$, then $x \in B \subseteq S$.
		by definition of $\setminus$ and of $S$.
	\item If $x \in C \setminus A$, then $x \in C \subseteq S$.
		by definition of $\setminus$ and of $S$.
	\item Q. E. D. by exhaustive case analysis.
	\end{enumerate}
\item Q. E. D. since two-way set inclusion implies equality.
\end{enumerate}
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem A real number $r$ is called {\em sensible} if there
exist positive integers $a$ and $b$ such that $\sqrt{a / b} = r$.  For
example, setting $a = 2$ and $b = 1$ shows that $\sqrt{2}$ is
sensible.  Prove that $\sqrt[3]{2}$ is not sensible.  (Consider only
positive real roots in this problem.)

\bigskip

\begin{proof}
The proof is by contradiction.  Assume for the purpose of
contradiction that $\sqrt[3]{2}$ is sensible.  Then there exist
positive integers $a$ and $b$ such that $\sqrt{a / b} = \sqrt[3]{2}$.
Squaring both sides of this equation gives $a / b = \sqrt[3]{4}$,
which implies that $\sqrt[3]{4}$ is rational.

Since $\sqrt[3]{4}$ is rational, we can write it as a fraction $x / y$
in lowest-terms, where $x$ is an integer and $y$ is a positive
integer.  Therefore, we have:

\begin{eqnarray*}
\sqrt[3]{4}	& = &	x / y \\
4		& = &	x^3 / y^3 \\
4 y^3		& = &	x^3
\end{eqnarray*}

In the last equation, the left side is even, and so the right side
must be even.  Since $x^3$ is even, $x$ itself must be even.  This
implies that the right side is actually divisible by 8, and so the
left side must also be divisible by 8.  Therefore, $y^3$ is even, and
so $y$ itself must be even.

The fact that both $x$ and $y$ are even contradicts the fact that $x /
y$ is a fraction in lowest terms.  Therefore, $\sqrt[3]{2}$ is not
sensible.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%\problem Use truth tables to determine whether the following propositions are
%tautologies.  In each case, your truth table should indicate truth
%values not only for the complete proposition, but also for the
%subexpressions to the left and right of the central $\vee$.
%
%\begin{problemparts}
%
%\problempart
%$(p \wedge q) \vee (q \wedge r) \vee (r \wedge p) \quad \vee \quad
%(\neg p \wedge \neg q) \vee (\neg q \wedge \neg r) \vee (\neg r \wedge
%\neg p)$
%
%
%\[
%\begin{array}{ccc|c|c|c}
%p & q & r & (p \wedge q) \vee (q \wedge r) \vee (r \wedge p) &
%(\neg p \wedge \neg q) \vee (\neg q \wedge \neg r) \vee
%(\neg r \wedge \neg p) &
%\begin{array}{c}
%\mbox{complete} \\
%\mbox{proposition} 
%\end{array} \\ \hline
%T & T & T & T & F & T \\
%T & T & F & T & F & T \\
%T & F & T & T & F & T \\
%T & F & F & F & T & T \\
%F & T & T & T & F & T \\
%F & T & F & F & T & T \\
%F & F & T & F & T & T \\
%F & F & F & F & T & T
%\end{array}
%\]
%
%The proposition is a tautology.
%
%\problempart
%$(p \wedge q) \vee (q \wedge r) \vee (r \wedge s) \vee (s \wedge p)
%\quad \vee \quad
%(\neg p \wedge \neg q) \vee (\neg q \wedge \neg r) \vee (\neg r \wedge
%\neg s) \vee (\neg s \wedge \neg p)$
%
%\[
%\begin{array}{cccc|c|c|c}
%p & q & r & s &
%\begin{array}{c}
%(p \wedge q) \vee (q \wedge r) \vee \\
%(r \wedge s) \vee (s \wedge p)
%\end{array} &
%\begin{array}{c}
%(\neg p \wedge \neg q) \vee (\neg q \wedge \neg r) \vee \\
%(\neg r \wedge \neg s) \vee (\neg s \wedge \neg p)
%\end{array} &
%\begin{array}{c}
%\mbox{complete} \\
%\mbox{proposition} 
%\end{array} \\ \hline
%T & T & T & T & T & F & T \\
%T & T & T & F & T & F & T \\
%T & T & F & T & T & F & T \\
%T & T & F & F & T & T & T \\
%T & F & T & T & T & F & T \\
%T & F & T & F & F & F & F \\
%T & F & F & T & T & T & T \\
%T & F & F & F & F & T & T \\
%F & T & T & T & T & F & T \\
%F & T & T & F & T & T & T \\
%F & T & F & T & F & F & F \\
%F & T & F & F & F & T & T \\
%F & F & T & T & T & T & T \\
%F & F & T & F & F & T & T \\
%F & F & F & T & F & T & T \\
%F & F & F & F & F & T & T
%\end{array}
%\]
%
%The proposition is not a tautology.
%
%\end{problemparts}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Rewrite each of the following expressions using the symbols
$\rightarrow$ and $\neg$, but not the symbols $\vee$ and $\wedge$.

\begin{problemparts}

\problempart  $p \vee q \vee \neg r$
\problempart  $p \wedge q \wedge \neg r$
\problempart  $\neg((p \vee \neg q) \wedge \neg (\neg r \vee s))$

\end{problemparts}

\bigskip

First, we will derive rules for translating and's and or's into
implications.  Then we will apply these rules to rewrite the given
expressions.

Recall that the expression $a \rightarrow b$ is equivalent to $\neg a
\vee b$.  Substituting $a = \neg c$ and $b = d$, we find that $c \vee
d$ can be rewritten as $\neg c \rightarrow d$.  Similarly, the
expression $\neg (a \rightarrow b)$ is equivalent to $\neg (\neg a
\vee b)$.  We can rewrite this last expression as $(a \wedge \neg b)$
by using DeMorgan's Law.  Substituting $a = c$ and $b = \neg d$, we
find that $c \wedge d$ can be rewritten as $\neg (c \rightarrow \neg
d)$.  In summary:

\begin{eqnarray*}
c \vee d	& = &	\neg c \rightarrow d \\
c \wedge d	& = &	\neg (c \rightarrow \neg d) \\
\end{eqnarray*}

The given expressions can now be translated using these two rules.

{\bf Part (a).}

\begin{eqnarray*}
p \vee q \vee \neg r
	& = &	(p \vee q) \vee \neg r \\
	& = &	(\neg p \rightarrow q) \vee \neg r \\
	& = &	\neg (\neg p \rightarrow q) \rightarrow \neg r
\end{eqnarray*}

{\bf Part (b).}

\begin{eqnarray*}
p \wedge q \wedge \neg r
	& = &	(p \wedge q) \wedge \neg r \\
	& = &	(\neg (p \rightarrow \neg q)) \wedge \neg r \\
	& = &	\neg((\neg (p \rightarrow \neg q)) \rightarrow r)
\end{eqnarray*}

{\bf Part (c).}

\begin{eqnarray*}
\neg((p \vee \neg q) \wedge \neg (\neg r \vee s))
	& = &	\neg((\neg p \rightarrow \neg q) \wedge
			\neg (r \rightarrow s)) \\
	& = &	(\neg p \rightarrow \neg q) \rightarrow (r \rightarrow s))) \\
	& = & 	(q \rightarrow p) \rightarrow (r \rightarrow s)
\end{eqnarray*}

The very last step is a simplification using the fact that the
implication $q \rightarrow p$ is equivalent to the contrapositive
$\neg p \rightarrow \neg q$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem A student is trying to prove that propositions $p$, $q$, and $r$ are
all true.  She proceeds as follows.  First, she proves three facts: $p
\rightarrow q$, $q \rightarrow r$, and $r
\rightarrow p$.  Then she concludes, ``Thus obviously $p$, $q$, and
$r$ are all true.''

\begin{problemparts}

\problempart Using logic notation and the symbols $p$, $q$, and $r$,
write down the logical implication that she uses in her final step.

\[
((p \rightarrow q) \wedge (q \rightarrow r) \wedge (r \rightarrow p))
\rightarrow (p \wedge q \wedge r)
\]

\problempart Use a truth table to determine whether this logical
implication is a tautology.

\[
\begin{array}{ccc|c|c|c}
p & q & r &
((p \rightarrow q) \wedge (q \rightarrow r) \wedge (r \rightarrow p)) &
(p \wedge q \wedge r) &
\begin{array}{c}
\mbox{complete} \\
\mbox{expression}
\end{array} \\ \hline
T & T & T & T & T & T \\
T & T & F & F & F & T \\
T & F & T & F & F & T \\
T & F & F & F & F & T \\
F & T & T & F & F & T \\
F & T & F & F & F & T \\
F & F & T & F & F & T \\
F & F & F & T & F & \rightarrow F \leftarrow
\end{array}
\]

The truth table indicates that the implication that she uses is {\em
not} a tautology.

\problempart Is her proof that propositions $p$, $q$, and $r$ are all
true correct?

Her proof is incorrect; she makes use of a
false proposition.  (However, the first part of her argument is
sufficient to show that either all three statements are true {\em or}
all three statements are false.)

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Express each of the following statements in formal
logic notation.  In addition to the usual logic symbols and variables,
you may build predicates using addition, multiplication, constants,
and equality and inequality symbols.  The domain of discourse is the
non-negative integers.  For example, the statement ``$n$ is an odd
number'' could be written ``$\exists x (2 \cdot x + 1 = n)$''.

\begin{problemparts}

\problempart $n$ is the sum of three perfect squares.

\[
\exists x \exists y \exists z (x \cdot x + y \cdot y + z \cdot z = n)
\]

\problempart $n$ is a prime number.

\[
(n > 1) \wedge \neg (\exists x \exists y ((x > 1) \wedge (y > 1) \wedge (x \cdot y = n))
\]

\problempart $n$ is a product of exactly two primes.

\begin{eqnarray*}
\exists x \exists y & ( &
	(x > 1) \wedge \neg (\exists a \exists b ((a > 1) \wedge (b > 1) \wedge (a \cdot b = x))) \wedge \\
	& & (y > 1) \wedge \neg (\exists c \exists d ((c > 1) \wedge (d > 1) \wedge (c \cdot d = y))) \wedge \\
	& & (x \cdot y = n))
\end{eqnarray*}

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem A self-proclaimed ``great logician'' has invented a
new quantifier, on par with $\exists$ (``there exists'') and $\forall$
(``for all'').  The new quantifier is symbolized by $\exists!$ and
read ``there exists a unique''.  The proposition $\exists!x P(x)$ is
true if there is exactly one $x$ in the domain of discourse for which
$P(x)$ is true.  The logician has noted, ``There used to be two
quantifiers, but now there are three!  I have extended the whole field
of mathematics by 50\%!''

\begin{problemparts}

\problempart Rewrite the proposition $\exists! x P(x)$ using only the
$\exists$ quantifier.

\[
\exists x (P(x) \wedge \neg (\exists y (x \neq y \wedge P(y)))
\]

\problempart Rewrite the proposition $\exists! x P(x)$ using only the
$\forall$ quantifier.

\[
\neg \forall x (\neg P(x) \vee \neg \forall y (x = y \vee \neg P(y))
\]

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%\problem
%
%\begin{problemparts}
%
%\problempart {\bf (Oiler's Conjecture)} The following claim,
%often confused with the famous Euler Conjecture, was made by the
%driver of a heating-oil truck in Cambridge.  Prove or disprove: the
%equation $a^3 + b^3 + c^3 + d^3 = e^3$ has no solutions when $a$, $b$,
%$c$, $d$, and $e$ are all positive integers.
%
%The claim is false.  One solution to the equation is:
%
%\[
%1^3 + 1^3 + 5^3 + 7^3 = 343 = 7^3
%\]
%
%\problempart {\bf (The Goldenbacher Conjecture)} The oiler's brother-in-law,
%Stu Goldenbacher, has made a claim of his own, which is similar to the
%well-known Goldbach Conjecture.  Prove or disprove: every positive
%even number is the sum of at most two primes, one of which has a
%single digit.  As evidence for his conjecture, Stu points out that 2 =
%2, 4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3, 10 = 5 + 5, and 12 = 7 + 5.
%
%There are only four possible ways to write a number $n$ as the sum of
%a single digit prime and another number: $2 + (n-2)$, $3 + (n-3)$, $5
%+ (n-5)$, and $7 + (n-7)$.  If there exists an $n$ such that $n-2$,
%$n-3$, $n-5$, and $n-7$ are all composite, then there is no way to
%write $n$ as the sum of two primes, one of which has a single digit,
%and the conjecture is disproved.
%
%Such is the case if, for example, we choose $n = 2 \cdot 3 \cdot 5
%\cdot 7 = 210$.  Then we have
%
%\begin{eqnarray*}
%n-2 & = & 2 \cdot(3 \cdot 5 \cdot 7 - 1) \quad \mbox{composite} \\
%n-3 & = & 3 \cdot(2 \cdot 5 \cdot 7 - 1) \quad \mbox{composite} \\
%n-5 & = & 5 \cdot(2 \cdot 3 \cdot 7 - 1) \quad \mbox{composite} \\
%n-7 & = & 7 \cdot(2 \cdot 3 \cdot 5 - 1) \quad \mbox{composite}
%\end{eqnarray*}
%
%Therefore, the conjecture is false.
%
%\end{problemparts}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem
A media tycoon has an idea for an all-news television network called
LNN: The Logic News Network.  Each segment will begin with a
definition of the domain of discourse and a few predicates.  The day's
happenings can then be communicated concisely in logic notation.  For
example, a broadcast might begin as follows:

\begin{quotation}
``THIS IS LNN.  The domain of discourse is $\{
\mbox{Bill}, \mbox{Monica}, \mbox{Ken}, \mbox{Linda}, \mbox{Betty}
\}$.  Let $D(x)$ be a predicate that is true if $x$ is deceitful.  Let
$L(x, y)$ be a predicate that is true if $x$ likes $y$.  Let $G(x, y)$
be a predicate that is true if $x$ turned over gifts to $y$.''
\end{quotation}

Complete the broadcast by translating the following statements into
logic notation.

\begin{problemparts}

\problempart If neither Monica nor Linda is deceitful, then Bill and
Monica like each other.

\[
(\neg (D(\mbox{Monica}) \vee D(\mbox{Linda}))) \rightarrow
(L(\mbox{Bill}, \mbox{Monica}) \wedge L(\mbox{Monica}, \mbox{Bill}))
\]

\problempart Everyone except for Ken likes Betty, and no one except Linda
likes Ken.

\begin{eqnarray*}
\forall x ((x  =   \mbox{Ken} \wedge \neg L(x, \mbox{Betty})) \vee
           (x \neq \mbox{Ken} \wedge      L(x, \mbox{Betty}))) \wedge \\
\quad \quad
\forall x ((x  =   \mbox{Linda} \wedge      L(x, \mbox{Ken})) \vee
           (x \neq \mbox{Linda} \wedge \neg L(x, \mbox{Ken})))
\end{eqnarray*}

\problempart If Ken is not deceitful, then Bill turned over gifts to
Monica, and Monica turned gifts over to someone.

\[
\neg D(\mbox{Ken}) \rightarrow
	(G(\mbox{Bill}, \mbox{Monica}) \wedge
	\exists x G(\mbox{Monica}, x))
\]

\problempart Everyone likes someone and dislikes someone else.

\[
\forall x \exists y \exists z (y \neq z \wedge L(x, y) \wedge \neg L(x, z))
\]

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem {\bf (The Mystery)} The 6.042 mascot, Theory Pig, was
recently found squished under a pile of course handouts.  Fortunately,
Theory Pig is okay and is getting his stuffing sorted out.  However,
he demands that the culprit or culprits be found.  The only clue is a
crumpled paper found nearby scrawled over with logic notation:

\begin{enumerate}
\item Domain of discourse $= \{ Duran, Khurshid, Lehman, Gould, Sherman \}$.
\item $G(x) = \mbox{true}$ if and only if $x$ is guilty.
\item $(\exists x G(x)) \wedge (\exists x (\neg G(x)))$
\item $(G(\mbox{Duran}) \vee G(\mbox{Khurshid})) \rightarrow
		\neg G(\mbox{Sherman})$
\item $\neg (G(\mbox{Khurshid}) \wedge G(\mbox{Lehman}))$
\item $\neg G(\mbox{Sherman}) \rightarrow (\exists x \exists y (x \neq
y \wedge G(x) \wedge G(y))$

\item $(G(\mbox{Duran}) \rightarrow G(\mbox{Sherman})) \wedge
	(G(\mbox{Sherman}) \rightarrow G(\mbox{Duran}))$
\item $\neg (G(\mbox{Lehman}) \wedge G(\mbox{Gould}))$
\end{enumerate}

Who squished Theory Pig?  State your answer and sketch your deductive
process.

\bigskip

Theory Pig was squished by Khurshid and Gould.

A straightforward, but laborious way to solve this problem is to write
out a table with $2^5 = 32$ entries, one for each guilty/innocent
combination.  If we cross off each entry that is contradicted by a
statement on the crumpled paper, then the single, remaining entry
indicates the culprits.

Here is an alternative, ad hoc approach.  Sherman appears often, so
let's first try to determine whether he is guilty.  Suppose that
Sherman is guilty.  Then by statement 4, neither Duran nor Khurshid
can be guilty.  However, by statement 7, Duran must be guilty.  This
is a contradiction with respect to Duran, and so Sherman must be
innocent.  Since Sherman is innocent, statement 7 implies that Duran
is also innocent, and statement 6 implies that there are at least two
culprits among the remaining three suspects, Khurshid, Lehman, and
Gould.  Suppose that Lehman is guilty.  Then Khurshid and Gould are
both innocent by statements 5 and 8.  This would imply only one
cuprit, giving a contradiction.  Therefore, Lehman must be innocent.
Since there are at least two culprits, Khurshid and Gould must both be
guilty.

(The simplest approach, of course, is a careful scrutiny of the moral
fibre of your TAs.)
\end{problems}
\end{document}