CMPS 211 Homework Assignment 04 Solution, Fall 2014

CMPS 211 – Fall 2014 1 Assignment 4 Solution Exercise 1: Let p be you have hyperglycemia Let q be you have hypertension Let r be you have headaches Let s be you have polydipsia Let t be you feel dizzy 1. p ∨ q → r ∧ s Premise 2. p ∨ q → r Simplification (1) 3. r → t Premise 4. ¬t Premise 5. ¬r Modus Tollens (3) and (4) 6. ¬(p ∨ q) Modus Tollens (2) and (5) 7. ¬p ∧ ¬q De Morgan’s Law (6) 8. ¬p Simplification (7) Exercise 2: a) 1. Parallelogram → 2 pairs of parallel sides Premise 2. Square → parallelogram Premise 3. Trapezoid → 1 pair of parallel sides Premise 4. Quadrilaterals → 4 sides Premise 5. ¬(1 pair of parallel sides) → ¬Trapezoid Contrapositive 6. ¬(2 pair of parallel sides) → ¬Parallelogram Contrapositive 7. Trapezoid → ¬Parallelogram Hypothetical Syllogism (3) and (6) 8. Parallelogram → ¬ Trapezoid Hypothetical Syllogism (1) and (5) 9. Square → 2 pairs of parallel sides Hypothetical Syllogism (1) and (2) Conclusions: squares have 2 pairs of parallel sides. Trapezoids are not parallelograms. Parallelograms are not trapezoids. If we assume that parallelograms, squares and trapezoids are quadrilaterals, then by Hypothetical Syllogism also we can conclude that each of them have 4 sides. CMPS 211 – Fall 2014 2 b) Let W(x) be I work day x Let S(x) be day x is sunny Let P(x) be day x is partly sunny 1. ∀x (W(x) → S(x) ∨ P(x)) Premise 2. W(Monday) ∨ W(Friday) Premise 3. ¬S(Tuesday) Premise 4. ¬P(Friday) Premise 5. S(Mon) ∨ P(Mon)) ∨S(Fri) Modus Ponens (1) and (2) 6. (W(Tues) ∧P(Tues)) ∨(¬W(Tues) c) Let p be I am cheered up Let q be I am upset Let r be I make all people around me motivated Let s be I make all people around me overjoyed 1. p ∨ q Premises 2. ¬ q Premises 3. p Disjunction Syllogism (1) and (2) 4. p → r ∨ s Premises 5. r ∨ s Modus Ponens (3) and (4) Conclusions: I make all people around me motivated, overjoyed or both d) 1. ∀x (Healthy(x) → ¬TastesGood(x)) Premise 2. Healthy(Tofu) → ¬TastesGood(Tofu) Universal Instantiation (1) 3. Healthy(Tofu) Premise 4. ¬TastesGood(Tofu) Modus Ponens (2) and (3) 5. ∀x (Eat(x) → TastesGood(x)) Premise 6. ¬Eat(Tofu) Premise 7. ¬Healthy(Cheeseburgers) Premise Conclusions: Tofu does not taste good is concluded from (2) and (3). We can’t conclude anything about cheeseburgers since we don’t know if it tastes good or not, all what we know is that it is not healthy. CMPS 211 – Fall 2014 3 Exercise 3: a) let R(x) be x is a real number 1. ∀x ((x2 ≠ 1) ∧ R(x) → x ≠ 1) Premise 2. R(a) ∧ (a2 ≠ 1) → a = 1 ? Premise 3. ∃x ((x2 ≠ 1) ∧ R(x) → x = 1) Contradiction (1) and (3) � The argument is not valid b) Let s be you are sick Let h be you are hungry Let c be you are feeling cold 1. s ∧ h → c Premise 2. c ∧ h → s ? Premise It is a fallacy to assume if c and h are true, we can conclude anything about s, since the c being true doesn’t conclude anything…and h doesn’t have any shown effect on s… � The argument is not valid Exercise 4: Line 3 and 5 have the same error (we can’t use simplification since we have disjunction and not conjunction) Exercise 5: 1. ∀x (A(x) ∨ B(x)) Premise 2. ∀x ((¬A(x) ∧ B(x)) → C(x)) Premise 3. ¬A(c) ∧ B(c)) → C(c) Universal Instantiation (2) 4. A(c) ∨ ¬B(c) ∨ C(c) Law of Implication (2) 5. A(c) ∨ B(c) Universal Instantiation (1) 6. A(c) ∨ C(c) Resolution (4) and (5) 7. ¬C(c) Premise 8. ¬C(c) → A(c) Law of Implication (6) CMPS 211 – Fall 2014 4 9. A(c) Modus Ponens (7) and (8) 10. ∀x (¬C(x) → A(x)) Universal Generalization (8) Exercise 6: 1. q → (u ∧ t) Premise 2. u → p Premise 3. q → u ∧t∧p Hypothetical Syllogism (1) and (2) 4. (p∧t) → (r ∨S) Premise 5. q → (r ∨S) Hypothetical Syllogism (3) and (4) 6. ¬S Premise 7. q → r Disjunctive Syllogism (5) and (6) Exercise 7: a) Samir is a student in this class. Premises Samir is from Russia. Premises Everyone from Russia has had a flu at least once. Premises Someone in this class has had a flu. Existential Generalization Let S(x) be x is a student of this class Let R(x) be x is from Russia Let F(x) be x has had a flu 1. S(Samir) Premise 2. R(Samir) Premise 3. ∀x (R(x) → F(x)) Premise 4. R(Samir) → F(Samir) Universal Instantiation (3) 5. F(Samir) Modus Ponens (2) and (4) 6. S(Samir) ∧ F(Samir) Conjunction (1) and (5) 7. ∃x (S(x) ∧ F(x)) Existential Generalization (6) b) Each of five roommates, Melissa, Aaron, Ralph, Veneesha, and Keeshawn, has taken CMPS 200. Every student who has taken CMPS 200 can take CMPS 212. CMPS 211 – Fall 2014 5 All five roommates can take CMPS 212 Let CMPS200(x) be x has taken CMPS 200 Let CMPS212(x) be x can take CMPS 212 1. CMPS200(Melissa) ∧ CMPS200(Aaron) ∧ CMPS200(Ralph) ∧ CMPS200(Veneesha) ∧ CMPS200(Keeshawn) Premises 2. ∀x (CMPS200(x) → CMPS212(x)) Premises 3. CMPS200(Melissa) → CMPS212(Melissa) Universal Instantiation (2) 4. CMPS200(Aaron) → CMPS212(Aaron) Universal Instantiation (2) 5. CMPS200(Ralph) → CMPS212(Ralph) Universal Instantiation (2) 6. CMPS200(Veneesha) → CMPS212(Veneesha) Universal Instantiation (2) 7. CMPS200(Keeshawn) → CMPS212(Keeshawn) Universal Instantiation (2) 8. CMPS200(Melissa) Simplification (1) 9. CMPS200(Aaron) Simplification (1) 10. CMPS200(Ralph) Simplification (1) 11. CMPS200(Veneesha) Simplification (1) 12. CMPS200(Keeshawn) Simplification (1) 13. CMPS212(Melissa) Modus Ponens (3) and (8) 14. CMPS212(Aaron) Modus Ponens (4) and (9) 15. CMPS212(Ralph) Modus Ponens (5) and (10) 16. CMPS212(Veneesha) Modus Ponens (6) and (11) 17. CMPS212(Keeshawn) Modus Ponens (7) and (12) 18. CMPS212(Melissa) ∧ CMPS212(Aaron) ∧ CMPS212(Ralph) ∧ CMPS212(Veneesha) ∧ CMPS212(Keeshawn) Conjunction (13), (14), (15), (16), (17) c) All self-­‐centered people suffer from the illusion of control. Premises Natasha, our classmate is self-­‐centered. Premises Some of our classmates suffer from the illusion of control. Existential Generalization Let S(x) be x is self-­‐centered Let C(x) be x is in our class Let I(x) be x suffers from the illusion of control 1. ∀x (S(x) → I(x)) Premises CMPS 211 – Fall 2014 6 2. S(Natasha) → I(Natasha) Universal Instantiation (1) 3. S(Natasha) Premises 4. C(Natasha) Premises 5. I(Natasha) Modus Ponens (2) and (3) 6. C(Natasha) ∧ I(Natasha) Conjunction (4) and (5) 7. ∃x (C(x) ∧ I(x)) Existential Generalization (6) d) All Math classes taught by professor John are wonderful. Premises Professor John is giving a course this semester. Premises The Math department has wonderful courses this semester. Modus Ponens Let J(x) be John is giving course x Let W(x) be course x is wonderful The domain of x is all math courses 1. ∀x (J(x) → W(x)) Premises 2. ∃x (J(x)) Premises 3. J(c) → W(c) Universal Instantiation (1) 4. J(c) Universal Instantiation (2) 5. W(c) Modus Ponens (3) and (4) 6. ∃x (W(x)) Existential Generalization (5) Exercise 8: The problem in concluding B(George, George) given “there exists an s such that B(s, George)”, is in the there exists itself, since this means that its is true from some s, and not for any value of s, so replacing s by George is fallacious. Exercise 9: a) Correct 1. ∀x (EnrolledInUni(x) → Dorm(x)) Premises 2. EnrolledInUni(Mia) → Dorm(Mia) Universal Instantiation (1) 3. ¬Dorm(Mia) Premises 4. ¬EnrolledInUni(Mia) Modus Tollens b) Not Correct 1. TouchScreen → Fragile Premises CMPS 211 – Fall 2014 7 2. ¬TouchScreen Premises We can’t conclude anything about the laptop since the hypothesis is false (the conclusion can have any truth value) c) Not Correct 1. Android → Java Premises 2. Java Premises We can’t conclude anything about the phone since the conclusion is true (the hypothesis can have any truth value) d) Correct 1. Plant → ProduceGlucose Premises 2. Palm → Plants Premises 3. Palm → ProduceGlucose Hypothetical Syllogism Exercise 10: 1. (p ∨ q) ∧ (¬p ∨ q) ∧ (p ∨ ¬q) ∧ (¬p ∨ ¬q) Premises 2. (p ∨ q) Simplification (1) 3. (¬p ∨ q) Simplification (1) 4. (p ∨ ¬q) Simplification (1) 5. (¬p ∨ ¬q) Simplification (1) 6. q Resolution (2) and (3) 7. ¬q Resolution (4) and (5) 8. q ∧ ¬q Conjunction (6) and (7) 9. False (not satisfiable) Negation Law (8)