diff options
Diffstat (limited to 'howard/hw2.tex')
| -rw-r--r-- | howard/hw2.tex | 196 |
1 files changed, 196 insertions, 0 deletions
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 |