CMPS 211 Homework Assignment 4, Fall 2014

American University of Beirut Department of Computer Science CMPS 211 – Discrete Mathematics – Fall 14/15 Please solve the following exercises and submit BEFORE 8:00 am of Tuesday, October 7th. Rules of submission: • Write your name, Section number and Professor name in your submission • Submit a softcopy or photocopy to Moodle before the deadline. • If your assignment is handwritten, submit the hardcopy paper to Bliss 210B, before Thursday 9th Oct. • If your assignment is typed, print it 2 pages per sheet, and preferably double sided, and submit it to Bliss 210B also, before Thursday 9th Oct. • If the door is closed, pass it under the door. Failing to submit a hardcopy of you assignment by Thursday will result in deducting points from your assignment. Exercise 1 (10 points) Use rules of inference to show that the hypotheses “If you have hyperglycemia or hypertension, then you will have headaches and polydipsia.” “If you have headaches, then you will feel dizzy” and “You don’t feel dizzy” imply the conclusion “You don’t have hyperglycemia.” Exercise 2 (10 points) For each of these sets of premises, what relevant conclusion or conclusions can be drawn? Explain the rules of inference used to obtain each conclusion from the premises. a) “All parallelograms have 2 pairs of parallel sides”, “Squares are parallelograms”, “Trapezoids have only 1 pair of parallel sides” “Quadrilaterals have 4 sides” b) “If I work, it is either sunny or partly sunny.” “I worked last Monday or I worked last Friday.” “It was not sunny on Tuesday.” “It was not partly sunny on Friday.” c) “I am cheered up or I am upset”, “I am not upset”, “If I am cheered up, I make all American University of Beirut Department of Computer Science CMPS 211 – Discrete Mathematics – Fall 14/15 people around me motivated or overjoyed.” d) “All foods that are healthy to eat do not taste good.” “Tofu is healthy to eat.” “You only eat what tastes good.” “You do not eat tofu.” “Cheeseburgers are not healthy to eat.” Exercise 3 (10 points) Determine whether these are valid arguments. a) If x2 is not equal to 1,where x is a real number, then x is not equal to 1. Let a be a real number where a2 is not equal to 1; then a is equal to 1. b) If you are sick and hungry, you will feel cold. Therefore, if you are feeling cold and hungry, then you are sick. Exercise 4 (10 points) Identify the error or errors in this argument that supposedly shows that if ∀x (P (x) ∨ Q(x)) is true then ∀x P(x) ∨∀x Q(x) is true. 1. ∀x (P(x) ∨ Q(x)) Premise 2. P(c) ∨ Q(c)) Universal Instantiation from 1 3. P(c) Simplification from (2) 4. ∀x P(x ) Universal generalization from (3) 5. Q(c) Simplification from (2) 6. ∀x Q(x) Universal generalization from (5) 7. ∀x (P(x) ∨ ∀x Q(x)) Conjunction from (4) and (6) Exercise 5 (10 points) Use rules of inference to show that if ∀x (A(x) ∨ B(x)) and ∀x ((¬A(x) ∧ B(x)) → C(x)) are true, then ∀x (¬C(x) → A(x)) is also true, where the domains of all quantifiers are the same. American University of Beirut Department of Computer Science CMPS 211 – Discrete Mathematics – Fall 14/15 Exercise 6 (10 points) Show that the argument form with premises (p ∧ t) → (r ∨ s), q → (u ∧ t), u → p, and ¬s and conclusion q → r is valid by using rules of inference. Exercise 7 (10 points) For each of these arguments, explain which rules of inference are used for each step. a) “Samir, a student in this class, is from Russia. Everyone from Russia has had a flu at least once. Therefore, someone in this class has had a flu” 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. Therefore, all five roommates can take CMPS 212” c) “All self-centered people suffer from the illusion of control. Natasha, our classmate is self-centered. Therefore, some of our classmates suffer from the illusion of control. d) All Math classes taught by professor John are wonderful. Professor John is giving a course this semester. Therefore, the Math department has wonderful courses this semester. Exercise 8 (10 points) What is wrong with this argument? Let B(x, y) be “x is brighter than y”. Given the premise ∃s B(s, George), it follows that B(George, George). Then by existential generalization it follows that ∃x B(x,x), so that someone is brighter than himself. Exercise 9 (10 points) For each of these arguments determine whether the argument is correct or incorrect and explain why: a) Everyone enrolled in the university has lived in a dormitory. Mia has never lived in a dormitory. Therefore, Mia is not enrolled in the university. b) Touch screen laptops are too fragile. My laptop’s screen isn’t a touch screen. Therefore, my laptop is not too fragile. c) All Android phones can run Java. My phone can run Java. Therefore my Phone is an Android Phone. American University of Beirut Department of Computer Science CMPS 211 – Discrete Mathematics – Fall 14/15 d) All plants produce glucose by photosynthesis. Palms trees are plants. Therefore Palm trees produce glucose. Exercise 10 (10 points) Use resolution to show that the compound proposition: (p ∨ q) ∧ (¬p ∨ q) ∧ (p ∨ ¬q) ∧ (¬p ∨ ¬q) is not satisfiable.