\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