\documentstyle[12pt,twoside]{article}

\newcommand{\problem}{%
  \paragraph{Problem}}
\newcommand(\solution}{%
  \paragraph{Solution}}

\begin{document}

\begin{problems}

%BEGIN Kavita's problems
% Fall 1998


%**************
%   PSET 1    *
%**************

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%\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
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   Kavita's problems

%BEGIN Joe's problems
\problem In some computer architectures, the basic computer operation
is ``NAND'', denoted~$\nand$, where $A \nand B$ means $\neg (A \land
B)$.  Show that all the basic boolean operations can be implemented
using the single $\nand$ operation.  That is, rewrite each of the
following formulas as equivalent formulas using only the $\nand$
operator (and parentheses).

\begin{minipage}[t]{1.5in}
\begin{problemparts}
\ppart $\neg A$
\ppart $A \lor B$
\ppart $A \land B$
\ppart $A \implies B$
\end{problemparts}
\end{minipage}

\solution{
\textbf{Solutions:}
\setcounter{problempartnum}{0}
\begin{minipage}[t]{3.5in}
\begin{problemparts}
\ppart $A \nand A$
\ppart $(A \nand A) \nand (B \nand B)$
        \quad ($\Longleftrightarrow
         \neg ( \neg A \land \neg B)
        \Longleftrightarrow 
        \neg A \nand \neg B$)
\ppart $(A \nand B) \nand (A \nand B)$ 
        \quad ($\Longleftrightarrow \neg(A \nand B)$)
\ppart $A \nand (B \nand B)$
        \quad ($\Longleftrightarrow B \lor \neg A$)
\end{problemparts}
\end{minipage}
}

\problem Identify the premises and conclusions of the following
deductive arguments and analyze their logical forms.  This may require
that you ``pin down'' a statement that could be interpreted many ways.
Determine which are valid deductions and which are not.  If the
deduction is invalid, demonstrate a possible scenario in which all the
premises are met but the conclusion is not.

\textbf{Note:} There are several ways to formalize many of these statements in
logical notation.  We will accept any \emph{reasonable} reading of the English.
Below, we show one such solution for each part.

\begin{problemparts}
\ppart Jane and Pete won't both win the math prize.  Pete will win
either the math prize or the chemistry prize.  Jane will win the math
prize.  Thus, Pete will win the chemistry prize.

\solution{
\textbf{Solution:} The deduction is:
\begin{center}
\begin{tabular}{l}
        $\neg (J \land M)$ \\
        $M \lor C$ \\ 
        $J$ \\ \hline
        $\therefore C$
\end{tabular}
\quad where 
\begin{tabular}{l}
        $J \equiv \mbox{``Jane will win the math prize.''}$ \\
        $M \equiv \mbox{``Pete will win the math prize.''}$ \\
        $C \equiv \mbox{``Pete will win the chemistry prize.''}$
\end{tabular}
\end{center}
This deduction is valid.  
}
\ppart The main course will be beef or fish.  The vegetable will be
peas or corn. We will not have both fish as a main course and corn as
a vegetable. Therefore, we will not have both beef as a main course
and peas as a vegetable.
\solution{
\textbf{Solution:} The deduction is:
\begin{center}
\begin{tabular}{l}
        $B \lor F$ \\
        $C \lor P$ \\
        $\neg (F \land C)$ \\ \hline
        $\therefore \neg (B \land P)$
\end{tabular}
\quad where 
\begin{tabular}{l}
        $B \equiv \mbox{``The main course will be beef.''}$ \\
        $F \equiv \mbox{``The main course will be fish.''}$ \\
        $C \equiv \mbox{``The vegetable will be corn.''}$ \\
        $P \equiv \mbox{``The vegetable will be peas.''}$ 
\end{tabular}
\end{center}
This deduction is invalid.  For example, $B \land \neg F \land C \land
P$ is consistent with the premises but not with the conclusion.  Note
that as formalized, there need not be only one main course and only
one vegetable; it is possible, for example, for the vegetable to be
both corn and peas, as in the scenario given.  If we wished to exclude
the possibility of multiple courses we could have used exclusive-or
instead of inclusive-or. So our premise about the main course would
then read $B \oplus F$ or, equivalently, 
$(B \lor F) \land \neg (B \land F)$. 
The premise about the vegetable could be changed similarly.  
The deduction is still invalid with this formalization. 
}

\ppart Either John or Bill is telling the truth.  Either Sam or Bill
is lying.  Thus, either John is telling the truth or Sam is lying.

\solution{
\textbf{Solution:}
We interpret ``John is lying,'' to be 
the negation of ``John is telling the truth.'' 
Similarly for the corresponding propositions involving Bill and Sam.
The deduction is:
\begin{center}
\begin{tabular}{l}
        $J \lor B$ \\
        $\neg S \lor \neg B$ \\ \hline
        $\therefore J \lor \neg S$
\end{tabular}
\quad where 
\begin{tabular}{l}
        $J \equiv \mbox{``John is telling the truth.''}$ \\
        $B \equiv \mbox{``Bill is telling the truth.''}$ \\
        $S \equiv \mbox{``Sam is telling the truth.''}$
\end{tabular}
\end{center}
This deduction is valid.  It is an example of a common
``cancellation'' rule that lets us get rid of the proposition $B$.
}

\ppart Either sales will go up and the boss will be happy, or expenses
will go up and the boss won't be happy.  Therefore, sales and expenses
will not both go up.

\solution{
\textbf{Solution:} The deduction is:
\begin{center}
\begin{tabular}{l}
        $(S \land H) \lor (E \land \neg H)$ \\ \hline
        $\therefore \neg (S \land E)$
\end{tabular}
\quad where 
\begin{tabular}{l}
        $S \equiv \mbox{``Sales will go up.''}$ \\
        $H \equiv \mbox{``The boss will be happy.''}$ \\
        $E \equiv \mbox{``Expenses will go up.''}$ 
\end{tabular}
\end{center}
This deduction is invalid. 
For example, $S \land E \land H$ is consistent 
with the premises but not with the conclusion. 
}

\ppart If the tax rate and unemployment both go up then there will be
a recession.  If the GNP goes up there will not be a recession.  GNP
and taxes are both going up.  Therefore, there will not be a
recession.

\solution{
\textbf{Solution:}
The deduction is:
\begin{center}
\begin{tabular}{l}
        $T \land U \implies R$ \\
        $G \implies \neg R$ \\
        $G \land T$ \\ \hline
        $\therefore \neg R$
\end{tabular}
\quad where 
\begin{tabular}{l}
        $T \equiv \mbox{``The tax rate goes up.''}$ \\
        $U \equiv \mbox{``Unemployment goes up.''}$ \\
        $G \equiv \mbox{``GNP goes up.''}$ \\
        $R \equiv \mbox{``There will be a recession.''}$
\end{tabular}
\end{center}
This deduction is valid. 
(The first premise is superfluous.)
}
\end{problemparts}

\problem Let $F(x,y)$ be the predicate ``$x$ can fool $y$'' and the
universe of discourse be the set of all people.  Use quantifiers to
express the following statements.
\begin{problemparts}
\ppart Everybody can fool Fred. \\
\solution{
\textbf{Solution:}
$\forall x F(x,\textrm{Fred})$
}
\ppart Evelyn can fool everybody. \\
\solution{
\textbf{Solution:}
$\forall y F(\textrm{Evelyn},y)$
}
\ppart Everybody can fool somebody. \\
\solution{
\textbf{Solution:}
$\forall x \exists y F(x,y)$
}
\ppart No one can fool everybody. \\
\solution{
\textbf{Solution:}
$\neg \exists x \forall y F(x,y)$
}
\ppart Everybody can be fooled by somebody. \\
\solution{
\textbf{Solution:}
$\forall y \exists x F(x,y)$
}
\ppart Nancy can fool exactly two people. \\
\solution{
\textbf{Solution:}
$\exists x \exists y 
    (x \neq y  
        \land F(\textrm{Nancy}, x)
        \land F(\textrm{Nancy}, y)
        \land \forall z 
                (z \neq x \land z \neq y \implies \neg F(\textrm{Nancy},z)))$
Alternatively: 
$\exists x \exists y 
    (x \neq y  
        \land F(\textrm{Nancy}, x)
        \land F(\textrm{Nancy}, y)
        \land \forall z 
                (z = x \lor z = y \lor \neg F(\textrm{Nancy},z)))$

Note that by convention, different logical operators bind more or less tightly.
Quantifiers and negation bind most tightly; 
$\land$ and $\lor$ bind more tightly than $\implies$.
}
\ppart There is exactly one person whom everybody can fool. \\
\solution{
\textbf{Solution:}
$\exists! y \forall x F(x,y)$. 

Note that $\exists! y P(y)$ is logically equivalent to 
$\exists y (P(y) \land \forall z (z \neq y \implies \neg P(z)))$. 
Thus, it is possible to rewrite the statement as 
$\exists y (\forall x F(x,y) 
                \land \forall z (z \neq y \implies \neg \forall x F(x,z)))$. 
}
\ppart There is someone who can fool exactly one person besides him- or
herself. \\
\solution{
\textbf{Solution:}
$\exists x \exists! y (x \neq y \land F(x,y))$.  
(This can be rewritten without $\exists!$ as we did above.)
%or $\exists y (x \neq y \land F(x,y) 
%               \land \forall z (z \neq y \implies \neg (x \neq z \land F(x,z))))$. 
}
\end{problemparts}

\problem Are these statements true or false?  The universe of
discourse is the natural numbers.  
(The set of natural numbers is $\{0,1,2, \ldots\}$.)

%\begin{minipage}[t]{3in}
\begin{problemparts}
\ppart $\forall x \exists y (2x-y=0)$
\solution{
\textbf{Solution:}
True. (Given a natural number $x$, consider $y = 2x$; $y$ is a natural number.)
}
\ppart $\exists y \forall x (2x-y=0)$
\solution{
\textbf{Solution:}
False. (Fix any $y$; there is always an $x > y/2$.)
}
\ppart $\forall x (x < 10 \implies \forall y (y < x \implies y < 9))$
\solution{
\textbf{Solution:}
True.  (Remember the universe of discourse is the natural numbers.)
}
\ppart $\forall x \exists y (y > x \land \exists z (y+z=100))$
\solution{
\textbf{Solution:} False. (If $x > 100$ then $y > 100$ so no $z \in \mathbb{N}$
works.)
}
\end{problemparts}

\problem \mbox{}
\begin{problemparts} 

\ppart
Show that $\forall x P(x) \lor \forall x Q(x)$ is not logically
equivalent to $\forall x (P(x) \lor Q(x))$.
\solution{
\textbf{Solution:}
The universal quantifier does not distribute over OR.  
Even if $\forall x (P(x) \lor Q(x))$, 
there may be two elements, $c_1$ and $c_2$, such that 
$P(c_1) \land \neg Q(c_1) \land \neg P(c_2) \land Q(c_2)$, 
and thus, $\neg (\forall x P(x) \lor \forall x Q(x))$. 

For example, suppose the universe of discourse is $\mathbb{N}$,
$P(x)$ is the proposition ``$x$ is even,'' and $Q(x)$ is the
proposition ``$x$ is odd.''  
It is not true that every natural number is even 
(i.e., $\neg \forall x P(x)$), 
nor is it true that every natural number is odd 
(i.e., $\neg \forall x Q(x)$). 
However, every natural number is either even or odd 
(i.e., $\forall x (P(x) \lor Q(x))$). 
}
\ppart 
Show that $\exists x (P(x) \implies Q(x))$ is logically equivalent to
$\forall x P(x) \implies \exists x Q(x)$.
\solution{
\textbf{Solution:}
First we show that the existential quantifier does distribute over OR:

\textbf{Lemma:} 
$\exists x (P(x) \lor Q(x))
                \Longleftrightarrow \exists x P(x) \lor \exists x Q(x)$. 

\textit{Proof:} 
In class, we showed one direction, 
that $\exists x (P(x) \lor Q(x))
                \Longrightarrow \exists x P(x) \lor \exists x Q(x)$. 
To see the other direction, 
suppose $\exists x P(x) \lor \exists x Q(x)$. 
We proceed by cases:
\begin{description}

\item[Case 1 ($\exists x P(x)$): ]
By existential instantiation, 
$P(c)$ for some $c \in U$. 
Therefore $P(c) \lor Q(c)$, 
and by existential generalization, 
$\exists x (P(x) \lor Q(x))$. 

\item[Case 2 ($\exists x Q(x)$): ]
This is exactly analogous to the previous case. 

\item[Exhaustive cases: ]
Since we have covered both disjuncts of our supposition, the two cases above are exhaustive.
\qed

\end{description}

We use this lemma in the following proof:
\begin{align*}
\exists x (P(x) \implies Q(x)) 
        & \Longleftrightarrow \exists x (\neg P(x) \lor Q(x)) 
                & \text{(truth table of $\implies$)} \\
        &\Longleftrightarrow \exists x \neg P(x) \lor \exists x Q(x) 
                & \text{(above lemma)} \\
        &\Longleftrightarrow \neg \forall x P(x) \lor \exists x Q(x) 
                & \text{(negation of $\forall$)} \\
        &\Longleftrightarrow \forall x P(x) \implies \exists x Q(x) 
                & \text{(truth table of $\implies$)} \\
\end{align*}
}
\end{problemparts}

\problem Consider the following theorem: Suppose $x$ is a real number
and $\frac{2x-5}{x-4}=3$ then $x=7$.
\begin{problemparts}
\ppart What is wrong with the following proof? Suppose $x=7$.  Then
\[
\frac{2x-5}{x-4}=\frac{2(7)-5}{7-4}=\frac{9}{3}=3.
\]
Thus, if $\frac{2x-5}{x-4}=3$ then $x=7$.
\solution{
\textbf{Solution:} This proof is a typical example of circular
reasoning.  We suppose $x=7$ and then conclude that $x=7$.  So, all we
have done is not contradict our supposition.  Unlike a proof by
contradiction, which shows our assumption is false, {\em not} arriving
a contradiction does {\em not} show our assumption is true.

In particular, the proof is of the form:
\begin{center}
\begin{tabular}{l}
        $P(x)$ \\
        $P(x) \implies Q(x)$ \\ \hline
        $\therefore Q(x) \implies P(x)$
\end{tabular}
\quad where 
\begin{tabular}{l}
        $P(x) \;\; \equiv\;\; x=7$ \\
        $Q(x) \;\; \equiv\;\; \frac{2x-5}{x-4}=3$ \\
\end{tabular}
\end{center}
The given ``proof'' does demonstrate that the second premise is true.  
However, the conclusion does not follow.
}
\ppart Give a correct proof of this theorem.
\solution{
\textbf{Solution:}
There are many ways to properly construct this proof.  We demonstrate a direct
proof using \emph{modus ponens}.

\begin{center}
\begin{tabular}{l}
        $Q(x)$ \\
        $Q(x) \implies P(x)$ \\ \hline
        $\therefore P(x)$
\end{tabular}
\quad where 
\begin{tabular}{l}
        $P(x) \;\; \equiv \;\; x=7$ \\
        $Q(x) \;\; \equiv \;\; \frac{2x-5}{x-4}=3$ \\
\end{tabular}
\end{center}
Proposition $Q(x)$ is given.  To complete the proof, we must now show that the
second premise (the implication) is a tautology.  
We do this using basic algebra and arithmetic:
\begin{align*}
Q(x) \equiv \frac{2x-5}{x-4} = 3 \;\;
        & \:\Longrightarrow \;\; 2x-5 = 3(x-4) \\ 
        & \Longleftrightarrow \;\; 2x-5 = 3x-12 \\
        & \Longleftrightarrow \;\; -5+12 = 3x-2x \\
        & \Longleftrightarrow \;\; 7 = x                &\equiv P(x) 
\end{align*}
}
\end{problemparts}

\problem Suppose $x$ is a real number.  Prove \textbf{by cases} that there is a
real $y$ such that $\frac{y+1}{y-2}=x$ if and only if $x \ne 1$.
\solution{
\textbf{Solution:}
We consider the cases $x \neq 1$ and $x = 1$ separately. 
\begin{description}

\item[Case 1 ($x \not = 1$): ]
We need to prove that there exists $y \in \mathbb{R}$ such that
$\frac{y+1}{y-2}=x$.  In particular, consider $y = \frac{2x+1}{x-1}$ (derived
by algebraic manipulation), which is a well-defined real number because $x \neq
1$.  Then:  
\[\frac{y+1}{y-2} 
        = \frac{\frac{2x+1}{x-1}+1}{\;\frac{2x+1}{x-1}-2\;} 
        = \frac{\frac{2x+1 + (x-1)}{x-1}}{\;\frac{2x+1-2(x-1)}{x-1}\;}
        = \frac{\frac{3x}{x-1}}{\;\frac{2x+1-2x+2}{x-1}\;}
        = \frac{3x}{3}
        = x
\]
Therefore, by existential generalization, $\exists y \in \mathbb{R}$ such that
$\frac{y+1}{y-2} = x.$

\item[Case 2 ($x = 1$): ]
We need to prove that no $y \in \mathbb{R}$ exists 
such that $\frac{y+1}{y-2}=x$. 
Suppose, for contradiction, that such a $y$ did exist.  Then:
\begin{align*}
\frac{y+1}{y-2} = x 
        &\Longleftrightarrow \;\; \frac{y+1}{y-2} = 1 
                & \text{(because $x = 1$)} \\
        &\:\Longrightarrow \;\; y+1 = y-2 
                & \text{(multiply both sides by $y-2$)} \\
        &\Longleftrightarrow \;\; 1 = -2 
                & \text{(subtract $y$ from both sides)} \\
        &\Longleftrightarrow \;\; \text{false.}
\end{align*}
Therefore our supposition is wrong, 
and there is no $y$ such that $\frac{y+1}{y-2}=x$. 

\end{description}
}

\problem Consider the following incorrect theorem:  
\[\text{If } \forall x \in A \; (x \ne 0) \text{ and }A \subseteq B \text{ then
}\forall x \in B \; (x \ne 0)\text{.}\] 

\vspace{-3ex}
\begin{problemparts}
\ppart What is wrong with the following proof of the theorem? Let $x$
be an arbitrary element of $A$.  Since $\forall x \in A \; (x \ne 0)$ we can
conclude $x \ne 0$.  Also, since $A \subseteq B$ we have $x \in B$.
Since $x \in B$, $x \ne 0$, and $x $ was arbitrary, we can conclude
(by universal generalization) that $\forall x \in B \; (x \ne 0)$.
\solution{
\textbf{Solution:}
Universal generalization requires that the generalized variable be
arbitrarily chosen \emph{from the set over which we are
generalizing}. We selected $x$ arbitrarily from set $A$ but are
generalizing over a different (larger) set $B$, 
which is not a valid inference rule.   To use universal generalization,
we should imagine an adversary picking the worst possible element from
the set over which we are generalizing.  The proof must work even for that
worst case.
}
\ppart Give a counterexample to the theorem.
\solution{
\textbf{Solution:} 
Let $A = \mathbb{N^+}$ and $B = \mathbb{Z}$. 
}
\end{problemparts}

%END   Joe's problems

%BEGIN Ray's problems

%%%%%%%%%%%%%%  S99 ps1


\problem (\S 1.1, Exercise 28) To make sense of this confusing
paragraph, let's introduce four boolean variables.

\begin{eqnarray*}
L	& = &	\text{file system locked} \\
N	& = &	\text{system operating normally} \\
Q	& = &	\text{messages are queued} \\
B	& = &	\text{messages are sent to the message buffer} \\
\end{eqnarray*}


Now we can translate the paragraph into logic notation as follows.

\begin{eqnarray*}
\neg L & \rightarrow & Q \\
\neg L & \leftrightarrow & N \\
\neg Q & \rightarrow & B \\
\neg L & \rightarrow & B \\
\neg B
\end{eqnarray*}

The specification is consistent if there is an assignment of truth
values to the variables that makes every expression true.

There are several ways to approach this problem.  One is to construct
a truth table with one line for each way of assigning truth values to
the variables that we defined, $L$, $N$, $Q$, and $B$.  For each
assignment, we could record the truth values of the five statements
above obtained from the system description.  If all five statements
are true for some assignment of truth values to the variables, then
the system is consistent; otherwise, the system is inconsistent.

We will use a more ad hoc approach here.  The final statement is true
only if $B$ is false.  This fact, together with the third and fourth
statements, imply that $Q$ is true and $L$ is true.  Since $L$ is
true, the second statement implies that $N$ is false.  Thus, we have
deduced the following:

\begin{eqnarray*}
L	& = &	\text{true} \\
N	& = &	\text{false} \\
Q	& = &	\text{true} \\
B	& = &	\text{false}
\end{eqnarray*}

With this assignment of truth values to variables, all of the five
statements are true, and so the system is consistent.



\problem (\S 1.2, Exercise 36) We give two proofs.  The first is from
first principles, but is rather intricate.  The second is simpler, but
assumes the result of problem 28 on page 20 of Rosen.

FIRST PROOF: We must show that for every compound proposition there is
an equivalent compound proposition containing only the NAND operator.

We can construct such a proposition as follows.  The new proposition
is the NAND of a set of subexpressions.  There is one such
subexpression for each assignment to the variables in the original
proposition that makes that proposition true.

A subexpression is formed from an assignment to the variables as
follows.  The subexpression is the NAND of many tiny expressions.  If
a variable $x$ is assigned the value TRUE, then the subexpression
contains the tiny expression $x$.  If variable $x$ is assigned the
value FALSE, then the subexpression contains the tiny expression $x
\text{ NAND } x$, which is logically equivalent to $\neg x$.

All that remains is to check that this new proposition is logically
equivalent to the original.  By the definition of NAND, the new
proposition is true if and only if one of the subexpressions is false.
Again by the definition of NAND, a subexpression is false if and only
if the variables are assigned a specific set of values that make the
original proposition true.  Since there is one such subexpression for
each assignment that makes the original expression true, the new
proposition is logically equivalent to the original.

\bigskip

SECOND PROOF: We must show that for every compound proposition there
is an equivalent compound proposition containing only the NAND
operator.  The result of problem 28 on page 20 of Rosen is that every
compound proposition is logically equivalent to a proposition
involving only $\neg$ and $\wedge$.  Consequently, it suffices to show
that every compound proposition involving only these two operators is
in turn logically equivalent to a proposition involving only the NAND
operator.

Given a compound proposition involving $\neg$ and $\wedge$, we
construct an equivalent proposition involving NAND by substitution as
follows.

\bigskip
\centerline{
\begin{tabular}{ccc}
replace this	& \hspace{1cm} & by this \\ \hline
$\neg p$	& & $p \text{ NAND } p$ \\
$p \wedge q$	& & $(p \text{ NAND } q) \text{ NAND } (p \text{ NAND } q)$
\end{tabular}
}
\bigskip

Truth tables establish that logical equivalence is preserved by these
substitutions.





\problem (\S 1.3, Exercise 10)

\begin{problemparts}
\problempart $\forall x \ F(x, \text{Fred})$
\problempart $\forall x \ F(\text{Evelyn}, x)$
\problempart $\forall x \ \exists y \ F(x, y)$
\problempart $\neg \exists x \ \forall y \ F(x, y)$
\problempart $\forall x \ \exists y \ F(y, x)$
\problempart $\neg \exists x \ (F(x, \text{Fred}) \wedge F(x, \text{Jerry}))$
\problempart $(\exists x \ \exists y \ (F(\text{Nancy}, x) \wedge F(\text{Nancy}, y) \wedge x \neq y)) \wedge \neg (\exists x \ \exists y \ \exists z \ (F(\text{Nancy}, x) \wedge F(\text{Nancy}, y) \wedge F(\text{Nancy}, z) \wedge x \neq y \wedge y \neq z \wedge x \neq z))$
\problempart $(\exists x \ \forall y \ F(y, x)) \wedge \neg (\exists x \ \exists y \ \forall z \ (F(z, x) \wedge F(z, y) \wedge x \neq y))$
\problempart $\neg \exists x \ F(x, x)$
\problempart $\exists x \ ((\exists y \ (F(x, y) \wedge x \neq y)) \wedge \neg (\exists y \ \exists z \ (F(x, y) \wedge F(x, z) \wedge y \neq z \wedge y \neq x \wedge z \neq x)))$
\end{problemparts}

\problem (\S 1.3, Exercise 26) Let the universe be the set of natural
numbers, $0, 1, 2, \ldots$.  Let $P(x)$ be the proposition that $x$ is
even, and let $Q(x)$ be the proposition that $x$ is odd.

In this case, the proposition $(\forall x \ P(x)) \vee (\forall x \
Q(x))$ is false; it is neither the case that every number is even nor
that every number is odd.  On the other hand, the proposition $\forall
x \ (P(x) \vee Q(x))$ is true; that is, every number is either even or
odd.

Since the first proposition can be false while the second proposition
is true, the two propositions are not equivalent.




%END   Ray's problems



%BEGIN George's problems
%fall00 Problem set 1
\problem \textbf{Propositional logic}
\bparts
\ppart Rosen \S 1.1, Exercise 24 (f).

\bigskip
\textbf{Solution:}\\
\begin{tabular}{ccc|cc||c}
$p$ & $q$ & $r$ & $p \land q$ & $\lnot r$ & $(p \land q) \lor \lnot r)$ \\ \hline
t & t & t & t & f & t \\
t & t & f & t & t & t \\
t & f & t & f & f & f \\
t & f & f & f & t & t \\
f & t & t & f & f & f \\
f & t & f & f & t & t \\
f & f & t & f & f & f \\
f & f & f & f & t & t \\ 
\end{tabular}
  

\ppart Rosen \S 1.2, Exercise 8 (c),(d).

\bigskip
\textbf{Solution:}\\
We construct a truth table for each implication and see that the relevant column contains only t's

\medskip
{\mathversion{bold} $[p \land (p \rightarrow q)] \rightarrow q$ } \\
\begin{tabular}{cc|cc||c}
$p$ & $q$ & $(p \rightarrow q)$ & $[p \land (p \rightarrow q)]$ & $[p \land (p \rightarrow q)] \rightarrow q$ \\ \hline
t & t & t & t & t \\
t & f & f & f & t \\
f & t & t & f & t \\
f & f & t & f & t \\
\end{tabular}

\medskip
{\mathversion{bold} $[(p \lor q) \land (p \rightarrow r) \land (q \rightarrow r)] \rightarrow r$} \\
\begin{tabular}{ccc|cccc||c}
$p$ & $q$ & $r$ & $(p \lor q)$ & $(p \rightarrow r)$ & $(q \rightarrow r)$ & $[(p \lor q) \land (p \rightarrow r) \land (q \rightarrow r)]$ & $[(p \lor q) \land (p \rightarrow r) \land (q \rightarrow r)] \rightarrow r$ \\ \hline
t & t & t & t & t & t & t & t \\   
t & t & f & t & f & f & f & t \\
t & f & t & t & t & t & t & t \\
t & f & f & t & f & t & f & t \\
f & t & t & t & t & t & t & t \\
f & t & f & t & t & f & f & t \\
f & f & t & f & t & t & f & t \\
f & f & f & f & t & t & f & t \\
\end{tabular}

\ppart Velleman \S 1.5, Exercise 6.

\bigskip
\textbf{Solution:}\\
{\mathversion{bold} $P \rightarrow (Q \rightarrow R)$}\\
$P \rightarrow (\lnot Q \lor R)$ [equivalence] \\
$\lnot P \lor (\lnot Q \lor R)$ [equivalence] \\
$\lnot P \lor \lnot Q \lor R$ [associative and commutative laws] 

\smallskip
{\mathversion{bold} $Q \rightarrow (P \rightarrow R)$}\\
$Q \rightarrow (\lnot P \lor R)$ [equivalence] \\
$\lnot Q \lor (\lnot P \lor R)$ [equivalence] \\
$\lnot P \lor \lnot Q \lor R$ [associative and commutative laws] 

\smallskip
{\mathversion{bold} $(P \rightarrow Q) \land (P \rightarrow R)$}\\
$(\lnot P \lor Q) \land (\lnot P \lor R)$ [equivalence]

\smallskip
{\mathversion{bold} $(P \land Q) \rightarrow R$}\\
$\lnot(P \land Q) \rightarrow R$ [equivalence]\\
$\lnot P \lor \lnot Q \lor R$ [De Morgan's law]

\smallskip
{\mathversion{bold} $P \rightarrow (Q \land R)$}\\
$\lnot P \lor (Q \land R)$ [equivalence] \\
$(\lnot P \lor Q) \land (\lnot P \lor R)$ [distributive law] 

\medskip
For the values $P$ = true, $Q$ = false, $R$ = false, \\
$\lnot P \lor \lnot Q \lor R$ evaluates to true \\
$(\lnot P \lor Q) \land (\lnot P \lor R)$ evaluates to false \\
thus, these two expressions are not equivalent.

\smallskip
Thus, Parts (a), (b) and (d) are equivalent. Parts (c) and (e) are equivalent.

\eparts

%fall00 Problem set 1
\problem  \textbf{Set theory}
\bparts
\ppart Rosen \S 1.4, Exercise 16 (a),(b),(c),(d).  

\bigskip
\textbf{Solution:}\\
{\mathversion{bold} $\emptyset$ } \\
No. The power set of every set includes at least the empty set, so the power set cannot be empty. Thus $\emptyset$  is not the power set of any set.

\smallskip
{\mathversion{bold} $\{\emptyset, \{a\}\}$ } \\
Yes. This is the power set of $\{a\}$.

\smallskip
{\mathversion{bold} $\{\emptyset, \{a\}, \{\emptyset, a\}\}$ } \\
No. This set has three elements. Since 3 is not a power of 2, this set cannot be the power set of any set.

\smallskip
{\mathversion{bold} $\{\emptyset, \{a\}, \{b\}, \{a, b\}\}$ } \\
Yes. This is the power set of $\{a, b\}$.

\ppart Rosen \S 1.5, Exercise 12(c).

\bigskip
\textbf{Solution:}\\
Let $x \in (A - B) - C$. Then $x$ is in $A - B$ but not in $C$. Since $x \in A - B$, we know that $x \in A$ (we also know that $x \notin B$, but that won't be used here). Since we have established that $x \in A$ but $x \notin C$, we have proved that $x \in A - C$. Thus, $(A - B) - C \subseteq A - C$.


\ppart Rosen \S 1.5, Exercise 18 (a),(b),(c).

\bigskip
\textbf{Solution:}\\
\epsfxsize=2.1in
\mbox{\epsfbox{figures/ps1P2cParta.eps}}
\epsfxsize=2.1in
\mbox{\epsfbox{figures/ps1P2cPartb.eps}}
\epsfxsize=2.1in
\mbox{\epsfbox{figures/ps1P2cPartc.eps}}

\ppart Rosen \S 1.5, Exercise 36.

\bigskip
\textbf{Solution:}\\
$\bigcup_{i=1}^{n} A_{i}$ = \{1, 2, 3, ...\}

\medskip
$\bigcap_{i=1}^{n} A_{i}$ = \{$n$, $n$ + 1, $n$ + 2, ...\}

\eparts                                                  

                            

   


%END   George's problems

%BEGIN Josh's problems
%END   Josh's problems


%BEGIN Ivan's problems (spring '98)

%%%%%%%%
%pset1 problem2 from spring98 (variant of F97)

\problem
Show that each of the following implications is a tautology by using truth
tables.

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

%%%%%%%% SOLUTION
%pset1 problem2 from spring98 (variant of F97)

\solution{
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
} %solution

%%%%%%%%
%pset1 problem3 from spring98 (variant of F97)

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

%%%%%%%% SOLUTION
%pset1 problem3 from spring98 (variant of F97)

\solution{
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.
} %solution

%%%%%%%%
%pset1 problem4 from spring98 (variant of F97)

\problem
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.
\item[b)] Every movie had a writer who was a professional screenwriter.
%typo corrected: inserted ``professional'':
\item[c)] There is a professional screenwriter who has written ``Pulp Fiction'' and
``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).

\end{description}

%%%%%%%% SOLUTION
%pset1 problem4 from spring98 (variant of F97)

\solution{
% 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}
} %solution

%%%%%%%%
%pset1 problem5 from spring98 (from F96 pset1 prob 6)

\problem

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


%%%%%%%% SOLUTION
%pset1 problem5 from spring98 (from F96 pset1 prob 6)

\solution{
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.
} %solution

%%%%%%%%
%pset1 problem6 from spring98 (variant of F97)

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

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


%%%%%%%% SOLUTION
%pset1 problem6 from spring98 (variant of F97)

\solution{
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}
} %solution


%%%%%%%%
%pset1 problem7 from spring98 (unchanged from F97)

\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.
\end{quote}

%%%%%%%% SOLUTION
%pset1 problem7 from spring98 (unchanged from F97)

\solution{
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.
} %solution

%END   Ivan's problems



%BEGIN Tina's problems
% Fall 1999

%%%%%%%%%%%
% problem set 1, problem 1
% basic Logic

\problem \textbf{Logic}:
\bparts
\ppart \S 1.1, Exercise 24(b).

\solution{\(\begin{tabular}{lllcc}
$p$ & $q$ & $r$       &        $p \vee q$ & $(p \vee q)\wedge r$\\
\hline
t & t & t	& 	    t	  &      t\\
t & t & f	&	    t	  &      f\\
t & f & t	& 	    t	  &      t\\
t & f & f	& 	    t	  &      f\\
f & t & t	& 	    t     &      t\\
f & t & f	&	    t     &      f\\
f & f & t	&	    f	  &      f\\
f & f & f	&	    f	  &      f\\
\end{tabular}\)}

\ppart \S 1.2, Exercise 6.

\solution{We see that the fourth and seventh columns are identical.\\
\(\begin{tabular}{llccccc}
$p$ & $q$ & $p \wedge q$ & $\neg(p \wedge q)$ & $\neg p$ &  $\neg q$ & $\neg p\vee\neg q$\\
\hline
t & t &     t	    &	  f	&	f & f	&     f\\
t & f &     f	    &     t	&	f & t	&     t\\
f & t &     f	    &	  t	&	t & f	&     t\\
f & f &	    f	    &     t	&	t & t	&     t
\end{tabular}\)}

\ppart \S 1.2, Exercise 8(a).

\solution{We construct a truth table for each implication and see that the
relevant column contains only $t$'s.\\
\(\begin{tabular}{llcccc}
$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\\
t & f & f &	t	&	f	&		t\\
f & t & t &	t	&	t	&		t\\
f & f & t &	f	&	f	&		t
\end{tabular}\)}

\ppart \S 1.3, Exercise 14 (d), (h), (i), (o).

\solution{(d) $\neg\exists x C(x,Bob)$ \\
          (h) $\exists x \forall y (x=y \leftrightarrow I(y))$\\
          (i) $\exists x \forall y(x\neq y \leftrightarrow I(y))$\\
          (o) $\exists x \exists y(x\neq y \wedge \forall z (C(x,z)\vee C(y,z)))$}

\ppart For each of the logical formulas in \S 1.3, Exercise 22(a), (c),
(d), (g), and (j), indicate whether or not it is true when the domain of
discourse is $\naturals$ (the natural numbers 0, 1, 2, \dots), $\integers$
(the integers), $\rationals$ (the rationals), $\reals$ (the real numbers), and
$\complex$ (the complex numbers).

\solution{\(\begin{array}{llllll}
Statement & \Nat & \Int & {\mathbb{Q}} & \Real & \Complex\\
\exists x(x^2=2) & f & f & f & t (x=\sqrt{2}) & t\\
\forall x \exists y (x^2 = y) & t & t & t & t (y=x^2)& t\\
\forall x \exists y (x=y^2) & f & f & f & f (take x<0) & t\\
\forall x\neq 0\exists y(xy=1) & f & f & t & t (y=1/x) & t\\
\exists x \exists y (x + 2y = 2 \wedge 2 x + 4 y = 5) & f & f & f & f & f
   \mbox{ (inconsistent system of equations)}
\end{array}\)}

\ppart \S 1.3, Exercise 42.

\solution{We need to show that each of these propositions implies the other.
Suppose that $\forall x P(x) \vee \forall x Q(x)$. We want to show
that $\forall x\forall y (P(x)\vee Q(y))$. By our hypothesis, one of the 
two things must be true. Either $P$ is universally true or $Q$ is universally
true. In the first case, $\forall x\forall y(P(x)\vee Q(y))$ is true, since
the first expression in the disjuction is true, no matter what $x$ and $y$ are;
and in the second case, $\forall x \forall y(P(x)\vee Q(y))$ is also true, since 
now the second expression in the disjunction is true, no matter what $x$ and 
$y$ are. Next we need to prove the converse. So suppose that 
$\forall x \forall y(P(x)\vee Q(y))$. We want to show that 
$\forall x P(x) \vee \forall x Q(x)$. If $\forall x P(x)$ is true then we are 
done. Otherwise, $P(x_0)$ must be false for some $x_0$ in the domain of 
discourse. For this $x_0$, then, the hypothesis tells us that $P(x_0)\vee Q(y)$
is true, no matter what $y$ is. Since $P(x_0)$ is false, it must be the case that 
$Q(y)$ is true for each $y$. In other words $\forall y Q(y)$ is true, or, to change
the name of the meaningless quantified variable, $\forall x Q(x)$ is true. This
certainly implies that $\forall x P(x) \vee \forall x Q(x)$ is true, as desired.}

\eparts

% problem set 1, problem 3
% Proofs
\problem \textbf{Proofs}  %From Fall 95 ps1, prob 7

Determine whether each of the following arguments is valid.  If an
argument is correct, what rule of inference (from Rosen, \S 3.1) is being
used?  If it is not, what fallacy (again from Rosen \S 3.1) occurs?

\begin{problemparts}
\problempart
{\em Theorem:} if $n^2>1$, then $n>1$.  {\em Proof:}
If $n$ is a real number such that $n>1$, then $n^2>1$.  Suppose that
$n^2>1$, then $n>1$.

\solution{Invalid. Fallacy of affirming the conclusion.}

\problempart
{\em Theorem:} The number $\log_2 3$ is irrational. {\em Proof:} A number is irrational if it is not the ratio of two integers.
Therefore, since $\log_2 3$ cannot be written in the form $a/b$ where
$a$ and $b$ are integers, it is irrational.

\solution{Invalid. Fallacy of affirming the conclusion.}

\problempart
{\em Theorem:} If $n^2 \leq 9$ then, $n \leq 3$.  {\em Proof:} Because
if $n$ is a real number with $n>3$, then $n^2 >9$.

\solution{Valid. Modus tollens.}

\problempart
{\em Theorem} If $n\leq 2$, then $n^2\leq 4$. {\em Proof:} Because if $n$ is a real number with $n>2$, then $n^2>4$.

\solution{Invalid. Fallacy of denying the hypothesis.}

\end{problemparts}


%END   Tina's problems

%BEGIN Joe's problems
\problem In some computer architectures, the basic computer operation
is ``NAND'', denoted~$\nand$, where $A \nand B$ means $\neg (A \land
B)$.  Show that all the basic boolean operations can be implemented
using the single $\nand$ operation.  That is, rewrite each of the
following formulas as equivalent formulas using only the $\nand$
operator (and parentheses).

\begin{minipage}[t]{1.5in}
\begin{problemparts}
\ppart $\neg A$
\ppart $A \lor B$
\ppart $A \land B$
\ppart $A \implies B$
\end{problemparts}
\end{minipage}

\solution{
\textbf{Solutions:}
\setcounter{problempartnum}{0}
\begin{minipage}[t]{3.5in}
\begin{problemparts}
\ppart $A \nand A$
\ppart $(A \nand A) \nand (B \nand B)$
        \quad ($\Longleftrightarrow
         \neg ( \neg A \land \neg B)
        \Longleftrightarrow 
        \neg A \nand \neg B$)
\ppart $(A \nand B) \nand (A \nand B)$ 
        \quad ($\Longleftrightarrow \neg(A \nand B)$)
\ppart $A \nand (B \nand B)$
        \quad ($\Longleftrightarrow B \lor \neg A$)
\end{problemparts}
\end{minipage}
}

\problem Identify the premises and conclusions of the following
deductive arguments and analyze their logical forms.  This may require
that you ``pin down'' a statement that could be interpreted many ways.
Determine which are valid deductions and which are not.  If the
deduction is invalid, demonstrate a possible scenario in which all the
premises are met but the conclusion is not.

\textbf{Note:} There are several ways to formalize many of these statements in
logical notation.  We will accept any \emph{reasonable} reading of the English.
Below, we show one such solution for each part.

\begin{problemparts}
\ppart Jane and Pete won't both win the math prize.  Pete will win
either the math prize or the chemistry prize.  Jane will win the math
prize.  Thus, Pete will win the chemistry prize.

\solution{
\textbf{Solution:} The deduction is:
\begin{center}
\begin{tabular}{l}
        $\neg (J \land M)$ \\
        $M \lor C$ \\ 
        $J$ \\ \hline
        $\therefore C$
\end{tabular}
\quad where 
\begin{tabular}{l}
        $J \equiv \mbox{``Jane will win the math prize.''}$ \\
        $M \equiv \mbox{``Pete will win the math prize.''}$ \\
        $C \equiv \mbox{``Pete will win the chemistry prize.''}$
\end{tabular}
\end{center}
This deduction is valid.  
}
\ppart The main course will be beef or fish.  The vegetable will be
peas or corn. We will not have both fish as a main course and corn as
a vegetable. Therefore, we will not have both beef as a main course
and peas as a vegetable.
\solution{
\textbf{Solution:} The deduction is:
\begin{center}
\begin{tabular}{l}
        $B \lor F$ \\
        $C \lor P$ \\
        $\neg (F \land C)$ \\ \hline
        $\therefore \neg (B \land P)$
\end{tabular}
\quad where 
\begin{tabular}{l}
        $B \equiv \mbox{``The main course will be beef.''}$ \\
        $F \equiv \mbox{``The main course will be fish.''}$ \\
        $C \equiv \mbox{``The vegetable will be corn.''}$ \\
        $P \equiv \mbox{``The vegetable will be peas.''}$ 
\end{tabular}
\end{center}
This deduction is invalid.  For example, $B \land \neg F \land C \land
P$ is consistent with the premises but not with the conclusion.  Note
that as formalized, there need not be only one main course and only
one vegetable; it is possible, for example, for the vegetable to be
both corn and peas, as in the scenario given.  If we wished to exclude
the possibility of multiple courses we could have used exclusive-or
instead of inclusive-or. So our premise about the main course would
then read $B \oplus F$ or, equivalently, 
$(B \lor F) \land \neg (B \land F)$. 
The premise about the vegetable could be changed similarly.  
The deduction is still invalid with this formalization. 
}

\ppart Either John or Bill is telling the truth.  Either Sam or Bill
is lying.  Thus, either John is telling the truth or Sam is lying.

\solution{
\textbf{Solution:}
We interpret ``John is lying,'' to be 
the negation of ``John is telling the truth.'' 
Similarly for the corresponding propositions involving Bill and Sam.
The deduction is:
\begin{center}
\begin{tabular}{l}
        $J \lor B$ \\
        $\neg S \lor \neg B$ \\ \hline
        $\therefore J \lor \neg S$
\end{tabular}
\quad where 
\begin{tabular}{l}
        $J \equiv \mbox{``John is telling the truth.''}$ \\
        $B \equiv \mbox{``Bill is telling the truth.''}$ \\
        $S \equiv \mbox{``Sam is telling the truth.''}$
\end{tabular}
\end{center}
This deduction is valid.  It is an example of a common
``cancellation'' rule that lets us get rid of the proposition $B$.
}

\ppart Either sales will go up and the boss will be happy, or expenses
will go up and the boss won't be happy.  Therefore, sales and expenses
will not both go up.

\solution{
\textbf{Solution:} The deduction is:
\begin{center}
\begin{tabular}{l}
        $(S \land H) \lor (E \land \neg H)$ \\ \hline
        $\therefore \neg (S \land E)$
\end{tabular}
\quad where 
\begin{tabular}{l}
        $S \equiv \mbox{``Sales will go up.''}$ \\
        $H \equiv \mbox{``The boss will be happy.''}$ \\
        $E \equiv \mbox{``Expenses will go up.''}$ 
\end{tabular}
\end{center}
This deduction is invalid. 
For example, $S \land E \land H$ is consistent 
with the premises but not with the conclusion. 
}

\ppart If the tax rate and unemployment both go up then there will be
a recession.  If the GNP goes up there will not be a recession.  GNP
and taxes are both going up.  Therefore, there will not be a
recession.

\solution{
\textbf{Solution:}
The deduction is:
\begin{center}
\begin{tabular}{l}
        $T \land U \implies R$ \\
        $G \implies \neg R$ \\
        $G \land T$ \\ \hline
        $\therefore \neg R$
\end{tabular}
\quad where 
\begin{tabular}{l}
        $T \equiv \mbox{``The tax rate goes up.''}$ \\
        $U \equiv \mbox{``Unemployment goes up.''}$ \\
        $G \equiv \mbox{``GNP goes up.''}$ \\
        $R \equiv \mbox{``There will be a recession.''}$
\end{tabular}
\end{center}
This deduction is valid. 
(The first premise is superfluous.)
}
\end{problemparts}

\problem Let $F(x,y)$ be the predicate ``$x$ can fool $y$'' and the
universe of discourse be the set of all people.  Use quantifiers to
express the following statements.
\begin{problemparts}
\ppart Everybody can fool Fred. \\
\solution{
\textbf{Solution:}
$\forall x F(x,\textrm{Fred})$
}
\ppart Evelyn can fool everybody. \\
\solution{
\textbf{Solution:}
$\forall y F(\textrm{Evelyn},y)$
}
\ppart Everybody can fool somebody. \\
\solution{
\textbf{Solution:}
$\forall x \exists y F(x,y)$
}
\ppart No one can fool everybody. \\
\solution{
\textbf{Solution:}
$\neg \exists x \forall y F(x,y)$
}
\ppart Everybody can be fooled by somebody. \\
\solution{
\textbf{Solution:}
$\forall y \exists x F(x,y)$
}
\ppart Nancy can fool exactly two people. \\
\solution{
\textbf{Solution:}
$\exists x \exists y 
    (x \neq y  
        \land F(\textrm{Nancy}, x)
        \land F(\textrm{Nancy}, y)
        \land \forall z 
                (z \neq x \land z \neq y \implies \neg F(\textrm{Nancy},z)))$
Alternatively: 
$\exists x \exists y 
    (x \neq y  
        \land F(\textrm{Nancy}, x)
        \land F(\textrm{Nancy}, y)
        \land \forall z 
                (z = x \lor z = y \lor \neg F(\textrm{Nancy},z)))$

Note that by convention, different logical operators bind more or less tightly.
Quantifiers and negation bind most tightly; 
$\land$ and $\lor$ bind more tightly than $\implies$.
}
\ppart There is exactly one person whom everybody can fool. \\
\solution{
\textbf{Solution:}
$\exists! y \forall x F(x,y)$. 

Note that $\exists! y P(y)$ is logically equivalent to 
$\exists y (P(y) \land \forall z (z \neq y \implies \neg P(z)))$. 
Thus, it is possible to rewrite the statement as 
$\exists y (\forall x F(x,y) 
                \land \forall z (z \neq y \implies \neg \forall x F(x,z)))$. 
}
\ppart There is someone who can fool exactly one person besides him- or
herself. \\
\solution{
\textbf{Solution:}
$\exists x \exists! y (x \neq y \land F(x,y))$.  
(This can be rewritten without $\exists!$ as we did above.)
%or $\exists y (x \neq y \land F(x,y) 
%               \land \forall z (z \neq y \implies \neg (x \neq z \land F(x,z))))$. 
}
\end{problemparts}

\problem Are these statements true or false?  The universe of
discourse is the natural numbers.  
(The set of natural numbers is $\{0,1,2, \ldots\}$.)

%\begin{minipage}[t]{3in}
\begin{problemparts}
\ppart $\forall x \exists y (2x-y=0)$
\solution{
\textbf{Solution:}
True. (Given a natural number $x$, consider $y = 2x$; $y$ is a natural number.)
}
\ppart $\exists y \forall x (2x-y=0)$
\solution{
\textbf{Solution:}
False. (Fix any $y$; there is always an $x > y/2$.)
}
\ppart $\forall x (x < 10 \implies \forall y (y < x \implies y < 9))$
\solution{
\textbf{Solution:}
True.  (Remember the universe of discourse is the natural numbers.)
}
\ppart $\forall x \exists y (y > x \land \exists z (y+z=100))$
\solution{
\textbf{Solution:} False. (If $x > 100$ then $y > 100$ so no $z \in \mathbb{N}$
works.)
}
\end{problemparts}

\problem \mbox{}
\begin{problemparts} 

\ppart
Show that $\forall x P(x) \lor \forall x Q(x)$ is not logically
equivalent to $\forall x (P(x) \lor Q(x))$.
\solution{
\textbf{Solution:}
The universal quantifier does not distribute over OR.  
Even if $\forall x (P(x) \lor Q(x))$, 
there may be two elements, $c_1$ and $c_2$, such that 
$P(c_1) \land \neg Q(c_1) \land \neg P(c_2) \land Q(c_2)$, 
and thus, $\neg (\forall x P(x) \lor \forall x Q(x))$. 

For example, suppose the universe of discourse is $\mathbb{N}$,
$P(x)$ is the proposition ``$x$ is even,'' and $Q(x)$ is the
proposition ``$x$ is odd.''  
It is not true that every natural number is even 
(i.e., $\neg \forall x P(x)$), 
nor is it true that every natural number is odd 
(i.e., $\neg \forall x Q(x)$). 
However, every natural number is either even or odd 
(i.e., $\forall x (P(x) \lor Q(x))$). 
}
\ppart 
Show that $\exists x (P(x) \implies Q(x))$ is logically equivalent to
$\forall x P(x) \implies \exists x Q(x)$.
\solution{
\textbf{Solution:}
First we show that the existential quantifier does distribute over OR:

\textbf{Lemma:} 
$\exists x (P(x) \lor Q(x))
                \Longleftrightarrow \exists x P(x) \lor \exists x Q(x)$. 

\textit{Proof:} 
In class, we showed one direction, 
that $\exists x (P(x) \lor Q(x))
                \Longrightarrow \exists x P(x) \lor \exists x Q(x)$. 
To see the other direction, 
suppose $\exists x P(x) \lor \exists x Q(x)$. 
We proceed by cases:
\begin{description}

\item[Case 1 ($\exists x P(x)$): ]
By existential instantiation, 
$P(c)$ for some $c \in U$. 
Therefore $P(c) \lor Q(c)$, 
and by existential generalization, 
$\exists x (P(x) \lor Q(x))$. 

\item[Case 2 ($\exists x Q(x)$): ]
This is exactly analogous to the previous case. 

\item[Exhaustive cases: ]
Since we have covered both disjuncts of our supposition, the two cases above are exhaustive.
\qed

\end{description}

We use this lemma in the following proof:
\begin{align*}
\exists x (P(x) \implies Q(x)) 
        & \Longleftrightarrow \exists x (\neg P(x) \lor Q(x)) 
                & \text{(truth table of $\implies$)} \\
        &\Longleftrightarrow \exists x \neg P(x) \lor \exists x Q(x) 
                & \text{(above lemma)} \\
        &\Longleftrightarrow \neg \forall x P(x) \lor \exists x Q(x) 
                & \text{(negation of $\forall$)} \\
        &\Longleftrightarrow \forall x P(x) \implies \exists x Q(x) 
                & \text{(truth table of $\implies$)} \\
\end{align*}
}
\end{problemparts}

\problem Consider the following theorem: Suppose $x$ is a real number
and $\frac{2x-5}{x-4}=3$ then $x=7$.
\begin{problemparts}
\ppart What is wrong with the following proof? Suppose $x=7$.  Then
\[
\frac{2x-5}{x-4}=\frac{2(7)-5}{7-4}=\frac{9}{3}=3.
\]
Thus, if $\frac{2x-5}{x-4}=3$ then $x=7$.
\solution{
\textbf{Solution:} This proof is a typical example of circular
reasoning.  We suppose $x=7$ and then conclude that $x=7$.  So, all we
have done is not contradict our supposition.  Unlike a proof by
contradiction, which shows our assumption is false, {\em not} arriving
a contradiction does {\em not} show our assumption is true.

In particular, the proof is of the form:
\begin{center}
\begin{tabular}{l}
        $P(x)$ \\
        $P(x) \implies Q(x)$ \\ \hline
        $\therefore Q(x) \implies P(x)$
\end{tabular}
\quad where 
\begin{tabular}{l}
        $P(x) \;\; \equiv\;\; x=7$ \\
        $Q(x) \;\; \equiv\;\; \frac{2x-5}{x-4}=3$ \\
\end{tabular}
\end{center}
The given ``proof'' does demonstrate that the second premise is true.  
However, the conclusion does not follow.
}
\ppart Give a correct proof of this theorem.
\solution{
\textbf{Solution:}
There are many ways to properly construct this proof.  We demonstrate a direct
proof using \emph{modus ponens}.

\begin{center}
\begin{tabular}{l}
        $Q(x)$ \\
        $Q(x) \implies P(x)$ \\ \hline
        $\therefore P(x)$
\end{tabular}
\quad where 
\begin{tabular}{l}
        $P(x) \;\; \equiv \;\; x=7$ \\
        $Q(x) \;\; \equiv \;\; \frac{2x-5}{x-4}=3$ \\
\end{tabular}
\end{center}
Proposition $Q(x)$ is given.  To complete the proof, we must now show that the
second premise (the implication) is a tautology.  
We do this using basic algebra and arithmetic:
\begin{align*}
Q(x) \equiv \frac{2x-5}{x-4} = 3 \;\;
        & \:\Longrightarrow \;\; 2x-5 = 3(x-4) \\ 
        & \Longleftrightarrow \;\; 2x-5 = 3x-12 \\
        & \Longleftrightarrow \;\; -5+12 = 3x-2x \\
        & \Longleftrightarrow \;\; 7 = x                &\equiv P(x) 
\end{align*}
}
\end{problemparts}

\problem Suppose $x$ is a real number.  Prove \textbf{by cases} that there is a
real $y$ such that $\frac{y+1}{y-2}=x$ if and only if $x \ne 1$.
\solution{
\textbf{Solution:}
We consider the cases $x \neq 1$ and $x = 1$ separately. 
\begin{description}

\item[Case 1 ($x \not = 1$): ]
We need to prove that there exists $y \in \mathbb{R}$ such that
$\frac{y+1}{y-2}=x$.  In particular, consider $y = \frac{2x+1}{x-1}$ (derived
by algebraic manipulation), which is a well-defined real number because $x \neq
1$.  Then:  
\[\frac{y+1}{y-2} 
        = \frac{\frac{2x+1}{x-1}+1}{\;\frac{2x+1}{x-1}-2\;} 
        = \frac{\frac{2x+1 + (x-1)}{x-1}}{\;\frac{2x+1-2(x-1)}{x-1}\;}
        = \frac{\frac{3x}{x-1}}{\;\frac{2x+1-2x+2}{x-1}\;}
        = \frac{3x}{3}
        = x
\]
Therefore, by existential generalization, $\exists y \in \mathbb{R}$ such that
$\frac{y+1}{y-2} = x.$

\item[Case 2 ($x = 1$): ]
We need to prove that no $y \in \mathbb{R}$ exists 
such that $\frac{y+1}{y-2}=x$. 
Suppose, for contradiction, that such a $y$ did exist.  Then:
\begin{align*}
\frac{y+1}{y-2} = x 
        &\Longleftrightarrow \;\; \frac{y+1}{y-2} = 1 
                & \text{(because $x = 1$)} \\
        &\:\Longrightarrow \;\; y+1 = y-2 
                & \text{(multiply both sides by $y-2$)} \\
        &\Longleftrightarrow \;\; 1 = -2 
                & \text{(subtract $y$ from both sides)} \\
        &\Longleftrightarrow \;\; \text{false.}
\end{align*}
Therefore our supposition is wrong, 
and there is no $y$ such that $\frac{y+1}{y-2}=x$. 

\end{description}
}

\problem Consider the following incorrect theorem:  
\[\text{If } \forall x \in A \; (x \ne 0) \text{ and }A \subseteq B \text{ then
}\forall x \in B \; (x \ne 0)\text{.}\] 

\vspace{-3ex}
\begin{problemparts}
\ppart What is wrong with the following proof of the theorem? Let $x$
be an arbitrary element of $A$.  Since $\forall x \in A \; (x \ne 0)$ we can
conclude $x \ne 0$.  Also, since $A \subseteq B$ we have $x \in B$.
Since $x \in B$, $x \ne 0$, and $x $ was arbitrary, we can conclude
(by universal generalization) that $\forall x \in B \; (x \ne 0)$.
\solution{
\textbf{Solution:}
Universal generalization requires that the generalized variable be
arbitrarily chosen \emph{from the set over which we are
generalizing}. We selected $x$ arbitrarily from set $A$ but are
generalizing over a different (larger) set $B$, 
which is not a valid inference rule.   To use universal generalization,
we should imagine an adversary picking the worst possible element from
the set over which we are generalizing.  The proof must work even for that
worst case.
}
\ppart Give a counterexample to the theorem.
\solution{
\textbf{Solution:} 
Let $A = \mathbb{N^+}$ and $B = \mathbb{Z}$. 
}
\end{problemparts}

%END   Joe's problems

\end{problems}

\end{document}

