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