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