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