PS03: More Propositional Logic

Due Wed 4/8 @ 1:30pm.
  1. Is the following proposition satisfiable? Explain. $$(p \lor q \lor \neg r) \land (p \lor \neg q \lor \neg s) \land (p \lor \neg r \lor \neg s) \land (\neg p \lor \neg q \lor \neg s) \land (p \lor q \lor \neg s)$$

Rewrite each of the following compound propositions so that each variable occurs at most once. Prove that your proposition is equivalent to the original using a truth table.

  1. $\neg p \land (p \lor q)$
  2. $p \Rightarrow (p \land q \land r)$
  3. $((p \land q) \Rightarrow (p \lor q)) \Rightarrow (q \Rightarrow r)$

Do the following problems from the book, listed on pages 330–332.

  1. 3.45
  2. 3.52 (and justify your answer)
  3. 3.56
  4. 3.79
  5. 3.80
  6. 3.81
  7. Prove that $\neg (p \Rightarrow q) \equiv p \land \neg q$ using a chain of logical equivalences, not a truth table. (You may use the equivalences from the previous three problems, De Morgan's Laws, and Double Negation.)
  8. Consider a set $S = \{p,q,r,s,t\}$ of Boolean variables. Let $\varphi = p \oplus q \oplus r \oplus s \oplus t$. Describe briefly (just a sentence or two) the conditions under which $\varphi$ is true. Use English and, if appropriate, standard (nonlogical) mathematical notation.
  9. 3.96
  10. 3.100
  11. 3.101