diff options
Diffstat (limited to 'howard')
| -rw-r--r-- | howard/Makefile | 12 | ||||
| -rw-r--r-- | howard/hw1.tex | 248 | ||||
| -rw-r--r-- | howard/hw2.tex | 196 | ||||
| -rw-r--r-- | howard/hw3.tex | 313 |
4 files changed, 769 insertions, 0 deletions
diff --git a/howard/Makefile b/howard/Makefile new file mode 100644 index 0000000..8e5dd3a --- /dev/null +++ b/howard/Makefile @@ -0,0 +1,12 @@ +.POSIX: +.SUFFIXES: .tex .pdf + +PDFTEX = pdftex + +.tex.pdf: + $(PDFTEX) $< + +all: hw1.pdf hw2.pdf hw3.pdf + +clean: + rm -f *.pdf *.log diff --git a/howard/hw1.tex b/howard/hw1.tex new file mode 100644 index 0000000..b9731b2 --- /dev/null +++ b/howard/hw1.tex @@ -0,0 +1,248 @@ +\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\item{\ifcase\indentlevel \number\itno.\or + \alph\itno)\else + (\number\itno)\fi + }% + #1\smallskip\advance\itno by 1} +\def\hline{\noalign{\hrule}} +\let\impl\rightarrow +\newskip\tableskip +\tableskip=10pt plus 10pt + +\li Evaluate each of the conditional statements to true or false + +{\startlist + \li If $1+2=4,$ then $9+0= -9$ + + With $p$ $1+2=4$ and $q$ $9+0= -9,$ this statement is $p\impl + q.$ + $1+2\neq 4,$ so this conditional is vacuously true. + + \li $13 > 19$ only if 13 is prime + + With $p$ 13 is prime and $q$ $13 > 19,$ this statement is + $p\impl q,$ and since $p$ is true and $q$ is false, this + statement is false. + + \li Horses can fly whenever horses cannot fly + + With $p$ ``horses cannot fly'' and $q$ ``horses can fly,'' this + is equivalent to $p\impl q.$ Since horses cannot fly, $p$ is + true and $q$ is false, so the statement is false. + + \li $3\cdot3 = 9,$ if $9+9 = 18$ + + With $p$ $9+9 = 18$ and $q$ $3\cdot3=9,$ this statement is + equivalent to $p\impl q,$ and since both are true, this + statement is true. +} + + +\li Let $p$ and $q$ be propositions, where $p$ is the statement ``It is +snowing outside,'' and $q$ is the statement ``It is June.'' Express each +of the following propositions as an English sentence. + +{\startlist + \li $p\impl q.$ + + ``If it is snowing outside, it is June.'' + + \li $\lnot p \land q.$ + + ``It is not snowing outside, and it is June.'' + + \li $\lnot p \lor (p\land q).$ + + ``It is not snowing outside, or it is snowing outside in June.'' +} + +\li Consider the statement: ``If the TAs make the homework too hard, +then the students will be sad.'' Write the converse, contrapositive, and +inverse of the statement. Don't worry about the grammar/tense, we just +want to see the correct idea. + +{\startlist + \li Converse + + ``If the students will be sad, the TAs make the homework too hard.'' + + \li Contrapositive + + ``If the students aren't sad, the TAs didn't make the homework too + hard.'' + + \li Inverse + + ``If the TAs don't make the homework too hard, the students will be + happy.'' +} + +\li How many rows appear in a truth table for each of these compound +propositions? + +{\startlist + \li $p\land q$ + + The number of rows is $2^v$ where v is the number of variables in + the expression. Therefore, this expression will have $2^2 = 4$ rows. + + \li $\lnot p \impl (p\impl q)$ + + This still only has two variables, so it will have $2^2 = 4$ rows. + + \li $(\lnot p\land q\land s)\lor(p\land\lnot q\land s)\lor(p\land + q\land\lnot s)$ + + This has three variables, so it will have $2^3 = 8$ rows. +} + +\li Using the following propositions, translate the sentence ``You +cannot see the movie if you are not over 18 years old and you do not +have the permission of a parent'' to a compound proposition. + +$m := \hbox{``You can see the movie''}$ + +$e := \hbox{``You are over 18 years old''}$ + +$p := \hbox{``You have the permission of a parent''}$ + +This is $(\lnot p\land\lnot e)\impl \lnot m.$ + +\li Construct truth tables for the following propositions. Include all +intermediate columns to receive full credit for each table. + +{\startlist + \li $p\lor q\land\lnot p$ + + \leavevmode + \halign{&\vrule\strut#&#\tabskip\tableskip&#&#\tabskip0pt\cr\hline + + &&$p$&&&&$q$&&&&$\lnot p$&&&&$q\land\lnot p$&&&& + $p\lor q\land\lnot p$&&\cr\hline + &&T&&&&T&&&&F&&&&F&&&&T&&\cr\hline + &&T&&&&F&&&&F&&&&F&&&&T&&\cr\hline + &&F&&&&T&&&&T&&&&T&&&&T&&\cr\hline + &&F&&&&F&&&&T&&&&F&&&&F&&\cr\hline + } + + \li $(p\lor\lnot q) \impl q$ + + \leavevmode + \halign{&\vrule\strut#&#\tabskip\tableskip&#&#\tabskip0pt\cr\hline + + &&$p$&&&&$q$&&&&$\lnot q$&&&&$p\lor\lnot q$&&&& + $(p\lor\lnot q)\impl q$&&\cr\hline + &&T&&&&T&&&&F&&&&T&&&&T&&\cr\hline + &&T&&&&F&&&&T&&&&T&&&&F&&\cr\hline + &&F&&&&T&&&&F&&&&F&&&&T&&\cr\hline + &&F&&&&F&&&&T&&&&T&&&&F&&\cr\hline + } + + \li $(\lnot q\impl\lnot q) \iff (\lnot p \impl \lnot q)$ + + \leavevmode + \halign{&\vrule\strut#&#\tabskip\tableskip&#&#\tabskip0pt\cr\hline + + &&$p$&&&&$q$&&&&$\lnot p$&&&&$\lnot q$&&&&$\lnot q\impl\lnot q$&&&& + $\lnot p\impl\lnot q$&&&& + $(\lnot q\impl\lnot q)\iff(\lnot p\impl\lnot q)$&&\cr\hline + &&T&&&&T&&&&F&&&&F&&&&T&&&&T&&&&T&&\cr\hline + &&T&&&&F&&&&F&&&&T&&&&T&&&&T&&&&T&&\cr\hline + &&F&&&&T&&&&T&&&&F&&&&T&&&&F&&&&F&&\cr\hline + &&F&&&&F&&&&T&&&&T&&&&T&&&&T&&&&T&&\cr\hline + } +} + +\li There is a spaceship where every passenger has exactly one role. +Each passenger can either be a Crewmate or an Imposter. A Crewmate +always tells the truth, and an Imposter always lies. For each question, +determine the role of Person A and the role of Person B, or write +``Cannot be determined'' for that person if there is not enough +information. Explain your reasoning for full credit! (You can use a +truth table or just plain English to explain.) + +{\startlist + \li Person A says ``I am a Crewmate, or B is a Crewmate,'' and + Person B says ``A is a Crewmate if I am an Imposter.'' + + If and only if A is a crewmate, their statement is true. Similarly, + if and only if B is a crewmate, their statement is true. We will use + this principle for all of the problems. + + In this problem, if both are crewmates, both statements are true (B + is not an imposter, so their statement is vacuously true, and A is a + crewmate or B is a crewmate). + + However, if both are imposters, both statements are false (neither + is a crewmate and A is not a crewmate even though B is an imposter). + This means we can't figure out any information. + + \li Person A says ``I am an Imposter, and Person B is a Crewmate,'' + and Person B says nothing. + + Both must be imposters. If A is a crewmate, their statement ``I am + an imposter'' is a lie, so they are an imposter by contradiction. + Since A is an an imposter, this statement must be a lie, so ``Person + B is a crewmate'' is false, and B is an imposter. + + \li Person A says ``Both Person B and I are Imposters,'' and Person + B says ``At least one of us is a Crewmate.'' + + By a similar logic as b, ``I am an imposter'' would be a lie if A + were a crewmate, so A is an imposter. And since that statement is + true, ``Person B is an imposter'' must be a lie, and Person B is a + crewmate. This makes B's statement true, validating our view. +} + +\li Show that $(p\impl q)\lor\lnot p \equiv p\impl q$ using logical +equivalences. Cite the laws of equivalences used to reach each step. + +\leavevmode +\goodbreak +\halign{\vrule\strut#\tabskip\tableskip&#\hfil&#\hfil&#\tabskip0pt&#\vrule\cr\hline +&$(p\impl q)\lor\lnot p$&Given&&\cr +&$(\lnot p\lor q)\lor\lnot p$&Conditional Identity&&\cr +&$(q\lor\lnot p)\lor\lnot p$&Commutative Law&&\cr +&$q\lor(\lnot p\lor\lnot p)$&Associative Law&&\cr +&$q\lor\lnot p$&Idempotent Law&&\cr +&$p\impl q$&Conditional Identity&&\cr +\hline +} + +\li Show that $\lnot ((p\land q)\lor p)\impl \lnot p$ is a tautology +using: + +{\startlist + \li a truth table (include all intermediate columns) + + \halign{&\vrule\strut#&#\tabskip\tableskip&#&#\tabskip0pt\cr\hline + + &&$p$&&&&$q$&&&&$p\land q$&&&&$(p\land q)\lor p$&&&& + $\lnot((p\land q)\lor p)$&&&& + $\lnot p$&&&&$\lnot ((p\land q)\lor p)\impl \lnot p$&&\cr\hline + &&T&&&&T&&&&T&&&&T&&&&F&&&&F&&&&T&&\cr\hline + &&T&&&&F&&&&F&&&&T&&&&F&&&&F&&&&T&&\cr\hline + &&F&&&&T&&&&F&&&&F&&&&T&&&&T&&&&T&&\cr\hline + &&F&&&&F&&&&F&&&&F&&&&T&&&&T&&&&T&&\cr\hline + } + + \li logical equivalences (cite the laws of equivalence used to reach + each step) + + \halign{\vrule\strut#\tabskip\tableskip&#\hfil&#\hfil&#\tabskip0pt&#\vrule\cr\hline + &$\lnot ((p\land q)\lor p)\impl \lnot p$&Given&&\cr + &$\lnot p\impl \lnot p$&Absorption Law&&\cr + &$p\lor\lnot p$&Conditional Identity&&\cr + &$T$&Complement Law&&\cr + \hline + } +} +\bye 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 diff --git a/howard/hw3.tex b/howard/hw3.tex new file mode 100644 index 0000000..ab61b0d --- /dev/null +++ b/howard/hw3.tex @@ -0,0 +1,313 @@ +\newfam\bbold +\def\bb#1{{\fam\bbold #1}} +\font\bbten=msbm10 +\font\bbsev=msbm7 +\font\bbfiv=msbm5 +\textfont\bbold=\bbten +\scriptfont\bbold=\bbsev +\scriptscriptfont\bbold=\bbfiv + +\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\ul{\bgroup\def\li##1\par{\item{$\bullet$} ##1\par}} +\let\endul\egroup +\def\hline{\noalign{\hrule}} +\let\impl\rightarrow +\newskip\tableskip +\tableskip=10pt plus 10pt +\def\endproof{\leavevmode\quad\vrule height 6pt width 6pt +depth 0pt\hskip\parfillskip\hbox{}{\parfillskip0pt\medskip}} + +\li Which rule of inference is used in each of these arguments? + +{\startlist + \li Richard is a Computer Science major. Richard is a Computer + Science major only if he attends Georgia Tech. Therefore, Richard + attends Georgia Tech. + + This is modus ponens. With $p$ ``Richard is a Computer Science + Major,'' and $q$ ``he attends Georgia Tech,'' we have $p\impl q$ and + $p,$ concluding $q.$ + + \li Discrete Math exams are fun or Python is a boring language. + Discrete Math exams are not fun or Rohan is a TA for Discrete Math. + Therefore, Python is a boring language or Rohan is a TA for Discrete + Math. + + This is resolution. With $p$ ``Discrete math exams are fun,'' $q$ + ``Python is a boring language,'' and $r$ ``Rohan is a TA for + Discrete Math,'' we have $p\lor q$ and $\lnot p\lor r,$ concluding + $q\lor r.$ + + \li If it snows today, the school will close. If the schools are + closed, then you will not go to class. Therefore, you do + not go to class, if it snows today. + + This is hypothetical syllogism. + Let $p$ ``it snows today,'' $q$ ``the schools will close,'' and $r$ + ``you will not go to class.'' We have $p\impl q$ and $q\impl r,$ + giving us $p\impl r.$ + + % hypothetical syllogism + + \li You are a Discrete Math student whenever you are a Computer + Science major. You are not a Discrete Math student. Therefore, you + are not a Computer Science major. + + This is modus tollens. + With $p$ ``you are a Computer Science major,'' and $q$ ``you are not + a Discrete Math student,'' we have $p\impl q$ and $\lnot q,$ + concluding $\lnot p.$ + + % modus tollens +} + +\li Using rules of inference, show that the premises below conclude with +$d.$ Give the reason for each step as you show that $d$ is concluded. +Each reason should be the name of a rule of inference and include which +numbered steps are involved. For example, a reason for a step might be +``Modus ponens $(2,3)$'' + +\halign{\vrule\strut#\tabskip\tableskip&#\hfil&#\hfil&#\tabskip0pt&#\vrule\cr\hline + &Statement&Reason&&\cr\hline + &$a\lor b$&Premise&&\cr + &$b\lor c\impl e$&Premise&&\cr + &$d\lor\lnot e$&Premise&&\cr + &$\lnot a\lor c$&Premise&&\cr + &$b\lor c$&Resolution (1,4)&&\cr + &$e$&Modus Ponens (2,5)&&\cr + &$e$&Disjunctive Syllogism (3,6)&&\cr + \hline +} + +\li Using the rules of inference, show that the following premises +conclude with ``Yoshi wins the race, and Luigi rides a bike.'' Be sure +to define all propositional variables for full credit (for example, you +may define ``$t:$ Toad gets lost'' as one of your propositional +variables). Remember, it is possible that you will use all premises, but +it is also possible that some are not needed. + +\ul + \li Toad gets lost, and Luigi rides a bike. + + \li If Luigi does not ride a bike, then Wario cheats. + + \li Rosalina is the best princess in the race. + + \li Wario does not cheat, or Toad does not get lost. + + \li If Wario does not cheat and Toad gets lost, then Yoshi wins the + race. + +\endul + +\noindent Variable definitions: +\ul + \li $t:$ Toad gets lost + + \li $l:$ Luigi rides a bike. + + \li $w:$ Wario cheats. + + \li $y:$ Yoshi wins the race + +\endul + +\smallskip +\vskip0pt plus 1in\goodbreak\vskip 0pt plus -1in +\halign{\vrule\strut#\tabskip\tableskip&#\hfil&#\hfil&#\tabskip0pt&#\vrule\cr\hline + &Statement&Reason&&\cr\hline + &$t\land l$&Premise&&\cr + %&$\lnot l\impl w$&Premise&&\cr + &$\lnot w\lor \lnot t$&Premise&&\cr + &$(\lnot w\land t)\impl y$&Premise&&\cr + &$t$&Simplification (1)&&\cr + &$\lnot w$&Disjunctive Syllogism (2,4)&&\cr + &$\lnot w\land t$&Conjunction (4,5)&&\cr + &$y$&Modus ponens (3,6)&&\cr + &$l$&Simplification (1)&&\cr + &$y\land l$&Conjunction (7,8)&&\cr + \hline +} +\smallskip + +This is the conclusion ``Yoshi wins the race, and Luigi rides a bike.'' +\hfil +\endproof + +\li For the following proof, there are blanks in many steps. Please fill +out each blank with its correct statement or reason. Note that the +domain for $x$ is all people, and Tashfia is a person. + +\def\ta{{\rm Tashfia}} +\smallskip +\vskip0pt plus 1in\goodbreak\vskip 0pt plus -1in +\halign{\vrule\strut#\tabskip\tableskip&#\hfil&#\hfil&#\tabskip0pt&#\vrule\cr\hline + &Statement&Reason&&\cr\hline + &$\forall x(B(x)\impl C(x))$&Premise&&\cr + &$A(\ta)$&Premise&&\cr + &$\forall x(A(x)\impl\lnot C(x))$&Premise&&\cr + &$A(\ta)\impl\lnot C(\ta)$&Universal Instantiation (3)&&\cr + &$\lnot C(\ta)$&Modus ponens (2,4)&&\cr + &$B(\ta)\impl C(\ta)$&Universal Instantiation (1)&&\cr + &$\lnot B(\ta)$&Modus tollens (5,6)&&\cr + &$\exists x\lnot B(x)$&Existential generalization (7)&&\cr\hline +} +\smallskip +\endproof + +\li The CS 2050 office hours cubicle is moving! The new cubicle has a +width of $3x$ and a length of $y,$ where $x, y\in Z^+.$ Prove or +disprove that the area of the cubicle is even whenever $x$ is even. Make +sure to include the introduction, body, and conclusion. Clearly state +your reasoning for all statements and use a two-column proof for the +body whenever possible. + +Let $x,y\in Z^+$ represent arbitrary parameters of the desk with $x$ +even. +Let the desk have width $w = 3x$ and length $l = y.$ +We will also say the desk has area $a = lw$ and prove that this area is +even. + +\smallskip +\vskip0pt plus 1in\goodbreak\vskip 0pt plus -1in +\halign{\vrule\strut#\tabskip\tableskip&#\hfil&#\hfil&#\tabskip0pt&#\vrule\cr\hline + &Statement&Reason&&\cr\hline + &$a = lw$&Premise&&\cr + &$w = 3x$&Premise&&\cr + &$l = y$&Premise&&\cr + &$x$ is even&Premise&&\cr + &$x,y\in Z^+$&Premise&&\cr + &$a = 3xy$&Substitution (1,2,3)&&\cr + &$\exists j\in\bb Z, x = 2j$&Definition of even (4)&&\cr + &$x = 2k$&Existential Instantiation (7)&&\cr + &$a = 6ky$&Substitution (6,8)&&\cr + &$a = 2(3ky)$&Algebra (9)&&\cr + &$\exists j\in\bb Z, a = 2j$&Existential generalization (10)&&\cr + &$a$ is even&Definition of even (11)&&\cr + \hline +} +\smallskip +\endproof + +\li Use a direct proof to show that if $n+9$ is odd, then $n^2-5n-14$ is +even. Make sure to include the introduction, body, and conclusion. +Clearly state your reasoning for all statements and use a two-column +proof for the body whenever possible. + +Let $n$ be an integer such that $n+9$ is odd. +We will show that $n^2-5n-14$ is even. + +\smallskip +\vskip0pt plus 1in\goodbreak\vskip 0pt plus -1in +\halign{\vrule\strut#\tabskip\tableskip&#\hfil&#\hfil&#\tabskip0pt&#\vrule\cr\hline + &Statement&Reason&&\cr\hline + &$n+9$ is odd&Premise&&\cr + &$\exists j\in\bb Z, n+9=2j+1$&Definition of Odd (1)&&\cr + &$n+9=2k+1$&Existential Instantiation (2)&&\cr + &$n = 2k-8$&Algebra (3)&&\cr + &$n^2-5n-14 = (4k^2-32k+64)-(10k+40)-14 = 2(2k^2-42k+5)$&Algebra (4)&&\cr + &$2k^2-42k+5\in\bb Z$&Closure of Integers (5)&&\cr + &$\exists j\in\bb Z, n^2-5n-14 = 2j$&Existential Generalization (5,6)&&\cr + &$n^2-5n-14$ is even&Definition of Even (7)&&\cr + \hline +} +\smallskip +\endproof + +\li Let $n$ be an integer. Prove the statement ``If $3n^2+8$ is even, +then $n$ is even.'' Make sure to include the introduction, body, and +conclusion. Clearly state your reasoning for all statements and use a +two-column proof for the body whenever possible. + +{\startlist + \li Prove the statement using a proof by contrapositive. + + Assume for the sake of contrapositive that $n$ is odd. + We will show that $3n^2+8$ is odd. + + \smallskip + \vskip0pt plus 1in\goodbreak\vskip 0pt plus -1in + \halign{\vrule\strut#\tabskip\tableskip&#\hfil&#\hfil&#\tabskip0pt&#\vrule\cr\hline + &Statement&Reason&&\cr\hline + &$n$ is odd&Premise&&\cr + &$\exists j\in\bb Z, n=2j+1$&Definition of Odd (1)&&\cr + &$n=2k+1$&Existential Instantiation (2)&&\cr + &$3n^2+8=3(2k+1)^2+8$&Substitution (3)&&\cr + &$3n^2+8=12k^2+12k+11=2(6k^2+6k+5)+1$&Algebra (4)&&\cr + &$\exists j\in\bb Z, 3n^2+8=2j+1$&Existential Generalization (5)&&\cr + &$3n^2+8$ is odd&Definition of Odd (6)&&\cr + \hline + } + \smallskip + \endproof + + \li Prove the statement using a proof by contradiction. + + Let $3n^2+8$ be even and, for the sake of contradiction, let $n$ be + odd. + + \smallskip + \vskip0pt plus 1in\goodbreak\vskip 0pt plus -1in + \halign{\vrule\strut#\tabskip\tableskip&#\hfil&#\hfil&#\tabskip0pt&#\vrule\cr\hline + &Statement&Reason&&\cr\hline + &$n$ is odd&Premise&&\cr + &$3n^2+8$ is even&Premise&&\cr + &$\exists j\in\bb Z, n = 2j+1$&Definition of odd (1)&&\cr + &$n = 2k+1$&Existential instantiation (3)&&\cr + &$\exists j\in\bb Z, 3n^2 + 8 = 2j$&Definition of even (2)&&\cr + &$3n^2 + 8 = 2l$&Existential instantiation (5)&&\cr + &$3(2k+1)^2 + 8 = 2l$&Substitution (4,6)&&\cr + &$12k^2+12k+3 + 8 = 2l$&Algebra (7)&&\cr + &$l = (6k^2+6k+5) + 1/2$&Algebra (8)&&\cr + &$l\not\in\bb Z$&Integer Definition (9)&&\cr + \hline + } + \smallskip + We have reached a contradiction because $l$ is both an integer and + not an integer. + \endproof +} + +\li Let $p$ be the product of 5 distinct integers, where each of the 5 +integers is between 1 and 63, inclusive. Prove or disprove that if $p$ +is odd, then at least one of these 5 integers in its product must be +odd. Make sure to include the introduction, body, and conclusion. +Clearly state your reasoning for all statements and use a two-column +proof for the body whenever possible. + +Let $a_1,a_2,\ldots,a_5 \in\bb Z\cap[1,63],$ such that $i\neq j\impl +a_i\neq a_j.$ +For the sake of contrapositive proof, let $a_i$ (for all $i$) be even. +We will show that $p = a_1a_2a_3a_4a_5$ is even. + +\smallskip +\vskip0pt plus 1in\goodbreak\vskip 0pt plus -1in +\halign{\vrule\strut#\tabskip\tableskip&#\hfil&#\hfil&#\tabskip0pt&#\vrule\cr\hline + &Statement&Reason&&\cr\hline + &$a_1$ is even&Premise&&\cr + &$\exists j\in\bb Z, a_1=2j$&Definition of Even (1)&&\cr + &$a_1=2k$&Existential Instantiation (2)&&\cr + &$p = a_1a_2a_3a_4a_5$&Premise&&\cr + &$p = 2ka_2a_3a_4a_5$&Substitution (3,4)&&\cr + &$p = 2(ka_2a_3a_4a_5)$&Associative Property (5)&&\cr + &$\exists j\in\bb Z, p = 2j$&Existential Generalization (6)&&\cr + &$p$ is even&Definition of Even (7)&&\cr + \hline +} +\smallskip +\endproof + +\bye |