Homework 2

COT-3100: Discrete Structures Homework 2 1. Write the following statements in symbolic form using the symbols ~, V and ∧ and the indicated letters to represent component statements. Let s = “stocks are increasing" and i = “interest rates are steady". (a) Stocks are increasing but interest rates are steady. Answer : s ∧ i (b) Neither are stocks increasing nor are interest rates steady. Answer : ∼ s ∧ ∼ i 2. Write the following statements in symbolic form using the symbols ∼ , V and ∧ and the indicated letters to represent component statements. Let h = “John is healthy", w= “John is wealthy", and s = “John is wise". (a) John is healthy and wealthy but not wise. Answer: (h ∧ w) ∧ ∼ s (b) John is not wealthy but he is healthy and wise. Answer ∼ w ∧ (h ∧ s) (c) John is neither healthy, wealthy, nor wise. Answer ( ∼ h w) s ∧ ∼ ∧ ∼ (d) John is neither wealthy nor wise, but he is healthy. Answer ( ∼ w ∧ ∼ s) ∧ h (e) John is wealthy, but he is not both healthy and wise. Answer w ∧ ∼ (h ∧ s) 3. Write truth tables for the following statement forms (make sure you follow the right order of prede- dence to parse the logic formula). (a) p ∧ ∼ q p q ~q p ∧ ∼ q T T F F T F T T F T F F F F T F (b) ∼ (p ∧ q) ∨ (p ∨ q) p q p ∧ q ∼ (p ∧ q) p v q ∼ (p ∧ q) ∨ (p ∨ q) T T T F T T T F F T T T F T F T T T F F F T T T (c) p ∧ (q ∧ r) p q r q ∧ r p ∧ (q ∧ r) T T T T T T T F F F T F T F F

T F F F F F T T F F F T F F F F F T F F F F F F F (d) p ∧ ( ∼ q ∨ r). p q r ∼ q ∼ q ∨ r p ∧ ( ∼ q ∨ r) T T T F T T T T F F F F T F T T T T T F F T T T F T T F T F F T F F F F F F T T T F F F F T T F 4. Use the truth table method to prove the following distributive laws p ∧ (q ∨ r) = (p ∧ q) ∨ (p ∧ r) p q r q ∨ r p ∧ q p ∧ r p ∧ (q ∨ r) (p ∧ q) ∨ (p ∧ r) T T T T T T T T T T F T T F T T T F T T F T T T T F F F F F F F F T T T F F F F F T F T F F F F F F T T F F F F F F F F F F F F and p ∨ (q ∧ r) = (p ∨ q) ∧ (p ∨ r): p q r q ∧ r p ∨ (q ∧ r) (p ∨ q) ∧ (p ∨ r) T T T T T T T T F F T T T F T F T T T F F F T T F T T T T T F T F F F F F F T F F F F F F F F F

F T T T T T T F F T T T T T (d) (p → r) ↔ (q → r) p q r p → r q→ r (p → r) ↔ (q → r) T T T T T T T T F T T T T F T F F T T F F F F F F T T T T T F T F T T T F F T T T F F F F T T T (e) (p → (q → r)) ↔ ((p ∧ q) → r) - Answer: This statement form is tautology p q r q → r P → q → r p ∧ q p ∧ q → r (p → (q → r)) ↔ ((p ∧ q) → r) T T T T T T T T T T F F F F F T T F T T T T T T T F F T T T T T F T T T T T T T F T F F F F F T F F T T T T T T F F F T T T T T 7. Write each of the following three statements in symbolic form and determine which pairs are logically equivalent. Include truth tables and a few words of explanation.  If it walks like a duck and it talks like a duck, then it is a duck.  Either it does not walk like a duck or it does not talk like a duck, or it is a duck.  If it does not walk like a duck and it does not talk like a duck, then it is not a duck. “It walks like a duck”: p “It talks like a duck”: q “it is a duck” : r p ∧ q → r ( ∼ p ∨ ∼ q) ∨ r ( ∼ p) ∧ ( ∼ q) → ( ∼ r)

p q r p ∧ q) → r ( ∼ p ∨ ∼ q) ∨ r ( ∼ p ∧ ∼ q) → ∼ r T T T T T T T T F F F T T F T T T T T F F T T T F T T T T T F T F T T T F F T T T F F F F T T T 8. Use the logical equivalence p → q ≡ ∼ p ∨ q and de Morgan's laws to rewrite the following statement forms using ∧ and ∼ only (that is, you should eliminate all ∨ , → and ↔ symbols in your answer statement forms). (a) p ∧ ∼ q → r ≡ ∼ (p ∧ ∼ q) ∨ r ≡ ∼ [(p ∧ ∼ q) ∧ ∼ r] (c) p ∨ ∼ q → r ∨ q ≡ p V ~ q) → (r V q) P → q ≡ ~ p V q ≡ ~(p V ~q) V (r V q) ~[(~(~p q)) (~r ~q))] ∧ ∧ ∧ (d) (p → (q → r)) ↔ ((p ∧ q) → r) ≡ ( ∼ p V r) ↔ (~q V r) ≡ ∼ [ ∼ (p ∧ ∼ r) ∧ (q ∧ ∼ r)] ∧ ∼ [ ∼ (q ∧ ∼ r) ∧ (p ∧ ∼ r)] 9. Rewrite the following statements which use “necessary condition" or “sufficient condition" form into statements using "if-then" form. (a) A sufficient condition for Jon's team to win the championship is that it win the rest of its games. If Jon’s team wins the rest of its games, the it will win the championship. (b) A necessary condition for this computer program to be correct is that it not produce error messages during translation. If the computer program is correct, then it does not produce error message during translation. 10. Use the contrapositive to rewrite the following statements in “if-then" form in two ways. (a) Being divisible by 3 is a necessary condition for this number to be divisible by 9. If this number is not divisible by 3, then it is not divisible by 9 If this number is divisible by 9, then its divisible by 3 (b) Doing homework regularly is a necessary condition for Jim to pass the course. If Jim doing homework regularly then he passes the course