HW 1 Answer Key

Section 1.1

8 a. r ∧ ¬q b. p ∧ q ∧ r c. r → p d. p ∧ ¬q ∧ r e. (p ∧ q) → r f. r ↔ (q ∨ p)

14 a. Converse: If I stay home, then it will snow tonight. Contrapositive: If I do not stsy at home then it will not snow tonight b. Converse: Whenever I go to the beach, it is a sunny summer day. Contrapositive: Whenever I do not go to the beach, it is not a sunny summer day. c. Converse: If i sleep until noon, then I stayed up late. Contrapositive: If I do not sleep until noon, then I do not stay up late.

22 a. 11000 b. 01101 c: 11001 d: 11011

Section1.2

4 a. p q r p ∨ q (p ∨ q) ∨ r q ∨ r p ∨ (q ∨ r) 0 0 0 0  0  0  0 0 0 1 0  1  1  1 0 1 0 1  1  1  1 0 1 1 1  1  1  1 1 0 0 1  1  0  1 1 0 1 1  1  1  1 1 1 0 1  1  1  1 1 1 1 1  1  1  1

We note that the fifth and seventh column of the table are identical

4b. p q r p ∧ q (p ∧ q) ∧ r q ∧ r p ∧ (q ∧ r) 0 0 0 0  0  0  0 0 0 1 0  0  0  0 0 1 0 0  0  0  0 0 1 1 0  0  1  0 1 0 0 0  0  0  0 1 0 1 0  0  0  0 1 1 0 1  0  0  0 1 1 1 1  1  1  1

We note that the fifth and seventh column of the table are identical

8c. p q p → q p ∧ (p → q) [p ∧ (p → q)] → r 0 0  1  0  1 0 1  1  0  1 1 0  0  0  1 1 1  1  1  1

10c. [p ∧ (p → q)] → q restatment [p ∧ (¬p ∨ q)] → q def. of implication ¬[p ∧ (¬p ∨ q)] ∨ q def. of implication ¬p ∨ ¬(¬p ∨ q) ∨ q DeMorgan ¬p ∨ (¬¬p ∧ ¬q) ∨ q DeMorgan ¬p ∨ (p ∧ ¬q) ∨ q double neg ((¬p ∨ p) ∧ (¬p ∨ ¬q)) ∨ q distributive (T ∧ (¬p ∨ ¬q)) ∨ q by definition (¬p ∨ ¬q) ∨ q domination ¬p ∨ (¬q ∨ q) association ¬p ∨ T by definition T domination

16. We can see from the definitions of implication and negation that each of these propositions is false in the case in which p is true and q is false, and true in the other three cases. Therefore the two propositions are logically equivalent.

20. a.p ∨ ¬q ∨ ¬r b.(p ∨ q ∨ r) ∧ s c.(p ∧ T) ∨ (q ∧ F)

24. \begin{matrix}p & q & r & p ∧ q ∧ ¬r \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{matrix}

26. Each line of the truth table corresponds exactly to one combination of truth values for the n atomic proositions involved.A conjunction that is true precisely in this case is the conjunction of all the atomic propositions that are true and the negations of all the atomic propositions that are false. If we do this for each line of the table for which the value of compound proposition is true, and take the disjunction of the resulting propositions, then we have the desired proposition in its disjunctive normal form.

39. 16

Must have explanation of where the 2^{2^{n}} comes from.