\problemdata       % Takes 5 *mandatory* arguments
  {logic-LNN}              % latex-friendly label for the prob.
  {logic}                  % The topic(s) of the problem content.
  {}                       % Source (if known)
  {S02 cp2M-2}             % Usage (list ones you are aware of).
  {Nick Matsakis, S02}     % Last revision info (author, date).
\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}


