path: root/howard/hw3.tex

\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