Problem 0: Complete the Canvas quiz "PSet 1 - Canvas".

Problem (16 points): Show that $(\neg p \vee q) \rightarrow (r \wedge \neg q)$ and $\neg q \wedge (p \vee r)$ are logically equivalent

• using truth tables
• using the list of logical equivalences (including the conversion from $\rightarrow$ to $\neg$ and $\vee$), labelling each step with the rule(s) you are using.

Problem (16 points): Let $a$ be the statement "Alex teaches CS", $b$ be the statement "Buwan teaches CS", and $c$ be the statement "Chichima teaches physics."

• For each of the following, write the statement form that most closely follows the natural language, and a logically equivalent statement form that does not use $\wedge$.
  • It is not the case that both Alex teaches CS and Chichima teaches physics.
  • Neither Alex nor Buwan teaches CS.
• For each of the following, write the statement form that most closely follows the natural language, and a logically equivalent statement form that uses only $\neg$ and $\wedge$ (and parentheses to force order of operations when necessary).
  • It is not the case that at least one of Alex or Buwan teaches CS.
  • If Chichima teaches physics then Alex does not teach CS.

Problem (4 points): In addition to and, or, not, and if/then, we can define other logical operators. For example, the binary operator NAND ("not and"), with p NAND q (written $p \uparrow q$) logically equivalent to $\neg(p \wedge q)$.

The truth table for NAND is then $$ \begin{array}{cc|c} p & q & p \uparrow q \\ \hline T& T& F\\ T& F& T\\ F& T& T\\ F& F& T\\ \end{array} $$ Find a statement form logically equivalent to $\neg(p \wedge \neg q) \vee r$ that uses (possibly more than once) $\uparrow$ as its only logical operator. You will find it helpful to complete the Canvas quiz before attempting this question.