\newcount\indentlevel
\newcount\itno
\def\reset{\itno=1}\reset
\def\afterstartlist{\advance\leftskip by .5in\par\advance\leftskip by -.5in}
\def\startlist{\par\advance\indentlevel by 1\advance\leftskip by .5in\reset
\aftergroup\afterstartlist}
\def\alph#1{\ifcase #1\or a\or b\or c\or d\or e\or f\or g\or h\or
    i\or j\or k\or l\or m\or n\or o\or p\or q\or r\or
    s\or t\or u\or v\or w\or x\or y\or z\fi}
\def\li#1\par{\medskip\penalty-100\item{\ifcase\indentlevel \number\itno.\or
                                  \alph\itno)\else
                                  (\number\itno)\fi
                           }%
         #1\smallskip\advance\itno by 1\relax}
\def\hline{\noalign{\hrule}}
\let\impl\rightarrow
\newskip\tableskip
\tableskip=10pt plus 10pt
\def\\{\hfil\break}

\li Express each of these statements using predicates and quanifiers

{\startlist
    \li ``Some pigs eat wheat.''

    Let the domain be the set containing all animals. \\
    Let $P(x):$ $x$ is a pig. \\
    Let $W(x):$ $x$ eats wheat.

    $$\exists x, P(x)\land W(x).$$

    \li ``All board games are fun.''

    Let the domain be the set of all board games. \\
    Let $B(x):$ $x$ is a board game.
    Let $F(x):$ $x$ is fun.

    $$\forall x, B(x)\impl F(x).$$

    \li ``Not all potatoes are sweet.''

    Let the domain be the set of all plants. \\
    Let $P(x):$ $x$ is a potato. \\
    Let $S(x):$ $x$ is sweet.

    $$\lnot\forall x, P(x)\impl S(x).$$
}


\li Determine the truth value of each of these statements if the domain
of each variable consists of all integers.

{\startlist
    \li $\forall x\exists y (\root 5 \of x > y^2)$

    False. $y^2 > 0$ for all $y,$ and $\root 5 \of {-1} = -1,$ disproving
    this statement.

    \li $\exists x\forall y((x = 2.5)\impl (y > x))$

    False. $y = 0 < 2.5 = x.$

    \li $\exists x\forall y(x^2 = y)$

    False. $1 = x^2 = 0$ is not possible.

    \li $\forall x\exists y(x^2 = y)$

    True. The integers are closed under squaring.
}

\li Rewrite each of these statements so that no negation is to the left
of a quantifier, so that every negation is to the left of a predicate
(in other words, push the negation in past the quantifiers).

{\startlist
    \li $\lnot\forall y(\forall x R(x,y)\land\exists x S(x,y))$

    $$\exists y(\exists x \lnot R(x,y)\lor\forall x \lnot S(x,y))$$

    \li $\forall x\lnot\exists y\forall z(A(x,y)\impl B(x,z))$

    $$\forall x\forall y\exists z\lnot(A(x,y)\impl B(x,z))$$

    \li $\lnot\exists x\lnot\forall y\lnot\forall z(A(x,z)\land B(y,z))$

    $$\forall x\forall y\exists z\lnot (A(x,z)\land B(y,z))$$

    \li $\lnot\exists x\forall y\exists z(P(x,y)\iff Q(z))$

    $$\forall x\exists y\forall z\lnot (P(x,y)\iff Q(z))$$

}

\li Let $S(x)$ be the statement ``$x$ has a sabre tooth tiger,'' let
$D(x)$ be the statement ``x has a dhole,'' and let $H(x)$ be the
statement ``x has a horse.'' Express each of these statements in terms
of $S(x),$ $D(x),$ $H(x),$ quantifiers, and logical connectives. Let the
domain consist of all people.

{\startlist
    \li Every person who owns a sabre tooth tiger also owns a dhole or a
    horse.

    $$\forall x S(x)\impl(D(x)\land H(x)).$$

    \li No one owns a sabre tooth tiger, and at least one person owns a
    horse.

    $$\forall x\lnot S(x) \land \exists x H(x).$$

    \li For each of the three animals---sabre tooth tigers, dholes, and
    horses---there is a person who has this animal. Hint: All three
    animals can, but do not have to be, owned by the same person.

    $$\exists x S(x) \land \exists x D(x) \land \exists x H(x).$$
}

\li Express each of these statements using quantifiers. Then form the
negation of the statement so that no negation is to the left of a
quantifier (in other words, push the negation in past the quantifiers).
Next, express the negation in English.

{\startlist
    \li Let the domain be all animals \\
    Let $B(x):$ $x$ is a bird \\
    Let $C(x):$ $x$ can chirp \\
    ``There exists a bird that can chirp.''

    $$\exists x B(x)\land C(x).$$

    \li Let the domain be all animals \\
    Let $C(x):$ $x$ is a cat \\
    Let $E(x):$ $x$ eats fish \\
    ``All cats eat fish.''

    $$\forall x C(x)\impl E(x).$$

    \li Let the domain be all animals
    Let $D(x):$ $x$ is a dog \\
    Let $M(x):$ $x$ can meow \\
    ``There exists a dog, only if not all animals can meow.''

    $$(\lnot\forall x M(x)) \impl (\exists x D(x)).$$
}

\li Determine the truth value of the statement $\exists x\forall
y(x^3\leq y^4)$ if the domain for the variable consists of:

{\startlist
    \li the positive real numbers

    This is not true because $0 < y < \root 4 \of x^3$ always exists for
    any $x$ (the fourth root of a cube of a positive number is positive,
    so this number is never zero)

    \li the non-negative integers

    This is true with $x=0$ because $y^4 \geq 0$ over this domain.

    \li the nonzero real numbers

    This is true with $x=-1$ because $y^4 \geq 0 > x^3 = -1.$
}

\li Show that $\lnot\forall x(P(x)\land\lnot Q(x))$ is logically
equivalent to $\exists x(P(x)\impl Q(x)).$

\halign{\vrule\strut#\tabskip\tableskip&#\hfil&#\hfil&#\tabskip0pt&#\vrule\cr\hline
    &$\lnot \forall x(P(x)\land\lnot Q(x))$&Given&&\cr
    &$\exists x \lnot(P(x)\land\lnot Q(x))$&DeMorgan's Law for Quantifiers&&\cr
    &$\exists x (\lnot P(x)\lor\lnot\lnot Q(x))$&DeMorgan's Law&&\cr
    &$\exists x (\lnot P(x)\lor Q(x))$&Double negation law&&\cr
    &$\exists x (P(x)\impl Q(x))$&Conditional Identity&&\cr
    \hline
}

\li Find a counterexample, if possible, to these universally quantified
statements, where the domain for all variables consists of all real
numbers. Otherwise, state that no counterexample exists.

{\startlist
    \li $\forall x\forall y(x^3\neq y^7)$

    With $x=y=1,$ $x^3 = y^7.$

    \li $\forall x\exists y(y = {x\over 2})$

    No counterexample exists.

    \li $\forall x\forall y((x\geq y)\impl(x^{100} > y)).$

    With $x=y=0,$ $x\geq y,$ but $x^{100} \not> y.$
}

\bye