\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