From 89862ae6a0554870a7708ae73112f86d2d21fc8d Mon Sep 17 00:00:00 2001
From: Holden Rohrer <hr@hrhr.dev>
Date: Thu, 10 Feb 2022 01:12:45 -0500
Subject: new teachers, new work

---
 howard/hw2.tex | 196 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 196 insertions(+)
 create mode 100644 howard/hw2.tex

(limited to 'howard/hw2.tex')

diff --git a/howard/hw2.tex b/howard/hw2.tex
new file mode 100644
index 0000000..f63b1ee
--- /dev/null
+++ b/howard/hw2.tex
@@ -0,0 +1,196 @@
+\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
-- 
cgit 

