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/hw3.tex | 313 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 313 insertions(+)
 create mode 100644 howard/hw3.tex

(limited to 'howard/hw3.tex')

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
-- 
cgit