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

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

\pset{1}{September 10, 1998}{Start of class on September 15, 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$.)

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

\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.)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%\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)
%$
%
%\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)
%$
%
%\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}

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

\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.

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

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

\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.
\problempart $n$ is a prime number.
\problempart $n$ is a product of exactly two primes.

\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.

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

\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.
%
%\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.
%
%\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 $\{
\text{Bill}, \text{Monica}, \text{Ken}, \text{Linda}, \text{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.

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

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

\problempart Everyone likes someone and dislikes someone else.

\end{problemparts}

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

\newpage

\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) = \text{true}$ if and only if $x$ is guilty.
\item $(\exists x G(x)) \wedge (\exists x (\neg G(x)))$
\item $(G(\text{Duran}) \vee G(\text{Khurshid})) \rightarrow
		\neg G(\text{Sherman})$
\item $\neg (G(\text{Khurshid}) \wedge G(\text{Lehman}))$
\item $\neg G(\text{Sherman}) \rightarrow (\exists x \exists y (x \neq
y \wedge G(x) \wedge G(y))$

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

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

\end{problems}
\end{document}
