CMPS 211 Homework Assignment 3, 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 30th, September. Only submit on Moodle. Hard copies are no longer accepted in class. You can scan your handwritten solution or take a photo of it and upload it on Moodle if you don’t want to type your solution. Exercise 1 (10 points) Translate these statements into English, where P(x) is “x is a Philosophy Professor” and L(x) is “x understands logic” and the domain consists of Professors. a) ∀x(P(x) ∧ L(x)) b) ∃x(P(x) ∧ L(x)) c) ∀x(P(x) → L(x)) d) ∃x(P(x)→ L(x)) Exercise 2 (10 points) Let I(x) be the statement “x has an iPhone,” let S(x) be the statement “x has a Samsung,” and let N(x) be the statement “x has a Nokia.” Express each of these statements in terms of I(x), S(x), N(x), quantifiers, and logical connectives. Let the domain consist of all students in your class. a) A student in your class has an iPhone, a Samsung, and a Nokia. b) No student in your class has a Nokia, an iPhone, and a Samsung. c) All students in your class have an iPhone, a Samsung, or a Nokia. d) Some student in your class has an iPhone and a Nokia, but not a Samsung. e) No student in your class has a Nokia, an iPhone, or a Samsung. Exercise 3 (10 points) Let P(x) be the statement “4x - 5 > 2x -1.” If the domain consists of all integers, what are the truth values of the following propositions? American University of Beirut Department of Computer Science CMPS 211 – Discrete Mathematics – Fall 14/15 a) P(2) b) P(3) c) P(0) d) ∃xP(x) e) ∃x¬P(x) f) ∀xP(x) g) ∀x¬P(x) Exercise 4 (10 points) Suppose that the domain of the propositional function P(x) consists of −4, −2, −1, 1, 2, and 4. Express these statements without using quantifiers, instead using only negations, disjunctions, and conjunctions. a) ∃xP(x) b) ∀xP(x) c) ∀x((x≠3)→P(x)) d) ∃x((x≥1)∧P(x)) e) ∃x(¬P(x))∧∀x((x<0)→P(x)) Exercise 5 (10 points) Translate in two ways each of these statements into logical expressions using predicates, quantifiers, and logical connectives. First, let the domain consist of the students in your class and second, let it consist of all people. a) There is a person in your class who cannot drive. b) Everyone in your class has a notebook. c) Somebody in your class is repeating this course. d) All students in your class can solve Fermat’s last theorem. American University of Beirut Department of Computer Science CMPS 211 – Discrete Mathematics – Fall 14/15 e) Some student in your class does not want to be rich. Exercise 6 (10 points) Let P (x, y) be the statement “Professor x has taken taught class y,” where the domain for x consists of all CMPS Professors and for y consists of all CMPS courses. Express each of these quantifications in English. a) ∃x∃y P(x, y) b) ∃x∀y P(x, y)  c) ∀x∃y P(x, y) d) ∃y∀x P(x, y) e) ∀y∃x P(x, y) f ) ∀x∀y P(x, y) Exercise 7 (10 points) Let C(x,y) mean that student x is enrolled in class y, where the domain for x consists of all students in your school and the domain for y consists of all classes being given at your school. Express each of these statements by a simple English sentence. a) C(Tarek Haddad, CMPS 211) b) ∃x C(x , Bio 210) c) ∃y C(David Cook, y ) d) ∃x(C(x, Math 201) ∧ C(x, CMPS 211)) e) ∃x∃y∀z((x̸=y)∧(C(x,z)→C(y,z))) f) ∃x∃y∀z((x̸=y)∧(C(x,z)↔C(y,z))) Exercise 8 (10 points) Let Q(x, y) be the statement “student x has given a talk at conference y.” Express each of these sentences in terms of Q(x, y), quantifiers, and logical connectives, where the domain for x consists of all students at your school and for y consists of all conferences. American University of Beirut Department of Computer Science CMPS 211 – Discrete Mathematics – Fall 14/15 a) No student at your school has ever given a talk at a conference. b) There is a student at your school who has given a talk on a conference. c) There is a student at your school who has given a talk at an ACM conference and IEEE conference. d) Every conference has had a talk by student from  your school. e) At least two students from your school have given talks at an IEEE conference. Exercise 9 (10 points) Use quantifiers and predicates with more than one variable to express these statements. a) There is a student in this class who can speak Aramaic. b) Some student in this class has eaten pears but has not eaten peaches. c) Every student in this class plays some instrument. d) All students in this class have learned at least one programming language. e) A student in this class grew up in the same town as exactly one other student. f) There is a student in this class who has eaten every dish offered by one of the restaurants on Bliss Street. g) Every Lebanese soccer player has played with all other Lebanese soccer players in at least 1 game. Exercise 10 (10 points) Express the negations of these propositions using quantifiers, and in English. a) There is a student in this class who had never failed a course. b) Every student in this class likes computer science. c) There is a student in this class who has taken every  mathematics course offered at this school. d) There is a student in this class who has been in at least  one room of every building in Beirut.