PS03: More Propositional Logic

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