\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
