\documentclass[11pt,twoside]{article}    
\usepackage{latex-macros/course}% !! use the macros 

%\backwardscompatibility        % !! use for backwards compatibility
%\showsolutions                 % !! use to force solutions & skip query
%\hidesolutions                 % !! use to force no solutions & skip query
\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}

\begin{document} 
\inclassproblems{2M}                    % !! start the paper

\begin{problem}
For each of the logical formulas, 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 $\complexes$ (the complex numbers).

\[\begin{array}{c}
\exists x\ (x^2=2)\\
\forall x \exists y\ (x^2 = y)\\
\forall y \exists x\ (x^2 = y)\\
\forall x\neq 0\exists y\ (xy=1)\\
\exists x \exists y\ (x + 2y = 2) \wedge (2 x + 4 y = 5)
\end{array}\]

\solution{\[
\begin{array}{llllll}
Statement & \naturals & \integers & \rationals & \reals & \complexes\\
\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 y \exists x\ (x=y^2) & f & f & f & f\ (\text{take }y<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
\end{array}
\]
}
\end{problem}


\begin{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}\noindent
``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$ gave 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.

\solution{
\[
(\neg (D(\mbox{Monica}) \vee D(\mbox{Linda}))) \implies
(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.

\solution{
\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 gave gifts to
Monica, and Monica gave gifts to someone.

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

\problempart Everyone likes someone and dislikes someone else.

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

\problempart How could you express ``Everyone except for Ken likes
Betty'' using just propositional connectives \emph{without} using any
quantifiers ($\forall, \exists$)?  Can you generalize to explain how
\emph{any} logical formula over this domain of discourse can be expressed
without quantifiers?  How big would the formula in the previous part be if
it was expressed this way?

\solution{
\[
L(\mbox{Bill},\mbox{Betty}) \land L(\mbox{Monica},\mbox{Betty}) \land
L(\mbox{Linda},\mbox{Betty}) \land L(\mbox{Betty},\mbox{Betty})
\]

In general, quantifiers can be eliminated by treating $\forall x\ P(x)$ as an
abbreviation for
\[
P(\mbox{Bill}) \land P(\mbox{Monica}) \land P(\mbox{Ken}) \land P(\mbox{Linda}) \land
P(\mbox{Betty}),
\]
and $\exists x\ P(x)$ as an abbreviation for
\[
P(\mbox{Bill}) \lor P(\mbox{Monica}) \lor P(\mbox{Ken}) \lor
P(\mbox{Linda}) \lor P(\mbox{Betty}).
\]

Expanded this way, the three-quantifier formula of the previous part would
expand by a factor of $5 \times 5 \times 5 = 125$.  So using quantifiers
can pay off even when they are not strictly necessary.}

\end{problemparts}
\end{problem}


\begin{problem}
Express each of the following propositions and predicates in formal logic
notation.  The domain of discourse is the nonnegative integers,
$\naturals$.

In addition to the propositional operators, variables and quantifiers, you
may define predicates using addition, multiplication, positive integers,
and equality and inequality symbols.  For example, the proposition ``3 is
an odd number'' could be written
\[
\exists x\ (2 x + 1 = 3).
\]

\begin{problemparts}
\problempart 
$n$ is the sum of three perfect squares.

\solution{
\[
\exists x \exists y \exists z\ (x \cdot x + y \cdot y + z \cdot z = n)
\]
}
\end{problemparts}

Since 0 is not an allowed constant, the predicate ``$x \neq 0$'' can't be
written directly, but note that it could be expressed in a simple way:
\[
\neg (x + x = x).
\]
Then the predicate $x > y$ could be expressed
\[
\exists w\ (y + w = x) \land (w \neq 0).
\]
Note that we've used ``$w \neq 0$'' in this formula, even though it's
technically not allowed.  But since we've shown how to express it by the
genuine formula, ``$\neg(w + w = w)$,'' we can use ``$w \neq 0$'' with the
understanding that it abbreviates the real thing.  And now that we've
shown how to express ``$x>y$'', it's ok to use it too.

\begin{problemparts}
\problempart 
$n$ is a prime number.

\solution{
\[
\text{is-prime}(n) \eqdef (n > 1) \wedge \neg (\exists x \exists y\ (x > 1) \wedge (y > 1) \wedge (x \cdot y = n))
\]
}

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

\solution{
\[
\exists x \exists y\ \neg (x = y) \land (n = x \cdot y) \land
\text{is-prime}(x)
\land \text{is-prime}(y).
\]
}

\end{problemparts}
\end{problem}

\iffalse

\begin{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 $U$ and read ``there exists a unique''.
The proposition $Ux\, P(x)$ is true iff there is \emph{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 $U x\, P(x)$ using only the
$\exists$ quantifier.

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

\problempart Rewrite the proposition $U x\, P(x)$ using only the
$\forall$ quantifier.

\solution{
\[
\neg \forall x\ (\neg P(x) \vee \neg \forall y\ (x = y \vee \neg P(y)))
\]
}
\end{problemparts}
\end{problem} 
\fi

\end{document}
